PaperlayerView exact revision on arXiv

Source-linked AI summary

Algorithms to estimate Shapley value feature attributions

Hugh Chen, Ian C. Covert, Scott M. Lundberg, Su-In Lee

arXiv:2207.07605v1cs.LGcs.GT

TL;DR

Shapley-value explanations are difficult to estimate and the growing algorithmic literature is hard to navigate. This paper separates feature removal from tractable estimation to survey 24 algorithms, showing distinct trade-offs across attribution types and model-specific versus model-agnostic approaches.

  • Problem

    The growing number and inherent complexity of Shapley-value algorithms make the literature difficult to navigate and may enable misuse.

  • Method

    The paper surveys 24 algorithms by separating feature-removal approaches from tractable estimation strategies and distinguishing model-agnostic from model-specific approximations.

  • Results

    Conditional Shapley values are difficult to estimate with low bias and variance, while Interventional TreeSHAP is non-trivial, bias-free, and variance-free.

  • Takeaways & Limitations

    The two-factor framework clarifies algorithmic innovations and indicates that tree models are particularly well-suited to Shapley-value explanations.

  • Takeaways & Limitations

    Choosing an appropriate baseline is difficult, and mean baselines can lack natural interpretations for discrete features.

Abstract

from arXiv · show

Feature attributions based on the Shapley value are popular for explaining machine learning models; however, their estimation is complex from both a theoretical and computational standpoint. We disentangle this complexity into two factors: (1)~the approach to removing feature information, and (2)~the tractable estimation strategy. These two factors provide a natural lens through which we can better understand and compare 24 distinct algorithms. Based on the various feature removal approaches, we describe the multiple types of Shapley value feature attributions and methods to calculate each one. Then, based on the tractable estimation strategies, we characterize two distinct families of approaches: model-agnostic and model-specific approximations. For the model-agnostic approximations, we benchmark a wide class of estimation approaches and tie them to alternative yet equivalent characterizations of the Shapley value. For the model-specific approximations, we clarify the assumptions crucial to each method's tractability for linear, tree, and deep models. Finally, we identify gaps in the literature and promising future research directions.

1 Introduction

Shapley value explanations address the opacity of increasingly capable machine-learning models through local feature attributions, but their use is complicated by feature removal choices and exponential-time computation. This section frames the literature around these two challenges and surveys 24 algorithms spanning model-agnostic and model-specific estimation strategies.

  • Motivation: Increasingly flexible machine-learning models often outperform humans but remain opaque, motivating methods that explain individual predictions through local feature attributions.Attributions represent each prediction with a vector φ ∈ R^d, where d is the number of model features.
  • Feature removal: Shapley value explanations differ in how they remove feature information, producing distinct approaches and interpretations linked to causal interventions or information theory.SHAP unifies additive attribution methods by defining a coalitional game, while practical conditional expectations may be replaced by marginal expectations that ignore feature dependencies.
  • Estimation complexity: Computing Shapley values is exponential in the number of features, requiring tractable approximations such as regression, sampling, or model-specific methods.Examples include KernelSHAP, IME, LinearSHAP, MaxSHAP, and DeepSHAP.
  • Survey scope: The survey organizes 24 distinct algorithms by combining feature-removal approaches with model-agnostic or model-specific estimation strategies.It presents variants of Shapley value explanations, methods for estimating their coalitional games, and assumptions enabling tractable approximation.

2 Feature attributions

Feature attributions assign scalar importance values to explain model predictions, either globally or for a specific explicand. Linear models provide an intuitive example, but nonlinear models require methods beyond inspecting parameters.

  • Feature attributions: Feature attributions explain predictions by assigning scalar values that represent each feature’s importance.The section introduces feature attributions using linear models, where each feature relates to the prediction through a model parameter.
  • Feature attributions: Local feature attributions explain an individual prediction f(x_e), with the explained sample called the explicand.For linear models, φ_i(f, x_e) = β_i x_e,i represents feature i’s contribution to that prediction.
  • Feature attributions: Using β_i x_e,i as a local attribution implicitly compares x_i against zero, although other values, distributions, or feature relationships may be preferable.These alternative feature-removal choices are addressed later in Section 4.
  • Feature attributions: Tree ensembles and deep learning models require methods beyond inspecting parameters because their many operations obscure individual feature roles.Their nonlinear flexibility captures more patterns in data but makes feature-role interpretation less direct than in linear models.

