arXiv：cs.AI· Christopher Musco, R. Teal Witter·· 24 天前
Leverage SHAP：以 O(n log n) 模型评估实现可证明准确的 Shapley 值估计
Provably Accurate Shapley Value Estimation via Leverage Score Sampling
AI 导读
研究者提出 Leverage SHAP，对 Kernel SHAP 做轻量修改，仅需 O(n log n) 次模型评估即可给出可证明准确的 Shapley 值估计，而精确计算一般模型需 O(2^n) 次评估。
正文 · 原文
Abstract:Originally introduced in game theory, Shapley values have emerged as a central tool in explainable machine learning, where they are used to attribute model predictions to specific input features. However, computing Shapley values exactly is expensive: for a general model with $n$ features, $O(2^n)$ model evaluations are necessary. To address this issue, approximation algorithms are widely used. One of the most popular is the Kernel SHAP algorithm, which is model agnostic and remarkably effective in practice. At the time of our original submission, no strong non-asymptotic complexity guarantees were known for Kernel SHAP. We address this issue by introducing Leverage SHAP, a lightweight modification of Kernel SHAP that provides provably accurate Shapley value estimates with just $O(n\log n)$ model evaluations. Our approach takes advantage of a connection between Shapley value estimation and agnostic active learning by employing leverage score sampling, a powerful regression tool. Beyond theoretical guarantees, we find that Leverage SHAP achieves an approximately $50\%$ reduction in error compared to the highly optimized implementation of Kernel SHAP in the widely used SHAP library [Lundberg & Lee, 2017].
| Comments: | Accepted to ICLR 2025 |
| Subjects: | Machine Learning (cs.LG); Artificial Intelligence (cs.AI) |
| Cite as: | arXiv:2410.01917 [cs.LG] |
| (or arXiv:2410.01917v3 [cs.LG] for this version) | |
| https://doi.org/10.48550/arXiv.2410.01917 arXiv-issued DOI via DataCite |
Submission history
From: R. Teal Witter [view email]
[v1]
Wed, 2 Oct 2024 18:15:48 UTC (272 KB)
[v2]
Mon, 10 Mar 2025 15:52:54 UTC (3,360 KB)
[v3]
Thu, 8 Oct 2026 23:10:08 UTC (820 KB)
来源：arXiv：cs.AI · arxiv.org