Improving the Weighting Strategy in KernelSHAP

• URL: http://arxiv.org/abs/2410.04883v2
• Date: Tue, 06 May 2025 06:40:31 GMT
• Title: Improving the Weighting Strategy in KernelSHAP
• Authors: Lars Henry Berge Olsen, Martin Jullum,
• Abstract summary: 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.
• Score: 0.8057006406834466
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In Explainable AI (XAI), Shapley values are a popular model-agnostic framework for explaining predictions made by complex machine learning models. The computation of Shapley values requires estimating non-trivial contribution functions representing predictions with only a subset of the features present. As the number of these terms grows exponentially with the number of features, computational costs escalate rapidly, creating a pressing need for efficient and accurate approximation methods. For tabular data, the KernelSHAP framework is considered the state-of-the-art model-agnostic approximation framework. KernelSHAP approximates the Shapley values using a weighted sample of the contribution functions for different feature subsets. We propose a novel modification of KernelSHAP which replaces the stochastic weights with deterministic ones to reduce the variance of the resulting Shapley value approximations. This may also be combined with our simple, yet effective modification to the KernelSHAP variant implemented in the popular Python library SHAP. Additionally, we provide an overview of established methods. Numerical experiments demonstrate that 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 -- essentially reducing the running time by up to $50\%$. These computational advancements push the boundaries of the feature dimensionality and number of predictions that can be accurately explained with Shapley values within a feasible runtime.

Related papers

• 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)
• FW-Shapley: Real-time Estimation of Weighted Shapley Values [21.562508939780532]
  We present Fast Weighted Shapley, an amortized framework for efficiently computing weighted Shapley values. We also show that our estimator's training procedure is theoretically valid even though we do not use ground truth weighted Shapley values during training. For data valuation, we are much faster (14 times) while being comparable to the state-of-the-art KNN Shapley.
  arXiv  Detail & Related papers  (2025-03-09T13:13:14Z)
• 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)
• Energy-Based Model for Accurate Estimation of Shapley Values in Feature Attribution [7.378438977893025]
  EmSHAP (Energy-based model for Shapley value estimation) is proposed to estimate the expectation of Shapley contribution function.<n>GRU (Gated Recurrent Unit)-coupled partition function estimation method is introduced.
  arXiv  Detail & Related papers  (2024-04-01T12:19:33Z)
• 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)
• Consensus-Adaptive RANSAC [104.87576373187426]
  We propose a new RANSAC framework that learns to explore the parameter space by considering the residuals seen so far via a novel attention layer. The attention mechanism operates on a batch of point-to-model residuals, and updates a per-point estimation state to take into account the consensus found through a lightweight one-step transformer.
  arXiv  Detail & Related papers  (2023-07-26T08:25:46Z)
• 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)
• Nearly Minimax Optimal Reinforcement Learning for Linear Markov Decision Processes [80.89852729380425]
  We propose the first computationally efficient algorithm that achieves the nearly minimax optimal regret $tilde O(dsqrtH3K)$. Our work provides a complete answer to optimal RL with linear MDPs, and the developed algorithm and theoretical tools may be of independent interest.
  arXiv  Detail & Related papers  (2022-12-12T18:58:59Z)
• A $k$-additive Choquet integral-based approach to approximate the SHAP values for local interpretability in machine learning [8.637110868126546]
  This paper aims at providing some interpretability for machine learning models based on Shapley values. A SHAP-based method called Kernel SHAP adopts an efficient strategy that approximates such values with less computational effort. The obtained results attest that our proposal needs less computations on coalitions of attributes to approximate the SHAP values.
  arXiv  Detail & Related papers  (2022-11-03T22:34:50Z)
• PDD-SHAP: Fast Approximations for Shapley Values using Functional Decomposition [2.0559497209595823]
  We propose PDD-SHAP, an algorithm that uses an ANOVA-based functional decomposition model to approximate the black-box model being explained. This allows us to calculate Shapley values orders of magnitude faster than existing methods for large datasets, significantly reducing the amortized cost of computing Shapley values.
  arXiv  Detail & Related papers  (2022-08-26T11:49:54Z)
• Shapley-NAS: Discovering Operation Contribution for Neural Architecture Search [96.20505710087392]
  We propose a Shapley value based method to evaluate operation contribution (Shapley-NAS) for neural architecture search. We show that our method outperforms the state-of-the-art methods by a considerable margin with light search cost.
  arXiv  Detail & Related papers  (2022-06-20T14:41:49Z)
• 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)
• groupShapley: Efficient prediction explanation with Shapley values for feature groups [2.320417845168326]
  Shapley values has established itself as one of the most appropriate and theoretically sound frameworks for explaining predictions from machine learning models. The main drawback with Shapley values is that its computational complexity grows exponentially in the number of input features. The present paper introduces groupShapley: a conceptually simple approach for dealing with the aforementioned bottlenecks.
  arXiv  Detail & Related papers  (2021-06-23T08:16:14Z)
• Robust Implicit Networks via Non-Euclidean Contractions [63.91638306025768]
  Implicit neural networks show improved accuracy and significant reduction in memory consumption. They can suffer from ill-posedness and convergence instability. This paper provides a new framework to design well-posed and robust implicit neural networks.
  arXiv  Detail & Related papers  (2021-06-06T18:05:02Z)
• Fast Hierarchical Games for Image Explanations [78.16853337149871]
  We present a model-agnostic explanation method for image classification based on a hierarchical extension of Shapley coefficients. Unlike other Shapley-based explanation methods, h-Shap is scalable and can be computed without the need of approximation. We compare our hierarchical approach with popular Shapley-based and non-Shapley-based methods on a synthetic dataset, a medical imaging scenario, and a general computer vision problem.
  arXiv  Detail & Related papers  (2021-04-13T13:11:02Z)
• A Multilinear Sampling Algorithm to Estimate Shapley Values [4.771833920251869]
  We propose a new sampling method based on a multilinear extension technique as applied in game theory. Our method is applicable to any machine learning model, in particular for either multi-class classifications or regression problems.
  arXiv  Detail & Related papers  (2020-10-22T21:47:16Z)
• Scalable Control Variates for Monte Carlo Methods via Stochastic Optimization [62.47170258504037]
  This paper presents a framework that encompasses and generalizes existing approaches that use controls, kernels and neural networks. Novel theoretical results are presented to provide insight into the variance reduction that can be achieved, and an empirical assessment, including applications to Bayesian inference, is provided in support.
  arXiv  Detail & Related papers  (2020-06-12T22:03:25Z)

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.