shapley values 特征重要性评估简介

117次阅读
没有评论

shapley values

这个想法最初来自1953年Lloyd Shaley 提出的IDEA,下面会通过简单的例子先解释下这个方法的工作原理,然后再总结。

给定一个集合 N ,这里面包含三个员工{A,B,C},公司的收入通过函数v(N)来表示。现在我们要衡量的是每一个员工对收入的贡献程度。

shapley提供的方案是考虑所有的员工的组合分别给公司的收入,同时可以考虑去掉某个员工带来的损失评估,综合评估得到每个员工对公司的收入共享的程度。

  • v({}) = 0
  • v({A}) = 10
  • v({B}) = 20
  • v({C}) = 30
  • v({A, B}) = 60
  • v({B,C}) = 70
  • v({A,C}) = 90
  • v({A, B,C}) = 100

以上就是列出了不同的组合下给公司带来的收益。比如如果一个员工都没有,那么这个公司也运营不起来,那么自然而言获得收入为 0. 然后就是分别雇佣单个员工产生的收益,雇佣两个员工带来的收益,最后雇佣三个员工的总收益。

一般而言,当我们增加员工的数量的时候,公司的收入都会相应的增长。举个例子:v({A})=10,此时公司有招聘了B,那么v({A,B})=60,那么我们可以下一个结论:B给公司带来的收益是50?乍一看好像是加入B之后导致的,但不见得是这样,你看下{B,C}组合的收益,发现B其实没有贡献那么多。直觉上去理解也是可以说的通,就是1+1>2,正是因为B的加入{A,B}使得公司的收入增加了。

在前面也提到了 shapley会考虑所有的组合,也就是全排列组合,下面给出公司人员从 0到3的组合:

  1. {} → {{ A} → {A, B} → {A, B, C}
  2. {} → {A} → {A, C} → {A, B, C}
  3. {} → {B} → {A, B} → {A, B, C}
  4. {} → {B} → {B, C} → {A, B, C}
  5. {} → {C} → {B, C} → {A, B, C}
  6. {} → {C} → {A, C} → {A, B, C}

每次都是增加一个新员工,这样我们可以计算每加入的新员工对公司带来的收益。

  • A: v({A}) − v({}) = 10 − 0 = 10
  • B: v({A, B}) − v({A}) = 60 − 10 = 50
  • C: v({A, B,C}) − v({A, B}) = 100 − 60 = 40

依次类推,我们可以得到每一个组合下面每一个员工对公司的收益贡献程度:

  1. {} → {A} → {A, B} → {A, B, C} || A = 10, B = 50, C = 40
  2. {} → {A} → {A, C} → {A, B, C} || A = 10, B = 10, C = 80
  3. {} → {B} → {A, B} → {A, B, C} || A = 40, B = 20, C = 40
  4. {} → {B} → {B, C} → {A, B, C} || A = 30, B = 20, C = 50
  5. {} → {C} → {B, C} → {A, B, C} || A = 30, B = 40, C = 30
  6. {} → {C} → {A, C} → {A, B, C} || A = 60, B = 10, C = 30

最后一步只要将当前统计的数据做下平均就是对应的shapley value了。

那么我们可以得到

Aavg = 30 , Bavg = 25 , Cavg = 45

由此可以做出相应的判断,C员工对公司的收益是三者之中贡献是最大的。

这样计算得到的Shapley值是唯一满足效率性(Efficiency)对称性(Symmetry)虚拟性(Dummy)可加性(Additivity)四个属性的归因方法,它们可以一起被视为公平支出的定义。

效率性(完整性):A B C 员工的累计贡献值等于公司的收入减去不招人的收入,这个不是常理?

对称性:如果存在两个员工比如 F和G ,对于组合S(不包含 F和G 的组合),此时若{S,F}={S,G},那么就可以认为这两个员工对公司的贡献程度是一样

虚拟性:假设给定一个员工 H 和 组合S(不包含 H 的组合),若{S,H}={S},那么这个员工的贡献就是 0,也就是有没有这个员工,公司的收益都不会变。

可加性:某个员工的总贡献程度是多个组合共享的累计和,举个例子比如公司有多个收入组合组成,那么这个员工对公司总收入的贡献程度可以由各个子收入的组成的求和来计算。

总结

这个方法可以这样的事情,但是一看到排列组合,这个计算的复杂度肯定是很高的,这个需要相应的方法去完善。 Strumbelj等人(2014)对此提出蒙特卡罗采样的近似值(Shapley采样值)因此可以减少计算量,有兴趣的可以参考一下。

admin
版权声明:本站原创文章,由admin2021-08-19发表,共计1711字。
转载提示:除特殊说明外本站文章皆由CC-4.0协议发布,转载请注明出处。
评论(没有评论)