Shapley Values and SHAP

1. Shapley Values

1.1 General Idea

Ref: How shapley values work Shapley values 假设有一个机器学习模型 $model(A,B,C)$ 根据特征 $A, B, C$ 预测房价，假设某实例（$house1$）房价预测为24200元，Shapley值将量化它的每一个特征对预测房价 $p(house1)=24200$ 的贡献。其具体表达式如下

$$p(house_1) = b + shapley_A(house_1) + shapley_B(house_1) + shapley_C(house_1)$$

为了计算这些特征的Shapley值，我们必须考虑所有可能的特征组合的幂集，对于每个组合（coalition），我们使用学习到的机器学习模型重新预测房价，如下图所示，这些预测通过增量添加的特性从上到下连接起来，对于没有特征的预测，其预测结果总是数据集中的平均房价（22500）。 ![[Pasted image 20250619181802.png]] 通过加权求和这些边际贡献，我们可以计算出特征 $A$ 对于实例 $house1$ 的 Shapley 值，权重是每层连接数的倒数，注意，权重之和为1。

$$shapley_A(house1) = \frac{1}{3} \times 2200 + \frac{1}{6} \times 1200 + \frac{1}{6} \times 8400 + \frac{1}{3} \times 600 \approx 2533.33$$

注：教材的思路和图中的边际贡献基本正确，但最终三个 Shapley 值存在数值不一致。按照图中明确给出的预测值和边际贡献，正确结果应约为： $\phi_A = 2533.33, \phi_B = 1233.33, \phi_C = -2066.67$ 而不是教材写的 $2,550、$1,250 和 -$2,100。

同样可以求得特征 $B$ 和特征 $C$ 对于实例 $house1$ 的 Shapley 值分别为 1233.33 和 -2066.67。实际房价和各个特征的 Shapley 值的关系等式成立。

$$24200 \approx 22500 + 2533.33 + 1233.33 - 2066.67$$

为了理解模型特征的全局重要性，可以计算平均 Shapley 值。

Shapley 值总是需要一个参考数据集，从中抽样来替代缺失的团队成员，可以使用所有的数据点，也就是所有的房屋实例，当前该房屋实例 $house1$ 是 $D$ 类房屋，也可以计算仅与其它同类的房屋进行比较的 Shapley 值，这减少了抽样和组合不切实际的值的问题。

1.2 Shapley value theory

我们感兴趣的是对每个特征如何影响一个数据点的预测，对于线性模型，容易计算单个效果。对于一个数据实例 $\mathbf{x}$ 线性模型的预测如下

$$\hat{f}(\mathbf{x}) = \beta_0 + \beta_1 x_1 + \cdots + \beta_p x_p$$

第 $j$ 个特征对预测 $\hat{f}(\mathbf{x})$ 的贡献 $\phi_j$ 为

$$\phi_j (\hat{f}) = \beta_j x_j - \beta_j \mathbb{E}[X_j]$$

其中 $\mathbb{E}[X_j]$ 是特征 $j$ 的平均效果估计，贡献是特征效果与平均效果之间的差值。如果我们加和该实例的所有特征贡献，计算结果如下

$$\begin{align} \sum_{j=1}^p \phi_j (\hat{f}) & = \sum_{j=1}^p \left(\beta_j x_j - \beta_j \mathbb{E}[X_j] \right)\\ & = \left(\beta_0 + \sum_{j=1}^p \beta_j x_j \right) - \left(\beta_0 + \sum_{j=1}^p \beta_j \mathbb{E}[X_j]\right) \\ & = \hat{f}(\mathbf{x}) - \mathbb{E}[\hat{f}(\mathbf{X})] \end{align}$$

这就是实例 $\mathbf{x}$ 的预测值减去平均预测值。

我们能对任何类型的模型都这样做吗？由于我们通常在其它类型的模型中没有类似的权重，因此需要一个不同的解决方案。合作博弈论给出了指导，通过其计算的 Shapley 值是为任何机器学习模型的单次预测计算特征贡献值的一种解决方案。

Shapley 值是通过一个关于玩家集合 $S$（所有不包含特征 $j$ 的特征子集） 的价值函数 $val$ 来定义的。

$$\phi_j(val) = \sum_{S\subseteq \{1,\dots,p\} \setminus \{j\} } \frac{\lvert S\rvert ! (p-\lvert S \rvert - 1)!}{p!} \left(val(S \cup \{j\}) - val(S) \right)$$

价值函数 $val_{\mathbf{x}}(S)$ 的定义

