通过杠杆分数采样实现具有可证明准确性的 Shapley 值估计

arXiv:2410.01917v3 公告类型：替换 摘要：Shapley 值最初源于博弈论，如今已成为可解释机器学习的核心工具，用于将模型预测归因于特定输入特征。然而，精确计算 Shapley 值的成本高昂：对于具有 $n$ 个特征的一般模型，需要进行 $O(2^n)$ 次模型评估。为解决这一问题，近似算法得到了广泛应用。其中最流行的算法之一是 Kernel SHAP，它不依赖于具体模型，且在实践中效果显著。在我们最初提交论文时，Kernel SHAP 尚无已知的强非渐近复杂度保证。为此，我们提出了 Leverage SHAP，这是对 Kernel SHAP 的一种轻量级修改，仅需 $O(n\log n)$ 次模型评估即可提供具有可证明准确性的 Shapley 值估计。我们的方法利用了 Shapley 值估计与不可知主动学习之间的联系，采用了杠杆分数采样这一强大的回归工具。除理论保证外，我们还发现，与广泛使用的 SHAP 库 [Lundberg & Lee, 2017] 中经过高度优化的 Kernel SHAP 实现相比，Leverage SHAP 可将误差降低约 $50\%$。