Leverage SHAP 能否以可证明的精度估计 Shapley 值？

Kernel SHAP 缺少非渐近保证

Shapley 值把一次模型预测分摊到各个输入特征上。精确计算代价很高：论文指出，对含 n 个特征的一般模型，需要 O(2^n) 次模型评估，因为价值函数几乎要在每个特征子集上查询一次。Kernel SHAP 绕开这一代价的做法，是把 Shapley 值看作一个在子集上定义的加权最小二乘回归的解，再用抽样的子集构造近似问题并求解。

论文给出的动机正是这一近似中的缺口。在最初投稿时，当 Kernel SHAP 使用的抽样行少于 2^n − 2 时，人们并不知道它有任何强的非渐近复杂度保证。非渐近保证是指在固定的有限样本量下就成立的界，而不只是在样本量趋于无穷时才成立——这正是实际使用所处的区间。Leverage SHAP 被提出作为补上这一缺口的方案，同时保留 Kernel SHAP 与模型无关的结构。

用杠杆分数替代按权重抽样

Kernel SHAP 按权重函数 w(|S|) = C(n,|S|)^-1 · (|S|(n−|S|))^-1 成比例地抽取子集，其直觉是回归和中较大的项应当被更频繁地抽到。论文认为，对最小二乘问题做子抽样，更有原则的做法是按各行的统计杠杆分数成比例抽样；杠杆分数衡量设计矩阵中某一行有多重要或多独特。

直接套用这一想法并不可行，因为设计矩阵有 2^n − 2 行，把全部杠杆分数写下来至少要 O(2^n) 时间。论文的关键技术一步是证明：用投影矩阵把带约束的 Shapley 回归改写成无约束回归后，任意子集 S 对应行的杠杆分数与 C(n,|S|)^-1 成正比。由于同一大小的所有子集分数相同，抽样就变得很便宜：先从 {1, …, n−1} 中均匀抽一个大小 s，再均匀随机抽一个该大小的子集。这个分布与 Kernel SHAP 的分布相似，但有实质区别。

保证约束的是目标误差而非单个值

定理 1.1 指出，对任意 ε > 0 和常数 δ > 0，Leverage SHAP 期望使用 m = O(n log(n/δ) + n·(1/(εδ))) 次价值函数评估，外加 O(mn²) 的额外运行时间，返回的估计 φ̃ 满足效率约束 ⟨φ̃,1⟩ = v([n]) − v(∅)，并且以 1 − δ 的概率满足 ∥Zφ̃ − y∥²₂ ≤ (1+ε)∥Zφ − y∥²₂。

这是对回归目标值的界，并不直接约束读者通常关心的逐特征误差。论文用推论 4.1 补上了一部分差距：如果估计满足效率约束和目标界，且 ∥Aφ∥² > 0，那么 ∥φ − φ̃∥²₂ ≤ εγ∥φ∥²₂，其中 γ = ∥Aφ − b∥²₂ / ∥Aφ∥²₂ 衡量最优系数能在多大程度上逼近目标向量。作者在附录 F 中报告，随着 γ 增大，所有基于回归的算法性能都会下降，他们据此认为 γ 并非其分析产生的假象。论文还在附录 C 中说明，为什么以乘性误差估计 Shapley 值是 NP 难的，这也是保证要这样表述的原因。

配对抽样与无放回抽样可以沿用

SHAP 库中的优化版 Kernel SHAP 包含两项实用改进：配对抽样，即抽到集合 S 时也抽它的补集，使每个特征出现在相同数量的样本中；以及无放回抽样，这在 n 较小时很重要，因为有放回抽样即使 m 接近或超过 2^n 也可能仍不准确。论文表明，杠杆分数抽样可以与配对抽样结合而不损失理论保证，而无放回版本在 m 较大时能进一步提升精度。

消融实验量化了各部分的作用。伯努利（无放回）抽样对大的 n 影响很小，但能把小 n 时 Leverage SHAP 的误差降低 1.1 到 10 倍，典型情形约为 2 倍，且随着 m 接近 2^n 而增大。在样本量实验的每一种设置下，配对抽样都把误差降低约四倍或更多。

误差约为优化版 Kernel SHAP 的一半

实验使用 SHAP 库中的八个数据集，n 从 4（IRIS）到 101（Communities）。真实 Shapley 值由树模型上的 Tree SHAP 算出，树模型用 XGBoost 训练，100 棵树、最大深度 4。主要指标是相对平方 ℓ2 误差 ∥φ − φ̃∥²₂ / ∥φ∥²₂；由于误差值很小时均值减标准差为负，结果以 100 次运行的中位数和四分位数报告。

在 m = 10n 时，除并列情形外，Leverage SHAP 在每个数据集上的平均误差都最低：例如 California（n = 8）上为 0.000249，优化版 Kernel SHAP 为 0.00301；Communities（n = 101）上为 0.0139 对 0.0231。作者报告，在整个研究中，相对于优化版 Kernel SHAP 实现，平均误差约降低 50%。在样本量扫描（m = 5n, 10n, 20n, …, 160n）中，除可以精确恢复的区域外，Leverage SHAP 稳定优于优化版 Kernel SHAP：在 Correlated 和 Independent（两者 n = 60）上，Leverage SHAP 误差的第三四分位数大致等于优化版 Kernel SHAP 的中位数；在 NHANES 和 Communities 上，至多约为其中位数的 1.5 倍；在小 n 数据集上则低于其中位数。由于两者都采用无放回抽样，当 m 接近 2^n 时，两种方法都达到基本机器精度。

n 相对 m 越大优势越明显

论文指出，当 n 相对 m 较大，且只能获得价值函数的含噪估计时，Leverage SHAP 相对 Kernel SHAP 的提升尤其显著。含噪情形在可解释 AI 中很常见：v(S) 是涉及随机基线的函数的期望，本身也要用有限样本估计。在附录 D 报告的噪声实验中，Leverage SHAP 在低噪声和中等噪声下达到或超过其他估计器。

适用范围在这里很重要。与 Kernel SHAP 一样，Leverage SHAP 假设可以黑盒访问单个价值函数 v；论文明确说，这一设定与那些在多个输入向量之间复用信息的工作不可比，因为每个输入向量都会诱导出自己的集合函数。实验使用树模型，以便精确 Shapley 值可计算；所报告的误差降低只针对这八个数据集和这些样本预算，并不是对任意模型类别或任意归因任务的断言。

该改的是抽样分布

论文的实践重点很窄也很具体：如果你已经在用 Kernel SHAP，而样本预算 m 相对 n 较小，那么值得改动的是抽样分布，而不是回归求解器。Leverage SHAP 保留同样的回归形式，并加入配对抽样和无放回抽样，因此所报告的收益来自评估哪些子集。它的保证是：以接近线性的样本代价，高概率得到接近最优的目标值；经验上的回报是，平均而言相对平方误差约为库中优化版实现的一半。

边界同样具体。当 m 接近 2^n 时，优化版 Kernel SHAP 和 Leverage SHAP 都达到基本机器精度，可提升的空间已经很小。而且，定理约束的是回归目标，推论 4.1 只有借助依赖问题的因子 γ 才能把它转成逐特征误差，因此逐特征承诺的强度取决于最优系数逼近目标的程度——作者通过实验表明，这一量增大时，所有基于回归的方法性能都会下降。

本文引用的文献