$$val_{\mathbf{x}}(S) = \int \hat{f}(x_1, \dots, x_p) \mathrm{d} \mathbb{P}_{X_C} - \mathbb{E}[\hat{f}(\mathbf{X})]$$

其中 $\mathbb{E}[\hat{f}(\mathbf{X})]$ 是模型在整个数据集上的平均预测值，$S$ 是我们关心的特征子集，$C$ 是所有不在 $S$ 中的其他特征（补集），这部分的意思是我们固定子集 $S$ 中特征的取值，然后对于团队之外的其他特征 $C$，我们用它们在整个数据集中的所有可能取值来进行积分。在实践中，这通常是通过蒙特卡洛采样来近似的：保持 $S$ 中特征值不变，从数据集中随机抽取多个样本来填充 $C$ 中特征的值，然后利用这些合成的样本输入模型得到多个预测，最后取这些预测的平均值。

所以 $val_{\mathbf{x}}(S)$ 的完整含义是：只知道特征子集 $S$ 的取值时，模型的期望预测值与模型的全局平均预测值之间的差值，它衡量了一个特征子集 $S$ 相比于一无所知时，能带来多少预测上的变化。

例子： 模型中有 4 个特征（$X_1, X_2, X_3, X_4$），我们要评估由 $x_1$ 和 $x_3$ 组成的子集 $S=\{1, 3\}$ 的价值 $val_{\mathbf{x}}(\{1, 3\})$，按照公式有

$$$$

Shapley 值是唯一满足效率性（Efficiency）、对称性（Symmetry）、哑元性（Dummy）和可加性（Additivity）这些性质的归因方法，这些性质合在一起可以被视为对公平报酬的定义。

效率性：特征贡献之和必须等于 $\mathbf{x}$ 的预测与平均预测之差。

$$\sum_{j=1}^p \phi_j = \hat{f}(\mathbf{x}) - \mathbb{E}[\hat{f}(\mathbf{X})]$$

对称性：如果两个特征值 $j$ 和 $k$ 对所有可能的联盟贡献相等，那么它们的贡献应该相同。

$$\begin{align} \text{if }val(S \cup \{j\}) = val(S \cup \{k\}) \quad \text{for all } S\subseteq \{1, \dots, p\} \setminus \{j, k\}, \quad \text{then } \phi_j = \phi_k \end{align}$$

哑元性：一个特征 $j$ 如果无论加入到哪个特征联盟，都不会改变预测值，那么它的 Shapley 值应为 0。

$$\text{if }val(S \cup \{j\}) = val(S ) \quad \text{for all } S\subseteq \{1, \dots, p\} \setminus \{j\}, \quad \text{then } \phi_j = 0$$

可加性：对于一个具有组合报酬 $val+val^+$ 的博弈，则总的 Shapley 值为

$$\phi_j + \phi_j^+$$

（简单来说，可加性意味着如果一个“游戏”可以被分解为多个子游戏的和，那么每个玩家在这个总游戏中的贡献（Shapley值），就等于他在所有子游戏中的贡献之和。）

1.3 Estimating Shapley values

要计算精确的 Shapley 值，必须评估所有可能的特征值联盟（集合）在包含和不包含第 $j$ 个特征时的情况。当特征数量稍多时，这个问题的精确解就变得棘手，因为可能的联盟数量会随着特征的增加而指数级增加。Štrumbelj（2014） 提出了一种使用蒙特卡洛采样的近似方法：

$$\hat{\phi}_j = \frac{1}{M} \sum_{m=1}^M \left(\hat{f}\left(\mathbf{x}_{+j}^{(m)} \right) - \hat{f}\left(\mathbf{x}_{-j}^{(m)} \right) \right)$$

其中 $\hat{f}\left(\mathbf{x}_{+j}^{(m)} \right)$ 是对 $\mathbf{x}$ 的预测，但其中随机数量的特征值被来自一个随机数据点 $\mathbf{z}$ 的特征值替换，除了特征 $j$ 的值保持不变。特征向量 $\hat{f}\left(\mathbf{x}_{-j}^{(m)}\right)$ 和 $\hat{f}\left(\mathbf{x}_{+j}^{(m)} \right)$ 几乎完全相同，唯一的区别是其特征 $j$ 的值 $x_j^{(m)}$ 也取自于抽样数据点 $\mathbf{z}$。

