Improving KernelSHAP: Practical Shapley Value Estimation via Linear Regression

• URL: http://arxiv.org/abs/2012.01536v3
• Date: Fri, 23 Apr 2021 01:33:31 GMT
• Title: Improving KernelSHAP: Practical Shapley Value Estimation via Linear Regression
• Authors: Ian Covert, Su-In Lee
• Abstract summary: We revisit the idea of estimating Shapley values via linear regression to understand and improve upon this approach. We develop techniques to detect its convergence and calculate uncertainty estimates. We develop a version of KernelSHAP for cooperative games that yields fast new estimators for two global explanation methods.
• Score: 9.89901717499058
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• Nonparametric Distribution Regression Re-calibration [3.0204520109309847]
  Minimizing overall prediction error encourages models to prioritize informativeness over calibration.<n>In safety-critical settings, trustworthy uncertainty estimates are often more valuable than narrow intervals.<n>We propose a novel non-parametric re-calibration algorithm based on conditional kernel mean embeddings.
  arXiv  Detail & Related papers  (2026-02-13T11:48:43Z)
• An Odd Estimator for Shapley Values [19.262788739385012]
  The Shapley value is a framework for attribution in machine learning, encompassing feature importance, data valuation, and causal inference.<n>We prove that the Shapley value depends exclusively on the odd component of the set function, and that paired samplingizes the objective regression to filter out the irrelevant even component.<n>We propose OddSHAP, a consistent estimator that performs regression solely on the odd subspace.
  arXiv  Detail & Related papers  (2026-02-01T19:07:16Z)
• 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)
• A Simplified Analysis of SGD for Linear Regression with Weight Averaging [64.2393952273612]
  Recent work bycitetzou 2021benign provides sharp rates for SGD optimization in linear regression using constant learning rate.<n>We provide a simplified analysis recovering the same bias and variance bounds provided incitepzou 2021benign based on simple linear algebra tools.<n>We believe our work makes the analysis of gradient descent on linear regression very accessible and will be helpful in further analyzing mini-batching and learning rate scheduling.
  arXiv  Detail & Related papers  (2025-06-18T15:10:38Z)
• Self-Boost via Optimal Retraining: An Analysis via Approximate Message Passing [58.52119063742121]
  Retraining a model using its own predictions together with the original, potentially noisy labels is a well-known strategy for improving the model performance.<n>This paper addresses the question of how to optimally combine the model's predictions and the provided labels.<n>Our main contribution is the derivation of the Bayes optimal aggregator function to combine the current model's predictions and the given labels.
  arXiv  Detail & Related papers  (2025-05-21T07:16:44Z)
• Principal Component Analysis When n < p: Challenges and Solutions [0.0]
  Principal Component Analysis is a key technique for reducing the complexity of high-dimensional data.<n>Standard principal component analysis performs poorly as a dimensionality reduction technique in high-dimensional scenarios.<n>We propose a novel estimation called pairwise differences covariance estimation.
  arXiv  Detail & Related papers  (2025-03-21T22:33:52Z)
• 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)
• Variance-Reducing Couplings for Random Features [57.73648780299374]
  Random features (RFs) are a popular technique to scale up kernel methods in machine learning. We find couplings to improve RFs defined on both Euclidean and discrete input spaces. We reach surprising conclusions about the benefits and limitations of variance reduction as a paradigm.
  arXiv  Detail & Related papers  (2024-05-26T12:25:09Z)
• Energy-based Model for Accurate Shapley Value Estimation in Interpretable Deep Learning Predictive Modeling [7.378438977893025]
  EmSHAP is an energy-based model for Shapley value estimation. It estimates the expectation of Shapley contribution function under arbitrary subset of features.
  arXiv  Detail & Related papers  (2024-04-01T12:19:33Z)
• Functional Partial Least-Squares: Optimal Rates and Adaptation [0.0]
  We propose a new formulation of the functional partial least-squares (PLS) estimator related to the conjugate gradient method. We show that the estimator achieves the (nearly) optimal convergence rate on a class of ellipsoids.
  arXiv  Detail & Related papers  (2024-02-16T23:47:47Z)
• Model-Based Epistemic Variance of Values for Risk-Aware Policy Optimization [59.758009422067]
  We consider the problem of quantifying uncertainty over expected cumulative rewards in model-based reinforcement learning. We propose a new uncertainty Bellman equation (UBE) whose solution converges to the true posterior variance over values. We introduce a general-purpose policy optimization algorithm, Q-Uncertainty Soft Actor-Critic (QU-SAC) that can be applied for either risk-seeking or risk-averse policy optimization.
  arXiv  Detail & Related papers  (2023-12-07T15:55:58Z)
• 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)
• Improved Convergence Rates for Sparse Approximation Methods in Kernel-Based Learning [48.08663378234329]
  Kernel-based models such as kernel ridge regression and Gaussian processes are ubiquitous in machine learning applications. Existing sparse approximation methods can yield a significant reduction in the computational cost. We provide novel confidence intervals for the Nystr"om method and the sparse variational Gaussian processes approximation method.
  arXiv  Detail & Related papers  (2022-02-08T17:22:09Z)
• Learning to Estimate Without Bias [57.82628598276623]
  Gauss theorem states that the weighted least squares estimator is a linear minimum variance unbiased estimation (MVUE) in linear models. In this paper, we take a first step towards extending this result to non linear settings via deep learning with bias constraints. A second motivation to BCE is in applications where multiple estimates of the same unknown are averaged for improved performance.
  arXiv  Detail & Related papers  (2021-10-24T10:23:51Z)
• An Imprecise SHAP as a Tool for Explaining the Class Probability Distributions under Limited Training Data [5.8010446129208155]
  An imprecise SHAP is proposed for cases when the class probability distributions are imprecise and represented by sets of distributions. The first idea behind the imprecise SHAP is a new approach for computing the marginal contribution of a feature. The second idea is an attempt to consider a general approach to calculating and reducing interval-valued Shapley values.
  arXiv  Detail & Related papers  (2021-06-16T20:30:26Z)
• A Distributional Analysis of Sampling-Based Reinforcement Learning Algorithms [67.67377846416106]
  We present a distributional approach to theoretical analyses of reinforcement learning algorithms for constant step-sizes. We show that value-based methods such as TD($lambda$) and $Q$-Learning have update rules which are contractive in the space of distributions of functions.
  arXiv  Detail & Related papers  (2020-03-27T05:13:29Z)

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.