作者：賈恩東
(資料圖片僅供參考)
本文約2000字，建議閱讀9分鐘
本文為你介紹更公平分配利益權(quán)重的一種算法——Shapley值方法。
本篇文章是數(shù)據(jù)派一文讀懂系列的新年第一篇原創(chuàng)，在這里祝賀大家新年學(xué)業(yè)有新成就，生活有新氣象！這次帶大家了解一種有趣的從數(shù)學(xué)角度計算合作博弈貢獻從而更公平分配利益權(quán)重的算法——Shapley值方法。
相信大家在日常生活中都接觸過這樣一個現(xiàn)象，那就是1+1不等于2。好了，不開玩笑，作者想說的是，很多時候多個主體分別產(chǎn)生的影響和共同產(chǎn)生的影響是不具備嚴(yán)格加性的。有句俗語，一個和尚挑水吃，兩個和尚抬水吃，三個和尚沒水吃。分開的三個和尚每個每天都挑水，但放在一起“協(xié)作”反而就沒有水產(chǎn)出了。這里是一個關(guān)于協(xié)作的負(fù)面例子，但更多的是協(xié)作的正面例子，就是1+1大于2的效應(yīng)。以下用一個案例具體來說明。
某公司有三個程序猿，分別是屌絲A，大佬B，美女C，如果大家不合作，A每個季度可以完成3個項目，B每個季度可以完成10個項目，C每個季度只能完成1個項目。但是老板小王為了充分挖掘員工潛力，合理配置公司資源，讓A，B，C嘗試了各種合作模式。王老板觀察發(fā)現(xiàn)，屌絲都是潛力股，美女都是催化劑：屌絲A和大佬B合作每個季度可以完成15個項目，合作效果提升還行；屌絲A和美女C合作每個季度可以完成50個項目，合作效果爆炸；大佬B和美女C合作每個季度僅完成了12個項目，看來對大佬來說不影響拔刀的速度就不錯了；ABC一起合作每個季度可以完成70個項目。最終王老板拍板讓ABC以后就一起工作，按照小組完成的項目數(shù)額外發(fā)放項目獎金。請問聰明的讀者，按照最公平正義的分配方法，哪位員工獲得的獎金是最多的呢？
說A的同學(xué)：明顯屌絲是潛力股，雖然單獨工作表現(xiàn)一般，但是和美女一起合作，大大激發(fā)了工作熱情，肯定是A貢獻最多！說B的同學(xué)：應(yīng)該是大佬貢獻最大，因為單獨來看，大佬本身能力是最強的！說C的同學(xué)：應(yīng)該是美女貢獻最大，雖然美女單獨工作沒什么效率，但顯然對團隊的影響無法替代！
請先別急，我們接下來使用理性的數(shù)學(xué)思維分析這個問題，可以順便推導(dǎo)出shapley值的公式。
設(shè)想我們順序?qū)BC放到合作隊伍中（合作隊伍一開始為空），那么合作的組合會有3!=6 種，如下表：
加入順序 | A加入的貢獻 | B加入的貢獻 | C加入的貢獻 |
A+B+C | 3-0=3 | 15-3=12 | 70-15=55 |
A+C+B | 3-0=3 | 70-50=20 | 50-3=47 |
B+A+C | 15-10=5 | 10-0=10 | 70-15=55 |
B+C+A | 70-12=58 | 10-0=10 | 12-10=2 |
C+A+B | 50-1=49 | 70-50=20 | 1-0=1 |
C+B+A | 70-12=58 | 12-1=11 | 1-0=1 |
表中的貢獻計算方法可以舉個例子來說明，B+C+A的順序組合中，A的貢獻是ABC的合作扣除BC的合作，即70-12=58；B的貢獻就是B加入空的貢獻，即10-0=10。其他類推。
但最終的加入順序只有一種，而各個順序都是等可能的。因此， A的貢獻可以計算期望：(3+3+5+58+49+58)/6=176/6 B的貢獻可以計算期望：(12+20+10+10+20+11)/6=83/6 C的貢獻可以計算期望：(55+47+55+2+1+1)/6=161/6
這些貢獻期望加在一起，(176+83+161)/6=70也恰是ABC的整體合作效果，驗證了我們計算的合理性。做個簡單除法，得出最終A的貢獻占比是29.33%，B的貢獻占比是13.83%，C的貢獻占比是26.83%。A的貢獻是最多的，C也很多，B最少。同學(xué)你猜對了嗎？
我們接下來把問題抽象化。假設(shè)有n 位合作人，任何一種合作組合例如第1位和第2位合作組合記為{1,2}，是一個有序集合的概念，對于組合 s 來說，它的收益表現(xiàn)記作 v(s)。假如某集合 s 包含 第 i 位合作人，則第 i 位 合作人在這種情形下的貢獻為 v(s)?v(s\textbackslash{i})，解釋為集合 s 的效益減去 集合 s 扣除第 i 位合作人后的新集合的效益。
因此我們可以得到第i 位合作人的貢獻期望為：
這里Si 是所有包含 i 的所有子集的集合， P(s)是對應(yīng)合作順序組合 s 的出現(xiàn)概率?？梢赃@樣計算該概率，首先 s 中 前|s|?1 合作人順序進入合作集合，然后是合作人 i 加入集合，最后是后 n?|s|個合作人加入合作集合。這樣構(gòu)成了該種順序組合，這樣有(|s|?1)!×1×(n?|s|)! 種，一共則有 n! 種順序組合，所以有：
最終的shapley值公式即：
到這里，關(guān)于shapley值方法的公式就已經(jīng)推導(dǎo)完畢了。
值得一提的是，Shapley值方法是有嚴(yán)格的公理化體系支持的，感興趣的同學(xué)可以自行檢索學(xué)習(xí)。Shapley值方法很公平，在經(jīng)濟、金融、管理、政治中都有不少的推廣應(yīng)用。比如多方金融投資合作如何分配利潤；不同人數(shù)的黨派團體如何更科學(xué)地設(shè)置投票通過票數(shù)；安全管理團隊中按照重要性對事故中的不同責(zé)任方進行責(zé)任判定等等。在機器學(xué)習(xí)中，也可以使用Shapley值方法對不同的特征進行重要性評價，進行特征的篩選工作，即使是深度神經(jīng)網(wǎng)絡(luò)這種黑盒模型也可以獲悉不同特征對于整個算法的貢獻分布。
在文章的最后，需要多提一句，Shapley值方法雖然很好，但對于n 值很大的情況，計算很不友好，因為需要獲悉所有組合集合的獲益，這種組合集合一共有 2^n 種，不論是數(shù)據(jù)獲得還是后續(xù)計算，都有不小的成本開銷，所以有幾種補救辦法，有的是將合伙人分成若干組，按照組為最小合作單位進行計算；有的則是只考慮 n?1 大小的組合上增加合伙人帶來的邊際貢獻等。無論是何種方法，本質(zhì)上都和本文核心內(nèi)容類似。
編輯：黃繼彥
數(shù)據(jù)派研究部介紹
數(shù)據(jù)派研究部成立于2017年初，以興趣為核心劃分多個組別，各組既遵循研究部整體的知識分享和實踐項目規(guī)劃，又各具特色：
算法模型組：積極組隊參加kaggle等比賽，原創(chuàng)手把手教系列文章；
調(diào)研分析組：通過專訪等方式調(diào)研大數(shù)據(jù)的應(yīng)用，探索數(shù)據(jù)產(chǎn)品之美；
系統(tǒng)平臺組：追蹤大數(shù)據(jù)&人工智能系統(tǒng)平臺技術(shù)前沿，對話專家；
自然語言處理組：重于實踐，積極參加比賽及策劃各類文本分析項目；
制造業(yè)大數(shù)據(jù)組：秉工業(yè)強國之夢，產(chǎn)學(xué)研政結(jié)合，挖掘數(shù)據(jù)價值；
數(shù)據(jù)可視化組：將信息與藝術(shù)融合，探索數(shù)據(jù)之美，學(xué)用可視化講故事；
網(wǎng)絡(luò)爬蟲組：爬取網(wǎng)絡(luò)信息，配合其他各組開發(fā)創(chuàng)意項目。
點擊文末“閱讀原文”，報名數(shù)據(jù)派研究部志愿者，總有一組適合你~
轉(zhuǎn)載須知
如需轉(zhuǎn)載，請在開篇顯著位置注明作者和出處（轉(zhuǎn)自：數(shù)據(jù)派THUID：DatapiTHU），并在文章結(jié)尾放置數(shù)據(jù)派醒目二維碼。有原創(chuàng)標(biāo)識文章，請發(fā)送【文章名稱-待授權(quán)公眾號名稱及ID】至聯(lián)系郵箱，申請白名單授權(quán)并按要求編輯。
未經(jīng)許可的轉(zhuǎn)載以及改編者，我們將依法追究其法律責(zé)任。
點擊“閱讀原文”加入組織~
標(biāo)簽： 機器學(xué)習(xí) 這個問題
