PaperlayerView exact revision on arXiv

Source-linked AI summary

Improving KernelSHAP: Practical Shapley Value Estimation via Linear Regression

Ian Covert, Su-In Lee

arXiv:2012.01536v3cs.LGstat.ML

TL;DR

Efficient Shapley value estimation is difficult because naive computation is exponential and KernelSHAP lacks clear unbiasedness, convergence, and uncertainty guarantees. The paper develops an unbiased regression estimator and practical convergence, uncertainty, and variance-reduction techniques, then extends the approach to stochastic cooperative games. It concludes that the original KernelSHAP has negligible bias, lower variance, and faster convergence, while the broader toolkit accelerates estimation for global explanation methods.

  • Problem

    Shapley value estimation is computationally challenging, while KernelSHAP’s unbiasedness, convergence behavior, uncertainty estimates, and sample requirements are insufficiently understood.

  • Method

    The paper analyzes original and unbiased KernelSHAP, develops convergence detection, uncertainty estimation, and variance reduction, and adapts regression estimation to stochastic cooperative games.

  • Results

    The original KernelSHAP has negligible bias, significantly lower variance, and faster convergence, while the proposed techniques provide confidence intervals and faster estimators for two global explanation methods.

  • Takeaways & Limitations

    The resulting tools make linear-regression-based Shapley value estimation more practical by automatically determining sample requirements, quantifying uncertainty, and accelerating estimation.

  • Takeaways & Limitations

    The paper focuses on regression-based estimation and leaves detailed comparisons with sampling-based and model-specific approximations for future work.

Abstract

from arXiv · show

The Shapley value concept from cooperative game theory has become a popular technique for interpreting ML models, but efficiently estimating these values remains challenging, particularly in the model-agnostic setting. Here, we revisit the idea of estimating Shapley values via linear regression to understand and improve upon this approach. By analyzing the original KernelSHAP alongside a newly proposed unbiased version, we develop techniques to detect its convergence and calculate uncertainty estimates. We also find that the original version incurs a negligible increase in bias in exchange for significantly lower variance, and we propose a variance reduction technique that further accelerates the convergence of both estimators. Finally, we develop a version of KernelSHAP for stochastic cooperative games that yields fast new estimators for two global explanation methods.

1 INTRODUCTION

Shapley values are widely used for ML model explanations, but their exponential calculation cost makes efficient estimation essential. This paper revisits linear-regression estimation to address KernelSHAP’s bias, convergence, uncertainty, and variance challenges.

  • Naive Shapley value calculation is exponential in the number of players, motivating sampling-based, model-specific, and regression-based approximations.
  • KernelSHAP’s unbiasedness has been questioned, and it lacks uncertainty estimates and guidance on the number of samples required.
  • The paper derives an unbiased KernelSHAP version and finds that the original has negligible additional bias but significantly lower variance.
  • The authors develop methods to detect convergence, determine required sample sizes automatically, and calculate uncertainty estimates.
  • A variance-reduction technique further accelerates convergence, while a stochastic-game adaptation yields approximations for SAGE and Shapley Effects.
  • Together, these contributions provide a more practical approach to estimating Shapley values through linear regression.

2 THE SHAPLEY VALUE

The Shapley value allocates a cooperative game’s total profit among players using fairness principles and average marginal contributions across orderings. In ML, this framework supports explanations of individual predictions and model behavior across datasets, and motivates weighted least-squares formulations.

  • A cooperative game assigns a value to every coalition of players, while ML explanation methods model features, neurons, or samples as players.
  • SHAP, IME, and QII explain individual predictions using feature-based cooperative games, whereas SAGE and Shapley Effects represent behavior across entire datasets.
  • The Shapley value provides a unique fairness-based allocation of the grand coalition’s total profit among players.
  • Each player’s Shapley value can be understood as its average marginal contribution across all possible player orderings.
  • The Shapley value can be characterized as the solution to a weighted least-squares problem using an additive model.
  • A carefully chosen Shapley kernel makes the optimal regression coefficients equal the Shapley values and enforces intercept and sum constraints.

3 LINEAR REGRESSION APPROXIMATIONS

