A Unified Framework for Provably Efficient Algorithms to Estimate Shapley Values

• URL: http://arxiv.org/abs/2506.05216v1
• Date: Thu, 05 Jun 2025 16:30:53 GMT
• Title: A Unified Framework for Provably Efficient Algorithms to Estimate Shapley Values
• Authors: Tyler Chen, Akshay Seshadri, Mattia J. Villani, Pradeep Niroula, Shouvanik Chakrabarti, Archan Ray, Pranav Deshpande, Romina Yalovetzky, Marco Pistoia, Niraj Kumar,
• Abstract summary: We describe a broad and unified framework that encompasses KernelSHAP and related estimators constructed using both with and without replacement sampling strategies.<n>We prove strong non-asymptotic theoretical guarantees that apply to all estimators from our framework.<n>We validate our approach against exact Shapley values, consistently achieving low mean squared error with modest sample sizes.
• Score: 4.445994770262589
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: Shapley values have emerged as a critical tool for explaining which features impact the decisions made by machine learning models. However, computing exact Shapley values is difficult, generally requiring an exponential (in the feature dimension) number of model evaluations. To address this, many model-agnostic randomized estimators have been developed, the most influential and widely used being the KernelSHAP method (Lundberg & Lee, 2017). While related estimators such as unbiased KernelSHAP (Covert & Lee, 2021) and LeverageSHAP (Musco & Witter, 2025) are known to satisfy theoretical guarantees, bounds for KernelSHAP have remained elusive. We describe a broad and unified framework that encompasses KernelSHAP and related estimators constructed using both with and without replacement sampling strategies. We then prove strong non-asymptotic theoretical guarantees that apply to all estimators from our framework. This provides, to the best of our knowledge, the first theoretical guarantees for KernelSHAP and sheds further light on tradeoffs between existing estimators. Through comprehensive benchmarking on small and medium dimensional datasets for Decision-Tree models, we validate our approach against exact Shapley values, consistently achieving low mean squared error with modest sample sizes. Furthermore, we make specific implementation improvements to enable scalability of our methods to high-dimensional datasets. Our methods, tested on datasets such MNIST and CIFAR10, provide consistently better results compared to the KernelSHAP library.

Related papers

• Generalized Linear Bandits: Almost Optimal Regret with One-Pass Update [60.414548453838506]
  We study the generalized linear bandit (GLB) problem, a contextual multi-armed bandit framework that extends the classical linear model by incorporating a non-linear link function.<n>GLBs are widely applicable to real-world scenarios, but their non-linear nature introduces significant challenges in achieving both computational and statistical efficiency.<n>We propose a jointly efficient algorithm that attains a nearly optimal regret bound with $mathcalO(1)$ time and space complexities per round.
  arXiv  Detail & Related papers  (2025-07-16T02:24:21Z)
• SIM-Shapley: A Stable and Computationally Efficient Approach to Shapley Value Approximation [8.323065815365602]
  Shapley value (SV) methods provide a principled framework for feature attribution in complex models but incur high computational costs.<n>We propose Iterative Momentum for Shapley Value Approximation (SIM-Shapley), a stable and efficient approximation method inspired by optimization.<n>In our numerical experiments, SIM-Shapley reduces computation time by up to 85% relative to state-of-the-art baselines.
  arXiv  Detail & Related papers  (2025-05-13T03:23:10Z)
• Improving the Weighting Strategy in KernelSHAP [0.8057006406834466]
  In Explainable AI (XAI) Shapley values are a popular framework for explaining predictions made by complex machine learning models.<n>We propose a novel modification of KernelSHAP which replaces the deterministic weights with ones to reduce the variance of the resulting Shapley value approximations.<n>Our methods can reduce the required number of contribution function evaluations by $5%$ to $50%$ while preserving the same accuracy of the approximated Shapley values.
  arXiv  Detail & Related papers  (2024-10-07T10:02:31Z)
• Provably Accurate Shapley Value Estimation via Leverage Score Sampling [12.201705893125775]
  We introduce Leverage SHAP, a light-weight modification of Kernel SHAP that provides provably accurate Shapley value estimates with just $O(nlog n)$ model evaluations.<n>Our approach takes advantage of a connection between Shapley value estimation and active learning by employing leverage score sampling, a powerful regression tool.
  arXiv  Detail & Related papers  (2024-10-02T18:15:48Z)
• Latent Semantic Consensus For Deterministic Geometric Model Fitting [109.44565542031384]
  We propose an effective method called Latent Semantic Consensus (LSC) LSC formulates the model fitting problem into two latent semantic spaces based on data points and model hypotheses. LSC is able to provide consistent and reliable solutions within only a few milliseconds for general multi-structural model fitting.
  arXiv  Detail & Related papers  (2024-03-11T05:35:38Z)
• Fast Shapley Value Estimation: A Unified Approach [71.92014859992263]
  We propose a straightforward and efficient Shapley estimator, SimSHAP, by eliminating redundant techniques. In our analysis of existing approaches, we observe that estimators can be unified as a linear transformation of randomly summed values from feature subsets. Our experiments validate the effectiveness of our SimSHAP, which significantly accelerates the computation of accurate Shapley values.
  arXiv  Detail & Related papers  (2023-11-02T06:09:24Z)
• Efficient Shapley Values Estimation by Amortization for Text Classification [66.7725354593271]
  We develop an amortized model that directly predicts each input feature's Shapley Value without additional model evaluations. Experimental results on two text classification datasets demonstrate that our amortized model estimates Shapley Values accurately with up to 60 times speedup.
  arXiv  Detail & Related papers  (2023-05-31T16:19:13Z)
• RKHS-SHAP: Shapley Values for Kernel Methods [17.52161019964009]
  We propose an attribution method for kernel machines that can efficiently compute both emphInterventional and emphObservational Shapley values We show theoretically that our method is robust with respect to local perturbations - a key yet often overlooked desideratum for interpretability.
  arXiv  Detail & Related papers  (2021-10-18T10:35:36Z)
• A bandit-learning approach to multifidelity approximation [7.960229223744695]
  Multifidelity approximation is an important technique in scientific computation and simulation. We introduce a bandit-learning approach for leveraging data of varying fidelities to achieve precise estimates.
  arXiv  Detail & Related papers  (2021-03-29T05:29:35Z)
• Large-Scale Methods for Distributionally Robust Optimization [53.98643772533416]
  We prove that our algorithms require a number of evaluations gradient independent of training set size and number of parameters. Experiments on MNIST and ImageNet confirm the theoretical scaling of our algorithms, which are 9--36 times more efficient than full-batch methods.
  arXiv  Detail & Related papers  (2020-10-12T17:41:44Z)
• Efficient Ensemble Model Generation for Uncertainty Estimation with Bayesian Approximation in Segmentation [74.06904875527556]
  We propose a generic and efficient segmentation framework to construct ensemble segmentation models. In the proposed method, ensemble models can be efficiently generated by using the layer selection method. We also devise a new pixel-wise uncertainty loss, which improves the predictive performance.
  arXiv  Detail & Related papers  (2020-05-21T16:08:38Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.