Shapley 值清晰解释

原文towardsdatascience.com/shapley-values-clearly-explained-a7f7ef22b104https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/310f93cb94c1fb8462f617b013ffe411.png照片由Vadim Sherbakov在Unsplash提供你上次和朋友们一起合作取得巨大成功是什么时候无论是赢得比赛、在工作中掌握一个项目还是在 Kaggle 竞赛中名列前三。如果你什么都想不起来真可怜你那么和朋友们度过的美好夜晚呢想象一下一个美妙的夜晚随后一起乘坐出租车回家却遇到了一笔不小的出租车账单。在这样的时刻你可能会发现自己想知道我们如何公平地将团队结果分配给每个成员一个团队也可以是机器学习模型的特征团队的结果是模型做出的预测。在这种情况下了解每个特征对最终预测的贡献程度是非常有趣的。这正是数据科学家通常感兴趣的内容。公平还是平均例如想象你和另外两个朋友一起参加比赛。你们表现良好作为团队获得了 12,000 欧元的奖金。你如何公平地分配这笔钱平均分配没问题每个人都能得到 4,000 欧元。但我们都知道通常有些人对团队的成功贡献比其他人多。所以可能像 5,000 欧元 4,000 欧元 3,000 欧元这样的分配方式会更合适具体取决于情况。或者拿那个出租车账单来说。你和两个朋友出去玩后回家这次回家的出租车费用总共是 60 欧元。每个人都付 20 欧元公平吗或者如果住在非常远的人付得更多而住在附近的人甚至住得很近这不更公平吗如果这个人必须付更多那么应该多付多少在这篇文章中我将向您展示如何使用Shapley 值来回答这类问题Shapley 值是以诺贝尔奖获得者Lloyd Shapley的名字命名的。它们提供了一个数学框架用于将团队成功的公平份额分配给每个贡献成员。三个绅士在出租车里作为运行示例让我们使用我之前提到的出租车场景。下面是一个稍微详细一点的故事在迷人的卢顿镇三位来自牛津、剑桥和伦敦的英国绅士身着时髦的西装度过了一个愉快的夜晚探索了它的鹅卵石街道。他们从一家当地酒吧开始举杯庆祝然后前往热闹的市场享受街头美食最后在一家精致的茶馆结束他们的夜晚一边品茶一边聆听现场钢琴家的舒缓旋律。笑声和共享的时刻温暖了他们的心三人告别卢顿留下了真正愉快夜晚的回响。多么美好的故事啊不是吗最后朋友们共乘一辆出租车——为了多在一起待会儿——回家。https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/587a89dfc681adb85f88b7bb782fc896.pngwww.google.com/maps/51.7811482,-0.4596552,8.75z?entryttu, 图片由作者提供。如您所见出租车必须行驶很长的路线从卢顿一直绕行到所有三个城市。出租车价格为每英里 3 英镑行驶了 161 英里总价为 483 英镑。哎呀。但现在问题来了每个人应该付多少钱让我们从几个观察开始。伦敦离卢顿最近相距 34 英里。如果伦敦的朋友独自回家其他两位朋友仍然需要旅行 127 英里才能回家这仍然相当多。这一点对其他城市并不适用。直观上这意味着去伦敦的朋友里程增加并不多因此与其他两位相比应该支付更少。现在我们将学习如何根据 Shapley 计算精确和公平的数字。计算 Shapley 值我们需要知道的一切来计算 Shapley 值是每个组合——也称为联盟——的出租车价格。从现在起让我们称这些朋友为C(**ambridge)、L(ondon)和O(xford)。C、L和O在一般情况下也被称为玩家。联盟价值我们已经确定由C、L和O组成的联盟将花费 483 英镑这是我们观察到的。我们也可以写成v({C,L,O}) 483这意味着联盟**{C, L, O**}的价值是 483。然而我们没有观察到其他联盟价值。当你想要计算 Shapley 值时通常会出现这种情况。你有了整个联盟的价值但你还需要想出其他的价值。例如如果只有C和O乘坐出租车价格会是多少在我们的案例中我们可以使用谷歌地图重建这些值。访问剑桥和牛津将是一段 127 英里的旅程费用为 127 英里 × 3 英镑/英里 381 英镑因此v({C,O}) 381。作为另一个例子考虑联盟{L}即只有去伦敦。这将是从卢顿出发的 34 英里旅程结果联盟价值价格为v({L}) 34 × 3 102。你可以为所有其他联盟做同样的计算并得到以下列表https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/971d679626706aa703db3a5d4a240872.png图片由作者提供。贡献值现在我们有了这个列表Shapley 值的概念围绕贡献的概念。作为一个例子让我们找出C的贡献。但“贡献”究竟是什么意思呢好吧如果出租车是空的——成本为 0——而C上车根据上面的表格价格从 0 上升到 114。在这种情况下C 的贡献是v({C}) –v({}) 114 – 0 114。作为另一个例子如果出租车里只有O成本为 150而C加入他成本增加到 381。因此这种情况下的贡献是v({C, O}) –v({O}) 381 – 150 231。每个人应支付的公平份额应该直观地与他们在联盟出租车中的存在对最终价值价格的贡献相关。然而我们面临以下困境贡献与时间概念紧密相关。你可以在我们如何得出C的贡献中看到这一点。首先出租车是空的然后C加入价格上升了 114 v({C}) –v({})。首先只有O在出租车里然后C加入价格上升了 231 v({C,O}) –v({O})。首先O和L在出租车里然后C加入价格上升了 195 v({C,L,O}) –v({L, O})。但你只知道每个人都坐了那辆出租车没有固有的时间顺序。那么C提高了价格 114、231 还是 195这就是解决这个困境的神奇调料只需对所有可能的联盟时间顺序的平均贡献值进行平均。听起来很抽象但让我们计算一下它对C是如何工作的。对排列进行平均如果我们只知道C、L和O都在出租车里让我们考虑它们可能进入出租车的所有顺序。让我们再列一个单子https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/162e0829fd7934cbf3eef4519ade0622.png图片由作者提供。在上面的表格中你可以看到很多我们之前见过的数字。如果C先来他的增量价值是 114。L和O之后的顺序不重要两种情况下都是 114。同样如果C最后来他的增量价值是 195。如果C在O之后来是 231。这里唯一的新数字是在L, C, O即当只有L在出租车里时C的增量价值。现在取平均值结果是C的 Shapley 值https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/39ff556130abb5c0f11151fba5c32262.png图片由作者提供。因此根据 Shapley 值公平价格应为C的 172£。你也可以为L和O做同样的数学计算得到https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/a1e1b4e43fc251331429e9424d0b6132.png每个人的公平份额。图片由作者提供。注意总和等于总价格483 172 119.5 191.5。这不是巧合而是一个被称为效率的可证明的结果。没有这个属性Shapley 值将毫无用处。Python 代码我编写了一些代码来复制我们所采取的步骤。这个代码绝对不是计算 Shapley 值最快的方法但你应该能够跟上。fromitertoolsimportpermutations# from the article, change it as you wishcoalition_values{frozenset():0,frozenset(C):114,frozenset(L):102,frozenset(O):150,frozenset((C,L)):285,frozenset((C,O)):381,frozenset((L,O)):288,frozenset((C,L,O)):483,}defcompute_shapley_values(coalition_values,player):playersmax(coalition_values,keylambdax:len(x))contributions[]forpermutationinpermutations(players):player_indexpermutation.index(player)coalition_beforefrozenset(permutation[:player_index])# excluding playercoalition_afterfrozenset(permutation[:player_index1])# player joined coalitioncontributions.append(coalition_values[coalition_after]-coalition_values[coalition_before])returnsum(contributions)/len(contributions)# average, results in Shapley valuesforplayerin(C,L,O):print(player,compute_shapley_values(coalition_values,player))# Output:# C 172.0# L 119.5# O 191.5如果n是玩家的数量我们将遍历n! 个玩家排列。即使对于小的n值例如 10这已经是一个巨大的数字了3,628,800 次迭代。这使得这种实现相当无用。此外我在取平均值之前将所有值存储在列表中所以从内存的角度来看上面的代码也只适用于小实例。通用公式现在我们知道了单个步骤让我给你介绍一下经典的 Shapley 值公式https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/ad1bea74aef94cfd37aad46e955ceb8c.png图片由作者提供。呼吁即使有了我们在文章中获得的全部知识这也相当复杂。让我在这里注释一些事情。https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/fbe418680f793c5e08fecefc38c4ebf0.png图片由作者提供。因此让我们开始吧。N是所有玩家的集合在我们的例子中N {C, L, O}而n |N| 是玩家的数量。S是一个联盟例如 {C,O}。你可以看到我们有了包含和不包含玩家i的联盟S的联盟值。取差值就得到了贡献值。x! 是阶乘函数即x! x· (x– 1) · (x– 2) · … · 2 · 1。重数现在唯一的神秘之处在于这个重数因子。为了理解它让我们回到C的贡献表。https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/162e0829fd7934cbf3eef4519ade0622.png图片由作者提供。你可以看到一些数字出现了多次即 114 和 195。这些数字是相同的因为所有玩家在C之前和之后的顺序对于贡献值来说并不重要。例如排序C, L, O和C, O, L具有相同的贡献值因为它们都使用了公式v({C}) –v({})。C是第一个它之后的顺序不重要。同样L, O, C和O, L, C也是如此。C是最后一个它之前的一切顺序不重要。如果有另外两个玩家X和Y以下排序也将具有相同的贡献值X, O, C, Y, LX, O, C, L, YO, X, C, Y, LO, X, C, L, YC排在第三位发生顺序和后续顺序不重要。在任何情况下贡献值是v({C, O, X}) –v({O,X})。重数计算具有相同贡献值的排列数。组合论证如下有n个玩家的一个排序我想计算位置|S| 1 的玩家的 Shapley 值。在这个玩家之前有|S|个其他玩家有|S|!种方式可以重新排列他们。在这个玩家之后还有n– |S| – 1 个其他玩家我们可以以(n –|S| – 1)!种方式重新排列他们。我们可以自由组合这两种排列导致|S|! · (n –|S| – 1)!种具有相同贡献值的排列这正是 Shapley 公式中的重复度因子。作为数值示例再次以类似X, O, C, Y, L的顺序考虑玩家示例。我们关注的是C。有三种方式可以排列X和O以及两种方式可以排列Y和L导致重复度为 2! · 2! 4这就是为什么这个列表有四个元素。更快的实现这里有一个更好的实现。我使用了公式中的变量名来使其更容易理解。fromitertoolsimportcombinationsfrommathimportfactorial coalition_values{frozenset():0,frozenset(C):114,frozenset(L):102,frozenset(O):150,frozenset((C,L)):285,frozenset((C,O)):381,frozenset((L,O)):288,frozenset((C,L,O)):483,}defpowerset(set_):Create all subsets of a given set.forkinrange(len(set_)1):forsubsetincombinations(set_,k):yieldset(subset)defcompute_shapley_values(coalition_values,i):Nmax(coalition_values,keylambdax:len(x))nlen(N)contribution0forSinpowerset(N-{i}):multiplicityfactorial(len(S))*factorial(n-len(S)-1)coalition_beforefrozenset(S)coalition_afterfrozenset(S|{i})contributionmultiplicity*(coalition_values[coalition_after]-coalition_values[coalition_before])returncontribution/factorial(n)forplayerin(C,L,O):print(player,compute_shapley_values(coalition_values,player))# Output:# C 172.0# L 119.5# O 191.5由于我们枚举所有子集这个实现会遍历 2ⁿ/ 2 **集合。这仍然很糟糕但不如第一个实现中的 n!迭代那么糟糕。对于 n 10只有 512 次迭代而不是超过 300 万次。Shapley 值的性质让我们以 Shapley 值的一些重要性质结束这篇文章。效率:所有玩家的 Shapley 值的总和等于完全联盟的价值。(证明点击这里.)对称性:如果两个玩家i和j有相同的贡献值即对于所有不包含玩家i和j的联盟S都有v(S∪ {i}) v(S∪ {j})那么他们的 Shapley 值也相等。(证明两个和都有相同的项因此整个和是相等的.)线性:如果有两个联盟价值函数v和w的游戏那么在组合游戏vw中玩家i的 Shapley 值等于单个游戏中 Shapley 值的和即ϕᵢ(vw) ϕᵢ(v) ϕᵢ(w). (证明将上面的 Shapley 公式代入 vw 代替 v。然后你可以将和分成两个和分别对应ϕᵢ(v)和ϕᵢ(w)。)零玩家:如果玩家i从未做出任何贡献那么他们的 Shapley 值为零即如果对于每个不包含i的S都有v(S∪ {i}) v(S)那么ϕᵢ(v)0*. (证明所有贡献值v(S∪ {i}) –v(S)都是零所以整个和是零。)*另一个有趣的事实是Shapley 值是唯一满足上述四个性质的价值。结论在团队成员之间公平分配联合团队努力的问题是每个人都从现实生活中知道的问题。我们经常求助于简单的解决方案比如将金库分成相等的部分。毕竟这样做很容易而且听起来在纸上看起来很公平。然而现在你有了计算每个成员实际公平份额的工具。至少如果你能量化所有联盟价值这是在实践中使用 Shapley 值的主要障碍同时还有计算的指数复杂性。在后续的文章中我们将更详细地探讨在机器学习中使用 Shapley 值来分解模型预测的应用。我希望你在今天学到了一些新的、有趣的和有价值的东西。感谢阅读如果你有任何问题请在LinkedIn上联系我如果你想要更深入地探索算法的世界可以尝试阅读我的新书《All About Algorithms》我仍在寻找作者All About Algorithms