📊 statistics

Approximate Shapley value estimation using sampling without replacement and variance estimation via the new Symmetric bootstrap and the Doubled half bootstrap

本文提出了一种增强型 KernelSHAP 算法，该算法利用用于无放回抽样的 Wallenius 非中心超几何分布，并引入了用于方差估计的对称自助法（Symmetric bootstrap），在仿真研究中证明了其性能可与现有最先进方法持平或更优。

原作者： Fredrik Lohne Aanes

发布于 2026-01-15

📖 1 分钟阅读☕ 轻松阅读

CC BY 4.0

原作者： Fredrik Lohne Aanes

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

大局观：公平地分蛋糕

想象一下，你和一群朋友一起烤了一个巨大的蛋糕（这就是你的 AI 模型预测）。你想确切知道每位朋友对最终味道的贡献是多少。是烘焙师加了最多的面粉？还是装饰师加了最多的糖？

在数据科学领域，这被称为计算 Shapley 值。这是一种通过数学方法，将预测的“功劳”公平地分配给不同的特征（如年龄、收入或健康状况）的方法。

问题在于，计算每一个朋友的确切贡献是非常缓慢的。如果你有 20 个朋友，他们组合成蛋糕的方式就有超过一百万种。你不可能品尝每一种可能的组合。

旧方法：“有放回”抽奖

标准方法（称为 KernelSHAP）试图通过走捷径来解决这个问题。它就像一场抽奖：

它把所有可能的“朋友组合”（协同体）都放入一个大帽子。
它从中抽出一些小组进行品尝。
症结所在： 它是有放回地抽取的。这意味着如果你抽出了“烘焙师 + 装饰师”，你会把他们放回帽子里。你可能会再次抽到这对组合，也可能永远抽不到“烘焙师 + 厨师”。

正因如此，你可能会重复品尝同一个小组，而错过了其他小组。这就像试图通过从一副牌中抽牌并每次都放回原处来收集全套卡片；你可能会一直抽到重复的普通卡，而永远找不到稀有的卡。

新方法：“无放回”品尝

作者 Fredrik Lohne Aanes 提出了一种更聪明的采样这些小组的方法。

1. Wallenius 分布（带权重的帽子）
作者没有使用随机抽取，而是使用一种特殊的数学规则（Wallenius 非中心超几何分布）来决定要品尝多少个不同规模的小组。

类比： 想象帽子里有不同颜色的球。有些颜色比其他颜色“更重”（更重要）。作者计算出你的样本中应该包含多少种颜色的球，才能得到一个公平的图景，而不是仅仅寄希望于运气。

2. 无放回采样
一旦作者决定了要品尝多少个小组，他们就会从帽子中取出这些小组，且不再放回。

为什么这很重要： 如果你抽出了“烘焙师 + 装饰师”，你就知道不会再次抽到他们。这保证了你获得的是一组多样化的、唯一的组合。这就像发牌：一旦一张牌被发出去，它就不再在牌堆里了。这使得数据更加高效且“噪声”更小。

新的问题：我们有多大的信心？

当我们使用样本来估计某件事时，我们需要知道自己能多大程度上信任它。在统计学中，这被称为方差或标准差。这就像是在问：“如果我再次进行这个实验，我会得到相同的结果吗？”

作者认为，旧的检查这种信心的方法（使用标准的“自助法/bootstrap”方法）对于这种特定类型的采样来说是有缺陷的。

缺陷： 传统的自助法假设你是在从一个无限的池子中抽取，你可以反复选择同一个项目。但由于作者是从有限的可能性列表中进行无放回采样，旧的数学逻辑失效了。这就像试图用测量无尽大海的规则去测量一个小小的、有限的游泳池。

解决方案：两种新的“信心检查器”

为了修复信心检查，作者引入了两种新方法：

1. 倍半自助法（Doubled Half Bootstrap，即“老实可靠”的升级版）
这是一种针对该特定问题进行了改编的已知方法。它就像是将你的样本分成两半，然后通过对未被选中的那一半进行“倍增”，来创建一个新的“伪样本”以进行对比测试。

2. 对称自助法（Symmetric Bootstrap，全新的明星方法）
这是作者的新发明。

