Shapley 值详解：从原论文出发，深入“公平分配大师”的数学内核

Shapley 值详解从原论文出发深入“公平分配大师”的数学内核上一篇文章我们用“三个程序员的项目奖金”作为引子介绍了 Shapley 值的基本思想。但 Shapley 值为什么是“公平”的它的数学公式是怎么来的它凭什么能从博弈论“跨界”到机器学习这些问题我们需要回到 1953 年 Lloyd Shapley 的那篇原论文中寻找答案。Shapley 在 1953 年发表了著名的论文A Value for n-Person Games。这篇论文的出发点非常朴素在多人合作博弈中如何给每个参与者分配一个“值”这个值能够公平地反映他对合作联盟的贡献要理解这个问题首先需要明确 Shapley 值处理的是什么样的“游戏”。一、前提设定什么是“合作博弈”Shapley 值属于合作博弈论的范畴。在合作博弈中我们关心的不是每个玩家怎么出牌、怎么博弈那是非合作博弈的内容而是——如果大家合作总收益该怎样公平分配在论文中Shapley 对“游戏”做了严格的数学定义。他定义了一个特征函数characteristic functionv这个函数接收一个玩家的子集联盟 S返回这个联盟如果单独合作能够获得的总收益 v(S)。特征函数有两个关键性质空集收益为零v(∅) 0。超可加性superadditivity如果两个联盟 A 和 B 没有交集那么它们合作后的收益至少不小于各自单干的收益之和。用数学公式表达就是当 A ∩ B ∅ 时v(A ∪ B) ≥ v(A) v(B)。这个“超可加性”其实就是“112”的数学表达。它捕捉了合作的本质大家一起干比各自为战更划算。Shapley 值的任务就是把合作产生的额外收益公平地分配回每一个参与者。二、核心思想Shapley 值的数学公式Shapley 值的计算逻辑非常简洁一个玩家的 Shapley 值等于他在所有可能的联盟形成顺序中边际贡献的平均值。用数学公式表达ϕi(v)∑S⊆N∖{i}∣S∣! (n−∣S∣−1)!n![v(S∪{i})−v(S)] \phi_i(v) \sum_{S \subseteq N \setminus \{i\}} \frac{|S|! \, (n - |S| - 1)!}{n!} \big[ v(S \cup \{i\}) - v(S) \big]ϕi​(v)S⊆N∖{i}∑​n!∣S∣!(n−∣S∣−1)!​[v(S∪{i})−v(S)]这个公式看起来有些复杂但拆解之后非常直观N所有玩家的集合共 n 个玩家。S不包含玩家 i 的一个联盟S ⊆ N \ {i}。v(S ∪ {i}) − v(S)玩家 i 加入联盟 S 后带来的边际贡献——即因为他加入联盟的收益增加了多少。|S|! (n − |S| − 1)! / n!这个边际贡献的权重。它的含义是在所有 n! 种玩家加入顺序中有多少种顺序恰好使得玩家 i 在第 |S|1 个位置加入、且在他前面恰好有 S 中的这些玩家。这个权重保证了所有可能的顺序都被公平地考虑到了。如果你觉得公式太抽象没关系。你只需要记住一句话Shapley 值就是把每种可能的加入顺序都试一遍看看每个人在每种情况下带来了多少增益然后取个平均。这个“平均”不是简单的算术平均而是经过严谨的排列组合加权后的平均。三、为什么“公平”四大公理的刻画Shapley 值之所以被誉为“公平分配的唯一数学解”是因为它是唯一同时满足以下四个公理的分配方案1. 对称性Symmetry如果两个玩家在所有联盟中的边际贡献完全相同那么他们应该得到相同的收益。说白了就是贡献相同的人拿钱就该一样多。玩家叫什么名字、标签是什么都不影响分配结果。2. 有效性Efficiency所有玩家的 Shapley 值加起来正好等于全体合作的总收益。用公式表示∑ᵢ φᵢ(v) v(N)。这意味着分配方案是“收支平衡”的——收益既不会被凭空创造也不会被无故遗漏每一分钱都分到了具体的人头上。3. 冗员性Dummy / Null Player如果一个玩家在任何联盟中的加入都不会增加收益那么他应该得到零。如果一个玩家是“打酱油”的对任何合作都没有额外贡献那他就没有资格参与分配。这保证了奖励只给真正出力的人。4. 加法性Additivity如果玩家们参与了两个独立的游戏那么每个人在两个游戏中的总收益等于他在每个游戏中分别获得的收益之和。用公式表示φ(v w) φ(v) φ(w)。这意味着分配方案是“可叠加”的不会因为游戏的组合而产生混乱。这四个公理看起来都非常符合我们对“公平”的直觉。而 Shapley 在 1953 年的原论文中正是以这三个公理当时他提出的是对称性、有效性和加法性冗员性可以视为加法性的推论为基础推导出了 Shapley 值的唯一表达式。换句话说如果你想让分配满足这四个公平条件那你别无选择——只能用 Shapley 值。四、一个完整的计算实例三家公司联盟光说不练假把式。让我们通过一个具体的例子来完整走一遍 Shapley 值的计算过程。题目设定有三家公司公司 1、公司 2、公司 3。它们单独经营时的盈利分别是v({1}) 100 万v({2}) 200 万v({3}) 300 万如果它们合作盈利能力会提升公司 1 公司 2v({1, 2}) 500 万公司 2 公司 3v({2, 3}) 600 万公司 1 公司 3v({1, 3}) 700 万三家公司全部合作v({1, 2, 3}) 1000 万问题如果三家公司全面合作这 1000 万该怎样公平分配解法分别计算每家公司的 Shapley 值。对于公司 1我们需要考虑所有不包含公司 1 的联盟 S即 ∅, {2}, {3}, {2, 3}然后计算公司 1 加入 S 的边际贡献并乘以对应的权重S不包含 1边际贡献 v(S∪{1}) − v(S)权重 |S|!(n−|S|−1)!/n!加权贡献∅v({1}) − v(∅) 100 − 0 1000! × 2! / 3! 2/6100 × 2/6 ≈ 33.33{2}v({1,2}) − v({2}) 500 − 200 3001! × 1! / 3! 1/6300 × 1/6 50{3}v({1,3}) − v({3}) 700 − 300 4001! × 1! / 3! 1/6400 × 1/6 ≈ 66.67{2,3}v({1,2,3}) − v({2,3}) 1000 − 600 4002! × 0! / 3! 2/6400 × 2/6 ≈ 133.33将最后一列相加得到公司 1 的 Shapley 值φ₁ 33.33 50 66.67 133.33 283.33 万同理计算公司 2S ∅v({2}) − v(∅) 200权重 2/6 → 200 × 2/6 ≈ 66.67S {1}v({1,2}) − v({1}) 500 − 100 400权重 1/6 → 400 × 1/6 ≈ 66.67S {3}v({2,3}) − v({3}) 600 − 300 300权重 1/6 → 300 × 1/6 50S {1,3}v({1,2,3}) − v({1,3}) 1000 − 700 300权重 2/6 → 300 × 2/6 100φ₂ 66.67 66.67 50 100 283.33 万对于公司 3S ∅v({3}) − v(∅) 300权重 2/6 → 300 × 2/6 100S {1}v({1,3}) − v({1}) 700 − 100 600权重 1/6 → 600 × 1/6 100S {2}v({2,3}) − v({2}) 600 − 200 400权重 1/6 → 400 × 1/6 ≈ 66.67S {1,2}v({1,2,3}) − v({1,2}) 1000 − 500 500权重 2/6 → 500 × 2/6 ≈ 166.67φ₃ 100 100 66.67 166.67 433.33 万验证φ₁ φ₂ φ₃ 283.33 283.33 433.33 1000 万 v({1, 2, 3})满足有效性公理。这个例子完整展示了 Shapley 值的计算流程也直观地体现了它“考虑所有可能合作顺序”的核心思想。注意一个有趣的细节公司 1 和公司 2 的 Shapley 值居然一样都是 283.33 万尽管公司 2 单干的收益200 万比公司 1100 万高一倍。这是因为公司 1 在与公司 3 合作时贡献非常大v({1,3}) − v({3}) 400 万拉高了它的平均边际贡献。Shapley 值的“公平”不只看单打独斗的能力更看合作中的催化作用。五、从博弈论到机器学习跨越的奥秘现在我们终于可以来回答那个最关键的问题了博弈论里的 Shapley 值是怎么跟机器学习模型解释联系起来的这个跨越由 Scott Lundberg 和 Su-In Lee 在 2017 年的论文A Unified Approach to Interpreting Model Predictions中完成。他们的核心洞见非常精妙把机器学习模型的预测过程看作一个合作博弈。论文提出了一个统一的解释框架——SHAPSHapley Additive exPlanations它为每个特征分配一个特定预测的重要性值。SHAP 的核心贡献包括(1) 识别出一类新的可加性特征重要性度量以及 (2) 理论结果表明该类中有一个具有一组理想属性的独特解决方案这个方案统一了六种现有方法。那么“合作博弈”是怎样映射到“机器学习”的下表清晰地展示了这个映射关系合作博弈中的概念机器学习中的对应玩家Player特征Feature联盟Coalition特征的子集特征函数 v(S)只使用 S 中特征时模型的预测输出玩家 i 的边际贡献加入特征 i 后预测值的变化总收益 v(N)使用所有特征时的预测值在这个映射下Shapley 值的计算逻辑完美保留我们评估每一个特征在所有可能的特征子集上的“边际贡献”然后加权平均就得到了该特征对当前预测的“重要性”。这个值被专门称为 SHAP 值它是 SHAP 方法的核心所在。更重要的是博弈论中的四大公理在机器学习中也完美对应——对称性、有效性、冗员性和加法性构成了特征归因的公平基础。Lundberg 和 Lee 证明了SHAP 是唯一同时满足局部精度、缺失性和一致性三个理想属性的可加性特征归因方法。这个理论结果赋予了 SHAP 坚实的数学基础这也是它能够在众多模型解释方法中脱颖而出的根本原因。小结Shapley 值之所以能从 1953 年的博弈论论文“穿越”到今天的机器学习领域是因为它解决的是一个根本性的问题如何公平地衡量每一个参与者对整体成果的贡献这个问题在经济学中重要在机器学习中同样重要。无论是分配合作收益的“玩家”还是影响模型预测的“特征”本质上都是在回答“谁的贡献有多大”这个问题。Shapley 值用一套简洁而严谨的数学框架给出了唯一满足公平公理的答案。这也正是 SHAP 这个名字中“Shapley”的真正分量——它不仅是一个算法更是一套被数学证明为“公平”的归因哲学。