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