按平均边际贡献分收益,为什么仍可能不稳定?
读后可检查:手算加入顺序的贡献,区分 Shapley 公理、核心与 SHAP 的建模选择。
📑 本页目录(点开跳转)
23 · Shapley 值
⏱ 36 分钟(原预计,仅供参考,可分次读) | 先算一次分配,再看公理和应用
🎯 一句话
Shapley 值:让所有加入顺序等可能,每个人分到自己平均带来的增量。
它回答“按这种贡献标准,应该怎么分”。上一章的核心回答“有没有联盟能另组队改善分配”;nucleolus 则按顺序尽量降低最严重的联盟不满。这些标准不同,答案也可能不同。
第一次读,可以先看三人手算,再看手套反例。已经在用模型解释工具的读者,可以从 SHAP 应用进入,再回来补公式。
🎲 一、先量一次增量,再谈怎样平均
沿用上一章的设定:成员集合是 $N$;$S$ 是其中一个联盟;$v(S)$ 是该联盟自己能获得、可在成员间转移分配的总价值。本章取 $v(\varnothing)=0$。
假设 $i$ 还不在 $S$ 里。让他加入,比较两笔总价值:
$$\Delta_i(S)=v(S\cup\{i\})-v(S)$$
这就是 $i$ 对 $S$ 的边际贡献。它不是 $i$ 单独能赚多少,而是“已有这些人时,多他一个增加多少”。
例如,糖加入“已经有面粉的团队”和加入“空团队”,增量可能不同。手套例子也一样:一只左手套能否产生价值,要看前面有没有右手套。
所以要说明怎么平均。 Shapley 的选择是:把所有人的加入顺序等权处理。这个假想排队是计算规则,不是在断言现实中的到场顺序真的随机。
📐 二、两个公式,算的是同一个平均
排列写法:一次队列贡献一组数
$n$ 是人数,$\Pi_N$ 是全部 $n!$ 个排列。$S_\pi(i)$ 表示在排列 $\pi$ 中排在 $i$ 前面的人。
先记这一排列中的增量:
$$\Delta_\pi(i)=\Delta_i(S_\pi(i))$$
再对所有排列取平均:
$$\phi_i=\frac{1}{n!}\sum_{\pi\in\Pi_N}\Delta_\pi(i)$$
联盟写法:合并“前面恰好是同一批人”的队列
不含 $i$ 的联盟 $S$ 若有 $s$ 人,它出现在 $i$ 前面的概率是:
$$\omega_s=\frac{s!(n-s-1)!}{n!}$$
于是同一个 Shapley 值也可以写成:
$$\phi_i=\sum_{S\subseteq N\setminus\{i\}}\omega_{|S|}\Delta_i(S)$$
两个阶乘分别数:前面 $S$ 内部怎么排,以及 $i$ 后面的人怎么排。它们不是多加的公平系数,而是从等概率排列数出来的权重。
三个人时,对固定的 $i$:
| 前面的联盟 | 每一个这样的联盟的权重 |
|---|---|
| 空联盟 | $1/3$ |
| 某一个人 | $1/6$ |
| 另外两个人都在 | $1/3$ |
中间有两个单人联盟,因此总权重是 $1/3+1/6+1/6+1/3=1$。不是把四个联盟各给 $1/4$。
手算三人例子时,排列写法更容易核对;程序可用联盟求和,也可随机采样排列估计,不必限定为某一种写法。
🔨 三、三人煎饼店:完整手算
这是为演示计算而设定的教学数据,不是市场定价或真实经营记录。
Alice(A)带面粉,Bob(B)带糖,Charles(C)带草莓。先列清所有联盟的价值,单位统一为美元:
| 联盟 | 做什么 | 价值 |
|---|---|---|
| ∅ | 无人参加 | 0 |
| A | 只有面粉 | 2 |
| B | 只有糖 | 1 |
| C | 只有草莓 | 3 |
| AB | 普通煎饼 | 5 |
| AC | 草莓煎饼 | 7 |
| BC | 糖与草莓 | 4 |
| ABC | 三人合作的产品 | 16 |
先跟着算第一行
顺序是 A、B、C:
- A 从空联盟开始,增加 $2-0=2$。
- B 加进来,总价值从 2 变成 5,增加 $5-2=3$。
- C 最后加入,总价值从 5 变成 16,增加 $16-5=11$。
列名始终按 A、B、C 放。 下一行即使 C 比 B 先到,也不要把“到场位置”和“这个人的列”混在一起。
六个排列逐项保留
| 排列 | A 的增量 | B 的增量 | C 的增量 |
|---|---|---|---|
| A,B,C | $2-0=2$ | $5-2=3$ | $16-5=11$ |
| A,C,B | $2-0=2$ | $16-7=9$ | $7-2=5$ |
| B,A,C | $5-1=4$ | $1-0=1$ | $16-5=11$ |
| B,C,A | $16-4=12$ | $1-0=1$ | $4-1=3$ |
| C,A,B | $7-3=4$ | $16-7=9$ | $3-0=3$ |
| C,B,A | $16-4=12$ | $4-3=1$ | $3-0=3$ |
现在按列求平均,一次只算一个人:
$$\phi_A=\frac{2+2+4+12+4+12}{6}=6$$
$$\phi_B=\frac{3+9+1+1+9+1}{6}=4$$
$$\phi_C=\frac{11+5+11+3+3+3}{6}=6$$
用两个总和自查
按列算完后的总和: $6+4+6=16$,全部价值正好分完。
每行的总和: 也都必须是 16,例如 $2+3+11=16$。一行从空联盟走到全体成员,中间价值在相邻两次相减时抵消,只剩 $v(N)-v(\varnothing)=16$。
这也解释了效率:每行都分完,所有行取平均后仍然分完。行和能帮忙查错,但多个错误可能相互抵消,不能代替逐项核对。
到这里已经会算一次 Shapley 值了。 想知道它是否能保证合作稳定,接着看手套反例;公理可以稍后再读。
⚖️ 四、四条公理确定了哪一种“公平”?
这里讨论同一有限成员集合上的可转移效用博弈,且空联盟价值为 0。分配规则要对这一类博弈都作出回答,而不只是碰巧满足某一个例子。
1. 效率:总价值分完
$$\sum_i\phi_i=v(N)$$
这不等于每个联盟都满意。后者是核心的要求。
2. 对称:可互换的成员拿一样
比较 $i,j$ 时,必须选择不含这两个人的 $S$。如果对每个这样的 $S$ 都有:
$$v(S\cup\{i\})=v(S\cup\{j\})$$
那么 $\phi_i=\phi_j$。这里比较的是他们对所有相关联盟的作用,不只比较单独价值。
3. 零贡献成员:始终不增加价值,就分到 0
如果对所有不含 $i$ 的 $S$,$\Delta_i(S)=0$,则 $\phi_i=0$。这是 null player(零贡献成员)条件。
它也常与 dummy player(虚拟成员)一起讲。更一般的 dummy 条件是:此人的边际贡献始终等于自己的单独价值 $v(\{i\})$,于是就应分到那个值,未必是 0。
4. 可加性:价值函数相加,分配也相加
先定义 $u(S)=v_1(S)+v_2(S)$,对每一个联盟都这样相加。可加性要求:
$$\phi_i(u)=\phi_i(v_1)+\phi_i(v_2)$$
这是明确的数学条件。若两个真实项目合并后还产生额外协同 $h(S)$,合并游戏就是 $v_1+v_2+h$,需要把第三项也计入。有协同不构成可加性的反例,漏记协同才是建模问题。
“唯一”有前提,不是所有公平观只有一个答案
Shapley 的经典刻画说明:在上述博弈类上,同时满足效率、对称、零贡献成员和可加性的规则,唯一是 Shapley 值。
唯一性依赖你接受这组公理。 换成按需要分配、按约定的议价权分配,或要求联盟稳定,可能得到不同答案。
📐 另一组刻画:效率、对称与边际性
边际性要求:若同一个人在两个博弈中对每个联盟的边际贡献都相同,他的分配就相同。
在同一成员集合的全部可转移效用博弈上,效率、对称与边际性也唯一确定 Shapley 值。这是 Young(1985)刻画的一种表述;Pintér 的论文,定理 3.5给出相应证明。
这里是另一组公理,不是简单把上面的可加性换个名称;也不能只检查一个孤立游戏,就宣布已经验证了整个规则的刻画。
🧤 五、按贡献分,不保证落在核心里
1 号有右手套,2、3 号各有一只左手套。能凑成一对时总价值为 1,否则为 0。
这个游戏是单调的简单博弈:联盟价值只有 0 或 1,增加成员不会把赢变成输。每个排列中,恰好有一人把价值从 0 变成 1,称为关键成员。
| 排列 | 关键成员 |
|---|---|
| 1,2,3 | 2 |
| 1,3,2 | 3 |
| 2,1,3 | 1 |
| 2,3,1 | 1 |
| 3,1,2 | 1 |
| 3,2,1 | 1 |
数一数每个人成为关键成员的次数,再除以 6:
$$\phi_1=\frac46=\frac23$$
$$\phi_2=\phi_3=\frac16$$
| 分配标准 | 本例结果 |
|---|---|
| Nucleolus;也是本例唯一的核心分配 | $(1,0,0)$ |
| Shapley 值 | $(2/3,1/6,1/6)$ |
检查联盟 $\{1,3\}$: Shapley 给他们的总和是 $2/3+1/6=5/6$,但他们自己合作能得到 1。因此这组分配不在核心里。
例如,两人可以改分为 $3/4$ 和 $1/4$,都比原来拿得多。这里证明的是存在联合改善的机会,不是断言他们在现实中必然立即散伙。
Shapley 满足的是指定的贡献公理,核心要求的是没有联盟能作出这种改善。“按贡献分”与“联盟稳定”不能互相替代。
📈 六、凸博弈:边际贡献不随联盟扩大而下降
设 $B\subseteq A$,且 $i$ 不在 $A$ 中。凸博弈要求:
$$\Delta_i(A)\geq\Delta_i(B)$$
读法是:已有团队从 $B$ 扩大到 $A$ 后,同一个人的加入增量不变小。允许相等,不要求严格变大。
📐 等价的集合形式:超模性
对所有联盟 $S,T\subseteq N$,有:
$$v(S\cup T)+v(S\cap T)\geq v(S)+v(T)$$
左边比较合并团队与交集的价值;右边是两个原团队的价值。这个集合函数条件称为超模性,与上面的边际贡献递增形式等价。
结论:凸博弈的核心非空,而且 Shapley 值在核心内。 这不是所有博弈都有的性质。
📐 为什么每个排列的边际贡献分配都稳定?
选任意排列,给每人分配他在该排列中的边际贡献,记为 $x_i$。望远镜求和保证全部分完。
再取任意联盟 $T$,保留它的成员在原队列中的相对顺序。每个人在全队列中的前驱集合,包含他在 $T$ 内的前驱集合。
因为边际贡献不会随集合扩大而减少,全队列给 $T$ 成员的增量总和,不小于只让 $T$ 自己依次进场的增量总和。后者恰好是 $v(T)$。
因此每个 $T$ 都满足核心约束。每个排列的分配都在核心里;核心是凸集,取它们的平均,也就是 Shapley 值,仍在核心里。
用手套例子反查: 2 号在 $\{1\}$ 后加入,贡献是 1;在 $\{1,3\}$ 后加入,贡献却是 0。边际贡献下降,所以它不是凸博弈。
🗳️ 七、Banzhaf:先分清两种归一化
继续使用单调简单博弈,且 $v(\varnothing)=0$、$v(N)=1$。如果联盟 $C$ 原来赢,去掉 $i$ 后输,就把 $i$ 在 $C$ 中记为一次关键成员。
记关键次数为 $\eta_i$。手套博弈的获胜联盟只有三个:
| 获胜联盟 | 哪些成员关键 |
|---|---|
| $\{1,2\}$ | 1、2 |
| $\{1,3\}$ | 1、3 |
| $\{1,2,3\}$ | 只有 1 |
因此 $\eta=(3,1,1)$。接下来除以什么,决定你在报告哪一种指数。
绝对 Banzhaf:除以其他人的子集数
$$b_i=\frac{\eta_i}{2^{n-1}}$$
相当于对其他人是否加入作独立、各半的选择:每个前驱子集等可能,计算 $i$ 能改变结果的概率。
本例得到 $(3/4,1/4,1/4)$,三者相加是 5/4,不是 1。不同人的关键事件不是互斥事件,所以这些概率不需要加起来等于 1。
归一化 Banzhaf:除以所有人的关键次数总和
$$\beta_i=\frac{\eta_i}{\sum_j\eta_j}$$
本例得到 $(3/5,1/5,1/5)$,总和当然是 1。只要分母非零,这就是归一化本身的结果。
| 本例的度量 | 1 号 | 2 号 | 3 号 | 总和 |
|---|---|---|---|---|
| Shapley | $2/3$ | $1/6$ | $1/6$ | 1 |
| 绝对 Banzhaf | $3/4$ | $1/4$ | $1/4$ | $5/4$ |
| 归一化 Banzhaf | $3/5$ | $1/5$ | $1/5$ | 1 |
真正的区别是随机模型与加权方式。 Shapley 等权平均排列;绝对 Banzhaf 等权平均其他人的子集;归一化 Banzhaf 再把各人的结果缩放到总和为 1。
不能说“归一化 Banzhaf 不满足总和为 1,所以不能分钱”。它可以提供单位价值的份额;但归一化本身不等于满足 Shapley 对全部可转移效用博弈的那组公理。使用前要先决定希望哪种权力或贡献标准。
🗜️ 八、怎么把 v 写短,怎么算得动?
这节可以后读。只要先记住:计算难度既取决于规则,也取决于输入怎样表示。 “人数少”与“输入短”不是同一件事。
图博弈:每条边由两个端点均分
给一张带权无向图,成员是节点,$v(S)$ 是 $S$ 内部所有边的权重之和。没有另外的节点收益时:
$$\phi_i=\frac12\sum_{j\ne i}w(\{i,j\})$$
为什么一半?一条边只有两个端点都出现才产生价值;随机排列中,两端点各有一半机会后到,获得这条边的增量。
这种表示能很快算 Shapley,但不能表示所有高阶协同。若允许负边权,核心非空判定一般是 coNP-完全;若边权全非负,游戏是凸的,核心非空,Shapley 就给出一个核心分配。
不要把“允许负权的一般难例”当成“所有图博弈都难”。这些区别见 Ieong 与 Shoham 原论文第 2.2 节对图博弈结果的说明。
MC-nets:满足哪些条件,就累计哪条规则
MC-nets 把 $v$ 写成一组“模式 → 数值”。模式列出哪些成员必须在、哪些必须不在;一个联盟的价值是所有命中规则的数值之和。
保留这个四规则算例:
| 规则 | 条件 | 命中后增加的价值 |
|---|---|---|
| $x_1\wedge x_2\to5$ | 1、2 都在 | 5 |
| $x_2\to2$ | 2 在 | 2 |
| $x_3\to4$ | 3 在 | 4 |
| $x_2\wedge\neg x_3\to-2$ | 2 在,3 不在 | −2 |
其中 $\wedge$ 表示“并且”,$\neg$ 表示“不在”。负数表示扣减,不是删掉这条规则。
逐个检查命中情况:
| 联盟 | 命中的值 | $v(S)$ |
|---|---|---|
| $\{2\}$ | $2-2$ | 0 |
| $\{2,3\}$ | $2+4$ | 6 |
| $\{1,2\}$ | $5+2-2$ | 5 |
| $\{1,2,3\}$ | $5+2+4$ | 11 |
本章每条规则至少有一个“必须在”的成员,因此空联盟不会命中。若允许纯否定规则,空联盟可能非零,必须先处理基准,不能无条件沿用 $\sum_i\phi_i=v(N)$。
逐条分配,再加起来
可加性在这里派上用场。前面两人共同带来 5 的规则,两人各分 2.5;单人规则直接归给那个人。
最后一条扣减规则有一点反直觉:2 号先来会触发 −2,3 号随后加入会取消这笔扣减。平均两个相对顺序,这条规则给 2 号 −1、给 3 号 +1。
| 规则 | 给 1 号 | 给 2 号 | 给 3 号 |
|---|---|---|---|
| 1、2 都在,加 5 | 2.5 | 2.5 | 0 |
| 2 在,加 2 | 0 | 2 | 0 |
| 3 在,加 4 | 0 | 0 | 4 |
| 2 在且 3 不在,减 2 | 0 | −1 | 1 |
| 合计 | 2.5 | 3.5 | 5 |
总和是 11,与 $v(N)$ 一致。负规则也能带来正的个人贡献,因为某个人可以消除扣减。
📐 为什么这种基本规则可以快速计算?
一条规则中,设有 $a\geq1$ 个“必须在”、$b\geq0$ 个“必须不在”的不同成员,规则数值为 $r$。条件不能互相矛盾。
只看这些成员的相对顺序,每个“必须在”的成员从该规则获得:
$$\frac{r}{a\binom{a+b}{a}}$$
若 $b>0$,每个“必须不在”的成员从该规则获得:
$$-\frac{r}{b\binom{a+b}{a}}$$
没出现在规则里的成员获得 0。前一项来自“最后一个正条件满足”,后一项来自“第一个负条件被破坏”。
因此逐条规则算再相加,算术操作数可随规则描述总长度线性增长;这不等于只随人数线性增长,也未把任意大整数运算当成真实机器上的零成本。
MC-nets 能表达任意空联盟为零的游戏,但最坏情况仍可能需要指数多条规则。“完全表达”不保证“所有游戏都压得很短”。原论文第 3–4 节
难度表,要连同输入条件一起读
下面的“难”是一般输入下的最坏情形,不是说每个小例子都无法算。
| 表示与条件 | 精确算 Shapley | 判核心非空 |
|---|---|---|
| 二进制编码权重的加权投票博弈 | 一般 NP-难 | 多项式时间 |
| 允许正负边权的图博弈 | 多项式时间 | coNP-完全 |
| 非负边权的图博弈 | 多项式时间 | 总是非空 |
| 基本合取规则 MC-nets | 对规则长度线性的算术操作数 | 一般 coNP-难 |
加权投票的计算难度可见 Matsui 与 Matsui 的原论文。核心非空则可通过是否存在否决者判断:去掉某人后,其余权重是否仍能达到门槛。
MC-nets 的核心非空一般困难,但规则依赖图的树宽固定有界时,有多项式算法;“树宽”衡量依赖结构离树有多远。这也是额外结构能让问题容易的例子。原论文第 5 节
不要记成“没有哪一种表示两项都容易”。 非负边权图就是反例;概念、表示和限制条件必须一起比较。
🤖 九、SHAP:解释模型还差一个建模选择
把成员换成特征,可以用 Shapley 思路分摊一次预测。但还不能跳过一个关键问题:
只给模型一部分特征时,没给的特征怎么处理?
先定义缺失特征的处理,再定义游戏
对要解释的样本 $x$,记 $g(S)$ 为“保留 $S$ 中的特征,按约定处理其他特征后”的模型输出。
例如,可以用选定背景样本补齐缺失特征再平均,也可以定义条件期望。它们对相关特征的处理可能不同,因此贡献结果也可能不同。
把空集合的输出作为基准:
$$\phi_0=g(\varnothing)$$
再定义中心化的联盟价值:
$$v(S)=g(S)-g(\varnothing)$$
若全部特征已知时 $g(N)=f(x)$,效率就给出:
$$f(x)=\phi_0+\sum_i\phi_i$$
这里的“严格加回预测值”对应效率,也叫局部准确性;不是前面“两份游戏相加”的可加性公理。
一个加法自查,不是因果效果
教学示例:若解释的是概率输出,基准为 0.40,两项贡献为 +0.15 和 −0.05,预测应为 0.50。
但若解释器输出的是对数几率,贡献就处于对数几率单位,不能把 +0.15 直接叫成“增加 15 个百分点”。输出空间要先对齐。
即使加法完全对上,也只证明这套归因规则分摊了预测。它不证明改动某个特征就会产生同样大小的现实效果。
等权平均是定义,不要求暴力枚举所有顺序
特征存在交互时,增量会随前面已知的特征变化;Shapley 用所有顺序的平均来分配这些变化。没有交互时,各顺序可以给出相同增量,规则仍然适用。
直接枚举全部 $n!$ 个排列代价很高,但可以合并联盟、采样,或利用模型结构。不能从定义里有 $n!$ 就断言所有精确算法都算不动。
- KernelSHAP用特殊加权的线性回归求归因,实际常结合联盟采样。代价取决于特征数、背景集、模型调用和采样预算,不能一概说“线上不能用”。KernelExplainer 官方说明
- TreeSHAP利用树结构,在支持的设置下精确计算相应游戏的归因。精确性依赖采用的特征依赖、缺失处理和输出定义,不代表对任意相关特征的条件分布都能直接精确求解。TreeExplainer 官方说明
先决定解释什么,再选择算法。速度快或结果能加回去,都不能代替对价值函数的检查。
🔗 这一章连到哪里
- 模型上线之后 10:SHAP 能做什么不能做什么:继续看背景集、解释器与因果误用。这里的贡献公理不提供干预效果保证。
- 22:联盟博弈与核心:复查为什么手套博弈的核心只有 $(1,0,0)$,以及 nucleolus 的目标。
- 24:投票规则:权力指数衡量个人的影响;投票规则研究如何把不同人的票汇成决定。
✅ 检查点
- Shapley 值的一句话直觉是什么?为什么不能只看一个联盟?
- 排列版、联盟版各如何计算?联盟权重中的两个阶乘在数什么?
- 煎饼例子的结果是多少?如何按行、按总和自查?
- 四条公理是什么?“唯一”有什么前提?真实项目合并产生协同,是否直接推翻可加性?
- 手套博弈的 Shapley 值在核心中吗?给出一个能联合改善的联盟。
- 凸博弈要求边际贡献严格增加吗?为什么其 Shapley 值在核心内?
- 手套博弈的关键次数、绝对 Banzhaf 和归一化 Banzhaf 各是多少?哪一个不要求加起来为 1?
- 图博弈怎么分配边权?MC-nets 的“线性”是相对什么长度?两项计算有没有同时容易的情况?
- SHAP 加回预测值对应哪条公理?为什么还要定义背景和输出单位?是否必须枚举全部排列?
👀 答案与核对位置
- 等权平均所有加入顺序下的个人增量。只看一个联盟会偏向某一种已有人手的条件。
- 排列版对每个排列的 $\Delta_\pi(i)$ 等权平均;联盟版按 $\omega_{|S|}$ 加权求和。两个阶乘分别数前驱联盟内部和后继成员的排法;联盟本身不等权。
- $(6,4,6)$,总和为 16;六行每行也为 16。行和能查错,但抵消的多项错误仍要逐项检查。
- 效率、对称、零贡献成员、可加性。在本章整个博弈类上同时满足它们,规则才唯一。额外协同应加入新的价值函数,不是把真实合并误写成只有两项的和。
- $(2/3,1/6,1/6)$ 不在核心。联盟 $\{1,3\}$ 共得 $5/6$,自行合作有 1,可改成 $(3/4,1/4)$,两人都改善。
- 只要求不减小,允许相等。每个排列的边际贡献向量都满足全部核心约束,其平均仍在凸的核心集合中。
- 关键次数 $(3,1,1)$;绝对指数 $(3/4,1/4,1/4)$ 总和为 $5/4$;归一化指数 $(3/5,1/5,1/5)$ 总和为 1。Shapley 与 Banzhaf 的本质区别是排列平均与子集平均的权重。
- 每条边两个端点各得一半。MC-nets 逐条算再相加,其算术操作数相对规则输入长度线性。非负权图博弈既能快算 Shapley,又总有核心;有界树宽也可帮助处理 MC-nets。
- 对应效率 / 局部准确性,不是游戏相加公理。背景处理决定 $v(S)$,单位决定数值如何相加;定义上的顺序平均不意味着算法必须暴力枚举,也不提供因果保证。
本节回顾
先记住这四件事
- Shapley 平均的是所有加入顺序下的增量,不是所有联盟等权平均。
- 贡献公理与核心稳定性是不同要求;凸博弈能把二者连接起来。
- 绝对 Banzhaf 的总和未必为 1,归一化 Banzhaf 的总和为 1。
- SHAP 先定义缺失特征与输出空间,再分摊预测;不是因果证明。
下一节 👉 24-投票规则.md