📊 statistics

An Odd Estimator for Shapley Values

本文介绍了 OddSHAP，这是一种新型的 Shapley 值估计器，它通过理论证明配对采样能够滤除集合函数中无关的偶成分，从而能够在仅有的奇子空间上进行高效的多项式回归，进而实现了最先进的准确度。

原作者： Fabian Fumagalli, Landon Butler, Justin Singh Kang, Kannan Ramchandran, R. Teal Witter

发布于 2026-06-01

📖 1 分钟阅读☕ 轻松阅读

原作者： Fabian Fumagalli, Landon Butler, Justin Singh Kang, Kannan Ramchandran, R. Teal Witter

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

想象一下你拥有一台复杂的机器，比如一辆自动驾驶汽车或一个医疗诊断工具，它做出了一个决策。你想知道：输入的哪些特定部分（特征）导致了这个决策？

在机器学习领域，**Shapley 值（Shapley value）**是用于回答这一问题的金标准数学工具。它能公平地将决策的“功劳”分配给所有输入特征。然而，计算精确的 Shapley 值就像是试图通过数清沙滩上每一粒沙子的数量来确定每粒沙子对总重量的贡献一样。这在数学上是可能的，但对于复杂问题来说，由于需要检查的组合数量过多，这在计算上是不可能的。

本论文介绍了一种更聪明、更高效的估计这些值的方法，称为 OddSHAP。以下是通过简单的类比对它的工作原理进行的解释。

1. 问题所在：“组合爆炸”陷阱

为了弄清楚一个特征有多重要，你通常需要测试机器在各种特征开启和关闭的不同组合下的表现。

旧方法： 想象你在试图通过品尝所有可能的食材组合来猜出一种汤的味道。如果你有 100 种食材，组合的数量将是天文数字。你不可能把它们全部尝一遍。
当前最佳方法： 科学家们使用了一种叫做“配对采样（paired sampling）”的技巧。他们不是品尝一碗随机的汤，而是同时品尝一碗汤及其完全相反的版本（原本缺失的都加上，原本添加的都去掉）。这有助于抵消一些噪声，但直到现在，才有人知道这种方法为什么如此有效。

2. 重大发现：“奇数（Odd）”的秘密

本文作者发现了一个基本的数学规则：Shapley 值只关心故事中“奇数（odd）”的部分。

将一个值函数（机器的逻辑）想象成一首歌。这首歌有两种类型的音符：

偶数音符（Even Notes）： 这些是对称的。如果你把这首歌倒过来播放，听起来还是一样的。在数学术语中，这些是当计算 Shapley 值时会相互抵消的模式。对于这项特定的计算来说，它们是“无关的噪声”。
奇数音符（Odd Notes）： 这些是不对称的。如果翻转它们，它们会发生变化。这些才是对 Shapley 值真正起作用的音符。

类比： 想象你正在尝试测量站在秤上的一个特定人的重量，但秤同时也正在称量围绕着他们的巨大且对称的雾团。雾很重，但它是完美平衡的（偶数），所以它不会让秤向左或向右倾斜更多。OddSHAP 的洞察力在于，意识到你可以完全忽略这些雾，只关注那个人。

3. 解决方案：OddSHAP

作者构建了一个名为 OddSHAP 的新估计器，它利用这种“奇数 vs 偶数”的洞察力来节省时间并提高准确性。

工作原理： OddSHAP 不再试图学习整首歌（整个机器逻辑），而是使用一种巧妙的采样技巧（配对采样）来自动过滤掉“偶数”音符。然后，它使用仅由**“奇数”音符**构建的模型。
代理技巧（The Proxy Trick）： 为了在不检查每一个音符的情况下找到最重要的“奇数”音符，它使用了一个“代理”模型（一个快速、简单的决策树）来充当侦察兵。侦察兵能快速识别出少数高影响力的交互作用（即最响亮的“奇数”音符），并忽略其余部分。
结果： 它解决了一个规模小得多的数学问题。这就像是通过只观察那些具有独特形状的拼图碎片来解决拼图，而忽略掉成千上万个对解题毫无帮助的相同正方形碎片。

4. 为什么它更好

论文将这种方法与许多其他顶尖方法在各种数据集（如预测房价、诊断癌症或分析文本）上进行了对比测试。

准确性： 当给予足够的数据（较大的“预算”）时，OddSHAP 是目前最准确的方法。它击败了之前的最佳方法，尤其是在处理复杂的深度学习模型（如用于图像识别的模型）时。
效率： 它避免了“组合爆炸”。当其他方法因为试图计算太多组合而陷入泥潭时，OddSHAP 直接切入了相关的部分。
解释谜团： 论文还最终解释了为什么旧有的“配对采样”技巧如此有效。事实证明，配对采样在无意中恰好做了 OddSHAP 有意为之的事情：它在数学上抵消了“偶数”噪声，只留下了有用的“奇数”信号。

总结

OddSHAP 是一种用于解释 AI 决策的新工具。它意识到，要理解为什么做出某个决策，你并不需要分析所有可能发生的情况。你只需要分析那些真正驱动结果的、特定的、不对称的模式。通过忽略对称的“噪声”，它比以往任何时候都更快、更准确地计算出答案。

注：局限性： 论文指出，虽然这种方法对于复杂的深度学习模型非常出色，但在处理噪声天然极低的简单树模型（如标准决策树）时，其效率略低于一些较旧的、规则化的方法。然而，对于 AI 最神秘的广泛且复杂的问题，OddSHAP 是新的最先进技术（state-of-the-art）。

技术摘要：一种奇数阶 Shapley 值估计器

问题陈述

