shapley value(シャープレイ値)とSHAPについて理解する

こんにちは。ざわかける！のざわ(@zw_kakeru)です。
今回はshapley value(シャープレイ値)とSHAPについてまとめてみます。
機械学習の中の「説明可能なAI」の文脈で出てくる概念ですね。
自分の理解を進めるためのメモです。

概要

まずは全体のまとめからです。
shapley値とSHAPについて、概要は次のとおりです。

• 協力ゲーム理論における概念であるshapley値を、機械学習の「説明可能なAI」の文脈に適応したのがSHAPである
• SHAPによってモデルの予測結果がブラックボックスではなく、どの特徴量が結果にどのような影響を与えたのかが分かるようになった
• shapley値
  • プレイヤーの貢献度を、そのプレイヤーが加わる前と後のすべての状況で報酬の差を計算して平均を取った値として定義する
  • この値を用いて報酬の分配を行う
• SHAP
  • shapley値におけるプレイヤーを特徴量、報酬を予測値に置き換えることによって、あるテストデータへの予測に対する各特徴量の貢献度を数値化することができた
  • 「その特徴量(プレイヤー)が参加していない」状況は、その特徴量の取る値の平均を使って代用する

以降の章ではそれぞれについて詳しく述べていきます。

shapley(シャープレイ)値

協力ゲーム理論において出てくる概念で、獲得した利得を各プレイヤーへ公正に分配する方法の一案です。
各プレイヤーに対してこの値を計算し、これを貢献度とみなして利益を分配します。
提唱されたのは1953年の経済学の文脈、提唱者はロイド・シャープレイさん(アメリカ)です。


例えば、AさんとBさんとCさんの3人で一緒に丸一日バイトして合計30万円の利益を得たとします。
これを3人で山分けする時、それぞれいくらずつのお金がもらえるでしょうか。
一番単純に考えるなら一人10万円ずつとなるでしょう。
しかしながら、例えばAさんが超絶仕事できるマンで、実質Aさんがほぼすべての利益を上げていた場合、この一人10万円ずつ分配は公正とは言えませんよね。

よってこの場合、得られた利益に対するAさんBさんCさんそれぞれの「貢献度」を計算し、その比率をもって30万円を山分けするのが適切であるといえます。

それはそうだという感じですが、ではこの「貢献度」って何ぞ、どうやって求めたらいいのという話になってきますね。

ここで天才であるシャープレイさんは、「発生しうるあらゆる状態において、あるプレイヤーがいない状態で得られる利得とそこへそのプレイヤーが加わった状態で得られる利得を比較し、その差分の平均がそのプレイヤーの貢献度である」ってすればいいんじゃね？と提案しました。
例えばAさんの貢献度を計算したい場合、発生しうるAさんがいない状態の利得とそこにAさんが加わった状態の利得について考えます。
発生しうるAさんがいない状態とは次の4パターンです。

1. 誰もバイトしなかった
2. Bさんだけが一日バイトした
3. Cさんだけが一日バイトした
4. BさんとCさんだけが一日バイトした

そして、上記の4パターンそれぞれにAさんが加わった状態は下記のようになります。

1. Aさんだけが一日バイトした
2. AさんとBさんだけが一日バイトした
3. AさんとCさんだけが一日バイトした
4. AさんとBさんとCさんが一日バイトした

そして、下の1~4のパターンで得られる利益から、対応する上の1~4のパターンで得られる利益を引いて平均を取ることで、Aさんが働くあらゆるパターン※1において、「Aさんが加わったことによってどのくらい利益が増えたのか」、すなわちAさんの「貢献度」を得ることができます。
(※1 厳密には違います。が、ここでは分かりやすくするために4パターンだけにしておきます。)

このようにして得られた「貢献度」のことをshapley値といいます。
Bさん、Cさんについても同様の計算を行なってshapley値を出せば、それぞれの貢献度が分かって公正な分配が可能になりますね。
例えばAさんのshapley値が20万、Bさんが7万、Cさんが3万となったのであれば、得られた30万の利益もAさんが20万、Bさんが7万、Cさんが3万受け取ればハッピーです。
めでたしめでたし。

※各プレイヤーのshapley値の合計は利得に一致する(数学的に考えたらわかる)ので、sharpley値はそのまま各プレイヤーの利益となります。

SHAP

SHAPは前述の協力ゲーム理論で提唱されていたshapley値の概念を機械学習の文脈に持ってきた手法で、SHapley Additive exPlanationsの略となっています。
shapley値における利得をモデルの予測値、各プレイヤーを各特徴量に置き換えることによって各特徴量の「貢献度」を数値化することに成功しました。
これによって、モデルの予測結果がブラックボックスではなく、どの特徴量が結果にどのような影響を与えたのかが分かるようになり、「説明可能なAI」の文脈で大きな進歩となったのです。
提唱されたのは2017年、提唱者はスコット・ルンドバーグさん(アメリカ)(マイクロソフトの社員)です。

例えば、特徴量aとbとcを使って関数fに回帰し、とある目的変数yを予測するとします。
すなわち y = f(a, b, c)です。

とある出力yの値に対して特徴量a、b、cそれぞれがどのくらい影響を与えたかを算出したい場合、
shapley値の時と同様に、「発生しうるあらゆる状態において、ある特徴量が無い状態で得られる出力とそこへその特徴量が加わった状態で得られる出力を比較し、その差分の平均がその特徴量の貢献度である」と考えることができます。
例えばある出力に対する特徴量aの貢献度を計算したい場合、発生しうるaが無い状態の出力とそこにaが加わった状態の出力について考えます。
発生しうる特徴量aが無い状態とは次の4パターンです。

