Abstract
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.
Introduction
Shapley values are often considered the gold standard for feature attribution in machine learning because they provide a fair distribution of "credit" for a model's prediction. However, exact calculation is computationally prohibitive, scaling exponentially with the number of features ($O(2^d)$). KernelSHAP, a regression-based approximation, has gained widespread adoption but suffers from several practical limitations: it lacks clear stopping criteria, provides no uncertainty estimates, and can be prohibitively slow for global explanation methods like SAGE.
Methodology: Upgrading KernelSHAP
This research systematically deconstructs the KernelSHAP framework to address these shortcomings through several key innovations:
Paired Sampling for Variance Reduction
The authors introduce a "paired sampling" trick. Instead of independent random sampling of feature subsets (coalitions), they sample a subset $z$ and its exact complement $1-z$. This technique mathematically guarantees lower variance in the resulting estimates, leading to significantly faster convergence.
Convergence Detection and Forecasting
By tracking the variance of estimates online, the authors developed a method to automatically stop the algorithm once confidence intervals shrink below a user-defined threshold. This removes the guesswork involved in choosing the number of samples.
Stochastic Cooperative Games
To accelerate global explanation methods, the authors reframed them as stochastic cooperative games. This allows KernelSHAP to be applied directly to random input-label pairs, avoiding the need for expensive dataset-wide expectations for every feature coalition.
Key Insights and Results
The evaluation across datasets like Census Income and German Credit yielded several critical findings:
The Bias-Variance Tradeoff: While the authors derived a mathematically unbiased version of KernelSHAP, they discovered that the original (technically biased) version is superior in practice. The original estimator trades a negligible amount of bias for a massive reduction in variance, as shown in the error decomposition.
Performance Gains: The combination of paired sampling and the original KernelSHAP algorithm achieved a 9x speedup on average compared to the baseline. Furthermore, the new stochastic estimator was the only method fast enough to make global methods like SAGE computationally feasible in many scenarios.
Conclusion
By refining the regression-based approach to Shapley values, this work transforms KernelSHAP into a more robust and efficient tool. The introduction of uncertainty estimates and automated stopping criteria addresses major usability hurdles, while variance reduction techniques and the stochastic game framework significantly expand the practical reach of both local and global model explanations. Future work may extend these variance reduction and convergence tracking insights to other popular methods like LIME.
Summary updated