作者:贾恩东
(资料图片仅供参考)
本文约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】至联系邮箱,申请白名单授权并按要求编辑。
未经许可的转载以及改编者,我们将依法追究其法律责任。
点击“阅读原文”加入组织~
推荐内容
- 原创 | 一文读懂机器学习中的shapley值方法
- 当前时讯:看过来,全国这100个职业“最
- 【天天播资讯】电子城: 电子城第十二届
- 物联网应用案例∣水力电力巡检
- 环球动态:606家机构已开立不良贷款转让业
- 全球热讯:【A-SOUL/嘉晚饭短篇】漫步
- 【世界新视野】[快讯]招商双债LOF公布年报
- 环球热点!威孚高科:Protean是轮毂电机
- 顺控发展1月17日快速上涨
- 图灵看市1.17-白银高位十字星、能否形成
- 最新快讯!业务员技巧与话术大全_业务员技
- 海沧区独生子女父母补贴政策(附补贴标准
- 湖南卫视春晚:王一博假唱,李一桐忘词,
- 辽宁省盘山县一化工厂发生火灾,致2死34
- 谁动了养元“植物蛋白饮料”的奶酪?
- 每日资讯:盗窃车辆金额有30万的有能判多
- 天天看点:2022年贵州扎实巩固拓展脱贫攻
- 环球消息!萝卜和枸杞能一起吃吗 萝卜和
- 如何重燃“烟火气”、促进消费升级备受关
- 河北省疾控中心提示:春节返乡不忘疫情防
- 世界观焦点:河南三门峡:开设新冠病毒感
- 天天快消息!发力精垂,从护肤到抗衰,HB
- 天天视讯!23民生银行CD026今日发布发行公告
- 邓海清:2022年12月CPI符合预期 PPI不及
- 全球观热点:宁波精达1月12日快速上涨
- 热文:天风证券:银行信贷量质齐优可期
- 全球快讯:1月11日基金净值:嘉实致安3个
- 快讯丨迪马股份:新增累计涉及诉讼、仲裁
- 同力日升董秘回复:截至2023年1月10日,
- 焦点消息!新年第一场冷空气发货!河南新
- 一路走好!37岁张小斐家中两位老人去世,
- 羽绒服洗了,怎样恢复弹性?
- 奥地利政要诋毁中国“动态清零”政策,外
- 今日观点!卡卡贷贷款逾期四年还不起征信
- 【环球新要闻】要命了!张天爱最新照片直
- 世界快播:借去花借款逾期47年不还会上征
- 世界即时:长沙万安网贷逾期2天会不会上
- 世界今热点:问下关于写欠条的注意事项有
- 全球快播:服役已有6年:Linux Kernel
- 全球看点:集结完毕!“陆地航母”整装待
- 优酷过冬,禁止“白嫖”
- 【环球新要闻】惊人相似!巴西国会周日涌
- 微头条丨判刑七年会缓刑多少年
- 全球热门:中钢协:2023年钢材需求有望恢
- 江西赣州,一女子和丈夫开车回家娘家,临行
- 香港与澳门将恢复跨境渡轮服务
- 今日最新!北京石景山区“三区建设”2023
- 精选!江苏北人:截至2023年1月5日 林涛
- 当前短讯!2023湖南师大附中星沙实验学校
- 智慧农业董秘回复:公司目前正在研发的是
- 每日视点!《中国影视蓝皮书》:五年征程
- 世界最新:北京朝阳医院第二发热门诊正式
- 当前视讯!研报精选|2023年科技行业关注
- 南瓜桑葚黄豆粥的做法?
- 2023年南京公园年卡在哪里可以办理
- 北京大兴:打造京津冀首个氢电耦合型零碳
- 茶好的精美句子(精选239句)
- “升温”成主旋律 周末将迎来18℃
- 热文:国寿精选LOF: 国寿安保基金管理有
- 天天快报!复旦张江(01349.HK)获得政府补
- 世界观焦点:河南三门峡:开设新冠病毒感
- 天天快消息!发力精垂,从护肤到抗衰,HB
- 天天视讯!23民生银行CD026今日发布发行公告
- 邓海清:2022年12月CPI符合预期 PPI不及
- 全球观热点:宁波精达1月12日快速上涨
- 热文:天风证券:银行信贷量质齐优可期
- 全球快讯:1月11日基金净值:嘉实致安3个
- 快讯丨迪马股份:新增累计涉及诉讼、仲裁
- 同力日升董秘回复:截至2023年1月10日,
- 焦点消息!新年第一场冷空气发货!河南新
- 一路走好!37岁张小斐家中两位老人去世,
- 羽绒服洗了,怎样恢复弹性?
- 奥地利政要诋毁中国“动态清零”政策,外
- 今日观点!卡卡贷贷款逾期四年还不起征信
- 【环球新要闻】要命了!张天爱最新照片直
- 世界快播:借去花借款逾期47年不还会上征
- 世界即时:长沙万安网贷逾期2天会不会上
- 世界今热点:问下关于写欠条的注意事项有
- 全球快播:服役已有6年:Linux Kernel
- 全球看点:集结完毕!“陆地航母”整装待
- 优酷过冬,禁止“白嫖”
- 【环球新要闻】惊人相似!巴西国会周日涌
- 微头条丨判刑七年会缓刑多少年
- 全球热门:中钢协:2023年钢材需求有望恢
- 江西赣州,一女子和丈夫开车回家娘家,临行
- 香港与澳门将恢复跨境渡轮服务
- 今日最新!北京石景山区“三区建设”2023
- 精选!江苏北人:截至2023年1月5日 林涛
- 当前短讯!2023湖南师大附中星沙实验学校
- 智慧农业董秘回复:公司目前正在研发的是
- 每日视点!《中国影视蓝皮书》:五年征程
- 世界最新:北京朝阳医院第二发热门诊正式
- 当前视讯!研报精选|2023年科技行业关注
- 南瓜桑葚黄豆粥的做法?
- 2023年南京公园年卡在哪里可以办理
- 北京大兴:打造京津冀首个氢电耦合型零碳
- 茶好的精美句子(精选239句)
- “升温”成主旋律 周末将迎来18℃
- 热文:国寿精选LOF: 国寿安保基金管理有
- 天天快报!复旦张江(01349.HK)获得政府补
- 新城控股董事长:开发业务平稳,商业经营
- 【天天快播报】海外抢单 外贸发力 “中
- 焦点速递!远兴能源:融资净偿还277.25万
- 每日速讯:国家减灾委员会办公室、应急管
- 微头条丨湖北汉江大桥跨年夜突发大火 警
- 启航2023!这批重大项目取得新进展
- 80用英语怎么说 80英语是什么
- 环球关注:Steam年度最畅销游戏出炉:第
- 世界今亮点!科兴制药(688136)12月30日
- 当前视讯!2022年终报道 | 年度经济关
- [快讯]清越科技:使用部分募集资金向全资
- 回顾2022年,这是中国军人的催泪瞬间!
- 焦点速看:中科云网:江苏高邮设子公司投
- 观焦点:车厘子烂的能吃吗?
- 天天日报丨frm一级考试报名多少钱
- 中节能湖北恩施300MW风电项目勘察设计开
- 京东金条借款逾期17年延迟还款会不会上征
- 平安新一贷网贷逾期16年征信有什么影响
- 世界微头条丨【机构调研记录】合煦智远基
- 播报:炒土豆时,你会和什么一起搭配来炒