PolySHAP: Extending KernelSHAP with Interaction-Informed Polynomial Regression

• URL: http://arxiv.org/abs/2601.18608v1
• Date: Mon, 26 Jan 2026 15:47:45 GMT
• Title: PolySHAP: Extending KernelSHAP with Interaction-Informed Polynomial Regression
• Authors: Fabian Fumagalli, R. Teal Witter, Christopher Musco,
• Abstract summary: We show that KernelSHAP avoids the exponential cost of approximating Shapley values by approximating the game as a linear function.<n>We also prove that paired sampling produces exactly the same value approximations as second-order PolySHAP, without ever fitting a degree 2.
• Score: 26.711792479550954
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Shapley values have emerged as a central game-theoretic tool in explainable AI (XAI). However, computing Shapley values exactly requires $2^d$ game evaluations for a model with $d$ features. Lundberg and Lee's KernelSHAP algorithm has emerged as a leading method for avoiding this exponential cost. KernelSHAP approximates Shapley values by approximating the game as a linear function, which is fit using a small number of game evaluations for random feature subsets. In this work, we extend KernelSHAP by approximating the game via higher degree polynomials, which capture non-linear interactions between features. Our resulting PolySHAP method yields empirically better Shapley value estimates for various benchmark datasets, and we prove that these estimates are consistent. Moreover, we connect our approach to paired sampling (antithetic sampling), a ubiquitous modification to KernelSHAP that improves empirical accuracy. We prove that paired sampling outputs exactly the same Shapley value approximations as second-order PolySHAP, without ever fitting a degree 2 polynomial. To the best of our knowledge, this finding provides the first strong theoretical justification for the excellent practical performance of the paired sampling heuristic.

Related papers

• 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)
• Closing the Approximation Gap of Partial AUC Optimization: A Tale of Two Formulations [121.39938773554523]
  The Area Under the ROC Curve (AUC) is a pivotal evaluation metric in real-world scenarios with both class imbalance and decision constraints.<n>We present two simple instance-wise minimax reformulations to close the approximation gap of PAUC optimization.<n>The resulting algorithms enjoy a linear per-iteration computational complexity w.r.t. the sample size and a convergence rate of $O(-2/3)$ for typical one-way and two-way PAUCs.
  arXiv  Detail & Related papers  (2025-12-01T02:52:33Z)
• Shapley Values: Paired-Sampling Approximations [0.0]
  Shapley values have become a very popular tool to explain machine learning predictions.<n>Based on Shapley's fairness axioms, every input (feature component) gets a credit how it contributes to an output (prediction)<n>The only limitation in computing the Shapley values (credits) for many different predictions is of computational nature.
  arXiv  Detail & Related papers  (2025-08-18T14:23:34Z)
• 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)
• Highly Adaptive Ridge [84.38107748875144]
  We propose a regression method that achieves a $n-2/3$ dimension-free L2 convergence rate in the class of right-continuous functions with square-integrable sectional derivatives. Har is exactly kernel ridge regression with a specific data-adaptive kernel based on a saturated zero-order tensor-product spline basis expansion. We demonstrate empirical performance better than state-of-the-art algorithms for small datasets in particular.
  arXiv  Detail & Related papers  (2024-10-03T17:06:06Z)
• 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)
• 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)
• Generalized Differentiable RANSAC [95.95627475224231]
  $nabla$-RANSAC is a differentiable RANSAC that allows learning the entire randomized robust estimation pipeline. $nabla$-RANSAC is superior to the state-of-the-art in terms of accuracy while running at a similar speed to its less accurate alternatives.
  arXiv  Detail & Related papers  (2022-12-26T15:13:13Z)
• Planning and Learning with Adaptive Lookahead [74.39132848733847]
  Policy Iteration (PI) algorithm alternates between greedy one-step policy improvement and policy evaluation. Recent literature shows that multi-step lookahead policy improvement leads to a better convergence rate at the expense of increased complexity per iteration. We propose for the first time to dynamically adapt the multi-step lookahead horizon as a function of the state and of the value estimate.
  arXiv  Detail & Related papers  (2022-01-28T20:26:55Z)
• 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)

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.