摘要
這一篇文章主要介紹模型解釋的一種方法, Shapley Value. 這里會(huì)介紹這種方法的原理, 對(duì)其公式進(jìn)行介紹. 同時(shí)會(huì)舉兩個(gè)例子來進(jìn)行詳細(xì)的解釋.
簡(jiǎn)介
這一篇文章會(huì)介紹Shapley Values來進(jìn)行模型的解釋. 這種方法是基于coalitional game theory的理論. 這種方法假設(shè)每一個(gè)變量扮演一場(chǎng)游戲中的一個(gè)角色, 這個(gè)變量對(duì)最后結(jié)果的影響(貢獻(xiàn)).
我們可以考慮這樣一個(gè)簡(jiǎn)單的例子,?當(dāng)團(tuán)隊(duì)里只有Ava的時(shí)候, 團(tuán)隊(duì)獲得的收益是5. 隨后Bill加入團(tuán)隊(duì), 此時(shí)團(tuán)隊(duì)的收益是9, 也就是Bill給團(tuán)隊(duì)帶來了4的收益. 最后, Christine加入團(tuán)隊(duì), 此時(shí)團(tuán)隊(duì)的收益是11, 也就是Christine給團(tuán)隊(duì)帶了2的收益. 那么最后每個(gè)人獲得的收益就是(5, 4, 2), 可以理解為每一個(gè)player的邊際收益.
但是這樣的做法存在一個(gè)問題, 這樣計(jì)算出來的邊際收益是與加入的順序是有關(guān)系的. 如果說Bill和Christine有相似的能力, 那么誰(shuí)先進(jìn)來, 后進(jìn)來的人就沒什么可以做了. 此時(shí)先來的人獲得的收益就會(huì)高. 但是實(shí)際上, 所有人是一起加入的, 此時(shí)應(yīng)該如何來分配收益.
下面就是對(duì)上面的問題進(jìn)行詳細(xì)的介紹. 這一篇文章主要會(huì)分為下面幾個(gè)部分進(jìn)行介紹:
Shapley Values的兩個(gè)例子(我們從兩個(gè)例子來理解Shapley Value)
理解Shapley Value的計(jì)算公式
Shapley Values的兩個(gè)例子
參考鏈接
Interpreting your deep learning model by SHAP
例子一--程序員分配獎(jiǎng)金
假設(shè)有一個(gè)程序C=100行代碼需要編寫,?今天產(chǎn)品經(jīng)理找了三個(gè)程序猿來完成, 按照完成量發(fā)獎(jiǎng)金.?每一個(gè)程序員單獨(dú)完成與相互合作的效率如下(完整的見下圖的表示):
L程序猿單獨(dú)完成可以完成10行代碼
M程序猿單獨(dú)完成可以完成30行代碼
N程序猿單獨(dú)完成可以完成5行代碼
L和M合作可以完成50行代碼
...
此時(shí), 會(huì)有3!(6種)合作的可能性會(huì)發(fā)生, 分別如下:
L邀請(qǐng)M形成組織S，M邀請(qǐng)N進(jìn)入組織S
L邀請(qǐng)N形成組織S ，N邀請(qǐng)M進(jìn)入組織S
M邀請(qǐng)L形成組織S 廊勃，L邀請(qǐng)N進(jìn)入組織S
… …
對(duì)于每一種合作的方式, 我們考慮他們的邊際收益, 即某人加入組織前后的收益變化. 下面的式子表示表示i加入集合S后的邊際貢獻(xiàn), 我們需要羅列出S所有的可能性.
我們說一下具體的例子, 比如說我們要計(jì)算L的貢獻(xiàn)值, 那么所有S可能的集合有:
S為空集
S中只有一個(gè)元素, 可以是M, 或是N
S中有兩個(gè)元素, 可以是M+N
共有5種可能性. 我們要分別計(jì)算著5種情況下的邊際收益(我們需要注意到的是, 這5種情況不是等可能出現(xiàn)的, ), 所以對(duì)于每一個(gè)人的收益的計(jì)算過程如下所示,?我們只是改變了加入的順序而已.
最后我們計(jì)算所有可能性下的收益的平均值, 就是某個(gè)人的貢獻(xiàn), 即Shapley Value. 計(jì)算結(jié)果如下所示.
我們這里需要注意的是, 這里三個(gè)人的Shapley Value的和是100, 這里的Shapley Value表示的就是每個(gè)人完成的代碼量(對(duì)于總的100的貢獻(xiàn)度).
例子二--拼車價(jià)格的計(jì)算
下面我們看第二個(gè)例子, 計(jì)算合理的拼車價(jià)格.
假設(shè)有A,B,C三位好友看完話劇準(zhǔn)備拼車回家封拧，拼車總價(jià)18元. 如果不拼車A回家需要6元岂却、B需要11元泉唁、C需要15元雷酪。(A-C是11). 其余每一段的價(jià)格如下圖所示, 問如何定價(jià)是最合理的.
所有上車的順序一共有6種情況, 分別如下所示, 這里雖然有6種情況, 但是其實(shí)三個(gè)人是一起上車的:
于是對(duì)應(yīng)上面每一種的上車的情況, 我們計(jì)算出每一種情況下A, B, C各需要支付多少.?每個(gè)人需要支付的如下表所示.
我們做一下簡(jiǎn)單的解釋, 我們選取上面的一個(gè)例子來進(jìn)行解釋,?假設(shè)現(xiàn)在上車的順序是B-C-A(不要被這里的上車順序所迷惑,?我們可以想象他們是在一個(gè)地方上車的, 只不過在一個(gè)地方上車的順序不一樣). 還是繼續(xù)解釋上面的例子,?上車的順序是B-C-A.
當(dāng)B上車的時(shí)候, B需要支付11元, 因?yàn)榇藭r(shí)B直接回去, 那么價(jià)格為11.
接著C上車, 開車的順序是B-C, 這時(shí)候總的價(jià)格為11+6(因?yàn)閺腂到C處需要6元), 相當(dāng)于C需要多支付6元.
最后A上車, 開車的順序是A-B-C(不管上車順序如何, 開車的順序都是A-B-C), 最終的價(jià)格為18, 所以此時(shí)B需要支付18-17=1元.
這個(gè)就是對(duì)應(yīng)上面的第四行計(jì)算出來的值.
Shapley Value的計(jì)算公式
下面我們理解一下Shapley Value的具體的計(jì)算公式. 大部分情況下, 我們看Shapley Value的計(jì)算公式的時(shí)候, 會(huì)看到下面的表達(dá)式.
這里是我們需要計(jì)算特征i的重要程度.?前面一部分表示的是權(quán)重, 后面一部分表示的是新增特征i前后的變化值. 我們還是看一個(gè)例子.
例如, 現(xiàn)在有5個(gè)player, ABCDE, 我們現(xiàn)在要計(jì)算C的收益
那么對(duì)于C來說, 加入的順序無論是ABC或是BAC對(duì)于C來說都是一樣的, 對(duì)于C來說, 前面AB的順序和他沒有關(guān)系.
所以我們可以使用集合來進(jìn)行計(jì)算, 計(jì)算集合(AB)的收益和(ABC)的收益, 從而可以計(jì)算出C的收益, 即f(ABC)-f(AB).
f(ABC)和f(AB)我們都是可以直接計(jì)算出來的, 但是我們需要對(duì)每一個(gè)集合加權(quán)重, 權(quán)重的大小與子集中包含的所有的序列順序有關(guān).
對(duì)于前面的例子捂龄，我們不僅要考慮C前面的可能的組合, AB, 或是BA, 也要考慮C后面的可能DE或是ED
所以對(duì)于上面的例子有4種可能性, ABCDE, ABCED, BACDE, and BACED (這就是上面公式中權(quán)重的由來)
我們?cè)倏匆幌律厦娴睦雍凸浇Y(jié)合來進(jìn)行講解.
具體計(jì)算過程
我們用上面的程序員分配獎(jiǎng)金的情況, 來具體算一下程序員M可以被分配到的獎(jiǎng)金. 下圖是每一種情況下的效率.
我直接將計(jì)算的過程以圖片的形式貼在這里了.
Shapley Value的性質(zhì)
這里介紹Shapley Value的三個(gè)性質(zhì).
如果一個(gè)player沒有帶來任何收益, 他計(jì)算得到的收益應(yīng)該是0(Dummy Player).
如果有兩個(gè)player在任何一個(gè)子集中增加相同的收益释涛，他們得到的收益也應(yīng)該是一樣的(Substitutability).
如果一個(gè)游戲是可以由兩個(gè)子游戲組成, 那么我們分別計(jì)算收益相加和直接計(jì)算總的收益分配應(yīng)該是一樣的.(Additivity, 滿足相加性)
證明鏈接:?http://www.lamsade.dauphine.fr/~airiau/Teaching/CoopGames/2011/coopgames-7[8up].pdf
還有一些需要說明的是, Shapley Value的計(jì)算的時(shí)間復(fù)雜度是很大的. 同時(shí)對(duì)于一些缺失變量我們需要多次隨機(jī)取樣來計(jì)算平均值, 這樣更加加大了運(yùn)算量. (The Shapley value requires?a lot of computing time. An exact computation of the Shapley value is computationally expensive because there are 2k?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.)
最后, 我們總結(jié)一下,?Shapley Value就是一個(gè)特征(player)在不同情況下對(duì)prediction的影響的平均值.
