Improving KernelSHAP: Practical Shapley Value Estimation Using Linear Regression

Ian Covert, Su-In Lee

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 have emerged as a premier method for machine learning interpretability, most notably through the SHAP framework. By treating features as participants in a cooperative game, they provide a mathematically rigorous way to distribute a model's prediction among its input features. However, the exact calculation of Shapley values is computationally prohibitive, requiring $2^d$ model evaluations for $d$ features.

KernelSHAP addressed this by framing the estimation as a weighted linear regression problem. Despite its popularity, KernelSHAP has lacked rigorous uncertainty estimates, clear convergence criteria, and a deep understanding of its statistical bias. This paper addresses these gaps, providing a more robust and efficient framework for regression-based Shapley estimation.

Methods and Theoretical Improvements

The authors introduce several key enhancements to the KernelSHAP algorithm:

Unbiased Estimator and Paired Sampling

By decomposing the KernelSHAP optimization, the authors derived a mathematically unbiased estimator. While the original KernelSHAP is technically biased, analysis reveals that this bias is negligible compared to the significant variance reduction it offers. To further improve efficiency, the researchers introduced Paired Sampling. Instead of random feature subset selection, this technique samples a subset and its exact complement together, effectively balancing the coalition space and drastically reducing variance without increasing the number of model evaluations.

SHAP Value Confidence Ellipsoids showing the impact of variance reduction techniques.

Convergence Detection and Forecasting

A major practical hurdle in using SHAP is determining the number of samples required for stable results. The authors proved that the variance of their estimators decreases at a predictable $O(1/n)$ rate. This allows for real-time calculation of confidence intervals and the ability to forecast the number of evaluations needed to reach a desired precision level.

Convergence forecasting for SHAP, Shapley Effects, and SAGE estimators.

Stochastic Cooperative Games

The framework was extended to handle "stochastic" games, where the value function is a random variable (e.g., model loss over a data sample). This extension enables fast estimation for global explanation methods like SAGE (Shapley Additive Global Explanations) and Shapley Effects.

Key Results

  • 9x Efficiency Gain: Combining the original KernelSHAP estimator with the new paired sampling technique resulted in a 9-fold reduction in the samples required for convergence compared to standard implementations.
  • Uncertainty Quantification: The paper introduces the first reliable 95% confidence intervals for SHAP and SAGE explanations, providing users with a clear measure of explanation stability.
  • Global Explanation Feasibility: The new stochastic estimators proved to be the only viable method for global explanations like SAGE to converge within reasonable computational limits, where previous naive approaches failed.

Conclusion

This work transforms KernelSHAP from a heuristic approximation into a statistically grounded tool with predictable performance. By providing convergence forecasting and variance reduction, the authors make high-quality model explanations significantly more accessible. Future work may extend these regression-based insights to other popular interpretability methods like LIME, which face similar challenges regarding variance and convergence guidance.

Summary updated

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.
BibTeX
@inproceedings{covert2021improving,
  author = {Ian Covert and Su-In Lee},
  title = {{Improving KernelSHAP: Practical Shapley Value Estimation Using Linear Regression}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2021},
  url = {https://openreview.net/forum?id=OD18u-XiqRI},
}
Figure