3 Shapley values

Shapley values allocate credit among players in a coalitional game by averaging each player’s marginal contribution across groups. They provide a uniquely defined credit-allocation solution under desirable axioms and have been adopted across several fields.

  • 3 Shapley values: Shapley values allocate credit to players represented by a set D through a subset function v(S) that maps coalitions to scalar values.The coalitional game considers all subsets in the power set P(D).
  • 3 Shapley values: Each player’s attribution is a weighted average of the profit increase when that player joins a group versus does not join it.The weighting depends on the coalition size and the total number of players.
  • 3 Shapley values: Shapley values are a unique solution to the credit-allocation problem under several desirable properties.These properties are presented as sufficient, but not exhaustive, axioms defining the Shapley value.

4 Shapley value explanations

Shapley explanations require defining a coalitional game for the model and specifying how present and absent feature values are represented. Baseline, conditional, and marginal approaches make different tradeoffs involving interpretability, baseline dependence, feature correlations, and model dependence.

  • Defining Shapley explanations: Shapley explanations first define a coalitional game v(S) from the machine-learning model, treating features as players and the explicand values as present features.Machine-learning models take vector inputs, whereas coalitional games take sets as inputs.
  • Baseline Shapley values: Baseline Shapley values replace absent features with values from a baseline sample, making them simple to implement but sensitive to an arbitrary baseline choice.Common baselines include all-zero, mean, uniform-distribution, and other choices, and baseline selection can heavily influence attributions.
  • Conditional and marginal Shapley values: Conditional Shapley values replace absent features using conditional distributions, avoiding a fixed baseline but requiring difficult conditional-expectation estimation and spreading credit across correlated features.They can assign high attribution to a feature not explicitly used by the model when it correlates with used features.
  • Baseline Shapley values: All-zero baselines can yield different attributions for equivalent models and explicands when feature encodings change, because zero may have arbitrary meaning.In the gender example, an encoded feature attribution changes sign despite equivalent models and explicands.
  • Conditional and marginal Shapley values: Marginal Shapley values may perturb data off-manifold, but they distinguish correlated variables and help identify whether the model functionally depends on a feature.Conditional values can support detecting reliance on protected classes through correlated features, whereas marginal values are useful for model debugging.
  • Conditional and marginal Shapley values: The paper advocates marginal and conditional Shapley values as practical alternatives to causal methods and fixed baselines for analyzing informational dependencies and functional form.Causal approaches rely on knowledge of an underlying causal graph, while marginal and conditional approaches cover two common model-interpretation use cases.

5 Algorithms to estimate Shapley value explanations

The section separates Shapley estimation into how feature information is removed and how values are tractably estimated, emphasizing challenges in conditional expectations and tradeoffs among model-agnostic methods. It also identifies model-specific advantages, including linear-time computation for linear models.

  • Conditional Shapley values: Conditional Shapley estimation is difficult because conditional distributions are unavailable, exact empirical matching is impractical, and similarity-based approximations retain dimensionality challenges.Empirical matching is exact only as baseline samples approach infinity, while similarity-based methods require a potentially undesirable similarity definition.
  • Conditional Shapley values: Conditional-expectation approaches are generally biased or inexact, and their approximation quality is difficult to quantify because the true conditional expectations are usually unknown.The paper favors generative or surrogate models as more flexible alternatives, although both require fitting an additional deep model.
  • Model-agnostic approximations: KernelSHAP is consistent and asymptotically unbiased, while its regularized and antithetic variants trade bias or sampling structure for reduced variance or improved convergence.SGD-Shapley uses projected stochastic gradient descent, but empirical evaluation finds that KernelSHAP consistently converges better.
  • Model-agnostic approximations: Antithetic KernelSHAP converges fastest on diabetes and NHANES, whereas adaptive-sampling IME and multilinear methods converge fastest on the 280-feature blog dataset.Adding 100 irrelevant features slows convergence, but adaptive methods are least affected because they can identify and ignore rapidly converged features.
  • Model-agnostic approximations: Model-agnostic estimators are flexible and apply to any coalitional game, but finite computational budgets make their stochastic estimates potentially inaccurate despite consistency with infinitely many samples.Antithetic sampling is reported to achieve near-best practical convergence among several more complex methods.
  • Model-specific approximations: For linear models, marginal Shapley values have linear feature complexity and equal baseline Shapley values using the mean baseline.This contrasts with the exponential complexity of the general case.

