[轻笔记] SHAP值的计算步骤

SHAP值的主要思想来自合作博弈论（coalitional game theory）中的Shapley值。Shapley值由Shapley在1953年提出，用来对玩家贡献进行评估，从而分配收益的一种方法。在机器学习中，SHAP值被用来解释学习模型对某一输入状态的各特征值对预测输出的贡献（重要程度）。本文主要记录SHAP的计算步骤。

定义（联盟）：假定状态空间为$n$维，标记为 A = { x 1 , x 2 , . . . , x n } A=\{x_1, x_2, ..., x_n\} A={x1​,x2​,...,xn​}，我们此时要估计第$i$个特征对预测输出的贡献，若有一集合$S$满足$S\subset A$且$x_i\notin S$，假定有一样本${\mathbf{x}}_k=[x_1=a_1,x_2=a_2,...,x_n=a_n]$，则称 S a = { x j = a j , ∀ j ∈ S } S_a=\{x_j=a_j, \forall j\in S\} Sa​={xj​=aj​,∀j∈S}为特征$x_i=a_i$的一个联盟。

举例：假定有一样本${\mathbf{x}}_k=[x_1=a_1,x_2=a_2,...,x_n=a_n]$，我们要评估$x_2$的SHAP值，当 S = { x 1 , x 3 } S=\{x_1, x_3\} S={x1​,x3​}时有联盟 S a = { x 1 = a 1 , x 3 = a 3 } S_a=\{x_1=a_1, x_3=a_3\} Sa​={x1​=a1​,x3​=a3​}。

定义（在联盟$S_a$下，$x_i=a$的贡献）：假定$S_a$为$x_i$的一个联盟，则在该联盟下，$x_i=a_i$的贡献定义如下：

E x j ∼ X j , ∀ j ≠ i 且 x j ∉ S ( f ^ ( S a ∪ { x i = a i } ∪ { x j } ) ) − E x j ∼ X j , ∀ x j ∉ S ( f ^ ( S a ∪ { x j } ) ) (1) E_{x_j \sim X_j, \forall j\neq i 且 x_j\notin S}(\hat{f}(S_a\cup \{x_i=a_i\} \cup \{x_j\}))-E_{x_j \sim X_j , \forall x_j \notin S} (\hat{f}(S_a\cup \{x_j\}))\tag{1} Exj​∼Xj​,∀j=i且xj​∈/S​(f^​(Sa​∪{xi​=ai​}∪{xj​}))−Exj​∼Xj​,∀xj​∈/S​(f^​(Sa​∪{xj​}))(1)
其中,$X_j$为生成特征$x_j$的分布函数。

式（1）可以简写成 v a l ( S a ∪ { x i } ) − v a l ( S a ) val(S_a\cup\{x_i\})-val(S_a) val(Sa​∪{xi​})−val(Sa​)，$va{l}_x(S_b)$是子集$S_b$的预测值在未包含$S_b$中的特征上的期望。

定义（SHAP值）：SHAP值是特征$x_i$所有可能联盟下的贡献的加权和，形式如下：