单个特征的近似 Shapley 值估算： 输出：第 $j$ 个特征的 Shapley 值。 需要：迭代次数 $M$，目标实例 $\mathbf{x}$，特征索引 $j$，数据矩阵 $\mathbf{X}$，以及机器学习模型 $f$。 对于所有 $m=1,\dots, M$： 从数据矩阵 $\mathbf{X}$ 中抽取一个随机实例 $\mathbf{z}$ 选择一个特征的随机排列 $\mathbf{o}$ 排列实例 $\mathbf{x}: \mathbf{x}_{\mathbf{o}} = (x_{(1)},\dots,x_{(j)},\dots,x_{(p)})$ 排列实例 $\mathbf{z}: \mathbf{z}_{\mathbf{o}}=(z_{(1)},\dots,z_{(j)},\dots,z_{(p)})$ 构建两个新实例 包含 $j$（注意 $j$ 后也需要替换为采样的特征值）：$\mathbf{x}_{+j}=(x_{(1)},\dots,x_{(j-1)},x_{(j)},z_{(j+1)},\dots,z_{(p)})$ 不含 $j$：$\mathbf{x}_{-j}=(x_{(1)},\dots,x_{(j-1)},z_{(j)},z_{(j+1)},\dots,z_{(p)})$ 计算边际贡献 $\phi_{j}^{(m)}=\hat{f}(\mathbf{x}_{+j})-\hat{f}(\mathbf{x}_{-j})$ 计算平均值作为 Shapley 值 $\phi_j(\mathbf{x})=\frac{1}{M}\sum_{m=1}^M \phi_j^{(m)}$

Shapley 值衡量的是，在某个特定的预测中，一个特征的“具体取值”将模型的最终预测结果，从“全体样本的平均预测结果（基线）”上推高或拉低了多少。

优点 坚实的理论基础：Shapley 值基于博弈论，并通过效率性、对称性、哑元性和可加性等公理保证了分配的公平性。这是它相对于 LIME 等其他方法的主要优势。 公平的分配：预测值与平均值之差被“公平地”在特征之间分配。 对比性：Shapley 值将一个预测与平均预测进行对比来解释它。在许多场景中，这比将预测与某个基线（如数据均为零）进行比较更有用。

局限性 计算成本高：Shapley 值的计算量非常大。在 99.9% 的现实世界问题中，只能计算近似解。精确计算 Shapley 值是 NP-难的。 容易被误解：Shapley 值很容易被错误地解读。一个特征值的 Shapley 值不是当我们从模型中移除该特征时的预测差异。Shapley 值的解释是：给定当前的特征值集合，一个特征值对预测值与平均预测值之差的贡献是 Shapley 值。 反事实场景不足：最近的一项研究（Bilodeau 等人，2024）表明，Shapley 值对反事实场景（例如，“如果我的收入更高，我的信用评分会是多少？”）的敏感性较低。例如，一个正的 Shapley 值并不意味着增加该特征值会增加预测值。相反，Shapley 值必须相对于用于估算的参考数据集来解释。 非稀疏性、只返回一个值、相关特征的问题

2. SHAP

精确计算 Shapley 值是一个 NP-hard 问题。对于一个有 N 个特征的模型，需要评估 $2^N$ 个可能的特征联盟。当特征数量稍多时（例如超过20个），这在计算上就变成了天文数字，完全不可行。Lundberg ( 2017 ) 提出的 SHAP (SHapley Additive exPlanations)是一种解释个体预测的方法，其能高效近似计算 Shapley 值，同时还提出了一个将 Shapley 值与 LIME 及其他事后归因方法联系起来的理论。

SHAP 的目标是通过计算每个特征对预测的贡献解释一个实例 $\mathbf{x}$ 的预测，SHAP 从联盟博弈论中计算 Shapley 值，数据实例的特征值充当联盟中的参与者。SHAP 带来的一个创新是，Shapley 值的解释被表示为一种可加性特征归因方法——一个线性模型。这种观点将 LIME 和 Shapley 值联系起来。

SHAP 将解释指定为