1. 特徴量が1つもない
2. bだけで出力をした
3. cだけで出力をした
4. bとcだけで出力をした

そして、上記の4パターンそれぞれにaが加わった状態は下記のようになります。

1. aだけで出力をした
2. aとbだけで出力をした
3. aとcだけで出力をした
4. aとbとcで出力をした

そして、シャープレイ値の時と同様に、下1~4のパターンで得られる出力(予測値)から、対応する上の1~4のパターンで得られる出力(予測値)を引いて平均を取ることで、この出力において、「aが加わったことによってどのくらい出力(予測値)が増えたのか」、すなわちaの「貢献度」を得ることができるのです。

しかし、ここで疑問が生じます。
shapley値の場合は、協力ゲーム理論において各プレイヤーの全ての参加パターンについてあらかじめ利得が分かっている前提でした。
すなわち、それぞれのプレイヤーが参加しなかった(いなかった)場合の利得もきちんと存在していました。
しかし機械学習モデルによる予測の出力において、「変数が無い」という状況は許されていません。
例えば、「bとcだけを使った予測」などはできないのです。
(y = f(null, b, c) みたいなことをしてyを求めることはできません。勝手に0を入れてみたりするわけにもいかないし…)
それとか、「特徴量の入力を一つもしなかった時」の予測値なんてものは存在しないのです。
これでは各パターンでの出力が得られないので貢献度も計算することができませんね。
どうすれば良いのでしょうか。

ここで天才であるルンドバーグさんは、「特徴量が無い場合を扱う時は、その特徴量の実データ(=訓練データ)が取った値の平均値を入れる」ってすればいいんじゃね？と提案しました。
すなわち「bとcだけを使った予測」というのを「aの実データの平均値とbとcを使った予測」と変換することによって、あらゆるパターンで特徴量が存在することが保証されるので「貢献度」も計算することができるようになったのです。
すなわち特徴量aが無い状態を次の4パターンとして捉え直します。

1. [aの平均]と[bの平均]と[cの平均]で出力した(≒特徴量が1つもない)
2. [aの平均]と[b]と[cの平均]で出力した(≒bだけで出力をした)
3. [aの平均]と[bの平均]と[c]で出力した(≒cだけで出力をした)
4. [aの平均]と[b]と[c]で出力した(≒bとcだけで出力をした)

そして、上記の4パターンそれぞれにaが加わった状態は下記のようになります。

1. [a]と[bの平均]と[cの平均]で出力した(≒aだけで出力をした)
2. [a]と[b]と[cの平均]で出力した(≒aとbだけで出力をした)
3. [a]と[bの平均]と[c]で出力した(≒aとcだけで出力をした)
4. [a]と[b]と[c]で出力した

これらの出力をそれぞれ比較して、差分の平均を取ることで、ようやく「aが加わったことによってどのくらい出力(予測値)が増えたのか」、すなわちaの「貢献度」を得ることができるようになりました。
めでたしめでたし。
このようにして機械学習の文脈で出力に対する各特徴量の貢献度を求める手法をSHAPといいます。

元々のshapley値と異なる点で注意すべきなのは、実データの平均値を使う影響で、算出される貢献度は特徴量a、b、cそれぞれの平均を用いて出力した予測値との差分となるという点です。
すなわち特徴量a、b、cの値の平均をfに与えて得られたy = f([aの平均], [bの平均], [cの平均])を予測のBaselineと定義し、このBaselineに対して、どれだけ変化を与えたかを「貢献度」としています。
よってshapley値とは異なり、貢献度が負の値になることも普通にあります。

SHAPのすごいところは、予測一つ一つに対してそれぞれの特徴量の貢献度をすべて計算することができる点です。
「このテストデータに対してこのように予測しました、貢献度の内訳はこうです」ということがすべてのテストデータに対して分かるので、予測の透明度が格段に上がりました。
今まで出力しか見えていなかったのがその内訳も見れるようになったので、「特徴量の捉え方が人間の直感と一致しているな」とか「似たような予測値だけど貢献度の内訳は全然違うぞ」とかが次々に分かってきています。
これはめちゃくちゃすごいことです。

例えばこれ。タイタニックの乗客の生存予測のSHAPです。
Baseline(= E[f(X)])は-0.748で、この人の生存確率(f(x))は最終的に28.9%と予測されています。
その内訳としては、女性であるというのが生存に大きく寄与しているものの、Pclass=3すなわち一番安いチケットクラスであることが生存確率を下げています。
この辺は私たちにも納得ができる結果となっていますね。
Embarked=Cすなわちフランスから乗ったことも生存に寄与してるけどこれはよく分かりません。

とかっていうことが分かるようになりました。めちゃすごくないですか。
今までは「この人の生存確率は28.9%です」しか分からなかったのがここまで詳細に、しかもテストデータごとに分かるようになったということなんですね〜。

おわりに

久しぶりに実装ではなく理論の話をした気がします。
数学的な話も書こうかと思ったんですけど、力尽きたのでまた今度気が向いたら加筆します。
(shapley値の定義の話と特性関数νの話とか。)
間違ったこと書いてたら指摘してください。
以上です。

参考

• shapley値の論文：A Value for N-Person Games
• SHAPの論文：A Unified Approach to Interpreting Model Predictions