計算式
$$
\phi_i\,(N, v) = \sum_{S \subseteq N\i} \frac{|S|! (N - |S| - 1)!}{N!} \left( v(S\,\cup\,i) - v(S)\right)
$$
具体例
参加者とその報酬について、SHAP(SHapley Additive exPlanations)で機械学習モデルを解釈する の設定を引用した。
| 参加者 | 集合表記 | 報酬 |
|---|---|---|
| A君 | {A} | 6 |
| B君 | {B} | 4 |
| C君 | {C} | 2 |
| A君とB君 | {A, B} | 20 |
| A君とC君 | {A, C} | 15 |
| B君とC君 | {B, C} | 10 |
| A君とB君とC君 | {A, B, C} | 24 |
A, B, C の参加順には 3! = 6 通りある。各参加順における A 君の貢献を、「A君が参加したタイミングで報酬がいくつ増えたか」として定義すると、下記のように求められる。
| 参加順 | 0 人 | 1 人 | 2 人 | 3人 | A 君の貢献 |
|---|---|---|---|---|---|
| 参加順1: A君→B君→C君 | {} 0 | {A} 6 | {A, B} 20 | {A, B, C} 24 | 6 - 0 = 6 |
| 参加順2: A君→C君→B君 | {} 0 | {A} 6 | {A, C} 15 | {A, B, C} 24 | 6 - 0 = 6 |
| 参加順3: B君→A君→C君 | {} 0 | {B} 4 | {A, B} 20 | {A, B, C} 24 | 20 - 4 = 16 |
| 参加順4: B君→C君→A君 | {} 0 | {B} 4 | {B, C} 10 | {A, B, C} 24 | 24 - 10 = 14 |
| 参加順5: C君→A君→B君 | {} 0 | {C} 2 | {A, C} 15 | {A, B, C} 24 | 15 - 2 = 13 |
| 参加順6: C君→B君→A君 | {} 0 | {C} 2 | {B, C} 10 | {A, B, C} 24 | 24 - 10 = 14 |
A 君の貢献度は、各パターンにおける貢献の平均値として下記のように求められる。
$$(6 + 6 + 16 + 14 + 13 + 14)\,/\,6 = 11.5$$
一般化
ある参加順において i よりも前に参加していた人々の集合を S と表記すると、その参加順における i の貢献は下記のように求められる。すなわち、各パターンにおける i の貢献は、「i よりも前に誰が参加していたか」に基づいて計算される。
$$v(S\,\cup\,i) - v(S)$$
i よりも前に参加した人は |S| 人、i より後に参加した人は N - |S| - 1 人なので、N! 通りの参加順のうち、このような参加順の数は下記のように表される。
$$|S|! \times (N - |S| - 1)!$$
S としては、全体から i を除外したもののうち、自由に選んでよい。可能な全ての S を対象としてこれらの積和を計算し、N! で除することで、Shapley 値を計算することができる。
問題点
N! 通りの参加順について考慮する必要があるので、N が増えると計算時間も膨大になる。機械学習の手法としては、多項式時間で計算可能な SHAP 値などが使用される。