The paper revisits KernelSHAP’s weighted-regression formulation, which approximates an exponentially large coalition objective by sampling. It then introduces an alternative that keeps the exact objective’s matrix structure while estimating only the value-dependent term.

  • 3.2 Dataset Sampling: Computing the exact regression objective requires evaluating the cooperative game on all 2^d coalitions, so KernelSHAP uses dataset sampling.
  • 3.2 Dataset Sampling: KernelSHAP samples n independent coalitions from a Shapley-kernel distribution and fits an approximate weighted least-squares objective.
  • 3.2 Dataset Sampling: Dataset sampling offers flexibility to use only enough samples to accurately approximate the objective and is also used by LIME.
  • 3.2 Dataset Sampling: The original KernelSHAP estimator is difficult to characterize because its bias, variance, and convergence depend on interacting estimated matrix and vector terms.
  • 3.3 An Exact Estimator: The alternative estimator approximates the exact full-coalition solution rather than exactly solving an approximate sampled problem.
  • 3.3 An Exact Estimator: Because the matrix term can be calculated exactly and efficiently, the proposed method estimates only the value-dependent vector term before forming the estimator.
  • 3.3 An Exact Estimator: The resulting alternative is called unbiased KernelSHAP and is compared with the original approach theoretically and empirically.

4 ESTIMATOR PROPERTIES

The estimators are consistent, while unbiased KernelSHAP is provably unbiased and the original estimator is harder to analyze but often has lower variance. Paired sampling, covariance-based convergence checks, and variance approximation make estimation more practical.

  • Consistency: Both KernelSHAP estimators are consistent as the sample count grows.The unbiased estimator’s convergence follows from the strong law, and the paper states that both estimators are consistent.
  • Bias: Unbiased KernelSHAP is both consistent and unbiased, whereas the original KernelSHAP is only provably consistent.The original estimator’s bias is difficult to verify because its estimated design matrix and response interact.
  • Bias and variance: 250-run experiments found errors dominated by variance; original KernelSHAP had virtually no bias and significantly lower variance.The observed bias for unbiased KernelSHAP can appear higher because of estimation error, although its bias is provably zero.
  • Variance reduction: Paired sampling preserves consistency and unbiasedness and can reduce variance when the game-specific positive-semidefinite condition holds.The paired strategy samples each subset together with its complement, at the cost of twice as many game evaluations for the modified estimator.
  • Variance reduction: For sufficiently large n, the paired estimator’s confidence ellipsoid is contained within the unbiased estimator’s when G_v ⪰ 0.For general games, only nonnegative diagonal entries of G_v are guaranteed, yielding a weaker axis-aligned precision comparison.
  • Convergence detection and forecasting: Covariance estimates can detect convergence, forecast required samples, and provide confidence intervals for both KernelSHAP estimators.The proposed stopping rule compares the largest standard deviation with a fraction of the range of Shapley value estimates; variance is empirically consistent with an O(1/n) rate for the original estimator.

5 STOCHASTIC COOPERATIVE GAMES

The paper extends Shapley values and regression-based estimation to stochastic cooperative games by averaging marginal contributions over player orderings and exogenous randomness. This yields consistent estimators and fast approximations for SAGE and Shapley Effects.

  • 5 STOCHASTIC COOPERATIVE GAMES: Stochastic cooperative games assign random outcomes to coalitions through a function V(S) that maps each coalition to a distribution.The uncertainty is represented by an exogenous variable U, making V(S,U) deterministic in S for fixed U.
  • 5 STOCHASTIC COOPERATIVE GAMES: The proposed stochastic Shapley value averages each player's marginal contribution over both player orderings and values of the exogenous variable U.This generalization is denoted φ_i(V).
  • 5 STOCHASTIC COOPERATIVE GAMES: By Shapley-value linearity, the stochastic value equals the Shapley value of the game's expectation, the expected value for fixed U, and the proposed generalized value.These equivalent formulations suggest deterministic-game calculations but may be slow or intractable when expectations or possible U values are numerous.
  • 5 STOCHASTIC COOPERATIVE GAMES: The paper introduces a fast regression-based estimator for generalized Shapley values in stochastic cooperative games using a simple modification of the preceding approaches.The construction uses independent pairs of samples and adapts the KernelSHAP estimator to the stochastic setting.
  • 5 STOCHASTIC COOPERATIVE GAMES: The adapted KernelSHAP estimator is consistent, while the analogous unbiased version is consistent and unbiased; both can provide uncertainty estimates and detect convergence.These estimators use paired sampling and are applied to global explanation methods including SAGE and Shapley Effects.
  • 5 STOCHASTIC COOPERATIVE GAMES: The stochastic approach dramatically speeds up SAGE and Shapley Effects, while paired sampling accelerates convergence for all estimators.Expectation-based estimators were prohibitively slow, whereas paired stochastic estimators were the fastest and converged for both datasets in the displayed sample range.

