Shapley Values是博弈论大师Lloyd Stowell Shapley基于合作博弈理论(cooperative game theory)提出来的解决方案，通常被翻译为夏普利值、沙普利值，是一种基于贡献的分配方式。

Shapley Values

简介

Shapley Values是博弈论大师Lloyd Stowell Shapley基于合作博弈理论(cooperative game theory)提出来的解决方案，通常被翻译为夏普利值、沙普利值，是一种基于贡献的分配方式。这种方法根据玩家们在Game中得到的总支出公平的分配总支出给玩家们

  • 玩家们 -> features value of the instance
  • Game -> model
  • 总支出 -> prediction

博弈根据是否可以达成具有约束力的协议，分为合作博弈和非合作博弈。合作博弈是指一些参与者以同盟、合作的方式进行的博弈，博弈活动就是不同集团之间的对抗。
合作博弈研究人们达成合作时如何分配合作得到的收益，即收益分配问题。合作博弈采取的是一种合作的方式，或者说是一种妥协。
合作博弈亦称为正和博弈，是指博弈双方的利益都有所增加，或者至少是一方的利益增加，而另一方的利益不受损害，因而整个社会的利益有所增加的。

合作博弈存在的两个基本条件是：

  1. 对联盟来说，整体收益大于其每个成员单独经营时的收益之和。
  2. 对联盟内部而言，应存在具有帕累托改进性质的分配规则，即每个成员都能获得不少于不加入联盟时所获的收益。

Shapley Value的四个公理：

  1. 对称性：如果player i和player j满足$v(S\cup i)=v(S \cup j)$，对于任意不包含i和j的联盟S都成立，那么$\phi_i(v)=\phi_j(v)$.
  2. 有效性：合作各方获利总和等于合作获利($\sum_{i\in P}\phi_{i}(v)=v(P)$)
  3. 冗员性：如果i是一个player，满足$v(S)=v(S\cup j)$对任意一个联盟S成立，那么$\phi_i(v)=0$;也就是说如果一个人加入任何一个联盟对联盟的收益都没有影响，也就是说，他对任何一个联盟都没有贡献，那这个人就不应该分得任何payoff，所以它的夏普利值为0.
  4. 任意两个game无关，它的夏普利值可以相加。($\phi[u+v]=\phi[u]+\phi[v]$对任何games u和v都成立)

公式1

记$I={1,2,…,n}$为n个合作人的集合

$$\phi_i(v)=\sum_{s\in S_i}\omega(|s|)[v(s)-v(s\setminus{i})]$$

其中，$S_i$是$I$中包含成员$i$的所有子集形成的集合，$|s|$是集合s元素的个数，$\omega(|s|)$是加权因子

$s\setminus {i}$，表示集合s中去掉元素i后的集合

$v(s)-v(s\setminus{i})$，成员i在联盟中的贡献，即成员i的边际贡献；

$\omega(|s|)$，即权重$\omega(|s|)=\frac{(|s|-1)!(n-|s|)!}{n!}$

Shapley Value由两权重系数和边际贡献两部分构成

公式的理解：

成员i的联盟会有很多个，我们列出包含成员i所有的联盟，然后依次计算每个联盟中，成员i的边际贡献，并将该边际贡献乘以该联盟出现的概率（权重），把结果值加起来就是成员i的夏普利值。

这里的边际贡献还好理解，联盟的收益-剔除成员i后联盟的收益，即成员i对联盟带来的增益贡献（边际贡献）；

权重公式的理解：

从公式来看，它只和联盟s的成员个数有关，分母n!表示n个成员的全排列，分子$(|s|-1)!(n-|s|)!$表示联盟s中除了成员i的排列数乘以联盟剩下的成员$(n-|s|)$要加入联盟s的排列数

img

img

公式2

初始方程：

$$\phi_i(v)=\sum_{S\subseteq N\setminus{i}}\frac{|S|!(|N|-|S|-1)!}{|N|!}(v(S\cup{i})-v(S))$$

让我们把它分解一下。在一个联盟game（前面描述的场景）中，我们有一组 p 个玩家。我们还有一个函数 val，它给出了这些参与者的任何子集的值，也就是说，S 是${x_1,…,x_p}$的子集，然后 val（S）给出了该子集的值。因此，对于一个联合博弈（p，v），我们可以使用这个方程来计算玩家 i 的贡献，即 Shapley 值。

