SHAP算法

SHAP算法

参考链接Interpretable Machine Learning

• 什么是SHAP？

  考虑一个场景，两名玩家1，2共同参加比赛，这样能够获得$C_{12}=10000$的奖金；

  如果玩家1单独参赛，能够获得$C_{1}=7500$的奖金；

  玩家2单独参赛能获得$C_{2}=5000$的奖金。

  当然，没有人参赛的时候，则$C_{0}=0$。

  引入边际贡献，这表示，一个玩家加入这个比赛小组而增加的奖金。

  如果玩家1加入玩家2的小组，这会让小组多出$C_{12}-C_{2}=5000$的奖金；

  如果玩家1单独作战（加入没有人的小组），那么（这个没有人的小组）会多出$C_1-C_0=7500$的奖金；

  取这两个收益进行平均，得到$\frac{5000+7500}{2}=6250$，这就是玩家1的预期边际贡献。

  按同样的方式，玩家二的预期边际贡献为$\frac{(C_{12}-C1)+(C_2-C0)}{2}=3750$。

  玩家的预期边际贡献，即为SHAP值。实际上，这个值的大小，是玩家/对所有他能加入的联盟的贡献/的加权平均值。

• 那么，考虑下一个问题：如何“加权”？

  考虑一个更复杂的场景，玩家1，2，3在参加比赛。因此，共有8种可能的联盟组合。不妨如下定义各个联盟能够获得的奖金：

  $$\begin{aligned} C_{123}&=10000 \\ C_0&=0 \\ C_{12}&=7500 \\ C_{13}&=7500 \\ C_{23}&=5000 \\ C_1&=5000 \\ C_2&=5000 \\ C_3&=0 \end{aligned}$$

  通过加权，我们可以计算玩家1的SHAP值：

  

  这里的权重，代表着玩家做出相应的边界贡献（也就是加入相应的联盟）的概率。

  以计算$P(C_{123}-C_{23})$（也就是玩家1加入玩家2，3联盟）的概率为例：

  首先，需要计算出玩家1加入玩家2，3联盟的可能组合。

  显然，有1->(2,3)和1->(3,2)这两种组合。而由玩家1，2，3构成的联盟共有$3!=6$种组合方式。

  红头发为玩家1；黑人为玩家2；绿衣服为玩家3

  

  所以，$P(C_{123}-C_{23})=\frac{2}{6}$。

  计算$P(C_{12}-C_{2})$为例，此时只有一种情况1->(2)。

  

  所以，$P(C_{12}-C_{2})=\frac{1}{6}$。

• 公式推导

  推广到p人的场景：

  玩家i对联盟做出相应的边界贡献的权重为

  $$weight=\frac{|S|!*(p-|S|-1)!}{p!}$$

  • $p!$是p个玩家构成的联盟的排列组合方式

    $|S|$是已经加入联盟中的玩家数量，因此，$|S|!$是由这S名玩家的排列方式

    $p-|S|-1$是玩家i在加入这个联盟s后还必须要加入的玩家数量，因此，$(p-|S|-1)!$是剩余加入玩家的排列方式

  我们可以看出，权重的本质，是所有可能排列中，S内成员先加入、玩家i随后加入、最后加入剩余成员的概率

  而在这种情况下，玩家做出的边界贡献为

  $$val(S∪{i})-val(S)$$

  而考虑玩家i能够加入的联盟s，将$\frac{|S|!*(p-|S|-1)!}{p!}*[val(S∪{i})-val(S)]$取Σ，则得到玩家i的SHAP值。

  $$\phi_{i}=\sum_{S \subseteq P \setminus\{i \}} \frac{| S |! \cdot( p-| S |-1 )!} {p!} \left[ f_{x} ( S \cup\{i \} )-f_{x} ( S ) \right]$$

