🤖 AI

Beyond Shapley: Efficient Computation of Asymmetric Shapley Values

本文通过利用因果图引入了计算非对称夏普利值（Asymmetric Shapley Values）的高效算法，证明了对于有根有向树，精确计算可以在多项式时间内完成，并针对任意因果有向无环图（DAGs）提出了一种统一的基于采样的近似方法，以克服标准夏普利值计算中的 #P-困难问题。

原作者： Ezequiel Companeetz, Santiago Cifuentes, Sergio Abriola

发布于 2026-06-25

📖 1 分钟阅读☕ 轻松阅读

CC BY 4.0

原作者： Ezequiel Companeetz, Santiago Cifuentes, Sergio Abriola

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

想象一下你拥有一支球员队伍（特征），他们正齐心协力赢得一场比赛（做出预测）。你想确切地知道每位球员为胜利贡献了多少功劳。在人工智能领域，这被称为可解释性（Explainability）。

最著名的方法叫做沙普利值（Shapley Values）。把它想象成一个公正的裁判，他会观察球员进入比赛的所有可能的先后顺序。如果球员 A 第一位、第二位或最后一位进入，裁判会计算由于该球员的加入，团队得分发生了多少变化。球员 A 的最终得分就是所有这些变化的平均值。

旧方法的问题
问题在于，计算每一个可能的顺序简直是一场噩梦。如果你有 20 名球员，就会有数十亿种顺序需要检查。对于复杂的 AI 模型，这种计算难度大到实际上几乎无法完成。

此外，旧方法将所有球员视为平等的。如果球员 B 是球员 A 的副本，他们会得到相同的分数。但在现实生活中，有时一个玩家会引起另一个玩家的行动。如果球员 A 导致球员 B 移动，那么球员 A 才是真正的幕后推手。旧方法忽略了这种“因果关系”。

新解决方案：非对称沙普利值 (Asymmetric Shapley Values, ASV)
这篇论文介绍了一个更聪明的裁判——非对称沙普利值 (ASV)。它不再查看所有可能的顺序，而是只查看符合因果图（Causal Map）（展示谁导致谁的图表）逻辑的顺序。

类比： 想象一条工厂装配线。你不能在造好车架之前就给车喷漆。因果图规定了“先造车架，后喷漆”。ASV 裁判会忽略任何试图在制造车架之前进行喷漆的顺序。他们只计算符合逻辑、符合因果关系的顺序。
益处： 这能提供关于谁真正导致了结果的更诚实的解释。而且，令人惊讶的是，在某些旧方法无法完成的情况下，这甚至让数学计算变得更容易了。

他们如何实现快速计算（魔法技巧）
即使有了因果图，检查所有有效的顺序仍然可能太慢。作者提出了两个聪明的技巧来加速这一过程：

“分组”技巧（等价类）：
想象你在计算有多少种排队方式。你意识到，对于计算目的而言，如果两个人都在主要负责人之后，那么他们交换位置并不重要。他们属于同一个“组”。
作者发现了一种方法，可以将数千个相似的顺序归入单个“桶”中（称为等价类）。与其检查 1,000,000 个顺序，他们可能只需要检查 500 个组。这把一个不可能完成的任务变成了一个快速的任务，尤其是当因果图看起来像一棵简单的树（如族谱）时。
“采样”技巧（通过样本进行猜测）：
如果地图太乱，无法整齐分组，他们就会使用采样法。他们不是检查每一个符合规则的顺序，而是随机抽取几百个符合规则的顺序并计算其平均值。

类比： 与其品尝大锅里每一粒米来判断是否咸，不如从不同位置舀出一勺。如果那一勺是咸的，你就知道整锅饭都是咸的。论文表明，这种“舀一勺”的方法既快速又能在很大程度上给出非常好的猜测。

他们测试了什么
作者在真实世界的数据结构（如用于预测癌症或儿童发育的网络）和人工生成的树状结构上测试了这些想法。

他们发现，对于树状结构，他们的“分组”方法速度极快，与旧方法相比，将工作量减少了数百万倍。
对于更复杂的结构，他们的“采样”方法既快速又足够精确，足以投入使用。

核心结论
这篇论文证明，通过尊重数据的“因果关系”规则，我们可以更准确、更快速地解释 AI 模型。他们展示了对于某些类型的数据，一种此前无法精确计算的方法现在可以被快速完成；而对于其他类型的数据，快速且准确的猜测也是轻而易举的。

技术摘要：超越 Shapley：高效计算非对称 Shapley 值

问题陈述

本文探讨了可解释人工智能（XAI）中特征归因所面临的计算与可解释性挑战。虽然 Shapley 值（及其机器学习实现 SHAP）提供了一种在理论上有据可依的方法，用于将模型的预测分配给输入特征，但它们存在两个主要局限性：