我们重写一下初始方程：

change

接下来通过分解方程的不同部分，以便加深理解，在这里我们定义一个具体的场景，使其所有部分都不再那么抽象。

假设我们经营一家生产砖块的工厂。我们的一个生产团队由四个人组成：Amanda、Ben、Claire和Don（从现在开始我将以他们名字的首字母来称呼他们）。每周他们一起设法生产出X块砖。由于我们工厂运转良好，有一笔奖金要发给队员们，但是为了让我们以公平的方式做到这一点，我们需要弄清楚每个人对每周生产X数量的砖块贡献了多少。

最困难的是，我们有好几个因素都会影响团队可以生产的砖块数量。其中之一是团队规模，因为团队规模越大，生产的砖块就越多。另一个可能是团队成员之间的合作程度。问题是，我们无法以有意义的方式量化这些影响，但幸运的事，我们可以使用Shapley值来回避这个问题。

我们现在已经定义了玩家（A、B、C和D）以及他们参与的game（生产砖块）。让我们从计算生产的X砖中有多少可以归于Don开始，即计算D的Shapley值。如果我们把它与Shapley值公式的参数联系起来，我们就得到：

$$N={A,B,C,D}\\ i=D$$

所以D是我们的球员i，整个N组由所有四个队员A，B，C和D组成，我们先看一下Shapley值公式的这一部分：

$$S\subseteq N\setminus{i}$$

也就是说，我们需要把我们的团队成员排除在我们现在关注的人之外。然后，我们需要考虑所有可能形成的子集。所以如果我们从组中排除D，我们就只剩下{A,B,C}。从这个剩余的组中，我们可以形成以下子集：

ziji

我们总共可以构造出其余团队成员的8个不同子集。其中一个子集是空集，即它没有任何成员。

现在让我们把注意力转移到这个部分：

$$(v(S\cup{i})-v(S))$$

这是我们Shapley值的一个基本概念的应用：在game中增加玩家i的边际价值。所以对于任何给定的子集，我们要比较它的值和当包括玩家i的时候它的值。通过这样做，我们得到了将玩家i添加到该子集的边际值。

我们把它和我们的例子联系起来，想看看如果我们把D加到8个子集中的每一个子集上，每周生产的砖块数量有什么不同。我们可以将这8个边缘值直观地表示为：

$$\nabla v_{A,D}\space \nabla v_{AB,D} \ \nabla v_{\emptyset,D} \space \space \nabla v_{B,D} \space \space \nabla v_{BC,D} \space \space \nabla v_{ABC,D} \ \nabla v_{C,D} \space \space \nabla v_{CA,D}$$

你可以将每种情况都视为我们需要观察的不同场景，以便公平地评估D对整个生产的贡献程度。这意味着，我们需要观察如果没有人工作（即空集合）会产生多少砖块，并将其与只有D工作时的情况进行比较。我们还需要观察AB产生的砖块数量，并将其与AB产生的砖块数量以及所有8个集合中D可以产生的砖块数量进行比较。

好吧，我们现在已经知道我们需要计算8个不同的边缘值。Shapley值方程告诉我们，我们需要它们加在一起。然而，在我们做这些之前，我们还需要调整每一个边际值，从等式的这一部分可以看出：

看出

它计算出除玩家i以外的所有剩余团队成员的子集的排列可以有多少个。或者换句话说：如果你有｜N｜-1个玩家，你能用它们组成多少个｜S｜大小的组？然后我们用这个数字除以玩家i对所有大小为｜S｜的群体的边际贡献。

在我们的场景中，｜N｜-1=3，也就是说，当我们计算D的Shapely值时，这些是剩下的团队成员数量。在我们的例子中，我们将使用等式的那一部分来计算我们可以形成多少个0、1、2和3大小的组，因为这些只是我们可以用剩下的成员构造的组大小。因此，例如，如果有｜S｜=2，那么我们可以构造3个不同的大小为2的组：AB、BC和CA。这意味着我们应该对8个边缘值中的每一个应用以下比例因子：

$$\frac{1}{3}\nabla v_{A,D}\space\space \frac{1}{3}\nabla v_{BC,D} \ 1\nabla v_{\emptyset,D} \space \space \frac{1}{3}\nabla v_{B,D} \space \space \frac{1}{3}\nabla v_{BC,D} \space \space 1\nabla v_{ABC,D} \ \frac{1}{3}\nabla v_{C,D} \space \space \frac{1}{3}\nabla v_{CA,D}$$

