Shapley 值清晰解释
原文：
towardsdatascience.com/shapley-values-clearly-explained-a7f7ef22b104
照片由Vadim Sherbakov在Unsplash提供
你上次和朋友们一起合作取得巨大成功是什么时候？无论是赢得比赛、在工作中掌握一个项目，还是在 Kaggle 竞赛中名列前三。如果你什么都想不起来（真可怜你），那么和朋友们度过的美好夜晚呢？想象一下：一个美妙的夜晚，随后一起乘坐出租车回家，却遇到了一笔不小的出租车账单。在这样的时刻，你可能会发现自己想知道：
我们如何公平地将团队结果分配给每个成员？
一个团队也可以是机器学习模型的特征，团队的结果是模型做出的预测。在这种情况下，了解每个特征对最终预测的贡献程度是非常有趣的。这正是数据科学家通常感兴趣的内容。
公平还是平均？
例如，想象你和另外两个朋友一起参加比赛。你们表现良好，作为团队获得了 12,000 欧元的奖金。你如何公平地分配这笔钱？平均分配没问题，每个人都能得到 4,000 欧元。但我们都知道，通常有些人对团队的成功贡献比其他人多。所以，可能像 5,000 欧元 + 4,000 欧元 + 3,000 欧元这样的分配方式会更合适，具体取决于情况。
或者拿那个出租车账单来说。你和两个朋友出去玩后回家，这次回家的出租车费用总共是 60 欧元。每个人都付 20 欧元公平吗？或者，如果住在非常远的人付得更多，而住在附近的人甚至住得很近，这不更公平吗？如果这个人必须付更多，那么应该多付多少？
在这篇文章中，我将向您展示如何使用Shapley 值来回答这类问题，Shapley 值是以诺贝尔奖获得者Lloyd Shapley的名字命名的。它们提供了一个数学框架，用于将团队成功的公平份额分配给每个贡献成员。
三个绅士在出租车里
作为运行示例，让我们使用我之前提到的出租车场景。下面是一个稍微详细一点的故事：
在迷人的卢顿镇，三位来自牛津、剑桥和伦敦的英国绅士，身着时髦的西装，度过了一个愉快的夜晚，探索了它的鹅卵石街道。他们从一家当地酒吧开始，举杯庆祝，然后前往热闹的市场享受街头美食，最后在一家精致的茶馆结束他们的夜晚，一边品茶，一边聆听现场钢琴家的舒缓旋律。笑声和共享的时刻温暖了他们的心，三人告别卢顿，留下了真正愉快夜晚的回响。
多么美好的故事啊，不是吗？最后，朋友们共乘一辆出租车——为了多在一起待会儿——回家。
www.google.com/maps/@51.7811482,-0.4596552,8.75z?entry=ttu, 图片由作者提供。
如您所见，出租车必须行驶很长的路线，从卢顿一直绕行到所有三个城市。出租车价格为每英里 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。
你可以为所有其他联盟做同样的计算，并得到以下列表：
图片由作者提供。
贡献值
现在我们有了这个列表，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都在出租车里，让我们考虑它们可能进入出租车的所有顺序。让我们再列一个单子！
图片由作者提供。
在上面的表格中，你可以看到很多我们之前见过的数字。如果C先来，他的增量价值是 114。L和O之后的顺序不重要，两种情况下都是 114。同样，如果C最后来，他的增量价值是 195。如果C在O之后来，是 231。这里唯一的新数字是在L, C, O，即当只有L在出租车里时C的增量价值。
现在？取平均值！结果是C的 Shapley 值：
图片由作者提供。
因此，根据 Shapley 值，公平价格应为C的 172£。你也可以为L和O做同样的数学计算，得到
每个人的公平份额。图片由作者提供。
注意，总和等于总价格：483 = 172 + 119.5 + 191.5。这不是巧合，而是一个被称为效率的可证明的结果。没有这个属性，Shapley 值将毫无用处。
Python 代码
我编写了一些代码来复制我们所采取的步骤。这个代码绝对不是计算 Shapley 值最快的方法，但你应该能够跟上。
from itertools import permutations
# from the article, change it as you wish
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,
}
def compute_shapley_values(coalition_values, player):
players = max(coalition_values, key=lambda x: len(x))
contributions = []
for permutation in permutations(players):
player_index = permutation.index(player)
coalition_before = frozenset(permutation[:player_index]) # excluding player
coalition_after = frozenset(permutation[: player_index + 1]) # player joined coalition
contributions.append(coalition_values[coalition_after] - coalition_values[coalition_before])
return sum(contributions) / len(contributions) # average, results in Shapley values
for player in ("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 值公式：
图片由作者提供。
呼吁，即使有了我们在文章中获得的全部知识，这也相当复杂。让我在这里注释一些事情。
图片由作者提供。
因此，让我们开始吧。N 是所有玩家的集合，在我们的例子中 N = {C, L, O}，而 n = |N| 是玩家的数量。S 是一个联盟，例如 {C, O}。你可以看到我们有了包含和不包含玩家 i 的联盟 S 的联盟值。取差值就得到了贡献值。x! 是阶乘函数，即 x! = x · (x – 1) · (x – 2) · … · 2 · 1。
重数
现在，唯一的神秘之处在于这个重数因子。为了理解它，让我们回到 C 的贡献表。
图片由作者提供。
你可以看到一些数字出现了多次，即 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, L
-
X, O, C, L, Y
-
O, X, C, Y, L
-
O, X, C, L, Y
C 排在第三位，发生顺序和后续顺序不重要。在任何情况下，贡献值是 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，这就是为什么这个列表有四个元素。
更快的实现
这里有一个更好的实现。我使用了公式中的变量名来使其更容易理解。
from itertools import combinations
from math import factorial
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,
}
def powerset(set_):
"""Create all subsets of a given set."""
for k in range(len(set_) + 1):
for subset in combinations(set_, k):
yield set(subset)
def compute_shapley_values(coalition_values, i):
N = max(coalition_values, key=lambda x: len(x))
n = len(N)
contribution = 0
for S in powerset(N - {i}):
multiplicity = factorial(len(S)) * factorial(n - len(S) - 1)
coalition_before = frozenset(S)
coalition_after = frozenset(S | {i})
contribution += multiplicity * (coalition_values[coalition_after] - coalition_values[coalition_before])
return contribution / factorial(n)
for player in ("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的游戏，那么在组合游戏v + w中玩家i的 Shapley 值等于单个游戏中 Shapley 值的和，即ϕᵢ(v+w) = ϕᵢ(v) + ϕᵢ(w). (证明：将上面的 Shapley 公式代入 v+w 代替 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》！我仍在寻找作者！
AtomGit 是由开放原子开源基金会联合 CSDN 等生态伙伴共同推出的新一代开源与人工智能协作平台。平台坚持“开放、中立、公益”的理念，把代码托管、模型共享、数据集托管、智能体开发体验和算力服务整合在一起，为开发者提供从开发、训练到部署的一站式体验。
更多推荐
0
0- 0
已为社区贡献153条内容
所有评论(0)