Fast Shapley Value Estimation: A Unified Approach

• URL: http://arxiv.org/abs/2311.01010v2
• Date: Thu, 23 May 2024 08:07:48 GMT
• Title: Fast Shapley Value Estimation: A Unified Approach
• Authors: Borui Zhang, Baotong Tian, Wenzhao Zheng, Jie Zhou, Jiwen Lu,
• Abstract summary: 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.
• Score: 71.92014859992263
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Shapley values have emerged as a widely accepted and trustworthy tool, grounded in theoretical axioms, for addressing challenges posed by black-box models like deep neural networks. However, computing Shapley values encounters exponential complexity as the number of features increases. Various approaches, including ApproSemivalue, KernelSHAP, and FastSHAP, have been explored to expedite the computation. In our analysis of existing approaches, we observe that stochastic estimators can be unified as a linear transformation of randomly summed values from feature subsets. Based on this, we investigate the possibility of designing simple amortized estimators and propose a straightforward and efficient one, SimSHAP, by eliminating redundant techniques. Extensive experiments conducted on tabular and image datasets validate the effectiveness of our SimSHAP, which significantly accelerates the computation of accurate Shapley values.

Related papers

• Improving the Sampling Strategy in KernelSHAP [0.8057006406834466]
  KernelSHAP framework enables us to approximate the Shapley values using a sampled subset of weighted conditional expectations. We propose three main novel contributions: a stabilizing technique to reduce the variance of the weights in the current state-of-the-art strategy, a novel weighing scheme that corrects the Shapley kernel weights based on sampled subsets, and a straightforward strategy that includes the important subsets and integrates them with the corrected Shapley kernel weights.
  arXiv  Detail & Related papers  (2024-10-07T10:02:31Z)
• Variational Shapley Network: A Probabilistic Approach to Self-Explaining Shapley values with Uncertainty Quantification [2.6699011287124366]
  Shapley values have emerged as a foundational tool in machine learning (ML) for elucidating model decision-making processes. We introduce a novel, self-explaining method that simplifies the computation of Shapley values significantly, requiring only a single forward pass.
  arXiv  Detail & Related papers  (2024-02-06T18:09:05Z)
• 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)
• DU-Shapley: A Shapley Value Proxy for Efficient Dataset Valuation [23.646508094051768]
  We consider the dataset valuation problem, that is, the problem of quantifying the incremental gain. The Shapley value is a natural tool to perform dataset valuation due to its formal axiomatic justification. We propose a novel approximation, referred to as discrete uniform Shapley, which is expressed as an expectation under a discrete uniform distribution.
  arXiv  Detail & Related papers  (2023-06-03T10:22:50Z)
• 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)
• Accelerating Shapley Explanation via Contributive Cooperator Selection [42.11059072201565]
  We propose a novel method SHEAR to significantly accelerate the Shapley explanation for DNN models. The selection of the feature coalitions follows our proposed Shapley chain rule to minimize the absolute error from the ground-truth Shapley values. SHEAR consistently outperforms state-of-the-art baseline methods across different evaluation metrics.
  arXiv  Detail & Related papers  (2022-06-17T03:24:45Z)
• Bias-Variance Tradeoffs in Single-Sample Binary Gradient Estimators [100.58924375509659]
  Straight-through (ST) estimator gained popularity due to its simplicity and efficiency. Several techniques were proposed to improve over ST while keeping the same low computational complexity. We conduct a theoretical analysis of Bias and Variance of these methods in order to understand tradeoffs and verify originally claimed properties.
  arXiv  Detail & Related papers  (2021-10-07T15:16:07Z)
• Efficient computation and analysis of distributional Shapley values [15.322542729755998]
  We derive the first analytic expressions for DShapley for the canonical problems of linear regression, binary classification, and non-parametric density estimation. Our formulas are directly interpretable and provide quantitative insights into how the value varies for different types of data.
  arXiv  Detail & Related papers  (2020-07-02T19:51:54Z)
• $\gamma$-ABC: Outlier-Robust Approximate Bayesian Computation Based on a Robust Divergence Estimator [95.71091446753414]
  We propose to use a nearest-neighbor-based $gamma$-divergence estimator as a data discrepancy measure. Our method achieves significantly higher robustness than existing discrepancy measures.
  arXiv  Detail & Related papers  (2020-06-13T06:09:27Z)
• Reintroducing Straight-Through Estimators as Principled Methods for Stochastic Binary Networks [85.94999581306827]
  Training neural networks with binary weights and activations is a challenging problem due to the lack of gradients and difficulty of optimization over discrete weights. Many successful experimental results have been achieved with empirical straight-through (ST) approaches. At the same time, ST methods can be truly derived as estimators in the binary network (SBN) model with Bernoulli weights.
  arXiv  Detail & Related papers  (2020-06-11T23:58:18Z)

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.