📊 statistics

ShaplEIG: Bayesian Experimental Design for Shapley Value Estimation

本文介绍了 ShaplEIG，这是一种利用高斯过程代理模型和闭式期望信息增益来自适应选择联盟的贝叶斯实验设计方法，从而在成本高昂、预算有限的场景下显著提高了 Shapley 值估计的样本效率。

原作者： David Rundel, Fabian Fumagalli, Maximilian Muschalik, Bernd Bischl, Matthias Feurer

发布于 2026-06-02

📖 1 分钟阅读☕ 轻松阅读

原作者： David Rundel, Fabian Fumagalli, Maximilian Muschalik, Bernd Bischl, Matthias Feurer

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

核心问题：“选择太多”的困境

想象一下，你正试图弄清楚在一次团队胜利中，每位球员分别做出了多少贡献。在机器学习的世界里，这些“球员”就是特征（例如患者的年龄或房屋的面积）或数据点。用来衡量这种贡献度的数学工具被称为Shapley Value（夏普里值）。

为了计算出精确的 Shapley Value，你必须测试所有可能的球员组合。

如果你有 10 名球员，就会有 1,024 种组合。
如果你有 20 名球员，组合数量将超过 100 万种。
如果你有 50 名球员，这个数字将巨大到超过宇宙中的原子总数。

此外，测试每种组合的成本也非常高昂。这可能需要从头开始重新训练一个复杂的 AI 模型，这会耗费数小时甚至花费大量资金。这就像是为了寻找完美的食谱，而去尝试世界上每一种可能的食材组合，你还没完成，时间与金钱就已经耗尽了。

现有方案：凭感觉猜与试

由于我们无法测试所有情况，现有的方法通常采用随机挑选组合进行测试，或者遵循固定的模式（例如“总是先测试较小的群体”）。

类比： 想象你是一名正在通过审问嫌疑人来破案的侦探。现有的方法就像是按字母顺序审问嫌疑人，或者从帽子里随机抓取名字。你可能会在采访错误的人时，错过了那个掌握着关键线索、却尚未被你问话的人所持有的真相。

新方案：ShaplEIG（聪明的侦探）

作者提出了一种名为 ShaplEIG 的新方法。它不再盲目猜测，而是基于**贝叶斯实验设计（Bayesian Experimental Design）**采用了一种“聪明侦探”的方法。

以下是它的工作步骤：

1. “代理”地图（水晶球）

由于测试每种组合的成本太高，ShaplEIG 构建了一个关于这场“游戏”的代理模型（surrogate model）（一种简化、快速的近似模型）。

类比： 想象你正在绘制一片巨大的、雾气缭绕的山脉。你不需要徒步走遍每一寸土地，而是根据几次初步的徒步探索，建立一个微小的、快速生成的地形 3D 模型。这个模型并不完美，但它能让你对山峰和山谷的位置有一个大致的判断。

2. “预期信息增益”（指南针）

这是本文的核心魔力所在。该方法会询问：“为了获得关于最终答案最多的信息，我下一步应该测试哪一个特定的组合？”

类比： 普通的侦探可能会问：“谁看起来很可疑？”（不确定性采样/Uncertainty Sampling）。而 ShaplEIG 会问：“如果我采访这个人，会对其他所有人关于整个谜团的理解产生多大的澄清作用？”
它计算的是预期信息增益（Expected Information Gain, EIG）。它观察自己构建的 3D 地图并表示：“测试这个特定的组合，将最有效地降低我们对所有球员最终得分的不确定性。”

3. “闭式解”捷径（超能力）

通常情况下，计算“我们能获得多少信息”是非常困难且缓慢的（就像是在拼图碎片不断移动时试图解开谜题）。

论文的突破点： 作者发现，由于 Shapley Value 是以特定的线性方式计算的，因此他们可以编写一个数学捷径（“闭式表达式”），从而瞬间计算出这种信息增益。
类比： 通常，为了知道一个新线索有多大帮助，你需要重新模拟整个调查过程。ShaplEIG 发现了一个公式，可以瞬间给出答案，就像一个 GPS 系统，无需重新绘制整个世界就能瞬间重新规划最佳路线。

4. “多项式”加速（电梯）

即便有了这个捷径，针对数百万种组合进行计算仍然会太慢。