• 机器学习中的SHAP分析

  术语对应：

  联盟里的玩家->参与预测的特征变量

  联盟获得的奖金->预测模型的结果

  联盟S的”值” -> 基于S的预测期望val(S)

  $$v a l_{x} ( S )=\mathbb{E}_{X_{\notin S}} [ f ( x_{S}, X_{\notin S} ) ]=\int f ( x_{S}, X_{\notin S} ) d P ( X_{\notin S} )$$

  其中，$x_S$是S中特征的观测值；$X_{\notin S}$是非S特征的随机变量，而$d P ( X_{\notin S} )$是非S特征的联合概率分布。

  这表示，特征联盟S的值是模型对/S中没有的所有特征变量/进行边缘化后的期望值。这里的“边缘化”，是指对非S特征的联合分布求期望，这可以通过积分(离散)或求和(离散)实现。“边缘化”的意义，是消除非S特征的影响，通过积分（或期望）将其”平均掉”，反映S特征的独立贡献。

TimeSHAP

相关资料

[TimeSHAP：通过序列扰动解释递归模型-Feedzai 技术博客.html](..\参考资料\TimeSHAP：通过序列扰动解释递归模型-Feedzai 技术博客.html)

TimeSHAP：通过序列扰动解释递归模型.html

[SHAP-Interpretable Machine Learning.html](..\参考资料\SHAP-Interpretable Machine Learning.html)

• 前置知识：kernelSHAP

  直接计算Shapley值需遍历所有 $2^p$ 个子集，计算复杂度为指数级。KernelSHAP 通过以下方法近似：

  • 仅采样部分特征子集；
  • 将Shapley值转换为线性回归问题，利用核函数逼近理论值。

  将Shapley值求解转化为优化问题：

  $$\min_{\phi_0, \phi_1, ..., \phi_p} \sum_{z' \in Z} \left[ f(h_x(z')) - \left( \phi_0 + \sum_{i=1}^p \phi_i z_i' \right) \right]^2 \cdot \pi_{x'}(z')$$

  其中：

  • $z' \in \{0,1\}^p$ 是二进制向量（1表示特征存在，0表示缺失）。

  • $h_x(z')$ 将 $z'$ 映射到原始特征空间（缺失特征用背景数据填充）。

  • 核函数 $\pi_{x'}(z')$ 定义为：

    $$\pi_{x'}(z') = \frac{(p-1)}{\binom{p}{|z'|} \cdot |z'| \cdot (p - |z'|)}$$

    这里 $|z'|$ 是子集大小，核函数的设计使得回归结果逼近Shapley值的权重。

  关于核函数，他的作用是通过调整不同子集的权重，使得回归结果符合Shapley值的权重分配。

  而线性模型，是假设Shapley值可表示为线性组合 $\phi_0 + \sum \phi_i z_i'$，通过加权最小二乘法求解。

  如何计算一个特征变量的shap值呢？

  1. 生成扰动样本：

     • 对输入实例 $x$，生成 $m$ 个二进制向量 $z' \in \{0,1\}^p$，每个元素表示对应特征是否“存在”。
     • 例如，$z' = (1,0,1)$ 表示包含第1、3个特征，缺失第2个。

  2. 映射到原始特征空间：

     • 对每个 $z'$，缺失特征用背景数据集（如训练集均值）填充，得到完整样本 $h_x(z')$。
     • 例如，若特征2缺失，则用背景数据的均值替代。

  3. 获取模型预测：

     • 计算每个扰动样本的预测值 $f(h_x(z'))$，得到目标变量 $y = [f(h_x(z'_1)), ..., f(h_x(z'_m))]$。

  4. 构建回归问题：

     • 设计矩阵 $Z$，每行对应一个 $z'$，增加一列1（截距项 $\phi_0$）。
     • 核权重矩阵 $W$ 为对角矩阵，元素为 $\pi_{x'}(z')$。

  5. 求解加权线性回归：

     • 通过解析解计算Shapley值：
       $\phi = (Z^T W Z)^{-1} Z^T W y$
     • 其中 $\phi = [\phi_0, \phi_1, ..., \phi_p]^T$。

  示例：

  • 若 $p=3$，生成 $z'=(1,0,1)$，填充缺失特征后输入模型得到预测值。
  • 回归方程：$f(z') \approx \phi_0 + \phi_1 \cdot 1 + \phi_2 \cdot 0 + \phi_3 \cdot 1$。
  • 通过大量样本的加权拟合，最终解得 $\phi_i$。