让我们思考一下为什么要这样做。我们想知道D对团队总产出的贡献有多大。为了做到这一点，我们计算了他对我们所能形成的团队中每个集合的贡献。通过添加这个比例因子，我们平均了其他团队成员对每个子集大小的影响。这意味着，当我们将D加入到一个0，1，2和3大小的团队中时，我们能够捕获这些团队的平均边际贡献。

接下来，分解最后一部分：

$$\frac{1}{|N|}$$

我们需要应用到所有的边际值，然后才能求和。我们必须把它们和总队员数分开。

我们为什么要这么做？好吧，如果我们看看砖厂的例子，我们已经平均出了其他团队成员对每个子集大小的影响，这样我们就可以算出D对0、1、2和3大小的组的贡献。最后一块拼图是平均小组规模的影响，也就是说，D贡献了多少与小组规模无关。

我们现在终于可以计算出D的Shapley值了，我们观察到他对团队中所有不同的子集的贡献是多少。我们还对团队成员组成和团队规模的影响进行了平均，这最终允许我们计算：

finalcalculate

数学符号更多的是一个图形化的说明，而不是一个数学的说明（这是我在脑海中想象它的方式）

在这里，我们得到了D的Shapely值。在我们为团队的其他成员完成这项工作之后，我们将知道每个人对每周生产的X块砖的贡献，这样我们就可以在所有团队成员中公平的分配奖金。

$$X=v({A,B,C,D})=\phi_A(v)+\phi_B(v)+\phi_C(v)+\phi_D(v)$$

我们可以发现，我们不需要知道任何关于值函数v的内部工作原理，只需要观察它为不同子集提供的值，我们可以从参与game的玩家中得到这些值。

这才是Shapley值背后真正的力量和吸引力，但是对于一组参与game的n个玩家，你将需要分析$2^n$个子集才能计算Shapley值。

公式3

Shapley Values通过S中玩家的值函数val定义的：

$$\phi_j(val) = \sum_{S \subseteq {x_1,…,x_p}\setminus{x_j}}{\frac{|S|!(p-|S|-1)!}{p!}} (val(S\cup{x_j})-val(S))$$

  • $x_1,…,x_p$为建立模型所使用的所有特征，p为所有的特征数量。
  • S为除了$x_j$的子集合。
  • Val(S)是对于集合S的预测值减去期望值（平均预测值）。

$$val_x(S)=\int \hat f (x_1,…,x_p)d\mathbb{P}_{x\notin S}-E_X(\hat f(X))$$

下面通过一个例子了解公式。

Example 1

假设工程师们需要合作写一个project，共计100行code，图一显示了工程师期望产出code的行数，也就是对应的val(S)

图一. 工程师期望产出code的行数

而我们想要计算出x1这位工程师的Shapley value，也就是他的贡献值该如何计算呢？可以参考一下图二的计算流程，三位工程师，会有六种排列组合，需要针对每种情形来计算出x1的Shapley value，因为先后顺序是会影响他的贡献值的，接着再把六个值加总平均就可以得到x1的Shapley value了。

图二.x1的Shapley value计算流程

在下图代入公式看看结果：

计算结果

最后我们可以分别计算出x2和x3的Shapley values，如图三所示，最后得到的x1 是 34.17, x2 是 41.7, x3 是 24.17，而这三个值相加就等于100行code，简单来说，这个Shapley values其实就是想要衡量个别的特征对模型的贡献程度是多少，而不收到其他特征的影响。

图三.x1，x2，x3的Shapley values计算过程

Example 2

某互联网公司今天需要加班，需要编写一个500行的程序代码，产品经理找了三个程序员来完成。按照完成量发奖金：1号普通程序员独立能写100行，2号大神程序员独立能写125行，3号美女程序员能写50行。但如果程序员两两合作，会产生不同的编码效率：1号和2号合作能写270行，2号与3号合作能写350行，1号与3号合作能写375行。当然，三名程序员共同合作能完成500行。若共有1000元项目奖金，该如何给这三名程序员分配呢？

下面，我们尝试用Shapley值经行计算。首先，计算可能的联盟数量。显然，三个人的联盟形成方法一共有6种：

（1）1号邀请2号加入组成S联盟，3号加入S联盟；

（2）1号邀请3号加入组成S联盟，2号加入S联盟；