Shapley 值是机器学习中归因的标准框架，用于特征重要性、数据估值和因果推理。然而，由于评估所需的联盟数量呈指数级增长（ $2^d$ ），精确计算其值通常是难以实现的。虽然存在近似方法，但最有效的估计器通常依赖于“配对采样”（即同时采样一个联盟 $S$ 及其补集 $S^c$ ），这是一种经验性的启发式方法，尽管它在提高准确性方面表现出色，但缺乏关于其为何有效（特别是在高阶交互方面）的严谨理论证明。此外，现有的高阶多项式回归方法（如 PolySHAP）面临着可扩展性瓶颈，其计算成本随多项式基底的大小呈二次方增长，限制了它们在高维设置中的应用。

方法论

作者提出了 OddSHAP，一种利用 Shapley 值的一个基本结构属性的创新估计器：它仅取决于值函数 $f$ 的奇数分量（odd component）。

理论基础

奇偶分解（Odd-Even Decomposition）： 任何集合函数 $f$ 都可以唯一地分解为一个奇分量（ $f_{odd}$ ）和一个偶分量（ $f_{even}$ ），其中 $f_{odd}(S) = -f_{odd}(S^c)$ 且 $f_{even}(S) = f_{even}(S^c)$ 。
Shapley 值属性： 作者证明了对于所有玩家 $i$ ， $\phi_i(f) = \phi_i(f_{odd})$ 。偶分量对 Shapley 值的贡献为零。
配对采样的机制： 本文首次为配对采样提供了通用的理论依据。通过使用对称权重的对 $(S, S^c)$ 进行采样，加权最小二乘回归问题会正交化（解耦）为独立的优化问题，分别处理奇分量和偶分量。由于偶分量是无关的，配对采样有效地隔离了计算 Shapley 值所需的信号。这解决了一个猜想，即使用 $k$ 阶拟合（对于奇数 $k$ ）的配对采样等价于 $(k+1)$ 阶拟合。

算法设计：OddSHAP

为了利用这一洞察并避免组合爆炸带来的高阶项拟合问题，OddSHAP 在 傅里叶基（Fourier basis） 而非一致性基（unanimity basis）下运行。

傅里叶基优势： 在傅里叶基中，基函数 $\chi_T$ 是奇函数当且仅当其基数 $|T|$ 为奇数。这使得奇项和偶项可以实现清晰的分离，而一致性基则无法做到这一点。
两阶段过程：
1. 交互筛选（Interaction Screening）： 对采样的联盟拟合一个梯度提升树（GBT）代理模型。通过类似 ProxySPEX 的方法，算法提取出一组稀疏的高影响奇数阶傅里叶系数。这避免了拟合所有可能交互的需求。
2. 奇数回归（Odd Regression）： 严格在选定的奇数阶傅里叶项（外加线性项）上进行加权最小二乘回归，并约束其匹配空集和全集的函数值。
效率： 通过将回归限制在奇数子空间内，并使用代理模型来选择项，该方法实现了相对于采样预算的多项式时间复杂度，绕过了固定阶数多项式方法中 $O(d^k)$ 的缩放问题。

核心贡献

统一了配对采样的理论： 论文证明了配对采样隐式地将回归目标解耦为奇、偶分量，为配对采样的经验成功提供了严谨的理论解释，并将之前的发现从低阶交互推广到了通用情况。
OddSHAP 估计器： 一种一致的估计器，仅在稀疏选择的奇数阶傅里叶基函数上执行多项式回归。它过滤掉了无关的偶分量，并通过代理模型识别高影响的交互。
达到最先进水平的性能： 大量的基准测试表明，在较大的采样预算下（特别是在高维设置中），OddSHAP 的估计精度优于现有方法（包括 RegressionMSR、LeverageSHAP 和 PolySHAP）。

实验结果

作者在涵盖深度学习（图像和文本）及表格领域的 8 个值函数上评估了 OddSHAP，维度 $d$ 从 14（DistilBERT）到 101（Crime 数据集）不等。

准确性： Odd-SHAP 一致地实现了最低的均方误差（MSE）和最佳的平均排名，特别是在采样预算 $m$ 足以检测出交互作用时（ $m > \eta \cdot d$ ）。
与 FFD 的比较： 在高阶交互显著的深度学习架构（ViT、DistilBERT）上，OddSHAP 的表现优于固定预算分数阶析因设计（FFD-RD）。相反，在交互作用迅速衰减的树模型表格数据集上，FFD-RD 的表现略好，这验证了领域特定的权衡。
消融研究：
- 配对 vs. 非配对： 配对采样始终优于非配对采样。
- 奇数 vs. 所有交互： 在配对采样下，包含偶数交互并不会带来收益，反而会因为消耗了数学上相互抵消的项而降低性能。
- 稀疏性： 引入适量的奇数交互（由回归变量因子 $\eta$ 控制）能显著降低误差，优于线性基准；但如果交互项过多，则会出现过拟合。

意义与主张

论文声称 OddSHAP 提供了一个灵活预算框架，能够稳健地适应各种不同的交互结构。其主要意义在于：

解决开放猜想： 它提供了解释为什么配对采样有效的根本理论机制，从经验观察上升到了结构性证明。
可扩展性： 它通过将模型限制在奇数子空间内，保留了高阶近似的表达能力，同时避免了极其昂贵的组合成本。
鲁棒性： 与依赖严格截断假设的方法（如 FFD）不同，OddSHAP 在高阶交互不可忽略的复杂深度学习领域依然有效，同时在稀疏的表格领域保持竞争力。

作者指出了局限性，即由于在选定交互上的二次方回归成本，算法的运行时间随预算呈三次方增长，且配对采样减少了独立样本的数量，可能会增加方差。然而，他们得出结论认为，该方法代表了模型无关设置下 Shapley 值估计的最先进方法。