Shapley值由Lloyd Shapley在1953年提出，用于公平分配合作博弈中玩家的贡献。其核心思想是根据每个玩家在不同联盟中的边际贡献来计算其应得的收益。
公式 #
Shapley值的计算公式为： $$\phi_i(v) = \sum_{S \subseteq N \setminus {i}} \frac{|S|! , (|N| - |S| - 1)!}{|N|!} \left( v(S \cup {i}) - v(S) \right)$$ 其中：
- \(\phi_i(v)\) 是玩家 \(i\) 的Shapley值。
- \(|N|\) 是所有玩家的集合。
- \(S\) 是不包含玩家 \(i\) 的子集。
- \(v(S)\) 是联盟 \(S\) 的收益。
计算步骤 #
- 列出所有可能的联盟：考虑所有不包含玩家 \(i\) 的子集 \(S\)。
- 计算边际贡献：对于每个联盟 \(S\)，计算玩家 \(i\) 加入后的收益变化 \(v(S \cup {i}) - v(S)\)。
- 加权平均：将边际贡献乘以权重 \(\frac{|S|! , (|N| - |S| - 1)!}{|N|!}\) ，并对所有联盟求和。
用户路径追踪中的实际案例 #
在用户路径追踪中，Shapley值可用于评估不同渠道对转化的贡献。
场景 #
假设用户转化路径涉及以下渠道：
- 搜索引擎（SE）
- 社交媒体（SM）
- 电子邮件（EM）
步骤 #
- 定义收益函数：收益函数 \(v(S)\) 表示联盟 \(S\) 带来的转化次数。
- 计算边际贡献：
- 对于联盟 \({}\)，加入SE后的转化次数为 \(v{SE}\)。
- 对于联盟 \({SE}\)，加入SM后的转化次数为 \(v{SE,SM}\)。
- 对于联盟 \({SE,SM}\)，加入EM后的转化次数为 \(v{SE,SM,EM}\)。
- 计算Shapley值：
- 对每个渠道，计算其在所有可能联盟中的边际贡献，并加权平均。
示例计算 #
假设：
- \(v({})=0\)
- \(v({SE})=10\)
- \(v({SM})=5\)
- \(v({EM})=3\)
- \(v({SE,SM})=20\)
- \(v({SE,EM})=15\)
- \(v({SM,EM})=10\)
- \(v({SE,SM,EM})=25\)
计算SE的Shapley值：
- 联盟 \({}\)：边际贡献 \(v({SE}) - v({}) = 10\)
- 联盟 \({SM}\)：边际贡献 \(v({SE,SM}) - v({SM})=15\)
- 联盟 \({EM}\)：边际贡献 \(v({SE,EM}) - v({EM}) = 12\)
- 联盟 \({SM,EM}\)：边际贡献 \(v({SE,SM,EM}) - v({SM,EM}) = 15\)
加权平均：
$$\phi_{SE} = \frac{1}{3} \times 10 + \frac{1}{6} \times 15 + \frac{1}{6} \times 12 + \frac{1}{3} \times 15 = 13 $$ 类似地，计算SM和EM的Shapley值。
总结 #
Shapley值通过公平分配贡献，帮助理解各渠道在用户转化路径中的实际作用，优化营销策略。
在Shapley值的计算中，权重 \(\frac{|S|! , (|N| - |S| - 1)!}{|N|!}\) 是由组合数学和概率论推导而来的。它的目的是确保每个联盟 \(S\) 的边际贡献被公平地加权，从而反映玩家 \(i\) 在所有可能加入顺序中的平均贡献。
以下详细解释权重的计算过程：
1. 权重的来源 #
Shapley值的核心思想是：考虑玩家 \(i\) 在所有可能的加入顺序中的边际贡献，并对这些贡献进行加权平均。权重 \(\frac{|S|! , (|N| - |S| - 1)!}{|N|!}\) 表示玩家 \(i\) 在某个特定联盟 \(S\) 之后加入的概率。
公式分解： #
- \(|S|!\)：联盟 \(S\) 中玩家的排列方式数。
- \((|N| - |S| - 1)!\)：在玩家 \(i\) 之后加入的玩家的排列方式数。
- \(|N|!\)：所有玩家的总排列方式数。
因此，权重 \(\frac{|S|! , (|N| - |S| - 1)!}{|N|!}\) 表示玩家 \(i\) 在联盟 \(S\) 之后加入的概率。
2. 权重的直观理解 #
假设有 \(N={1,2,3}\) 三个玩家，我们计算玩家 \(i = 1\) 的Shapley值。所有可能的加入顺序（排列）共有 \(∣N∣! = 6\) 种：
- \(1 → 2 → 3\)
- \(1 → 3 → 2\)
- \(2 → 1 → 3\)
- \(2 → 3 → 1\)
- \(3 → 1 → 2\)
- \(3 → 2 → 1\)
对于玩家 \(1\)，我们需要计算它在每种加入顺序中的边际贡献，并赋予相应的权重。
例子： #
- 在顺序 \(1 → 2 → 3\) 中，玩家 \(1\) 是第一个加入的，其边际贡献是 \(v({1})−v({})\)。
- 在顺序 \(2 → 1 → 3\) 中，玩家 \(1\) 是第二个加入的，其边际贡献是 \(v({1, 2})−v({2})\)。
- 在顺序 \(2 → 3 → 1\) 中，玩家 \(1\) 是最后一个加入的，其边际贡献是 \(v({1, 2, 3}) − v({2, 3})\)。
3. 权重的具体计算 #
以 \(N={1,2,3}\) 为例，计算玩家 \(1\) 的权重。
可能的联盟 SS： #
- \(S={}\)
- \(S={2}\)
- \(S={3}\)
- \(S={2, 3}\)
对于每个联盟 SS，计算权重 \(\frac{|S|! , (|N| - |S| - 1)!}{|N|!}\)。
计算过程： #
-
联盟 \(S={}\)：
- \(∣S∣=0\)
- 权重：\(\frac{0!(3 − 0 − 1)!}{3!}=\frac{1 \times 2}{6}=\frac{2}{6}=\frac{1}{3}\)
-
联盟 \(S={2}\)：
- \(∣S∣ = 1\)
- 权重：\(\frac{1!(3 − 1 − 1)!}{3!}=\frac{1 \times 1}{6}=\frac{1}{6}\)
-
联盟 \(S={3}\)：
- \(∣S∣ = 1\)
- 权重：\(\frac{1!(3 − 1 − 1)!}{3!}=\frac{1 \times 1}{6}=\frac{1}{6}\)
-
联盟 \(S={2, 3}\)：
- \(∣S∣ = 2\)
- 权重：\(\frac{2!(3 − 2 − 1)!}{3!}=\frac{2 \times 1}{6}=\frac{2}{6}=\frac{1}{3}\)
4. 总结 #
权重 \(\frac{|S|! , (|N| - |S| - 1)!}{|N|!}\) 的计算方法：
- 确定联盟 \(S\) 的大小 \(∣S∣\)。
- 计算 \(∣S∣!\) 和 \((∣N∣ − ∣S∣ − 1)!\)。
- 将结果除以 \(∣N∣!\)。
在用户路径追踪的案例中，权重的作用是公平地分配每个渠道（玩家）在所有可能路径中的贡献。通过这种方式，Shapley值能够提供一种无偏的贡献评估方法。