高效的ShapValue计算 - TreeShap分析

最近的带货文写的有点多，感觉都快不会写技术文了……正好前两天在公司跟同事讨论到Shap value的一些计算细节，顺手整理成文，与大家一同交流。

Shap运作方式

Shap作为一个模型解释工具大家应该都已经很熟悉了。这里我们就不贴公式之类的了，大致讲一下运行流程。标准的shap运行逻辑大致如下：

我们有一个黑盒模型m，有一条需要预测解释的条目x，由a, b, c三个特征组成。我们如何获取到特征a在最终预测中的贡献度呢？ 首先引入一个概念， 特征的缺失和引入 。要了解特征贡献，一个直观的想法就是看某个特征在与不在对预测结果造成的影响。在shap里，特征“缺失”，一般的方法是在 所有样本中采样 ，去看这个特征如果随机选择一个值，模型输出如何。特征的“引入”，则表示这个特征使用了预测条目中的值，模型的输出如何。

接下来一个概念是看特征在不同阶段引入的边际贡献。也就是说a, b, c三个特征，a特征的贡献，要分别计算a作为第一个特征引入，作为第二个特征引入，作为第三个特征引入的边际贡献是多少。我们用a代表特征引入，a'代表特征缺失，具体计算如下：

1. 第一个特征引入，使用m(a, b', c') - m(a', b', c')得到边际贡献。
2. 第二个特征引入，使用1/2 * (m(a, b, c') - m(a', b, c')) + 1/2 * (m(a, b', c) - m(a', b', c))，得到边际贡献。可以看到作为第二个特征引入时有两种情况，所以这里分别乘以1/2。
3. 第三个特征引入，使用m(a, b, c) - m(a', b, c)得到边际贡献。
4. 最后再把三种情况分别乘以1/3加和，就是特征a的总体贡献。

要计算其它特征的贡献度，对b和c做同样的计算就可以。这里m(a', b', c')就是传说中的 base value ，加上三个特征的贡献度，正好得到最终的预测值。这也是shap的一个非常优良的特性，可加性。Shap在理论上还有一些其它优点，感兴趣的同学可以参考shap的论文： https:// dl.acm.org/doi/pdf/10.5 555/3295222.3295230 。

TreeShap的效率提升

背景资料

从上面的计算过程可以看到，shap可以作用于任何黑盒模型，但是计算复杂度非常高。首先特征在不同位置引入这个遍历，会达到 指数级 的复杂度。另外在估计特征缺失时，进行 多次采样 也需要多次触发模型预测过程。所以就有一些利用模型本身的特性来加速计算shap的方法。今天我们主要来看TreeShap的效率提升方法。相关参考资料如下：

TreeShap加速的论文也来自shap库的作者，具体可以参考这里： https:// arxiv.org/pdf/1706.0606 0.pdf

Shap库中调用的部分，注意解释运行时也有不同的模式，作者上述文章中的实现对应的是tree path dependent模式： https:// github.com/slundberg/sh ap/blob/master/shap/explainers/_tree.py

我们以lgb为例，可以看到库中只是简单的提交了一个original_model.predict(..., pred_contrib=True )，所以主要代码还是在lgb库中： https:// github.com/microsoft/Li ghtGBM/blob/master/src/io/tree.cpp

主要看TreeShap这个方法。注意这个方法的实现，其实也是这位shap库的作者，人家还是很硬核的，shap库的可视化做的非常漂亮，写cpp一样也是信手拈来，还发了几篇很有影响力的论文。一般学术成果要推广，能 实现高性能，高质量且易用的library 还是非常关键的一点。不过嘛，shap库里的Python代码质量还是有不少提升空间的……

利用树结构评估特征贡献

从前面shap的运行方式来看，我们在计算过程中，分别用模型预测了8种不同的的特征组合采样，来看特征边际贡献值。但树模型是如何进行判断和预测的方式，我们是非常明确的。在每个节点，树模型都会选择一个特征进行分裂，如果这个节点选择的特征，是“缺失”状态，那么对于这个特征的贡献度，我们可以理解为是左右两棵子树贡献度之和。如果这个节点选择的特征是“引入”状态，那么我们可以看这个特征值下我们会走到左节点还是右节点，贡献度完全由那个节点产生。这样我们可以从特征组合的黑盒角度转变为 从树的结构的角度 去计算各个特征的贡献度了，跟计算feature importance的想法类似。

这就是论文中提到的Algorithm 1的内容：

具体流程如下： 还是以a, b, c三个特征为例，如果把c特征设为“缺失”，那么样本就是a, b, c'，公式中的S就是(a, b)，代表存在的特征是哪些。

在算特征贡献度的时候，如果是叶子节点，则用的是w * vj，这个vj就是叶子节点的预测值，w是叶子节点的sample数量相比父节点的占比，这个看代码更清楚：

const double w = data_count(node);
// 先可以不用理会这个hot, cold fraction
const double hot_zero_fraction = data_count(hot_index) / w;
const double cold_zero_fraction = data_count(cold_index) / w;

如果是中间节点，先判断这个dj(split的特征索引)是不是属于S，按上面的例子，是如果这个节点的分裂条件是c，那么dj就不属于S，如果是a或者b，就属于。

如果属于S，就按照这个节点的threshold去分裂，分到左边，则采用左边节点(aj)的贡献度，分到右边，则采用右边节点(bj)的贡献度。

如果不属于，则更新左右两边的w，递归算完后加起来。这里公式写错了，右边应该是跟上面一样，换成bj。

利用algorithm 1，我们 去掉了原版计算shap过程中对缺失特征做的“采样”处理 ，提升了一部分效率。

利用遍历树进一步加速

有了algorithm 1之后，我们可以把不同特征组合方式输入进去来求得各个特征的贡献度，但特征组合仍然是2^M的指数级复杂度。这里一个很自然的想法就是我们不需要遍历特征组合情况，而 只要遍历树的路径的所有可能 即可，在遍历过程中把计算的path信息记录下来，然后在叶子节点就能计算出这条path的特征贡献信息。这就是作者在文中提出的Algorithm 2的大致思路。

例如某个节点x，使用了特征a来做分裂条件，那么在经过这个节点时，不管特征组合如何变化，只可能有特征a的存在与缺失两种情况，这也是对应到代码中的one path和zero path的fraction。

phi[el.feature_index] += w*(el.one_fraction - el.zero_fraction)*leaf_value_[~node];

叶子节点的这个计算，就对应上了原版shap中的红框部分：

作者代码里还有hot, cold index，看着有点confuse，其实就是根据特征决策走的哪个节点，true就是hot，否则就是cold，这会跟Algorithm 1里的aj, bj部分对应上。

const int hot_index = Decision(feature_values[split_feature_[node]], node);
const int cold_index = (hot_index == left_child_[node] ? right_child_[node] : left_child_[node]);

论文中Algorithm 2的伪代码的流程还挺复杂的，核心是这一块：

其中extend就是去增长path，更新zero, one fraction等信息，还比较直观。Unwind这个是判断path中是否已经对这个feature做过split了，如果是的话就undo掉，在这个节点再做split，我个人理解是对path中保留的feature信息做了合并，也就是路径中可能对a特征有多次的使用，但最后在看贡献度时，我们会把多次操作的zero, one fraction信息合并在一起。这样复杂度会从节点数的平方降低到 树的深度的平方 。这块的详细代码比较复杂，我们这边就不做深入展开，只需要了解大致的思路即可。

其它模型实现

Shap库中还有很多其它模型的优化实现，比如对于深度神经网络，有利用gradients特性的DeepExplainer，对于黑盒模型，也有优化了运算速度的KernelExplainer等，有兴趣的同学可以进一步深入学习。

另外Shapley的应用也不局限于模型解释，例如在滴滴拼车这类cost sharing问题上，也能见到它的身影。博弈论相关的思想，对于解决很多实际商业问题都很有借鉴意义，值得深入了解。

问题

这个方法看上去很美好，但实际看现在的shap库的运行时的默认方法，用的是 feature_perturbation='interventional' 模式，这种模式下必须传入backgroupd data才行。 具体的原因可以看这个github issue，做了很好的总结： what's the difference between feature_perturbation="interventional" and feature_perturbation="tree_path_dependent" · Issue #1098 · slundberg/shap

简单来说，我们在文中分析的方法，计算的是通过条件概率 E[f(x)|x_s] 的形式去获取到特征的贡献度，从而可能导致一些模型并没有explicitly使用的特征被赋予一些贡献度(参考这篇文章中的例子)。而一些批评者认为从因果模型角度看，我们更应该使用 E[f(x)|do(X = x_s)] 的形式来构建shap解释的过程。所以目前的默认模式更符合这种因果的观点，从background data去做特征数值的采样达到 do(X = x_s) 的效果。

另外一个观点是true to the data和true to the model的trade-off，如作者所说：

I view it as a fundamental trade-off between being "true to the data" and never providing inputs that are off-manifold, and being "true to the model" and never letting credit bleed between correlated features.

这篇论文给了一些例子，讲解我们如何在这两种模式中做出选择： https:// arxiv.org/pdf/2006.1623 4.pdf

因果模型也是个非常有意思的话题，之后我们有时间再做进一步的分析讲解 :)