运作方式： 想象你有一份你所品尝的小组名单。为了创建一个新的测试样本，你为每个小组做出决定：“我们要包含这个小组 0 次、1 次，还是 2 次？”
对称性： 其中的奥妙在于，该方法确保了平均而言，你选择 0 次 的小组数量等于你选择 2 次 的小组数量。
类比： 这就像一个平衡的跷跷板。如果你从左边移走一个小组（0 次），你必须在右边添加一个不同小组的副本（2 次），以保持天平完美平衡。这确保了数学在“无放回”采样下的准确性。

结果：奏效了吗？

作者使用关于预期寿命（如 GDP、受教育程度和婴儿死亡率等因素）的真实数据测试了这些想法。

品尝（估计）： 新方法（无放回采样）的表现与现有的最佳工具（称为 shapr）一样出色。它提供了同样准确的答案，解释了谁对预测做出了贡献。
信心检查（方差）：
- 旧的“倍半自助法”表现尚可，但有时会在数学上遇到困难（数字并不总是能完美对齐）。
- 新的对称自助法表现得非常好。它运行快速、易于理解，并且能非常准确地估计我们对结果的信心。事实上，它的表现略优于现有 shapr 软件内置的信心检查器。

结论

这篇论文并不是声称它能治愈疾病或预测股市。它只是说明了：

我们可以通过使用特定的数学规则采样唯一的特征组合（无放回采样），从而更高效地计算 AI 解释。
我们可以通过使用一种新的、平衡的方法（对称自助法）来计算误差范围，从而使这些结果更值得信赖。

这种新方法在获取答案方面与目前的行业标准一样好，但它提供了一种更好、更快且在数学上更严谨的方式，来检查我们对答案的确定程度。

技术摘要：使用无放回抽样与新自助法方差估计量的近似 Shapley 值估算

1. 问题陈述

经典的 KernelSHAP 框架（Lundberg 和 Lee, 2017）旨在通过对子集进行采样而非评估所有 $2^p$ 个可能的子集来降低 Shapley 值估算的计算成本。然而，现有的实现通常采用有放回抽样的方式抽取联盟（coalitions）。这种方法引入了特定的统计挑战：

抽样效率低下： 有放回抽样会导致一个加权版本的“赠券收集者问题”（Coupon Collector's Problem），即随着样本量增加，获取唯一联盟的过程变得越来越困难，尤其是在处理低权重联盟时。
方差估计的局限性： 传统的自助法（bootstrap）方法假设样本是独立同分布（i.i.d.）的。当从有限总体（所有可能的联盟集合）中进行无放回抽样时，这一假设会被破坏。因此，标准的自助法技术可能会产生错误的 Shapley 值方差估计，因为它未能考虑到有限总体的约束条件——即如果评估了所有联盟，方差在理论上应趋于零。

本文通过提出一个利用无放回抽样并引入符合有限总体理论的新型自助法来准确估计近似 Shapley 值方差的框架，解决了上述问题。

2. 方法论

2.1 通过 Wallenius 分布实现无放回抽样

所提算法通过修改 KernelSHAP 程序，实现了对联盟的无放回抽样。该过程包含两个主要步骤：

分层（Stratification）： 将联盟按其包含的特征数量（规模）进行分组。
确定样本量： 算法不是随机地逐个抽取联盟，而是使用 Wallenius 非中心超几何分布计算每个组中预期抽取的联盟数量。该分布模拟了具有不同权重的项的偏向性无放回抽样。
- 算法使用该分布的期望值（取最近整数）来确定从每个层中抽取的联盟数量。
- 一旦确定计数，将在每个组内进行无放回抽样。
- 配对策略： 为了进一步降低方差，该方法采用了配对策略（Kroese et al., 2013）。如果抽中了一个联盟 $S$ ，则其补集 $S^c$ 也会被纳入计算，从而确保配对组中特征的总和保持不变。

2.2 通过自助法进行方差估计

本文评估了三种用于在新的抽样设计下估计 Shapley 值标准差的方法：

