机器学习现在是以迅雷不及盗铃之势席卷了几乎所有科技、商业、医疗、生活领域,基于gbdt的各种优化以及ensemble横扫所有数据竞赛,cnn则是霸榜图像领域。看起来,时代已经变了。但,等等,还有一个问题,设想一下,当你的模型用于医疗领域,你用了一个极深的神经网络,然后告诉用户很可能得了癌症,那么,为什么呢?为什么要相信你呢?你是不是应该给出一个合理的解释呢?你该如何给出一个合理的解释呢?(另一个相似的领域大概就是无人车了)


通常对于大多数基于机器学习的项目,我们只注重结果,而不注重可解释性。但人毕竟不是机器,要说服人相信机器比人做的更好,至少在现在这个阶段,解释显得尤为重要。然而,这方面的研究,相比层出不穷的各种花式神经网络连接方式,显然落伍太多。

这里介绍一个机器学习的通用归因算法:shap value

项目git地址:https://github.com/slundberg/shap <https://github.com/slundberg/shap>
,深度支持xgboost、lightgbm等火得发烫的模型,目前近900star,可以的。

Shapley value起源于博弈论:n个人合作,创造了v(N)的价值,如何对所创造的价值进行分配。
notation: 全集N={x1,x2,⋯,xn}
有n个元素xi,任意多个人形成的子集S⊆N,有v(S)表示S子集中所包括的元素共同合作所产生的价值。最终分配的价值(Shapley
Value)ψi(N,v)其实是求累加贡献(marginal
contribution)的均值。例如A单独工作产生价值v({A}),后加入B之后共同产生价值v({A,B}),那么B的累加贡献为v({A,B})−v({A})。对于所有能够形成全集N的序列,求其中关于元素xi的累加贡献,然后取均值即可得到xi的Shapley
Value值。但枚举所有序列可能性的方式效率不高,注意到累加贡献的计算实际为集合相减,对于同样的集合计算次数过多是效率低下的原因。公式中S表示序列中位于xi前面的元素集合,进而N∖S∖{xi}表示的是位于xi后面的元素集合,而满足只有S集合中的元素位于xi之前的序列总共有|S|!(|N|−|S|−1)!个,其内序列中产生的xi累加贡献都是v(S⋃{xi})−v(S);最后对所有序列求和之后再取均值。
假设特征全集为F,则有:


求得每一维特征的shapley value值,值越大对目标函数的影响越正向,值越小对目标函数的影响越负向。

API
注意LightGBM中有内嵌的接口,
lightgbm.Booster.predict(data, pred_contrib=True)
Xgboost中也是如此,
xgboost.Booster.predict(data, pred_contribs=False)

复杂度
问题似乎已经解决了,但,让我们来看一下复杂度,外层循环遍历所有可能的特征组合O(TL2N)O(TL2N)
,其中T是树的数量,L是最大叶子节点数,N是特征数,下面将要出现的D是树的最大深度,总体来说复杂度是指数级的。。。
于是,在这篇 paper中(https://arxiv.org/pdf/1706.06060.pdf
<https://arxiv.org/pdf/1706.06060.pdf>
),针对ensemble的树模型提出了一种指数级优化到多项式级的算法,对平衡树复杂度可达O(TLlog2L)O(TLlog2L) ,对非平衡树为O(TLD2)O
(TLD2) 。

二阶情形
对于树类模型,由于其隐含了特征组合,通常我们还希望知道模型对于二阶组合特征的归因。

如上,二阶shap(i, j)可以看作当feature j是否存在时feature i的shap value 之差,于是所有关于j的二阶组合复杂度为O(TL
D2)O(TLD2),总复杂度达到O(TMLD2)O(TMLD2),其中M为特征数。

二阶归因在xgboost中也有实现,xgboost.Booster.predict()中参数predict_interactions=True即可,输出矩阵size为(nsample,
nfeats + 1, nfeats + 1),最后一行和最后一列为偏置项。