（3）2号邀请1号加入组成S联盟，3号加入S联盟；

（4）2号邀请3号加入组成S联盟，1号加入S联盟；

（5）3号邀请1号加入组成S联盟，2号加入S联盟；

（6）3号邀请2号加入组成S联盟，1号加入S联盟；

按照Shapley值的计算过程，下一步需要计算每位程序员的边际贡献，

img

1号普通程序员的Shapley值为：$\frac{100 + 100 + 145 + 150 + 325 + 150}{6}= \frac{970}{6}$

2号大神程序员的Shapley值为：$\frac{170 + 125 + 125 + 125 + 125 + 300}{6} = \frac{970}{6}$

3号美女程序员的Shapley值为：$\frac{230 + 275 + 230 + 225 + 50 + 50}{6} = \frac{1060}{6}$

三人的Shapley值的总和正好等于500。 所以根据Shapley值，1号普通程序员应该获得奖金为：1000 x 0.3233 = 323.3元，2号大神程序员应该获得奖金同样为323.3元，3号美女程序员获得奖金为353.3元。

蒙特卡洛采样近似

其实这样直接计算Shapley value是非常耗费计算资源的，而当feature values比较多时，可能的联盟数量呈指数性增加，因此对于计算精确的Shapley值是一个大问题，对于这个问题， Štrumbelj et al. 提出了蒙特卡洛采样的近似值：

$$\hat \phi_j=\frac{1}{M}\sum_{m=1}^{M}(\hat f(x_{+j}^{m})-\hat f(x_{-j}^{m}))$$

  • $x_{+j}=(x_1,…,x_{j-1},x_{j},z_{j+1},…,z_p)$，意思是除了特征值$x_j$以外，其他不在联盟内的特征值被来自随机数据点z的特征值替换。
  • $x_{-j}=(x_1,…,x_{j-1},z_{j},z_{j+1},…,z_p)$，表示连特征值$x_j$都要替换

Shapley Value的线性扩展形式(Multilinear extension form)

用v表示一个p个人的合作博弈，P是这个game中的carrier，那么multilinear extesion(MLE) of v 就是一个函数$f:[0,1]^p \rightarrow \R$

$$f(x_1,…,x_p)=\sum_{S\subseteq P}[\prod_{i\in S}x_i\prod_{j\notin S}(1-x_j)]v(S)$$

这个函数有两个解释方法：

  1. 对于这个game中的联盟S，我们把联盟中的人（即$i\in S$）看成统一体，这个统一体和不是联盟中的人进行一个inessential game;
  2. 把公式中的$x_i$看作player i加入联盟S的概率，因此联盟S形成的概率就是S中的每个人都加入S的概率和S外的每个人都不加入S的概率乘起来，再乘上这个概率对应的colition S的value，那么函数f就可以看作所有coalition的expected value，也就是一个期望的形式。

定理：game v是inessential当且仅当它的multilinear function $f$是变量的线性组合。

也就是说$f(x_1,…,x_n)=\sum_{i=1}^{n}v(i)x_i$，其中$v(S)=\sum_{i\in S}v(i),∀S\in P$

只要理解了MLE的解释，就不难理解这个定理了，证明比较简单。

用MLE求夏普利值，公式如下：
$$\phi_i[v]=\int_{0}^{1}\frac{\partial f(t,…,t)}{\partial x_i}dt$$

其中$\frac{\partial f(t,…,t)}{\partial x_i}$可以理解为player i对这个game的边际贡献（marginal contribution），对这个贡献求积分，就是衡量player i对所有包含它的联盟的总贡献(reflecting individual conributions)，跟shapely值的思想一致。从偏导的定义出发，求$f$对$x_i$ 的偏导相当于衡量$x_i$每变化一单位，$f$ 会变化多少，也就是$x_i$的变化对$f$的影响，其中$x_i$表示player i 加入联盟S的概率，$f$是所有coalition的expected value，而$x_i$对$f$的影响则可以理解为player i对整个game的影响力，也就是贡献。

参考文献

[1] 可解釋 AI (XAI) 系列 — SHAP

[2] SHAPLEY值的一个应用

[3] Shapley Value（夏普利值）

[4] 关于Shapley Value（夏普利值）的公式

[5] 机器学习中的 Shapley 值怎么理解？

[6] 合作博弈中夏普利值（Shapley Value）的主要思想、公理及求解公式的理解