$$g(\mathbf{z}')=\phi_0 + \sum_{j=1}^M \phi_j z_j'$$

其中 $g$ 是解释模型，$\mathbf{z}'=(z_1', \dots, z_M')^{\top} \in \{0, 1\}^M$ 是联盟向量，$M$ 是最大联盟规模，$\phi_j \in \mathbb{R}$ 是特征 $j$ 的特征归因，即 Shapley 值。为了计算 Shapley 值，我们模拟只有一些特征值“存在”，而另一些则“不存在”。对于我们感兴趣的实例 $\mathbf{x}$，联盟向量 $\mathbf{x}'$ 是一个全为 1 的向量，即所有特征值都存在，公式简化为 $g(\mathbf{x}') = \phi_0 + \sum_{j=1}^M \phi_j$SHAP 描述了以下三个理想属性： 1、局部准确性（Local accuracy）

$$\hat f(\mathbf{x}) = g(\mathbf{x}')=\phi_0 + \sum_{j=1}^M \phi_j x_j'$$

如果定义 $\phi_0=\mathbb{E}[\hat f(X)]$ 并设所有 $x_j'$ 为 1，这就是 Shapley 的效率性属性

$$\hat f(\mathbf{x}) = \phi_0 + \sum_{j=1}^M \phi_j x_j' = \mathbb{E}[\hat f(X)] + \sum_{j=1}^M \phi_j$$

2、缺失性（Missingness）

$$x_j' = 0\Rightarrow \phi_j = 0$$

缺失性指出，一个缺失的特征其归因值为零。在联盟表示法中，要解释的实例的所有特征值 $x_j'$ 都应为 1，缺失性属性强制要求缺失特征的 Shapley 值为 0，在实践中，这仅与值为常数的特征有关。 3、一致性（Consistency） 令 $\hat f_{\mathbf{x}}(\mathbf{z}') = \hat f(h_{\mathbf{x}}(\mathbf{z}'))$ 且 $\mathbf{z}_{-j}'$ 表示 $z_j'=0$，对于任何两个模型 $\hat f$ 和 $\hat f'$，如果满足

$$\hat f_{\mathbf{x}}'(\mathbf{z}')-\hat f_{\mathbf{x}}'(\mathbf{z}_{-j}') \geq \hat f_{\mathbf{x}}(\mathbf{z}')-\hat f_{\mathbf{x}}(\mathbf{z}_{-j}')$$

对于所有输入 $\mathbf{z}'\in \{0, 1\}^{M}$，则

$$\phi_j(\hat f', \mathbf{x})\geq \phi_j(\hat f, \mathbf{x})$$

一致性属性指出，如果一个模型发生变化，使得一个特征值的边际贡献增加或保持不变（无论其他特征如何），那么其 Shapley 值也应增加或保持不变。

2.1 SHAP 估计

2.1.1 Kernel SHAP

KernelSHAP 是 SHAP 框架中最为核心和通用的算法之一。它的最大特点是模型无关性 (Model-Agnostic)，这意味着它可以应用于任何类型的机器学习模型（如神经网络、支持向量机、K近邻等），无论其内部结构多么复杂，只要我们能获取其输入和输出即可。

五个步骤

1. 采样联盟向量 $\mathbf{z}_k' \in \{0, 1\}^M, k \in \{1,\dots, K\}$。
2. 通过首先将 $\mathbf{z}_k'$ 转换为原始特征空间，然后应用模型 $\hat f: \hat f(h_{\mathbf{x}}(\mathbf{z}_k'))$，来获取每个 $\mathbf{z}_k'$ 的预测。
3. 使用 SHAP 核计算每个联盟 $\mathbf{z}_k'$ 的权重。
4. 拟合加权线性模型。
5. 返回 Shapley 值 $\phi_k$，即线性模型的系数。

我们可以通过重复抛硬币来创建一个随机联盟，直到我们得到一个由 0 和 1 组成的链。例如，向量 $(1,0,1,0)^{\top}$ 意味着有一个由第一个和第三个特征组成的联盟。$K$ 个采样的联盟成为回归模型的数据集，回归模型的目标是联盟的预测。

为了从特征值的联盟转换到有效的数据实例，我们需要一个函数 $h_{\mathbf{x}}(\mathbf{z}')=\mathbf{z}$，其中 $h_{\mathbf{x}}:\{0, 1\}^M \rightarrow \mathbb{R}^p$。函数 $h_{\mathbf{x}}$ 将 1 映射到我们想要解释的实例 $\mathbf{x}$ 的相应值，对于表格数据，它将 0 映射到我们从数据中采样的另一个实例的值。这意味着我们将“特征值不存在”等同于“特征值被数据中的随机特征值替换”。

对于表格数据的 $h_{\mathbf{x}}$ 将特征 $X_j$ 和 $X_{-j}$（其他特征）视为独立的，并对边际分布进行积分：

$$\hat f(h_{\mathbf{x}}(\mathbf{z}')) = \mathbb{E}_{X_{-j}}[\hat f(x_j, X_{-j})]$$

从边际分布中采样意味着忽略存在和不存在特征之间的依赖结构，因此 Kernel SHAP 与所有基于排列的解释方法一样，可能会给不太可能的实例赋予权重，导致结果变得不可靠。

如果我们从条件分布中采样，价值函数会改变，因此 Shapley 值作为解的博弈也会改变。结果，Shapley 值的解释也会不同，例如，一个可能根本没被模型使用的特征，在使用条件采样时，可能会有一个非零的 Shapley 值，否则会违反哑元性公理。

为了实现符合 Shapley 的加权，Lundberg 和 Lee 提出了 SHAP 核：

$$\pi_{\mathbf{x}}(\mathbf{z}') = \frac{(M-1)}{\binom{M}{\lvert\mathbf{z}'\rvert} \lvert \mathbf{z}'\rvert (M - \lvert \mathbf{z}' \rvert)}$$

$M$ 是最大联盟规模，$\lvert \mathbf{z}' \rvert$ 是实例 $\mathbf{z}'$ 中存在特征的数量，使用此核权重的线性回归可以产生 Shapley 值。其背后的直觉是：包含很少特征（例如只有1个）或很多特征（例如总特征数 M-1 个）的联盟，对于我们理解单个特征的独立贡献或边际贡献信息量最大，因此应该赋予高权重。包含接近一半特征（M/2 个）的联盟，信息量相对较小，因此赋予低权重。

我们有了数据、目标和权重，构建加权线性回归所需的一切都已具备

$$g(\mathbf{z}') = \phi_0 + \sum_{j=1}^M \phi_j z_j'$$

我们通过优化以下损失函数 $L$ 来训练线性模型 $g$

$$L(\hat f, g, \pi_{\mathbf{x}}) = \sum_{\mathbf{z}'\in \mathbf{Z}}\big[\hat f(h_{\mathbf{x}}(\mathbf{z}')) - g(\mathbf{z}') \big]^2 \pi_{\mathbf{x}}(\mathbf{z}')$$

由于我们处于线性回归的设置中，我们也可以利用回归的标准工具，例如可以添加正则化项来使模型稀疏（不过不确定由此产生的系数是否仍然是有效的 Shapley 值）。

2.1.2 TreeSHAP

Lundberg，Erion，和 Lee 提出了 TreeSHAP，这是 SHAP 的一个变体，适用于基于树的机器学习模型，如决策树、随机森林和梯度提升树。与精确的 KernelSHAP 相比，它将计算复杂度从 $O(TL2^M)$ 降低到 $O(TLD^2)$，其中 $T$ 是树的数量，$L$ 是任何树中的最大叶子数，$D$ 是任何树的最大深度。

TreeSHAP 有两个版本：“干预式”(Interventional) 计算经典的 Shapley 值。“路径依赖式”(Tree-path dependent) 计算类似于条件 SHAP 值的东西。shap Python 包中的原始实现曾经是路径依赖式版本，但现在是干预式版本。

2.1.3 Permutation Method

最高效的模型无关估计器是排列方法（Permutation Method），其思想是通过创建特征的排列组合，来巧妙地从联盟（coalitions）中进行抽样。

让我们来看一个例子，其中有四个特征值，分别是 $x_{\text{park}},x_{\text{cat}},x_{\text{area}},x_{\text{floor}}$。这些特征的一个随机排列会是 $(x_{\text{cat}},x_{\text{area}}, x_{\text{park}},x_{\text{floor}})$。基于这个排列，我们可以通过从左到右开始构建联盟来计算边际贡献

• 将 $x_{\text{cat}}$ 添加到 $\emptyset$（空集）
• 将 $x_{\text{area}}$ 添加到 $\{x_{\text{cat}} \}$
• 将 $x_{\text{park}}$ 添加到 $\{x_{\text{cat}},x_{\text{area}} \}$
• 将 $x_{\text{floor}}$ 添加到 $\{x_{\text{cat}},x_{\text{area}},x_\text{park} \}$ 同样地，也可以反向进行。每一次正向和反向的排列都会为每个特征提供两个边际贡献，假设有 $p!$ 种可能的特征排列，并且 $o(k)$ 是第 $k$ 个排列，那么特征 $j$ 的 Shapley 值可以计算为：

$$\hat \phi_j^{(i)} = \frac{1}{m} \sum_{k=1}^m \hat\Delta_{o(k),j}$$

项 $\hat \Delta_{o(k),j}$ 是第 $k$ 个边际贡献，这意味着我们可以将 Shapley 值计算为所有贡献的简单平均值，我们可以对排列进行抽样，然后仍然取其平均值，由于我们执行了正向和反向迭代，我们将 Shapley 值计算为

$$\hat \phi_j^{(i)} = \frac{1}{2m}\sum_{k=1}^m \left(\hat \Delta_{o(k),j} + \hat \Delta_{-o(k),j} \right)$$