最初在博弈论中引入的 Shapley 值已成为可解释机器学习中的核心工具，用于将模型预测归因于特定输入特征。然而，精确计算 Shapley 值的成本很高：对于具有 $n$ 个特征的通用模型，需要 $O(2^n)$ 次模型评估。为了解决这个问题，广泛使用近似算法。其中最流行的一种是 Kernel SHAP 算法，该算法与模型无关，在实践中非常有效。然而，据我们所知，Kernel SHAP 没有任何强烈的非渐近复杂度保证。我们通过引入 Leverage SHAP 来解决这个问题，Leverage SHAP 是 Kernel SHAP 的轻量级修改，它仅使用 $O(n\log n)$ 次模型评估即可提供可证明准确的 Shapley 值估计。我们的方法利用了 Shapley 值估计与不可知主动学习之间的联系，通过采用杠杆得分采样，这是一种强大的回归工具。除了理论保证外，我们还表明 Leverage SHAP 始终优于甚至在普遍存在的 SHAP 库 [Lundberg & Lee, 2017] 中提供的 Kernel SHAP 的高度优化实现。