无效的直觉方法： 直接应用于加权最小二乘问题的标准 Horvitz-Thompson 方差估计量。作者证明该方法是无效的，因为它未能考虑到配对策略引入的特定依赖关系，以及在 KernelSHAP 背景下 $Z^T W Z$ 矩阵的结构。
倍半自助法（Doubled Half Bootstrap, Antal 和 Tillé, 2014）： 这是一种已知的针对有限总体的处理方法，其中单元是通过伯努利抽样选择的，且未被选中的单元被随机抽取两次。该方法被实现用于对比。
对称自助法（Symmetric Bootstrap，新贡献）： 一种专门为此背景开发的创新自助法。
- 机制： 在每次自助样本中，原始样本中的每个单元可以出现 0 次、1 次或 2 次。
- 对称性： 该方法确保出现 0 次的单元总数等于出现 2 次的单元总数。
- 概率： 单元 $k$ $k$ 出现 $S_k$ $S_{k}$ 次的概率定义为：
  - $Pr(S_k = 0) = Pr(S_k = 2) = \frac{1}{2}(1 - \frac{n}{N})$
  - $Pr(S_k = 1) = \frac{n}{N}$
- 特性： 这种构造确保了期望值 $E(S_k) = 1$ 且方差 $Var(S_k) = 1 - \frac{n}{N}$ ，满足了有限总体抽样中有效方差估计所需的必要条件（Horvitz-Thompson 一致性）。
- 处理非整数情况： 当“0 次”或“2 次”出现的预期次数为非整数时，引入一个伯努利随机变量在相邻整数值之间切换，以确保程序能够全自动运行。

2.3 计算实现

贡献函数 $v(S)$ 使用对抽样联盟的回归进行估计。实现过程利用稀疏矩阵和 Cholesky 分解（Matrix 包）来高效处理线性模型，能够在单核上数分钟内完成超过 65,000 个线性模型的均值估计（Aanes, 2025）。

3. 核心贡献

抽样框架： 将 Wallenius 非中心超几何分布集成到 KernelSHAP 框架中，以实现高效的无放回抽样，避免了有放回抽样中固有的“赠券收集者问题”导致的效率低下。
对称自助法： 引入了一种专门针对有限总体无放回抽样设计的、计算高效的自助法。它满足了进行无偏方差估计所需的矩条件（均值和方差）。
方差估计分析： 对方差估计器进行了严格比较，证明了标准的自助法在这一特定设计下是无效的，并且新的对称自助法优于或等同于现有的倍半自助法（Antal 和 Tillé, 2014）。

4. 结果

研究使用来自 Kaggle 的 “Life Expectancy” 数据集进行了两次模拟研究，将新方法与采用有放回抽样的最先进 shapr R 包（版本 1.0.7）进行了对比。

小型模拟研究（5 个特征，16 个联盟）：
- 新的抽样方法产生的 Shapley 值估计的标准差与 shapr 相当。
- Antal-Tillé 自助法表现不佳，频繁导致非满秩矩阵（ $Z^T W Z$ ）以及不准确的方差估计。
- 对称自助法的表现明显优于 Antal-Tillé，尽管它偶尔会产生比真实值（重采样所有联盟）略显“激进”（较小）的标准差。
大型模拟研究（16 个特征，402 个联盟）：
- 对称自助法与 Antal-Tillé 方法产生的标准差估计值难以区分。
- 这两种新的自助法方法在表现上都略优于 shapr 内置的自助法程序，后者往往会低估多个变量的标准差。
- 新的抽样算法（无放回）在 Shapley 值估计本身的准确性方面，表现与 shapr 方法（有放回）相似。

5. 意义与结论

论文得出结论，提出的结合了通过 Wallenius 分布实现的无放回抽样与新型对称自助法的算法，为现有的 KernelSHAP 实现提供了一个鲁棒的替代方案。

性能： 在点估计方面，该新方法表现得与改进后的 KernelSHAP 方法（shapr 包）“相似”。
方差估计： 对称自助法被强调为一种“计算非常快、易于理解”的方法，其表现良好，特别是在大型模拟研究中。它填补了文献中关于有限总体无放回随机抽样“通用”自助法方法的空白。
局限性： 作者谦虚地指出，在最小的研究中，对称自助法偶尔会对某些变量产生略微偏小（激进）的标准差，但它始终能捕捉到最大的标准差。
适用性： 该方法适用于通过线性或广义线性模型（即预测在转换尺度上呈线性）来估计贡献函数的场景，并利用了快速计算技术。

这项工作确立了有限总体理论可以成功应用于 Shapley 值估算，以提高抽样效率并提供有效的方差估计，克服了该领域传统 i.i.d. 自助法假设的理论局限性。