6 Discussion

The discussion separates Shapley explanation complexity into feature removal and tractable estimation, clarifying sources of bias and variance across algorithms. It also emphasizes transparent reporting of explanation parameters and convergence, while identifying improved stopping conditions as a future direction.

  • 6 Discussion: Shapley explanation complexity is organized around feature removal approaches and tractable estimation strategies, making algorithmic innovations and bias-variance sources easier to understand.The framework covers numerous algorithms and links their properties to these two factors.
  • 6 Discussion: Baseline and marginal Shapley estimates are generally unbiased, whereas conditional Shapley estimates are biased because conditional expectations are fundamentally challenging to estimate.Choosing a single baseline to represent feature removal remains difficult.
  • 6 Discussion: Model-agnostic approaches are flexible and often bias-free but have non-trivial variance, while model-specific approaches are typically deterministic and sometimes unbiased.Only LinearSHAP and Interventional TreeSHAP are identified as unbiased for baseline and marginal Shapley values.
  • 6 Discussion: IME is bias-free but has non-zero variance from stochastic estimation, whereas Shapley cohort refinement has both bias and variance from conditional modeling and sampling.IME combines marginal Shapley values with a bias-free random order value strategy; cohort refinement models conditional expectations empirically and similarity-based.
  • 6 Discussion: Shapley analyses should report the explanation type, baseline distribution, and estimation strategy, and sampling-based methods should discuss convergence to validate estimates.Tool developers are encouraged to make convergence transparent through explicit assessment.
  • 6 Discussion: Future work should develop stopping conditions that detect when additional marginal contributions are unlikely to change feature-attribution rankings.A threshold on the largest standard deviation may still leave enough variance to change relative feature importance.

7 Recommendations based on data domain

Best practices for Shapley explanations depend on data-domain characteristics, including feature and sample counts, correlation, structure, causal knowledge, and how feature absence can be represented. Feature reduction, suitable marginal or conditional approaches, structured-data methods, and domain-specific baselines can improve tractability and interpretability.

  • Number of features: As feature count grows, model-agnostic explanation costs increase exponentially with the number of possible coalitions, motivating removal of invariant or highly redundant features.Feature selection can reduce the computational burden before explanation generation.
  • Number of samples: Large sample sizes improve conditional Shapley estimates, whereas very small datasets favor parametric assumptions or marginal Shapley values.Samples are more important for estimating conditional expectations and distributions than for generating explanations from the fitted model.
  • Feature correlation: High feature correlation can create large discrepancies between marginal and conditional Shapley values, so practitioners should choose the removal approach carefully or compare both estimates.Correlated features can also make individual attributions harder to interpret, especially when single pixels lack semantic meaning.
  • Data structure: For structured data, feature grouping and specialized methods such as L-Shapley and C-Shapley reduce computational complexity, while FastSHAP accelerates explanations for expensive deep models.For tabular data, tree ensembles can provide performant models that are relatively easy to explain with TreeSHAP variants.
  • Causal knowledge and feature absence: When causal knowledge exists, causal Shapley explanations can respect underlying relationships or assign importance to causal-graph edges, potentially improving on conditional Shapley values.Feature absence should also follow domain conventions, such as masking tokens in text or gray, black, or blurred baselines in images.

8 Related work

