arXiv cs.AI· Christopher Musco, R. Teal Witter·· 6 天前AI 评分24
Leverage SHAP：通过杠杆分数采样实现可证明精确的 Shapley 值估计
Provably Accurate Shapley Value Estimation via Leverage Score Sampling
AI 导读
研究者提出 Leverage SHAP，对 Kernel SHAP 做轻量修改，仅需 O(n log n) 次模型评估即可给出可证明精确的 Shapley 值估计。该方法利用 Shapley 值估计与不可知主动学习之间的联系，采用杠杆分数采样。相比 SHAP 库中高度优化的 Kernel SHAP 实现，其误差降低约 50%。该工作已被 ICLR 2025 接收。
正文 · 原文
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