用采样方法让模型解释更准更快，只需原方法十分之一的计算量。
Provably Accurate Shapley Value Estimation via Leverage Score Sampling
- 通过杠杆率采样优化采样策略，提升估计效率。
- 仅需O(n log n)次模型评估，精度远超现有方法。
- 理论保证强，适合对解释准确性要求高的场景。
Shapley值在可解释机器学习中被广泛用于归因输入特征对模型预测的贡献。然而，精确计算其值代价高昂：对于具有n个特征的一般模型，需O(2^n)次模型评估。为缓解此问题，近似算法被普遍采用，其中最流行的是无需依赖模型结构的Kernel SHAP，但其缺乏严格的非渐近复杂度保证。本文提出Leverage SHAP，作为Kernel SHAP的轻量级改进版本，利用其与无监督主动学习之间的联系，引入杠杆率采样技术，仅需O(n log n)次模型评估即可获得可证明准确的Shapley值估计。实验表明，Leverage SHAP在多个数据集上均显著优于现有SHAP库中的高度优化实现。
原文摘要 · Abstract (English)
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. However, to the best of our knowledge, Kernel SHAP has no strong non-asymptotic complexity guarantees. We address this issue by introducing Leverage SHAP, a light-weight 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 show that Leverage SHAP consistently outperforms even the highly optimized implementation of Kernel SHAP available in the ubiquitous SHAP library [Lundberg & Lee, 2017].
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。