The paper situates Shapley-based local feature attributions among alternative coalitional games and game-theoretic solution concepts. These alternatives include global or loss-based games, causal and structural values, and gradient-based extensions.

  • Alternative coalitional games change the coalition value, including mean test loss for global attributions and per-sample loss for local attributions.
  • Asymmetric Shapley values incorporate causal information by assigning zero weight to random order values inconsistent with the underlying causal graph.
  • Banzhaf values assign equal weight to every coalition, while Owen values incorporate coalition structure for hierarchical explanations and groups of strongly correlated features.
  • Aumann-Shapley values extend Shapley values to infinite games and connect to Integrated Gradients, which requires model gradients and therefore excludes some nondifferentiable models.

Data and code availability

The study uses publicly available diabetes, NHANES, and BlogFeedback datasets, drawing the first two from specified software packages.

  • Data and code availability: The diabetes dataset is publicly available and was used in its sklearn package version.Source: https://www4.stat.ncsu.edu/~boos/var.select/diabetes.html.
  • Data and code availability: The NHANES dataset is publicly available and was used in its shap package version.Source: https://wwwn.cdc.gov/nchs/nhanes/nhefs/.
  • Data and code availability: The BlogFeedback dataset is publicly available from the UCI Machine Learning Repository.Source: https://archive.ics.uci.edu/ml/datasets/BlogFeedback.

A Appendix · A.1 Datasets

The appendix compares unbiased stochastic estimators and their variants using three datasets with varying numbers of features.

  • A.1 Datasets: Three datasets with varying numbers of features are used to compare unbiased stochastic estimators and their variants.The datasets support the appendix’s estimator comparison.

A.1.1 Diabetes

The diabetes dataset contains 442 patients described by ten baseline input features, with diabetes progression measured one year later as a continuous output.

  • A.1.1 Diabetes: The dataset includes 442 observations, ten input features, and a continuous target measuring diabetes disease progression one year after baseline.Features include age, sex, and BMI.

A.1.2 NHANES

The NHANES dataset contains 14,264 cases with 79 patient features and a binary outcome indicating 5-year mortality.

  • A.1.2 NHANES: NHANES includes 14,264 records, 79 input features such as age, sex, and BMI, and a binary label for 5-year mortality.The positive class represents mortality within five years after patient features were measured.

A.1.3 Blog · A.2 Experiments

The blog dataset contains 52,397 observations, 280 features, and a non-binary target measuring comments in the next 24 hours. Experiments compare estimator error, bias, and variance across datasets, finding benefits from antithetic and adaptive sampling while SGD is unhelpful for least-squares estimators.

  • A.1.3 Blog: The blog dataset has n = 52397 observations, 280 features, and a non-binary output equal to comments in the next twenty-four hours.
  • A.2 Experiments: Experiments compare estimators using mean squared error against true baseline Shapley values estimated by TreeSHAP.The comparisons cover Figures 6-11 and include Random q and SGD-Shapley variants.
  • A.2 Experiments: Bias and variance are reported separately because they sum to estimator error, with shorthand identifying the sampling-based estimator families.MEF, ROF, RO, and LS denote multilinear extension, random order feature-wise, random order, and least-squares approaches, respectively.
  • A.2 Experiments: Antithetic and adaptive sampling are generally helpful, but their gains vary with dataset feature count.They are only mildly helpful for the small-feature diabetes dataset; NHANES shows greater separation, with antithetic sampling more helpful than adaptive sampling.
  • A.2 Experiments: The default multilinear sampling method improves over random q by sampling q at fixed intervals according to the trapezoid rule.
  • A.2 Experiments: SGD is unhelpful for least-squares estimators, while finite-trial effects can produce non-zero bias even for provably unbiased approaches.With more trials, the observed bias of such approaches would continue to shrink.
  • A.2 Experiments: The experiments include error figures for diabetes, NHANES, and blog datasets, plus comparisons involving additional zero features.
  • A.2 Experiments: Bias and variance tables are provided separately for diabetes, NHANES, and blog datasets.
Loading 2207.07605v1…