ϕ i ( v a l ) = ∑ S ∪ A 且 x i ∉ S ∣ S ∣ ! ( n − ∣ S ∣ − 1 ) ! n ! ( v a l ( S a ∪ { x i } − v a l ( S a ) ) (2) \phi_i(val)=\sum_{S\cup A 且 x_i\notin S}\frac{|S|!(n-|S|-1)!}{n!}(val(S_a\cup\{x_i\}-val(S_a))\tag{2} ϕi​(val)=S∪A且xi​∈/S∑​n!∣S∣!(n−∣S∣−1)!​(val(Sa​∪{xi​}−val(Sa​))(2)

举例：假定有数据集$D=\{({\mathbf{x}}_1,y_1),({\mathbf{x}}_2,y_2),...,({\mathbf{x}}_m,y_m)\}$，$m$为数据个数。假定该数据状态有4维，标记为 { x 1 , x 2 , x 3 , x 4 } \{x_1, x_2, x_3, x_4\} {x1​,x2​,x3​,x4​}。经过该数据集，我们训练得到一模型$\hat{f}$，我们现在想查看某一样本 x i = { x 1 = 3 , x 2 = 5 , x 3 = 9 , x 4 = 1 } \mathbf{x}_i=\{x_1=3, x_2=5, x_3=9, x_4=1\} xi​={x1​=3,x2​=5,x3​=9,x4​=1}中第2个特征对预测结果$\hat{f}({\mathbf{x}}_i)$的贡献。

• step 1：确定$x_2=5$所有可能的联盟总共有8个，如下所示
  $S_1=\varnothing$
  S 2 = { x 1 = 3 } S_2=\{x_1=3\} S2​={x1​=3}
  S 3 = { x 3 = 9 } S_3=\{x_3=9\} S3​={x3​=9}
  S 4 = { x 4 = 1 } S_4=\{x_4=1\} S4​={x4​=1}
  S 5 = { x 1 = 3 , x 3 = 9 } S_5=\{x_1=3, x_3=9\} S5​={x1​=3,x3​=9}
  S 6 = { x 1 = 3 , x 4 = 1 } S_6=\{x_1=3, x_4=1\} S6​={x1​=3,x4​=1}
  S 7 = { x 3 = 9 , x 4 = 1 } S_7=\{x_3=9, x_4=1\} S7​={x3​=9,x4​=1}
  S 8 = { x 1 = 3 , x 3 = 9 , x 4 = 1 } S_8=\{x_1=3, x_3=9, x_4=1\} S8​={x1​=3,x3​=9,x4​=1}

• step 2：对于所有的联盟利用式（1）计算其对预测结果的贡献，以 S 2 = { x 1 = 3 } S_2=\{x_1=3\} S2​={x1​=3}为例
  从数据集$D$中随机采样$K$次，获得了$K$个数据样本，对于每个样本${\mathbf{x}}_a=[x_1=a_1,x_2=a_2,x_3=a_3,x_4=a_4]$做如下操作：
  a) 保持联盟中的特征$x_1$,要求贡献的特征$x_2$与${\mathbf{x}}_a$中的对应特征的值相等，计算$\hat{f}(x_1=3,x_2=5,x_3=a_3,x_4=a_4)$；
  b)仅保持联盟中的特征$x_1$，其它与${\mathbf{x}}_a$中的对应特征的值相等，计算$\hat{f}(x_1=3,x_2=a_2,x_3=a_3,x_4=a_4)$；
  c)计算$v_k=\hat{f}(x_1=3,x_2=5,x_3=a_3,x_4=a_4)-\hat{f}(x_1=3,x_2=a_2,x_3=a_3,x_4=a_4)$
  计算完得到$K$个$v_k,k=1,2,...,K$，取平均$v(S)=\frac{1}{K}{\sum }_{k=1}^K{v}_k$近似式(1)。

• step 3：根据$\frac{|S|!(n-|S|-1)!}{n!}$计算各联盟的权值如下
  $S_1:\frac{1}{4}$
  $S_2:\frac{1}{12}$
  $S_3:\frac{1}{12}$
  $S_4:\frac{1}{12}$
  $S_5:\frac{1}{12}$
  $S_6:\frac{1}{12}$
  $S_7:\frac{1}{12}$
  $S_8:\frac{1}{4}$

• step 4：对计算得到的$v(S_i),i=1,2,....,8$按以上权值进行加权求和得到$x_2=5$对于$\hat{f}({\mathbf{x}}_i$的预测结果的SHAP值。
  ${\varphi }_2(val)=\frac{1}{4}v(S_1)+\frac{1}{12}v(S_2)+\frac{1}{12}v(S_3)+\frac{1}{12}v(S_4)+\frac{1}{12}v(S_5)+\frac{1}{12}v(S_6)+\frac{1}{12}v(S_7)+\frac{1}{4}v(S_8)$。

END