🤖 machine learning

Shapley Value Approximation Based on k-Additive Games

本文介绍了 SVA $k_{\text{ADD}}$ ，这是一种新颖的近似方法，通过拟合 $k$ -加性代理博弈来估计沙普利值，以克服公平分配和机器学习可解释性中精确计算所固有的指数级计算复杂度。

原作者： Guilherme Dean Pelegrina, Patrick Kolpaczki, Eyke Hüllermeier

发布于 2026-05-13

📖 1 分钟阅读☕ 轻松阅读

原作者： Guilherme Dean Pelegrina, Patrick Kolpaczki, Eyke Hüllermeier

原始论文根据 CC0 1.0（http://creativecommons.org/publicdomain/zero/1.0/）发布到公有领域。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

以下是论文《基于 k-可加博弈的沙普利值近似》的通俗解释，辅以日常类比。

大局观：公平地分蛋糕

想象你和一群朋友在经营一个柠檬水摊。一天结束时，你们赚了钱。核心问题是：谁应得多少钱？

是挤柠檬的人做得最多吗？
是举牌子的人吸引了最多顾客吗？
是带糖的人让饮料更好喝了吗？

在机器学习（AI）的世界里，这是同样的问题。一个 AI 模型做出了预测（比如诊断疾病或判断邮件是否为垃圾邮件）。我们想知道：是哪一条具体数据（特征）导致了该预测？

“沙普利值”是由博弈论学家劳埃德·沙普利发明的一种数学公式。它是公平性的黄金标准。它通过考察所有可能的参与者组合，精确计算出每位“参与者”（特征）对最终结果的贡献程度。

问题：数学太难了

这里的难点在于：要完美计算沙普利值，你必须检查每一种可能的团队组合。

如果你有 10 个朋友，就有 1,024 种组合。
如果你有 20 个朋友，就有超过100 万种组合。
如果你有 50 个朋友，这个数字大得惊人，计算所需的时间将超过宇宙的年龄。

由于现代 AI 模型通常拥有成百上千个特征，计算精确的沙普利值是不可能的。这就像试图数清海滩上的每一粒沙子，以便公平地分配海滩的价值。我们需要一个捷径，但这个捷径必须足够准确，值得信赖。

解决方案：SVAkADD（“智能代理”方法）

这篇论文的作者提出了一种名为SVAkADD的新方法。与其试图数清每一粒沙子，他们构建了一个简化模型（一个“代理”），该模型模仿真实博弈，但更容易求解。

以下是他们如何做到的，使用了一个富有创意的类比：

1. “团队合作”假设（k-可加性）

作者假设，虽然每个人的贡献都很重要，但复杂的团队合作通常只在一定规模内存在。

1-可加性： 只有个人努力重要。（无论和谁一起工作，你都很出色）。
2-可加性： 成对组合重要。（你和你的好朋友合作无间，但三人小组可能会变得混乱）。
3-可加性： 小团体重要。（三人组配合良好，但十人委员会太混乱，无法产生独特的“魔力”效应）。

论文将此称为k-可加性。他们假设 4 人、5 人或 10 人同时互动的情况如此罕见或微不足道，以至于我们可以忽略它们。这将一个数学上不可能解决的问题变成了一个可管理的问题。

2. “品尝测试”（采样）

研究人员没有测试每一种可能的柠檬水配方（联盟），而是对配方进行了随机采样。

他们混合几种特定的配料组合。
他们品尝结果（计算数值）。
他们利用这些少量的品尝测试来“拟合”他们的简化模型。

3. “魔法公式”（优化）

一旦有了品尝测试，他们就解决一个特定的数学谜题（优化问题），以找到简化模型的参数。

精彩之处： 作者从数学上证明，如果为他们选择的品尝测试设定正确的“权重”，那么从这个简化模型中得到的答案，将完全等同于如果他们测试了每一种组合所能得到的完美沙普利值。
即使他们忽略了复杂的 10 人互动，数学也保证了最终得出的“公平份额”数值在他们测试的场景中是正确的。

为什么这比其他捷径更好

其他方法试图通过随机猜测并取平均值来猜测答案（就像多次掷骰子）。

论文的方法： 这就像基于少量测量数据构建蓝图。一旦蓝图建成，你就可以立即读出答案。
结果： 论文表明，他们的方法比随机猜测方法收敛（变得准确）得快得多。你需要更少的“品尝测试”（样本）来获得可靠的答案。

他们的发现（结果）

研究人员在真实世界的数据集上测试了这种方法（例如预测泰坦尼克号幸存者、葡萄酒质量或乳腺癌检测）。

速度与准确性： 他们发现，假设互动发生在3 人小组中（3-可加性）通常是“最佳点”。它既足够复杂以保证准确性，又足够简单以保持快速。
超越竞争对手： 在许多测试中，在相同的计算时间或数据样本量下，他们的方法（SVAkADD）比当前的顶级方法（如 KernelSHAP）更准确。
无需特殊规则： 这种方法适用于任何类型的博弈或 AI 模型。无论数据是关于医疗记录、股票价格还是体育统计数据，它都适用。

一句话总结

这篇论文介绍了一种新方法，通过构建一个忽略过于复杂群体互动的简化“团队合作模型”，在 AI 特征之间公平地分配功劳，使我们能够快速、准确地计算公平份额，而无需检查每一种可能性。

