模型解释–Shapley Values

简介

这一篇文章会介绍Shapley Values来进行模型的解释. 这种方法是基于coalitional game theory的理论. 这种方法假设每一个变量扮演一场游戏中的一个角色, 这个变量对最后结果的影响(贡献).

我们可以考虑这样一个简单的例子, 当团队里只有Ava的时候, 团队获得的收益是5. 随后Bill加入团队, 此时团队的收益是9, 也就是Bill给团队带来了4的收益. 最后, Christine加入团队, 此时团队的收益是11, 也就是Christine给团队带了2的收益. 那么最后每个人获得的收益就是(5, 4, 2), 可以理解为每一个player的边际收益.

但是这样的做法存在一个问题, 这样计算出来的边际收益是与加入的顺序是有关系的. 如果说Bill和Christine有相似的能力, 那么谁先进来, 后进来的人就没什么可以做了. 此时先来的人获得的收益就会高. 但是实际上, 所有人是一起加入的, 此时应该如何来分配收益.

下面就是对上面的问题进行详细的介绍. 这一篇文章主要会分为下面几个部分进行介绍:

• Shapley Values的两个例子(我们从两个例子来理解Shapley Value)
• 理解Shapley Value的计算公式

Shapley Values的两个例子

参考链接

• 能不能形象的介绍一下 shapley 值法？
• Interpreting your deep learning model by SHAP

例子一--程序员分配奖金

假设有一个程序C=100行代码需要编写, 今天产品经理找了三个程序猿来完成, 按照完成量发奖金. 每一个程序员单独完成与相互合作的效率如下(完整的见下图的表示):

• L程序猿单独完成可以完成10行代码
• M程序猿单独完成可以完成30行代码
• N程序猿单独完成可以完成5行代码
• L和M合作可以完成50行代码
• ...

此时, 会有3!(6种)合作的可能性会发生, 分别如下:

• L邀请M形成组织S，M邀请N进入组织S
• L邀请N形成组织S ，N邀请M进入组织S
• M邀请L形成组织S ，L邀请N进入组织S
• … …

对于每一种合作的方式, 我们考虑他们的边际收益, 即某人加入组织前后的收益变化. 下面的式子表示表示i加入集合S后的边际贡献, 我们需要罗列出S所有的可能性.

我们说一下具体的例子, 比如说我们要计算L的贡献值, 那么所有S可能的集合有:

• S为空集
• S中只有一个元素, 可以是M, 或是N
• S中有两个元素, 可以是M+N

共有5种可能性. 我们要分别计算着5种情况下的边际收益(我们需要注意到的是, 这5种情况不是等可能出现的, ), 所以对于每一个人的收益的计算过程如下所示, 我们只是改变了加入的顺序而已.

最后我们计算所有可能性下的收益的平均值, 就是某个人的贡献, 即Shapley Value. 计算结果如下所示.

我们这里需要注意的是, 这里三个人的Shapley Value的和是100, 这里的Shapley Value表示的就是每个人完成的代码量(对于总的100的贡献度).

例子二--拼车价格的计算

下面我们看第二个例子, 计算合理的拼车价格.

假设有A,B,C三位好友看完话剧准备拼车回家，拼车总价18元. 如果不拼车A回家需要6元、B需要11元、C需要15元。(A-C是11). 其余每一段的价格如下图所示, 问如何定价是最合理的.

所有上车的顺序一共有6种情况, 分别如下所示, 这里虽然有6种情况, 但是其实三个人是一起上车的:

于是对应上面每一种的上车的情况, 我们计算出每一种情况下A, B, C各需要支付多少. 每个人需要支付的如下表所示.

我们做一下简单的解释, 我们选取上面的一个例子来进行解释, 假设现在上车的顺序是B-C-A(不要被这里的上车顺序所迷惑, 我们可以想象他们是在一个地方上车的, 只不过在一个地方上车的顺序不一样). 还是继续解释上面的例子, 上车的顺序是B-C-A.

• 当B上车的时候, B需要支付11元, 因为此时B直接回去, 那么价格为11.
• 接着C上车, 开车的顺序是B-C, 这时候总的价格为11+6(因为从B到C处需要6元), 相当于C需要多支付6元.
• 最后A上车, 开车的顺序是A-B-C(不管上车顺序如何, 开车的顺序都是A-B-C), 最终的价格为18, 所以此时B需要支付18-17=1元.
• 这个就是对应上面的第四行计算出来的值.

Shapley Value的计算公式

下面我们理解一下Shapley Value的具体的计算公式. 大部分情况下, 我们看Shapley Value的计算公式的时候, 会看到下面的表达式.

这里是我们需要计算特征i的重要程度. 前面一部分表示的是权重, 后面一部分表示的是新增特征i前后的变化值. 我们还是看一个例子.

• 例如, 现在有5个player, ABCDE, 我们现在要计算C的收益
• 那么对于C来说, 加入的顺序无论是ABC或是BAC对于C来说都是一样的, 对于C来说, 前面AB的顺序和他没有关系.
• 所以我们可以使用集合来进行计算, 计算集合(AB)的收益和(ABC)的收益, 从而可以计算出C的收益, 即f(ABC)-f(AB).
• f(ABC)和f(AB)我们都是可以直接计算出来的, 但是我们需要对每一个集合加权重, 权重的大小与子集中包含的所有的序列顺序有关.
• 对于前面的例子，我们不仅要考虑C前面的可能的组合, AB, 或是BA, 也要考虑C后面的可能DE或是ED
• 所以对于上面的例子有4种可能性, ABCDE, ABCED, BACDE, and BACED (这就是上面公式中权重的由来)

我们再看一下上面的例子和公式结合来进行讲解.

具体计算过程

我们用上面的程序员分配奖金的情况, 来具体算一下程序员M可以被分配到的奖金. 下图是每一种情况下的效率.

我直接将计算的过程以图片的形式贴在这里了.

Shapley Value的性质

这里介绍Shapley Value的三个性质.

• 如果一个player没有带来任何收益, 他计算得到的收益应该是0(Dummy Player).
• 如果有两个player在任何一个子集中增加相同的收益，他们得到的收益也应该是一样的(Substitutability).
• 如果一个游戏是可以由两个子游戏组成, 那么我们分别计算收益相加和直接计算总的收益分配应该是一样的.(Additivity, 满足相加性)

证明链接: http://www.lamsade.dauphine.fr/~airiau/Teaching/CoopGames/2011/coopgames-7[8up].pdf

还有一些需要说明的是, Shapley Value的计算的时间复杂度是很大的. 同时对于一些缺失变量我们需要多次随机取样来计算平均值, 这样更加加大了运算量. (The Shapley value requires a lot of computing time. An exact computation of the Shapley value is computationally expensive because there are 2^k possible coalitions of the feature values and the "absence" of a feature has to be simulated by drawing random instances, which increases the variance for the estimate of the Shapley values estimation.)

最后, 我们总结一下, Shapley Value就是一个特征(player)在不同情况下对prediction的影响的平均值.