6 EXPERIMENTS

Experiments evaluate uncertainty estimates, convergence forecasting, and estimator runtime across four datasets. Paired sampling consistently accelerates convergence, forecasts improve with more samples, and the fastest stochastic estimators outperform expectation-based alternatives.

  • 6 EXPERIMENTS: The experiments use census income, Portuguese bank marketing, German credit, and breast cancer subtype classification datasets with tree-based models.For BRCA, the analysis uses a random subset of 100 of 17,814 genes to avoid overfitting.
  • 6 EXPERIMENTS: SHAP and SAGE examples include convergence thresholds and 95% confidence intervals, features not previously offered by KernelSHAP.SAGE uses the estimator designed for stochastic cooperative games.
  • 6 EXPERIMENTS: 9× average speedup is achieved by paired sampling over original KernelSHAP when explaining 100 instances across the datasets.The dataset-sampling original is consistently faster than the unbiased estimator, while paired sampling enables significantly faster convergence.
  • 6 EXPERIMENTS: Convergence forecasts become more accurate with more samples and vary within an increasingly narrow range around the true required sample count.The forecasts show positive bias, but that bias diminishes with more samples.
  • 6 EXPERIMENTS: Expectation-based estimators for SAGE and Shapley Effects are prohibitively slow and could not reach convergence in the displayed sample range.Paired stochastic estimators are fastest for both datasets and are the only methods that converged for both in that range.

7 DISCUSSION

The paper improves the practicality of linear-regression Shapley value estimation by adding convergence detection, uncertainty estimates, variance reduction, and stochastic-game estimators. It focuses on regression-based estimation while leaving detailed comparisons with sampling-based and model-specific approximations for future work.

  • 7 DISCUSSION: The paper develops linear-regression approaches that automatically determine sample requirements, provide confidence intervals, and accelerate Shapley value estimation.These improvements include convergence detection, uncertainty estimation, and variance reduction.
  • 7 DISCUSSION: The approach is extended to produce significantly faster estimators for two global explanation methods based on stochastic cooperative games.
  • 7 DISCUSSION: The paper focuses on regression-based Shapley value estimation and leaves detailed comparisons with sampling-based and model-specific approximations to future work.
  • 7 DISCUSSION: The authors suggest that insights about convergence and uncertainty may also apply to LIME, whose variance can be high with too few samples.

A CALCULATING A EXACTLY

This appendix derives the matrix A used in the Shapley value linear regression solution from the distribution of a random binary vector Z. Its diagonal entries are constant, while off-diagonal entries depend on d and are numerically computable.

  • A CALCULATING A EXACTLY: A is defined as the expectation E[ZZT] in the Shapley value linear regression problem.
  • A CALCULATING A EXACTLY: The entries of A can be calculated from the known distribution p(Z) of the random binary vector Z.
  • A CALCULATING A EXACTLY: The diagonal entries Aii equal 1/2 regardless of d.
  • A CALCULATING A EXACTLY: The off-diagonal entries Aij depend on d and can be calculated numerically in O(d) time.

B VARIANCE REDUCTION PROOF

The appendix proves a weaker non-negativity condition for the matrix Gv used in the variance-reduction analysis. Specifically, every cooperative game has non-negative diagonal elements in Gv.

  • B VARIANCE REDUCTION PROOF: For every cooperative game v, the diagonal elements satisfy (Gv)ii ≥ 0.