论文的突破点： 他们使用了一种涉及基本对称多项式（Elementary Symmetric Polynomials）（一种数学模式）的巧妙数学技巧，将一个呈指数级增长（1, 10, 100, 1000...）的计算过程转变为呈多项式级增长（1, 10, 100, 1000... 但增长速度慢得多）。
类比： 与其一步一个脚印地爬山（指数级），他们建造了一部电梯（多项式级），即使面对极高的山峰也能快速到达顶端。

结果：更好的答案，更少的工作

作者在各种困难任务上测试了 ShaplEIG，例如：

确定哪些特征对医疗诊断模型最为重要。
为数据集中的特定数据点进行估值。
理解哪些设置（超参数）能让 AI 模型表现最佳。

结果：
在几乎所有的测试中，ShaplEIG 都比现有的最佳方法更快、且用更少的昂贵测试找到了正确答案。

类比： 如果其他方法需要采访 400 名嫌疑人才能以 90% 的准确率破案，ShaplEIG 通常只需 200 次采访就能完成，且准确度更高。

总结

ShaplEIG 是一种智能的方法，用于估算 AI 模型中每个部分对其决策的贡献程度。它不再盲目地测试随机组合，而是利用一个数学“指南针”来挑选下一个最具信息量的测试。通过使用巧妙的数学捷径，它能够快速处理任务，在面对昂贵的 AI 模型时节省了大量的时间和金钱。

技术摘要：ShaplEIG

问题陈述

Shapley 值（SVs）是可解释机器学习中一种具有原则性的归因度量，然而其精确计算通常是难以实现的。计算负担源于两个因素：一是随着玩家数量 $p$ 的增加，联盟数量呈指数级增长（ $2^p$ ）；二是评估每个联盟的价值函数 $\nu$ 的成本极高。在诸如基于重训练的特征重要性、数据估值和超参数重要性等应用中，价值函数评估可能涉及完整的模型重训练或昂贵的推理，这严重限制了评估预算。

现有的近似方法，包括蒙特卡洛采样和基于代理的方法（例如 Kernel SHAP、回归 MSR），通常依赖于固定的、非自适应的采样分布。这引发了一个问题：通过根据先前的观测结果自适应地选择用于评估的联盟，是否可以提高近似精度，特别是在低预算机制下？虽然贝叶斯实验设计（BED）提供了一个使用期望信息增益（EIG）进行序列设计的框架，但由于缺乏闭式 EIG 表达式以及在高维离散空间中估计 EIG 的计算困难，其在 SV 估计中的应用一直受到限制。

方法论

作者提出了 ShaplEIG，一种贝叶斯实验设计方法，通过自适应选择联盟来最大化关于 Shapley 值的信息增益。

1. 使用汉明核的高斯过程代理

ShaplEIG 使用高斯过程（GP）代理来对价值函数 $\nu$ 进行建模。为了处理联盟的二进制输入空间（表示为指示向量 $z \in \{0, 1\}^p$ ），该方法采用了汉明距离核（Hamming distance kernel）。该核通过加权汉明距离量化联盟之间的相似性，并带有可学习的长度尺度超参数 $\xi$ 。给定观测数据集 $D_t$ ，GP 提供了整个 $2^p$ 个联盟的价值函数的后验分布。

2. 通过线性关系实现一致的 SV 估计

一个关键的理论见解是 Shapley 值相对于价值函数的线性关系。SVs $\phi$ 可以表示为价值函数向量 $\nu$ 的线性变换： $\phi = A\nu$ ，其中 $A$ 是由 Shapлоley 公式导出的已知矩阵。因此，在 GP 代理下，SVs 的后验分布也是高斯的，并且具有闭式解：
$\phi | D_t \sim \mathcal{N}_p(A\mu_{\nu|D_t}, A\Sigma_{\nu|D_t}A^\top)$
作者从后验均值中提取 SV 估计值，即 $\hat{\phi} = A\mu_{\nu|D_t}$ 。至关重要的是，对于无噪声（或准无噪声）GP，该估计量是一致的（consistent）：如果评估了所有 $2^p$ 个联盟，估计值将精确收敛于真实的 Shapley 值。

3. 闭式期望信息增益 (EIG)

