用多项式回归提升Shapley值估计精度，更准确捕捉特征间非线性交互。
PolySHAP: Extending KernelSHAP with Interaction-Informed Polynomial Regression
- 用高阶多项式替代线性近似，更好建模特征间复杂交互
- 在多个基准数据集上显著提升Shapley值估计准确性
- 首次理论证明配对采样等价于二阶多项式方法，解释其高效原因
Shapley值已成为可解释人工智能（XAI）中的核心博弈论工具。然而，精确计算需对d个特征进行2^d次模型评估。Lundberg和Lee提出的KernelSHAP算法通过随机特征子集的小规模评估，将游戏近似为线性函数，有效避免了指数级开销。本文提出PolySHAP，通过更高阶多项式近似游戏，以捕捉特征间的非线性交互。实验表明，PolySHAP在多个基准数据集上均获得更优的Shapley值估计。我们进一步证明该估计具有一致性。此外，我们发现配对采样（paired sampling）——一种广泛用于提升KernelSHAP性能的技巧——等价于不显式拟合二次多项式的二阶PolySHAP方法。据我们所知，这是首个对配对采样卓越表现提供强有力理论支持的发现。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。