B.1 Theorem 1 Proof

The theorem proof analyzes when complement-paired sampling reduces estimator variance by comparing covariance structures and confidence regions. It also connects Shapley Effects to stochastic cooperative games and distinguishes its exogenous randomness from SAGE’s.

  • B.1 Theorem 1 Proof: The variance-reduction analysis pairs each sample zi drawn from p(Z) with its complement 1 − zi when estimating b.
  • B.1 Theorem 1 Proof: The proof compares the covariance of the paired estimator with the covariance of the original estimator after accounting for twice as many cooperative game evaluations.
  • B.1 Theorem 1 Proof: Gv is the symmetric negated cross-covariance between M0 and M1, and its eigen-structure determines whether the variance-reduction approach is effective.
  • B.1 Theorem 1 Proof: When Gv ⪰ 0, the paired estimator has a confidence ellipsoid contained within that of the original estimator using twice the sample budget.The ellipsoid comparison is made in the asymptotically normal regime.
  • B.1 Theorem 1 Proof: Non-negative diagonal elements of Gv are necessary but not sufficient for Gv ⪰ 0, although the weaker condition holds for all cooperative games.
  • B.1 Theorem 1 Proof: The paired sampling technique yields lower variance for each Shapley value estimate in the axis-aligned directions of the confidence ellipsoids.
  • B.1 Theorem 1 Proof: Shapley Effects can be represented as the expectation of a stochastic cooperative game, including versions using arbitrary loss functions such as cross entropy.
  • B.1 Theorem 1 Proof: For the stochastic cooperative game underlying Shapley Effects, the exogenous random variable is U = X, unlike the one implicitly used by SAGE.

D STOCHASTIC COOPERATIVE GAME PROOFS

The stochastic-game construction adapts KernelSHAP estimators by modifying the b estimator, while unbiasedness or consistency follows from unbiased sampling and large-sample convergence. The section also relates generalized Shapley values to the Shapley values of the expected game and derives covariance-based sample comparisons.

  • Stochastic cooperative games: Generalized Shapley values equal the Shapley values of the game’s expectation, φ_i(¯V), and can be characterized as optimal coefficients of a weighted least-squares problem.The expected game is defined by ¯V(S) = E_U[V(S, U)].
  • Stochastic KernelSHAP: The stochastic KernelSHAP estimator uses the original A estimator with a modified b estimator and converges consistently as the sample size grows.The strong law of large numbers gives convergence of the A estimator, after which the modified b estimator converges to b.
  • Unbiased stochastic estimator: Pairing independent samples of Z and U adapts unbiased KernelSHAP to stochastic cooperative games while preserving unbiasedness and consistency.The paired estimator is constructed by estimating b with paired independent samples and substituting it into the Shapley value estimator.
  • Convergence analysis: Convergence thresholds can be related approximately to the trace of the estimator covariance matrix, enabling sample requirements to be compared through covariance-trace ratios.The covariance matrices used for the ratios are estimated across 100 runs with n = 2048 samples.

F CONVERGENCE EXPERIMENTS

Experiments across multiple datasets and predictions compare original and unbiased KernelSHAP, with paired sampling reducing error for both. The original estimator generally converges faster, while variance dominates bias and its variance approximately follows an inverse-sample-size rate.

  • Individual-prediction experiments: The original KernelSHAP estimator converges significantly faster than the unbiased version across census, bank-marketing, and German-credit predictions.The results also confirm that paired sampling is effective for both estimators.
  • Global bias and variance: After 256 samples, original KernelSHAP with paired sampling has comparably low bias and variance, approximately zero, across the global evaluation.Across estimators, bias is nearly zero and variance is often significantly larger than bias.
  • Variance scaling: The original KernelSHAP variance empirically decreases at approximately O(1/n), matching the rate proved for the unbiased version.The product of variance and sample count remains roughly constant as sample size increases across the evaluated datasets.
  • Algorithms: The appendix provides algorithms for original and unbiased KernelSHAP, their stochastic-game adaptations, convergence detection, paired sampling, and uncertainty estimation.
Loading 2012.01536v3…