作者：贾恩东
【资料图】
本文约2000字，建议阅读9分钟
本文为你介绍更公平分配利益权重的一种算法——Shapley值方法。
本篇文章是数据派一文读懂系列的新年第一篇原创，在这里祝贺大家新年学业有新成就，生活有新气象！这次带大家了解一种有趣的从数学角度计算合作博弈贡献从而更公平分配利益权重的算法——Shapley值方法。
相信大家在日常生活中都接触过这样一个现象，那就是1+1不等于2。好了，不开玩笑，作者想说的是，很多时候多个主体分别产生的影响和共同产生的影响是不具备严格加性的。有句俗语，一个和尚挑水吃，两个和尚抬水吃，三个和尚没水吃。分开的三个和尚每个每天都挑水，但放在一起“协作”反而就没有水产出了。这里是一个关于协作的负面例子，但更多的是协作的正面例子，就是1+1大于2的效应。以下用一个案例具体来说明。
某公司有三个程序猿，分别是屌丝A，大佬B，美女C，如果大家不合作，A每个季度可以完成3个项目，B每个季度可以完成10个项目，C每个季度只能完成1个项目。但是老板小王为了充分挖掘员工潜力，合理配置公司资源，让A，B，C尝试了各种合作模式。王老板观察发现，屌丝都是潜力股，美女都是催化剂：屌丝A和大佬B合作每个季度可以完成15个项目，合作效果提升还行；屌丝A和美女C合作每个季度可以完成50个项目，合作效果爆炸；大佬B和美女C合作每个季度仅完成了12个项目，看来对大佬来说不影响拔刀的速度就不错了；ABC一起合作每个季度可以完成70个项目。最终王老板拍板让ABC以后就一起工作，按照小组完成的项目数额外发放项目奖金。请问聪明的读者，按照最公平正义的分配方法，哪位员工获得的奖金是最多的呢？
说A的同学：明显屌丝是潜力股，虽然单独工作表现一般，但是和美女一起合作，大大激发了工作热情，肯定是A贡献最多！说B的同学：应该是大佬贡献最大，因为单独来看，大佬本身能力是最强的！说C的同学：应该是美女贡献最大，虽然美女单独工作没什么效率，但显然对团队的影响无法替代！
请先别急，我们接下来使用理性的数学思维分析这个问题，可以顺便推导出shapley值的公式。
设想我们顺序将ABC放到合作队伍中（合作队伍一开始为空），那么合作的组合会有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 来说，它的收益表现记作 v(s)。假如某集合 s 包含 第 i 位合作人，则第 i 位 合作人在这种情形下的贡献为 v(s)−v(s\textbackslash{i})，解释为集合 s 的效益减去 集合 s 扣除第 i 位合作人后的新集合的效益。
因此我们可以得到第i 位合作人的贡献期望为：
这里Si 是所有包含 i 的所有子集的集合， P(s)是对应合作顺序组合 s 的出现概率。可以这样计算该概率，首先 s 中 前|s|−1 合作人顺序进入合作集合，然后是合作人 i 加入集合，最后是后 n−|s|个合作人加入合作集合。这样构成了该种顺序组合，这样有(|s|−1)!×1×(n−|s|)! 种，一共则有 n! 种顺序组合，所以有：
最终的shapley值公式即：
到这里，关于shapley值方法的公式就已经推导完毕了。
值得一提的是，Shapley值方法是有严格的公理化体系支持的，感兴趣的同学可以自行检索学习。Shapley值方法很公平，在经济、金融、管理、政治中都有不少的推广应用。比如多方金融投资合作如何分配利润；不同人数的党派团体如何更科学地设置投票通过票数；安全管理团队中按照重要性对事故中的不同责任方进行责任判定等等。在机器学习中，也可以使用Shapley值方法对不同的特征进行重要性评价，进行特征的筛选工作，即使是深度神经网络这种黑盒模型也可以获悉不同特征对于整个算法的贡献分布。
在文章的最后，需要多提一句，Shapley值方法虽然很好，但对于n 值很大的情况，计算很不友好，因为需要获悉所有组合集合的获益，这种组合集合一共有 2^n 种，不论是数据获得还是后续计算，都有不小的成本开销，所以有几种补救办法，有的是将合伙人分成若干组，按照组为最小合作单位进行计算；有的则是只考虑 n−1 大小的组合上增加合伙人带来的边际贡献等。无论是何种方法，本质上都和本文核心内容类似。
编辑：黄继彦
数据派研究部介绍
数据派研究部成立于2017年初，以兴趣为核心划分多个组别，各组既遵循研究部整体的知识分享和实践项目规划，又各具特色：
算法模型组：积极组队参加kaggle等比赛，原创手把手教系列文章；
调研分析组：通过专访等方式调研大数据的应用，探索数据产品之美；
系统平台组：追踪大数据&人工智能系统平台技术前沿，对话专家；
自然语言处理组：重于实践，积极参加比赛及策划各类文本分析项目；
制造业大数据组：秉工业强国之梦，产学研政结合，挖掘数据价值；
数据可视化组：将信息与艺术融合，探索数据之美，学用可视化讲故事；
网络爬虫组：爬取网络信息，配合其他各组开发创意项目。
点击文末“阅读原文”，报名数据派研究部志愿者，总有一组适合你~
转载须知
如需转载，请在开篇显著位置注明作者和出处（转自：数据派THUID：DatapiTHU），并在文章结尾放置数据派醒目二维码。有原创标识文章，请发送【文章名称-待授权公众号名称及ID】至联系邮箱，申请白名单授权并按要求编辑。
未经许可的转载以及改编者，我们将依法追究其法律责任。
点击“阅读原文”加入组织~
