作者：賈恩東本文約2000字，建議閱讀9分鐘本文為你介紹更公平分配利益權(quán)重的一種算法——Shapley值方法。
(資料圖片)
本篇文章是數(shù)據(jù)派一文讀懂系列的新年第一篇原創(chuàng)，在這里祝賀大家新年學業(yè)有新成就，生活有新氣象！這次帶大家了解一種有趣的從數(shù)學角度計算合作博弈貢獻從而更公平分配利益權(quán)重的算法——Shapley值方法。
相信大家在日常生活中都接觸過這樣一個現(xiàn)象，那就是1+1不等于2。好了，不開玩笑，作者想說的是，很多時候多個主體分別產(chǎn)生的影響和共同產(chǎn)生的影響是不具備嚴格加性的。有句俗語，一個和尚挑水吃，兩個和尚抬水吃，三個和尚沒水吃。分開的三個和尚每個每天都挑水，但放在一起“協(xié)作”反而就沒有水產(chǎn)出了。這里是一個關(guān)于協(xié)作的負面例子，但更多的是協(xié)作的正面例子，就是1+1大于2的效應。以下用一個案例具體來說明。
某公司有三個程序猿，分別是屌絲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的同學：明顯屌絲是潛力股，雖然單獨工作表現(xiàn)一般，但是和美女一起合作，大大激發(fā)了工作熱情，肯定是A貢獻最多！說B的同學：應該是大佬貢獻最大，因為單獨來看，大佬本身能力是最強的！說C的同學：應該是美女貢獻最大，雖然美女單獨工作沒什么效率，但顯然對團隊的影響無法替代！
請先別急，我們接下來使用理性的數(shù)學思維分析這個問題，可以順便推導出shapley值的公式。
設想我們順序?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最少。同學你猜對了嗎？
我們接下來把問題抽象化。假設有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)是對應合作順序組合 s 的出現(xiàn)概率?？梢赃@樣計算該概率，首先 s 中 前|s|?1 合作人順序進入合作集合，然后是合作人 i 加入集合，最后是后 n?|s|個合作人加入合作集合。這樣構(gòu)成了該種順序組合，這樣有(|s|?1)!×1×(n?|s|)! 種，一共則有 n! 種順序組合，所以有：
最終的shapley值公式即：
到這里，關(guān)于shapley值方法的公式就已經(jīng)推導完畢了。
值得一提的是，Shapley值方法是有嚴格的公理化體系支持的，感興趣的同學可以自行檢索學習。Shapley值方法很公平，在經(jīng)濟、金融、管理、政治中都有不少的推廣應用。比如多方金融投資合作如何分配利潤；不同人數(shù)的黨派團體如何更科學地設置投票通過票數(shù)；安全管理團隊中按照重要性對事故中的不同責任方進行責任判定等等。在機器學習中，也可以使用Shapley值方法對不同的特征進行重要性評價，進行特征的篩選工作，即使是深度神經(jīng)網(wǎng)絡這種黑盒模型也可以獲悉不同特征對于整個算法的貢獻分布。
在文章的最后，需要多提一句，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ù)的應用，探索數(shù)據(jù)產(chǎn)品之美；
系統(tǒng)平臺組：追蹤大數(shù)據(jù)&人工智能系統(tǒng)平臺技術(shù)前沿，對話專家；
自然語言處理組：重于實踐，積極參加比賽及策劃各類文本分析項目；
制造業(yè)大數(shù)據(jù)組：秉工業(yè)強國之夢，產(chǎn)學研政結(jié)合，挖掘數(shù)據(jù)價值；
數(shù)據(jù)可視化組：將信息與藝術(shù)融合，探索數(shù)據(jù)之美，學用可視化講故事；
網(wǎng)絡爬蟲組：爬取網(wǎng)絡信息，配合其他各組開發(fā)創(chuàng)意項目。
點擊文末“閱讀原文”，報名數(shù)據(jù)派研究部志愿者，總有一組適合你~
轉(zhuǎn)載須知
如需轉(zhuǎn)載，請在開篇顯著位置注明作者和出處（轉(zhuǎn)自：數(shù)據(jù)派THUID：DatapiTHU），并在文章結(jié)尾放置數(shù)據(jù)派醒目二維碼。有原創(chuàng)標識文章，請發(fā)送【文章名稱-待授權(quán)公眾號名稱及ID】至聯(lián)系郵箱，申請白名單授權(quán)并按要求編輯。
未經(jīng)許可的轉(zhuǎn)載以及改編者，我們將依法追究其法律責任。
點擊“閱讀原文”加入組織~
滾動