核心贡献在于推导了关于候选联盟 $z^{(i)}$ 对 SVs 的 EIG 的闭式表达式。通过将序列选择建模为一个以 SVs 为线性终极目标的贝叶斯线性逆问题，证明了 EIG 仅取决于 SVs 的后验协方差：
$\text{EIG}^{(t)}_{\phi}(z^{(i)}) \propto -\log \det \left( A \Sigma_{\nu|\nu'(z^{(i)}), D_t} A^\top \right) + C$
这避免了 BED 中通常需要的嵌套期望，因为 EIG 仅取决于实验设计（所选的联盟）而非特定的结果 $y(x)$ 。

4. 通过基本对称多项式的有效计算

直接计算 EIG 涉及对大小为 $2^p \times 2^p$ 的矩阵进行操作，会导致指数级的复杂度。作者提出了一种高效的计算方案，通过利用汉明核的乘法结构，将复杂度降低至多项式时间（ $O(p^4 + t^3)$ ）：

EIG 所需的项（具体为 $A\Sigma_{\nu|D_t}e_i$ 和 $A\Sigma_{\nu|D_t}A^\top$ ）被改写为核评估的加权和。
这些和被识别为缩放的基本对称多项式（ESPs）。
通过使用动态规划和前缀/后缀表高效计算这些多项式，该方法避免了显式的联盟枚举。

5. 算法

算法按贪婪方式进行：

使用小型设计进行初始化（例如，杠杆得分采样）。
拟合 GP 代理并优化超参数。
使用高效的多项式方案计算所有候选联盟的 EIG。
选择 EIG 最大的联盟，评估价值函数，并更新数据集。
重复上述步骤直到预算耗尽。

核心贡献

ShaplEIG 框架： 引入了一种新型的、基于 BED 的 SV 估计方法，该方法使用带有汉明核的 GP 代理，并根据 EIG 自适应选择联盟。
闭式 EIG： 证明了在 GP 代理下，针对 Shapley 值的 EIG 存在闭式表达式，这利用了 SVs 在价值函数中的线性关系。
多项式复杂度： 提出了一种高效的 EIG 计算方案，通过基本对称多项式将复杂度从指数级降低到关于玩家数量（ $p$ ）的多项式级。
一致性估计： 提供了一个一致的 SV 估计器，当所有联盟都被评估时，它会收敛到精确值，这与某些需要额外调整步骤的基于树的代理方法形成对比。

实验结果

作者在涉及中小规模游戏（ $8 \le p \le 101$ ）的多种高成本应用场景中评估了 ShaplEIG：

任务： 全局特征重要性 (TabPFN)、数据估值 (Random Forest, Gradient Boosting)、超参数重要性 (XGBoost, LCBench) 以及局部解释 (ResNet, ViT, Random Forest)。
基准测试： 与 Kernel SHAP、Leverage SHAP、置换采样以及最先进的回归 MSR（结合 XGBoost）进行对比。
消融实验： 与使用相同 GP 代理但采用不同选择策略（随机、不确定性采样、杠杆得分采样）的变体进行对比。

发现：

样本效率： 在大多数任务中，ShaplEIG 在低预算机制下始终能实现最佳的整体准确度（最低的均方误差）。它通常在性能上严格优于竞争对手，特别是在玩家交互非均匀的非对称博弈中。
消融见解： 其强劲的表现主要归功于基于 EIG 的选择策略，而非仅仅是使用了 GP 代理。不确定性采样（US）的表现往往比随机采样更差，这表明最大化边际方差并不等同于最大化关于线性变换后的 SVs 的信息。
可扩展性： 对于较大的游戏（ $p > 16$ ），即使采用定时而非每轮迭代进行超参数重拟合，该方法仍然有效。
计算成本： 虽然 EIG 计算非常高效（秒级），但对于较大的 $p$ ，超参数拟合可能会成为瓶颈（对于 $p \approx 100$ ，每轮迭代可能需要 25 分钟）。作者指出，ShaplEIG 最适合那些价值函数评估确实非常昂贵的场景，从而证明其开销是合理的。

重要性与声明

本文声称 ShaplEIG 提供了一个原则性的框架，用于提高成本高昂的博弈中 SV 估计的样本效率。通过推导闭式 EIG 和高效的多项式时间计算方案，作者克服了将贝叶斯实验设计应用于该领域的主要障碍。

作者谦虚地指出，虽然该方法会产生重复 GP 优化的计算开销，但在评估预算有限时，它能显著提升估计精度。他们承认，对于规模极大或价值函数成本较低的场景，这种开销可能会变得难以承受，并建议未来的工作应侧重于进一步的计算改进，以扩大该方法的适用范围。该工作并不声称解决了所有场景下的 SV 估计问题，而是专门针对价值函数极其昂贵、自适应选择至关重要的这一特定领域。