计算上的不可行性： 计算精确的 Shapley 值通常是 #P-难的，特别是对于表达能力强的模型（如神经网络）或底层数据分布较为复杂（如朴素贝叶斯分布）的情况。
可解释性缺陷： 标准 Shapley 值对所有特征进行对称处理。这无法捕捉因果关系，可能会将等同的重要性分配给原因及其确定性的结果，从而掩盖了真实的生成数据过程。

为了解决第二个问题，研究者提出了非对称 Shapley 值（ASV），它将计算限制在尊重给定因果图（即有向无环图或 DAG）的特征排列之中。然而，ASV 的计算复杂度尚未得到深入探讨。本文研究了在特定语境下，引入因果约束是否能使 ASV 的计算比标准 Shapley 值更具可行性。

方法论

作者提出了一套算法，通过利用因果图的结构和底层概率分布（建模为贝叶斯网络），来精确或近似地计算 ASV。

1. 理论可行性分析

作者针对朴素贝叶斯分布下的 ASV 进行了理论可行性分析。他们证明，在某些模型族且处于朴素贝叶斯分布下时，计算标准 Shapley 值是难以处理的；但如果用于 ASV 的因果图与朴素贝叶斯网络结构一致，则计算 ASV 是多项式时间内可解的。这表明，分布所带来的因果约束可以打破原本使问题变得困难的对称性。

2. 通过等价类进行精确计算

为了将可行性扩展到更通用的因果结构（特别是根向有向树），作者引入了一种减少排列搜索空间的方法：

等价类： 他们定义了因果图拓扑排序的一个等价关系。对于特征 $x$ ，如果两个排序中位于 $x$ 之前的特征集合是相同的，则这两个排序是等效的。
算法： 该算法不再遍历所有的拓扑排序（这可能是指数级的），而是计算等价类（ $\Lambda_x^C$ ）的集合及其大小。随后，通过将边际贡献乘以每个等价类的大小进行加权求和，从而计算出 ASV。
复杂度： 对于根向有向树，等价类的数量受 $h \cdot l + 1$ 限制（其中 $h$ 为深度， $l$ 为叶节点数）。作者提供了一个多项式时间算法（相对于等价类数量而言）来计算这些类别及其大小。

3. 通过采样进行近似计算

对于精确计算可能不可行的任意因果 DAG，作者提出了一种基于采样的近似方案。

采样拓扑排序： 该方法依赖于均匀随机采样拓扑排序。作者实现了两种方法：
1. 针对多树（polytrees）（即任意两点间最多只有一条路径的图）的递归计数算法，通过计数拓扑排序来正确加权源节点。
2. 针对一般 DAG 的基于随机游走算法（基于 Bubley & Dyer, 1999）。
误差界限： 他们形式化地指出，如果拓扑排序采样器与均匀分布的距离为 $\epsilon_{samp}$ ，且特征函数（期望模型值）的近似误差为 $\epsilon_{\nu}$ ，则最终的 ASV 估计值的加性误差为 $O(\epsilon_{samp} + \epsilon_{\nu})$ 。

主要结果

作者在现实世界的贝叶斯网络（Cancer, Child）和人工结构（平衡树、朴素贝叶斯、多路径结构）上评估了其方法。

减少搜索空间： 等价类方法显著降低了与枚举所有拓扑排序相比的计算负担。在 "Child" 网络中，拓扑排序的数量约为 $7.41 \times 10^{11}$ ，而等价类的数量平均仅约为 $2003$。
运行效率：
- 计算实际规模图的等价类耗时不到一秒。
- 精确算法的运行时间与等价类数量强相关，这使得预计算类计数可以作为计算成本的预测指标。
- 对于较大的图，枚举所有拓扑排序变得不可行，而等价类方法仍保持在可处理范围内。
采样性能：
- 作者为多树设计的自定义递归采样算法非常高效，由于采用了并行候选生成技术，其相对于样本量的缩放是非线性的。
- 使用 1,000 个样本进行采样，ASV 值的平均相对误差约为 8%。对于较大的 ASV 值，误差较低；对于极小的真实值，误差较高。

意义与主张

本文声称，当因果结构具有相关性时，ASV 是一个可行且可能更优的解释框架，因为它捕捉到了标准 SHAP 所忽略的依赖关系。其主要贡献在于证明了因果约束可以将一个难以处理的问题转化为易于处理的问题（例如，在朴素贝叶斯分布下的决策树）。

作者强调，尽管 ASV 提供了这些理论和实际上的优势，但其可扩展性高度依赖于因果图的拓扑结构：

对于根向有向树和多树，通过等价类进行精确计算是可行的。
对于稠密或大型 DAG，等价类的数量仍可能增长过大，从而需要使用基于采样的近似方法。

研究结论认为，只要因果图已知且图结构允许高效的枚举或采样，ASV 就是一个充满前景的 XAI 方向。未来的工作建议将精确算法推广到更广泛的图类（如一般多树），并优化采样机制。