技术摘要：基于 k-加性博弈的 Shapley 值近似

问题陈述

Shapley 值是公平分配问题的标准解法，被广泛应用于可解释人工智能（XAI），用于量化特征或数据点对模型性能的个体贡献。然而，其精确计算需要评估 $n$ 个参与者的所有 $2^n$ 种可能的联盟，导致计算复杂度呈指数级增长。这使得在特征数量适中或评估复杂、资源密集型模型时，精确计算变得不可行。因此，近似方法是必要的，但现有方法往往难以在计算效率与所得重要性分数的准确性之间取得平衡。

方法论：SVAkADD

作者提出了SVAkADD（基于 k-加性的 Shapley 值近似），这是一种新颖的方法，通过将结构化的k-加性代理博弈拟合到联盟值的采样子集来近似 Shapley 值。

核心概念：k-加性

SVAkADD 不直接通过边际贡献的蒙特卡洛采样来估计 Shapley 值，而是假设底层博弈可以通过k-加性博弈进行近似。在此类博弈中，大小超过 $k$ 的联盟的交互指数（Shapley 交互）被假定为零。

表示：代理博弈的价值函数 $\nu_k$ 表示为所有大小 $|B| \leq k$ 的联盟 $B$ 的 Shapley 交互指数 $I(B)$ 的线性变换。
参数缩减：这一假设将定义博弈所需的参数数量从 $2^n$ 大幅减少到多项式数量（例如 $O(n^k)$ ），从而使优化变得可行。

优化框架

该方法将近似问题表述为约束加权最小二乘问题：

目标：最小化原始博弈中观测到的联盟值 $\nu(A)$ 与 k-加性代理 $\nu_k(A)$ 预测值之间的加权平方误差。
约束：优化过程强制执行效率公理，确保代理的 Shapley 值之和等于大联盟价值与空集价值之差（ $\nu(N) - \nu(\emptyset)$ ）。
加权：作者解析推导了最小二乘问题的特定权重 $w^*_A = \binom{n-2}{|A|-1}^{-1}$ 。他们证明，如果观测到所有联盟，求解此特定优化将产生精确的 Shapley 值，无论原始博弈是否真正具有 k-加性。

算法

SVAkADD 算法步骤如下：

采样：确定性评估空集 $\emptyset$ 和大联盟 $N$ 。随后，基于与推导出的权重 $w^*_A$ 成正比的概率分布，从幂集中采样 $T-2$ 个额外联盟（排除 $\emptyset$ 和 $N$ ）。
拟合：利用采样数据求解约束加权最小二乘问题，以估计 $|B| \leq k$ 的交互指数 $I(B)$ 。
提取：代理博弈的 Shapley 值可直接作为单元素交互指数（ $I(\{i\})$ ）获得，这些指数作为原始博弈的估计值。

主要贡献

新颖的近似方法：引入 SVAkADD，该方法将 k-加性代理博弈拟合到采样数据，为直接边际贡献采样提供了一种结构化的替代方案。
理论严谨性：解析证明对于 $k=1, 2, 3$ ，当观测到完整联盟集时，所提出的加权最小二乘优化可产生精确的 Shapley 值。这确立了 k-加性是近似的一种工具，而非对博弈结构的限制性假设。
模型与领域无关性：该方法不需要价值函数的特定结构属性，使其适用于任何合作博弈，包括机器学习中局部和全局的特征解释。
实证评估：在各种数据集和解释类型（全局、局部、无监督）上，与最先进基线（KernelSHAP、分层 SVARM、分层采样）进行了全面比较。

实验结果

作者在涵盖 9 到 14 个特征的数据集上评估了 SVAkADD，涉及全局、局部和无监督任务。

收敛性：该方法表现出具有竞争力的性能。虽然在极低采样预算下，其误差可能高于某些基线，但随着预算增加，它收敛到精确 Shapley 值的速度更快，特别是在 Adult 和 ImageNet 数据集上的局部归因任务中。
$k$ 的选择：实验突显了灵活性与收敛速度之间的权衡。
- 低 $k$ 值（1 或 2）通常收敛缓慢，因为缺乏足够的灵活性来建模复杂的特征交互。
- 较高的 $k$ 值（3 或 4）通常收敛显著更快，并在几个样本后优于低阶模型。
- 作者建议将 $k=3$ 作为首选默认值，在误差减少与所需参数数量之间提供良好平衡。
比较：SVAkADD 始终与 KernelSHAP 和分层 SVARM 竞争或优于它们，特别是在需要中等采样预算下高精度的场景中。

意义与主张

论文声称 SVAkADD 提供了一种具有理论依据且实际有效的 Shapley 值近似方法。通过利用 k-加性博弈的结构，该方法将估计问题转化为多项式时间优化，并在特定加权条件下保证精确恢复。

作者强调，他们的方法是模型无关且领域独立的，能够处理任何合作博弈形式。他们得出结论，虽然没有任何单一近似方法能在所有场景（取决于数据集、任务和预算）中占据主导地位，但 SVAkADD 提供了一种稳健的替代方案，利用 Shapley 交互的理论属性来实现高精度。论文还指出，当 $k \geq 2$ 时，该方法自然地提供了交互效应（冗余或互补）的估计，从而在个体特征重要性之外提供了额外的可解释性。