Shapley value

我们先介绍一下沙普利值。沙普利值来源于合作博弈，cooperative game (coalitional game)。区别于传统博弈认为个体之间是相互独立的并分析其纳什均衡的方法，合作博弈会考虑每个player之间的协作关系，分析合作中会出现的$1+1>2$的收益等情景。合作博弈中一般包含$N$个参与者，以及一个用于评估不同参与者合作收益的value function$v$, 且$v(\varphi )=0$。

Shapley value的目的就是根据各种不同的合作方式及其收益总结出每个人的贡献是多少？

考虑一个打工人的例子，假设资本家是$o$ owner,提供生成工具，没有他就不会有任何产出，然后有$m$个工人，那么player一共有
N = { o , w 1 , . . . , w m } \displaystyle N=\{o,w_{1} ,...,w_{m}\} N={o,w1​,...,wm​}. 针对不同的打工的队伍，他们生成价值可以用一个value function来衡量：

$$v(S)=\{\begin{array}{ll}mp,& \text{if }o\in S\\ 0,& \text{otherwise}\end{array}$$

这里$S\subseteq N$,$m$是 S \ { o } \displaystyle S\backslash \{o\} S\{o}的工人数量。现在我们想知道，每个player对这个生产价值$mp$的贡献。直觉上，资本家的贡献肯定是最大的，因为没了他不行，而工人的贡献则相对较少，有什么合理的方法来衡量每个人的贡献呢？

一个粗糙的想法是：每个player得到的回报（贡献）应该正比于他们的marginal contributions: v ( S ) − v ( S \ { i } ) \displaystyle v( S) -v( S\backslash \{i\}) v(S)−v(S\{i}).

换句话说，我们是在用“删除”的方法来评估一个人的贡献，但是，显然在不同的协作场景下，删除带来的差异很可能是不一样的，例如，

v ( N ) − v ( N \ { i } ) = { p if  i ≠ o m p if  i = o v( N) -v( N\backslash \{i\}){\displaystyle =\begin{cases} p & \text{if } i\neq o\\ mp & \text{if} \ i=o \end{cases}} v(N)−v(N\{i})={pmp​if i=oif i=o​

但是除了$N$还有很多可能不同的协作情况$S\subseteq N$，我们需要找到一个合理的权重分配方式，综合所有可能情况下的删除贡献，同时又让这个贡献满足一些比如对称性的性质。为此，shapley设计了几条公理，推导出了shapley value，用${\varphi }_i(v)$表示第i个player的贡献。

公理1(对称性,Symmetry):如果player $i,j$，不管什么 情况，他们value都是一样的， v ( S ∪ { i } ) = v ( S ∪ { j } ) \displaystyle v( S\cup \{i\}) =v( S\cup \{j\}) v(S∪{i})=v(S∪{j})，对于任意的不包含$i,j$的$S$都成立，则他们的贡献也应该是一样的，于是${\varphi }_i(N,v)={\varphi }_j(N,v).$

公理2（dummy players）: 如果player $i$无论怎样的value都是0， v ( S ∪ { i } ) = v ( S ) \displaystyle v( S\cup \{i\}) =v( S) v(S∪{i})=v(S)，则他的贡献也应该是0，${\varphi }_i=0$.

公理3（Additivity）: 如果这个博弈可以分解为2个，即$v=v_1+v_2$，那么对应的贡献也应该能分解${\varphi }_i(N,v_1+v_2)={\varphi }_i(N,v_1)+{\varphi }_i(N,v_2)$

基于以上公理，我们可以推导出shapley value，对于coalitional game$(N,v)$

ϕ i ( N , v ) = ∑ S ⊆ N \ { i } ∣ S ∣ ! ( ∣ N ∣ − ∣ S ∣ − 1 ) ! N ! [ v ( S ∪ { i } ) − v ( S ) ] = ∑ S ⊆ N ∖ { i } ( N 1 , ∣ S ∣ , n − ∣ S ∣ − 1 ) − 1 ( v ( S ∪ { i } ) − v ( S ) ) = 1 N ∑ S ⊆ N ∖ { i } ( N − 1 ∣ S ∣ ) − 1 ( v ( S ∪ { i } ) − v ( S ) ) = 1 number of players ∑ coalitions including  i marginal contribution of  i  to coalition number of coalitions excluding  i  of this size \begin{aligned} \phi _{i} (N,v) & =\sum _{S\subseteq \mathcal{N} \backslash \{i\}}\frac{|S|!(|N|-|S|-1)!}{N!}\Bigl[ v(S\cup \{i\})-v(S)\Bigr]\\ & {\displaystyle =\sum _{S\subseteq N\setminus \{i\}}\binom{N}{1,|S|,n-|S|-1}^{-1} (v(S\cup \{i\})-v(S))}\\ & ={\displaystyle \frac{1}{N}\sum _{S\subseteq N\setminus \{i\}}\binom{N-1}{|S|}^{-1} (v(S\cup \{i\})-v(S))}\\ & {\displaystyle =\frac{1}{\text{number of players}}\sum _{\text{coalitions including } i}\frac{\text{marginal contribution of } i\text{ to coalition}}{\text{number of coalitions excluding } i\text{ of this size}}} \end{aligned} ϕi​(N,v)​=S⊆N\{i}∑​N!∣S∣!(∣N∣−∣S∣−1)!​[v(S∪{i})−v(S)]=S⊆N∖{i}∑​(1,∣S∣,n−∣S∣−1N​)−1(v(S∪{i})−v(S))=N1​S⊆N∖{i}∑​(∣S∣N−1​)−1(v(S∪{i})−v(S))=number of players1​coalitions including i∑​number of coalitions excluding i of this sizemarginal contribution of i to coalition​​

可以证明这个shapley value是唯一的。他有几种不同但等价的表示方法，最直观的可能是最后一种，其核心思想是计算不同size下$S$的数量，于是其倒数则可以认为这个size下每个$S$所出现的概率，将其作为权重，然后又因为总权重加起来等于N所以除以N标准化一下。

我们来看下刚才资本家的例子，我们考虑 N = { o , w 1 , w 2 } \displaystyle N=\{o,w_{1} ,w_{2}\} N={o,w1​,w2​}，只有两个工人，一个资本家，于是

∣ S ∣ = 1 : v ( { o } ) = 0 , v ( { w 1 } ) = 0 , v ( { w 1 } ) = 0 ∣ S ∣ = 2 : v ( { o , w 1 } ) = p , v ( { o , w 2 } ) = p , v ( { w 1 , w 2 } ) = 0 ∣ S ∣ = 3 : v ( { o , w 1 , w 2 } ) = 2 p \begin{aligned} |S|=1 & :v(\{o\}) =0,v(\{w_{1}\}) =0,v(\{w_{1}\}) =0\\ |S|=2 & :v(\{o,w_{1}\}) =p,v(\{o,w_{2}\}) =p,v(\{w_{1} ,w_{2}\}) =0\\ |S|=3 & :v(\{o,w_{1} ,w_{2}\}) =2p \end{aligned} ∣S∣=1∣S∣=2∣S∣=3​:v({o})=0,v({w1​})=0,v({w1​})=0:v({o,w1​})=p,v({o,w2​})=p,v({w1​,w2​})=0:v({o,w1​,w2​})=2p​

于是，

ϕ o = 1 3 [ v ( { ϕ } ∪ { o } ) − v ( { ϕ } ) + 1 2 ( v ( { w 1 } ∪ { o } ) − v ( { w 1 } ) ) + 1 2 ( v ( { w 2 } ∪ { o } ) − v ( { w 2 } ) ) + v ( { w 1 , w 2 } ∪ { o } ) − v ( { w 1 , w 2 } ) ] = 1 3 [ 0 − 0 + 1 2 ( p − 0 + p − 0 ) + 2 p − 0 ] = p \begin{aligned} \phi _{o} & =\frac{1}{3}[ v(\{\phi \} \cup \{o\}) -v(\{\phi \})\\ & +\frac{1}{2}( v(\{w_{1}\} \cup \{o\}) -v(\{w_{1}\})) +\frac{1}{2}( v(\{w_{2}\} \cup \{o\}) -v(\{w_{2}\}))\\ & +v(\{w_{1} ,w_{2}\} \cup \{o\}) -v(\{w_{1} ,w_{2}\})]\\ & =\frac{1}{3}\left[ 0-0+\frac{1}{2}( p-0+p-0) +2p-0\right] =p \end{aligned} ϕo​​=31​[v({ϕ}∪{o})−v({ϕ})+21​(v({w1​}∪{o})−v({w1​}))+21​(v({w2​}∪{o})−v({w2​}))+v({w1​,w2​}∪{o})−v({w1​,w2​})]=31​[0−0+21​(p−0+p−0)+2p−0]=p​

ϕ w 1 = 1 3 [ v ( { ϕ } ∪ { w 1 } ) − v ( { ϕ } ) + 1 2 ( v ( { o } ∪ { w 1 } ) − v ( { o } ) ) + 1 2 ( v ( { w 2 } ∪ { w 1 } ) − v ( { w 2 } ) ) + v ( { o , w 2 } ∪ { w 1 } ) − v ( { o , w 2 } ) ] = 1 3 [ 0 − 0 + 1 2 ( p − 0 + 0 − 0 ) + 2 p − p ] = p 2 \begin{aligned} \phi _{w_{1}} & =\frac{1}{3}[ v(\{\phi \} \cup \{w_{1}\}) -v(\{\phi \})\\ & +\frac{1}{2}( v(\{o\} \cup \{w_{1}\}) -v(\{o\})) +\frac{1}{2}( v(\{w_{2}\} \cup \{w_{1}\}) -v(\{w_{2}\}))\\ & +v(\{o,w_{2}\} \cup \{w_{1}\}) -v(\{o,w_{2}\})]\\ & =\frac{1}{3}\left[ 0-0+\frac{1}{2}( p-0+0-0) +2p-p\right] =\frac{p}{2} \end{aligned} ϕw1​​​=31​[v({ϕ}∪{w1​})−v({ϕ})+21​(v({o}∪{w1​})−v({o}))+21​(v({w2​}∪{w1​})−v({w2​}))+v({o,w2​}∪{w1​})−v({o,w2​})]=31​[0−0+21​(p−0+0−0)+2p−p]=2p​​

类似的${\varphi }_{w_2}=\frac{p}{2}$，可以发现${\varphi }_o+{\varphi }_{w_1}+{\varphi }_{w_2}=v(N)=2p$. 而且资本家的贡献比打工人要多，符合我们的直觉。

Shapley value在机器学习任务上可解释性的运用

如果我们将value function看做是机器学习模型，那么$N$就是模型某个样本输入，在可解释性任务中，我们一般需要去解释某个样本各个“取值”的贡献，也就是去解释$N$中每个维度的贡献。如果我们按照shapley value的计算方式，我们就需要去取$S\subseteq N$子集，然而一个机器学习模型无法真的输入一个子集，所以我们只能对那些被“删除”的取值设置一个baseline，比如均值，零值等等，如何选baseline也是一门学问，已经有很多相关的论文[5]。

使用shapley value的好处是，它有效建模了不同取值间的交互效应，并在此基础上计算出了一个满足上述三个公理的贡献值。

参考资料

[1] interpretable-ml-book/shapley

[2] 能不能形象的介绍一下 shapley 值法？

[3] Rozemberczki B, Watson L, Bayer P, et al. The shapley value in machine learning[J]. arXiv preprint arXiv:2202.05594, 2022.

[4] Understanding The Shapley Value

[5] 可解释性：完善Shapley value理论体系，建模并学习基准值