Shapley值：合作博弈中的公平收益分配.
在一个多方合作的场景中，例如商业联盟的利润分配、立法机构中不同党派的权力衡量或者机器学习模型中各个特征对最终预测的贡献；一个关键的问题是如何公平地分配合作所产生的总收益。1953年，诺贝尔经济学奖得主劳埃德·夏普利（Lloyd Shapley）提出的Shapley值，为此问题提供了一个具有坚实公理基础的解决方案。
1. 合作博弈与特征函数
合作博弈（Cooperative Game）又称正和博弈，是指一些参与者以形成联盟、互相合作的方式所进行的博弈。这样一来博弈活动就变成了不同集团之间的对抗。在合作博弈中，参与者未必会做出合作行为，会有一个来自外部的机构用不同方式(例如合约)惩罚非合作者。一个合作博弈由两部分构成：
- 参与者集合 (Set of Players): 一个有限的参与者集合 $F = {1, 2, \dots, n}$。在机器学习的语境下，这就是模型的输入特征集合。
- 特征函数 (Characteristic Function): 一个函数 $v: 2^F \to \mathbb{R}$，它将任意一个参与者子集（称为一个联盟 (Coalition)）$S \subseteq F$ 映射到一个实数值 $v(S)$。这个值代表了当只有联盟 $S$ 中的成员合作时，它们能共同产生的总收益。我们通常假设 $v(\emptyset) = 0$，即没有参与者时没有收益。
在机器学习模型的可解释性分析中，特征函数 $v(S)$ 被定义为：当只有特征子集 $S$ 中的特征被模型所知时，模型的预测输出。对于“未知”的特征，我们通常用其在背景数据集中的期望值或某个基线值来代替。
我们的目标是找到一个分配向量 $(\phi_1, \phi_2, \dots, \phi_n)$，其中 $\phi_i$ 是分配给参与者 $i$ 的收益，这个分配需要是“公平”的。
2. 公平性的公理化定义
分配需要是“公平”，则应该满足以下四个“公平性”公理的分配方案。
-
效率性 (Efficiency): 所有参与者分配到的收益之和，应等于全体参与者合作产生的总收益。 \(\sum_{i \in F} \phi_i = v(F) - v(\emptyset)\) 这意味着所有收益都被完全分配，没有凭空产生，也没有无故消失。
-
对称性 (Symmetry): 如果两个参与者 $i$ 和 $j$ 对于任何不包含它们的联盟 $S$ 都是可互换的，即 $v(S \cup {i}) = v(S \cup {j})$，那么他们应该获得相同的收益：$\phi_i = \phi_j$。 这意味着贡献相同的参与者，报酬也应相同。
-
虚拟参与者 (Dummy Player): 如果一个参与者 $i$ 的加入对任何联盟都没有任何贡献，即对于所有 $S \subseteq F \setminus {i}$，都有 $v(S \cup {i}) = v(S) + v({i})$（且通常$v({i})=v(\emptyset)$），那么它应该只获得其单独行动的收益：$\phi_i = v({i}) - v(\emptyset)$。 这意味着“滥竽充数”者不应从他人的合作中分得一杯羹。
-
可加性 (Additivity): 如果一个博弈可以被看作是两个独立博弈 $(v_1, v_2)$ 的和，即 $v(S) = v_1(S) + v_2(S)$ 对于所有 $S$，那么对于任何参与者 $i$，其在组合博弈中的收益应该等于其在两个独立博弈中收益的和：$\phi_i(v_1+v_2) = \phi_i(v_1) + \phi_i(v_2)$。 这保证了分配规则的一致性。
Shapley于1953年证明，对于任何合作博弈，存在且仅存在一种分配方案同时满足这四个公理。这个唯一的方案就是Shapley值。
3. Shapley值的数学推导
Shapley值的核心思想是边际贡献 (Marginal Contribution)。参与者 $i$ 的贡献，取决于它加入联盟的时间点。为了公平，我们应该考虑所有可能的加入顺序，并计算其边际贡献的期望值。
假设参与者以一个随机的排列 $\pi$ 顺序加入联盟。令 $S_{\pi, i}$ 为在该排列 $\pi$ 中，位于参与者 $i$ 之前的所有参与者的集合。那么，当 $i$ 加入时，其边际贡献为： \(\Delta v_i(\pi) = v(S_{\pi, i} \cup \{i\}) - v(S_{\pi, i})\)
Shapley值 $\phi_i$ 被定义为在所有可能的 $n!$ 个排列中，参与者 $i$ 的边际贡献的平均值：
\[\phi_i = \frac{1}{n!} \sum_{\pi \in \Pi_F} \Delta v_i(\pi)\]其中 $\Pi_F$ 是所有 $n!$ 个排列的集合。
这个公式虽然直观，但不便于计算。我们可以将其转化为一个等价的、更常用的形式。考虑一个固定的联盟 $S \subseteq F \setminus {i}$。一个排列中，特征 $i$ 恰好在联盟 $S$ 之后加入的概率是多少？这相当于 $S$ 中的 $|S|$ 个成员排在最前面，然后是 $i$，然后是剩下的 $n - |S| - 1$ 个成员。
- $S$ 中成员的排列方式有 $|S|!$ 种。
- 剩下的成员的排列方式有 $(n - |S| - 1)!$ 种。
- 总排列方式有 $n!$ 种。
因此，任何一个特定的前序联盟 $S$ 出现的概率为 $\frac{|S|!(n - |S| - 1)!}{n!}$。
将所有具有相同前序联盟 $S$ 的排列组合并，我们可以重写Shapley值的公式：
\[\phi_i(v) = \sum_{S\subseteq F\setminus\{i\}} \frac{|S|!(n-|S|-1)!}{n!} \left[v\left(S\cup\{i\}\right)-v(S)\right]\]标准Shapley值公式精确地表达了：一个参与者的Shapley值，是它在所有可能的联盟情境下，其边际贡献的加权平均值。
4. 应用实例
a) 简单的商业联盟示例
假设三个公司A, B, C考虑合作。它们的特征函数（年利润，单位：百万）如下：
- $v(\emptyset) = 0$
- $v({A}) = 10, v({B}) = 20, v({C}) = 30$
- $v({A, B}) = 50$
- $v({A, C}) = 60$
- $v({B, C}) = 70$
- $v({A, B, C}) = 100$
我们来计算公司A的Shapley值 $\phi_A$：
- A最先加入 (S=∅): 边际贡献 = $v({A}) - v(\emptyset) = 10$。权重 = $\frac{0!2!}{3!} = 1/3$。
- A在B之后加入 (S={B}): 边际贡献 = $v({A, B}) - v({B}) = 50 - 20 = 30$。权重 = $\frac{1!1!}{3!} = 1/6$。
- A在C之后加入 (S={C}): 边际贡献 = $v({A, C}) - v({C}) = 60 - 30 = 30$。权重 = $\frac{1!1!}{3!} = 1/6$。
- A最后加入 (S={B,C}): 边际贡献 = $v({A, B, C}) - v({B, C}) = 100 - 70 = 30$。权重 = $\frac{2!0!}{3!} = 1/3$。
同理可计算 $\phi_B=33.33$, $\phi_C=43.33$。 注意到效率性公理：$23.33 + 33.33 + 43.33 \approx 100 = v({A, B, C})$。
b) 在机器学习中的应用：SHAP (SHapley Additive exPlanations)
在机器学习模型可解释性中，Shapley值的应用框架被称为SHAP。
- 参与者 (Players): 模型的输入特征。
- 博弈 (Game): 对单个预测实例进行预测的过程。
- 收益 (Payoff): 模型的实际预测值与一个基线预测值（例如，所有训练样本的平均预测值）之差。
- 特征函数 $v(S)$: 使用特征子集 $S$ 中的特征值，并用基线值填充其他特征，然后进行预测得到的值。
SHAP值 $\phi_i$ 的解释: 特征 $i$ 的值，将模型的预测从基线值“推向”最终预测值的贡献量。
