🏠 总目录📚 本教程 23 · Shapley 值 ← →

按平均边际贡献分收益,为什么仍可能不稳定?

读后可检查:手算加入顺序的贡献,区分 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:

  1. A 从空联盟开始,增加 $2-0=2$。
  2. B 加进来,总价值从 2 变成 5,增加 $5-2=3$。
  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!$ 就断言所有精确算法都算不动。

先决定解释什么,再选择算法。速度快或结果能加回去,都不能代替对价值函数的检查。


🔗 这一章连到哪里


✅ 检查点

  1. Shapley 值的一句话直觉是什么?为什么不能只看一个联盟?
  2. 排列版、联盟版各如何计算?联盟权重中的两个阶乘在数什么?
  3. 煎饼例子的结果是多少?如何按行、按总和自查?
  4. 四条公理是什么?“唯一”有什么前提?真实项目合并产生协同,是否直接推翻可加性?
  5. 手套博弈的 Shapley 值在核心中吗?给出一个能联合改善的联盟。
  6. 凸博弈要求边际贡献严格增加吗?为什么其 Shapley 值在核心内?
  7. 手套博弈的关键次数、绝对 Banzhaf 和归一化 Banzhaf 各是多少?哪一个不要求加起来为 1?
  8. 图博弈怎么分配边权?MC-nets 的“线性”是相对什么长度?两项计算有没有同时容易的情况?
  9. SHAP 加回预测值对应哪条公理?为什么还要定义背景和输出单位?是否必须枚举全部排列?
👀 答案与核对位置
  1. 等权平均所有加入顺序下的个人增量。只看一个联盟会偏向某一种已有人手的条件。
  2. 排列版对每个排列的 $\Delta_\pi(i)$ 等权平均;联盟版按 $\omega_{|S|}$ 加权求和。两个阶乘分别数前驱联盟内部和后继成员的排法;联盟本身不等权。
  3. $(6,4,6)$,总和为 16;六行每行也为 16。行和能查错,但抵消的多项错误仍要逐项检查。
  4. 效率、对称、零贡献成员、可加性。在本章整个博弈类上同时满足它们,规则才唯一。额外协同应加入新的价值函数,不是把真实合并误写成只有两项的和。
  5. $(2/3,1/6,1/6)$ 不在核心。联盟 $\{1,3\}$ 共得 $5/6$,自行合作有 1,可改成 $(3/4,1/4)$,两人都改善。
  6. 只要求不减小,允许相等。每个排列的边际贡献向量都满足全部核心约束,其平均仍在凸的核心集合中。
  7. 关键次数 $(3,1,1)$;绝对指数 $(3/4,1/4,1/4)$ 总和为 $5/4$;归一化指数 $(3/5,1/5,1/5)$ 总和为 1。Shapley 与 Banzhaf 的本质区别是排列平均与子集平均的权重。
  8. 每条边两个端点各得一半。MC-nets 逐条算再相加,其算术操作数相对规则输入长度线性。非负权图博弈既能快算 Shapley,又总有核心;有界树宽也可帮助处理 MC-nets。
  9. 对应效率 / 局部准确性,不是游戏相加公理。背景处理决定 $v(S)$,单位决定数值如何相加;定义上的顺序平均不意味着算法必须暴力枚举,也不提供因果保证。

本节回顾

先记住这四件事

下一节 👉 24-投票规则.md

打卡记录保存在你的浏览器里,首页能看到总进度