猫になりたい

コンサルのデータ分析屋、計量経済とか機械学習をやっています。pyてょnは3.7を使ってマスコレルウィンストングリーン。

機械学習:SHAP valueの論文を理解する

NIPS2017の論文、 A Unified Approach to Interpreting Model Predictions で提案されたSHAP valueについて、SHAP valueの式の中身を理解することに重点を置いてまとめました。
合わせて続編の論文である [1802.03888] Consistent Individualized Feature Attribution for Tree Ensembles についても少し触れます。

shapパッケージの使い方、提案された計算アルゴリズムの詳細については触れません。

SHAP valueとは

SHAP valueとは機械学習モデルの中身を説明するための手法です。

機械学習を実運用するにあたってモデルがどうしてその予測結果を出したのかの判断ロジックが問題になる場合があります。 通常、その様な説明性をモデルに求める場合は線形回帰を使うしか無く、予測能力を重視した場合は解釈性については諦めるしかありませんでした。 複雑なモデルの中身を可視化する方法はLIME等いくつかが提案されていましたが、その手法を用いると理論的にどう良いのかは明らかではありませんでした。*1

筆者たちは以前に提案された、モデルを解釈するための手法の幾つかはAdditive Feature Attribution Methodsという枠組みで説明できることを明らかにした上で、 Local accuracy、Missingness、Consistencyという望ましい性質を持つ唯一の指標を提案しました。
これがSHAP valueです。

但し、SHAP valueをそのまま求めるのは計算量が多くて大変なので、著者達は一定の仮定のもとでの高速な計算方法を提案しています。 また決定木とその応用モデルでは仮定を置かずにSHAP valueの高速な計算を行う手法も提案しています。

SHAP valueはゲーム理論に登場するshapley valueというものを各説明変数が予測に寄与する度合いとして使用しています。 そのため、以下ではまずShapley valueについて解説し、続いてSHAP valueについてまとめます。
Shapley valueについてご存知の方はSHAP valueのセクションまで飛ばして下さい。

Shapley value

ここではSHAP valueのアイディアに使われているShapley valueについて説明します。

Shapley valueとは

Shapley valueとはゲーム理論の中の協力ゲーム理論に出てくる概念です。 「複数人で協力して何某かの利得(報酬)が得られるゲームがあったとき、その利得をどの様に分けるのが公平か」、という問題を考えるとShapley valueに基づく配分は幾つかの点で望ましい利得の配分を達成します(ここではShapley valueの望ましさについては触れません)。 具体例を考えてみましょう。

今A、B、Cの3人のプレイヤーがそれぞれ事業を始めようとしているとします。
それぞれが別々に事業を起こしても良いのですが、皆が協力して事業を行ったほうが利益は大きくなるでしょう(この場合利益が利得に該当します)。 そこでA、B、Cで協力して事業を起こしたところ、100万円という利益を得ました。さて、この100万円をどう分配するのが公平なのでしょうか。

1つの考えうる方法は、それぞれのプレイヤーが居たときと居ないときでの利得の差を各プレイヤーの貢献度と見做す方法です。
最初Aが一人で事業を行っていてそこにB、Cという順番でプレイヤーが加わったとします。
提携(協力関係のこと)に加わっているプレイヤーの集合Sが与えられたときに、提携 Sが生み出す利益を v(S)と定義するとそれぞれのプレイヤーの貢献度は、

  • Aの貢献度: v(\{A\}) - v(\{ \})
  • Bの貢献度: v(\{A, B\}) - v(\{A \})
  • Cの貢献度: v(\{A, B, C\}) - v(\{A, B \})

と表現できます。
 v(\{ \})は提携に誰も加わっていない、つまり事業を誰も行っていない状態と考えて下さい。

しかしこれには提携に入ってきた順番で貢献度が変わる場合に対応できません。
例えばB、とCが同じ様なスキルの人材だったとき、スキルは同じにもかかわらず先に提携に入ったというだけでBの貢献度が高くなってしまいます。*2
そこで、全ての「プレイヤーが提携に参入する順番」が等確率で起きると仮定したときの貢献度を求めることでプレイヤーが参入する順番に依存しない貢献度が計算しよう、と考えたのがShapley valueです。

計算例

先の例でShapley valueを計算してみましょう。
提携に加わる順番を次の様に表すと定義します。

 A ← B ← C := A、B、Cの順番に提携に加わる

提携への加わり方のパターンを縦軸に、各プレイヤーの貢献度を横軸に取った、各パターンに於けるプレイヤーの貢献度の表を作ると次のようになります。

提携の加わり方 Aの貢献度 Bの貢献度 Cの貢献度
A ← B ← C  v(\{A\}) - v(\{ \})  v(\{A, B\}) - v(\{A \})  v(\{A, B, C\}) - v(\{A, B \})
A ← C ← B  v(\{A\}) - v(\{ \})  v(\{A, B, C\}) - v(\{A, C \})  v(\{A, C\}) - v(\{A \})
B ← A ← C  v(\{A, B\}) - v(\{B \})  v(\{B\}) - v(\{ \})  v(\{A, B, C\}) - v(\{A, B \})
B ← C ← A  v(\{A, B, C\}) - v(\{B, C \})  v(\{B\}) - v(\{ \})  v(\{B, C\}) - v(\{B \})
C ← B ← A  v(\{A, B, C\}) - v(\{B, C \})  v(\{B, C\}) - v(\{C \})  v(\{C\}) - v(\{ \})
C ← A ← B  v(\{A, C\}) - v(\{C \})  v(\{A, B, C\}) - v(\{A, C \})  v(\{C\}) - v(\{ \})

Table 1.

さて、各提携にから得られる利得が以下であったとしましょう。

$$ \begin{align} v(\{A, B, C\}) &= 100 \\ v(\{A, B\}) = v(\{B, C \}) &= v(\{A, C\}) = 100 \\ v(\{ A \}) = v(\{ B \}) &= v(\{ C \}) = 0 \\ \end{align} $$

この時Shapley valueは次のようになります。

提携の加わり方 Aの貢献度 Bの貢献度 Cの貢献度
A ← B ← C 0 50 0
A ← C ← B 0 0 50
B ← A ← C 50 0 0
B ← C ← A 0 0 50
C ← B ← A 0 50 0
C ← A ← B 50 0 0
======== ======== ======== ========
合計 100 100 100
Shapley value 50/3 50/3 50/3

Table 2. 例えばAの貢献度は (0+0+50+0+0+50) \div 60 = \frac{50}{3}という様に計算される。
他のプレイヤーについても同様。

以上によりこの例ではどのプレイヤーのShapley valueも \frac{50}{3}になりました。
つまりA、B、Cにそれぞれ \frac{50}{3} \approx 16.6 万円ずつ分配するのが良いという結論になります。

Shapley valueの計算式

以上の様に導出したShapley valueですが、計算式を一般化すると各プレイヤーのShapley value  \phi_iは次のように求められます。

Shapley value $$ \begin{align} \phi_i = \sum_{S \subseteq F \setminus \{i\}} \frac{|S|! (|F| - |S| - 1)!}{|F|!} [ v(S \cup \{ i \} ) - v(S) ] \end{align} $$

ここで、

  •  Fは全プレイヤーの集合
  • Sはプレイヤー iが提携に入る前に既に提携に加わっているプレイヤーの集合

です。
このShapley valueの式の意味を図解すると以下のようになります;

f:id:shikiponn:20190609160500p:plain:w600
Figure 3. Shapley valueの数式の意味

SHAP valueはこのShapley valueの式を使用して計算します。


スポンサーリンク

SHAP value

SHAP valueとShapley valueの違い

Shapley valueのセクションで述べたようにSHAP valueはShapley valueの計算式を 使用して算出します。そのためSHAP valueはShapley value殆どそのものと言っても差し支えありません。

SHAP valueとShapley valueの唯一の違いは計算の一部にあります。
A、B、Cの三人のプレイヤーからなる協力ゲームのShapley valueを求めるとき、Bの次にAが提携に参加した時のBの貢献度は提携からの利得を計算する関数 v()を用いて次の様に計算します。

$$ \begin{align} v(\{ A, B \}) - v(\{ A \}) \end{align} $$

ここではプレイヤーBは最初のv()にしか入力されていませんし、プレイヤーCはどちらの v()にも入力されていません。 しかし機械学習のモデルで特徴量Aは入れるがBは入れない(欠損にする)ということは出来ません。

そこでSHAP valueでは上記の様な場合、missingに該当する変数について期待値を取ることでこの問題を回避しています。
つまりSHAP valueの計算だと上式は、

$$ \begin{align} E _{C} [v( A, B, C | A, B )] - E_{B, C} [v( A, B, C | A ) ] \end{align} $$

という風になります。

SHAP valueの求め方

ではSHAP valueの計算式を見てみましょう。
あるサンプルに於ける特徴量 iのSHAP value  \phi_iはstraightforwardには以下のように計算できます。 *3

SHAP value $$ \begin{align} \phi_i = \sum_{S \subseteq F \setminus \{i\}} \frac{|S|! (|F| - |S| - 1)!}{|F|!} [ f_x (S \cup \{i\}) - f_x(S) ] \tag{1}\\\\ where \quad f_x(S) = f(h^{-1}_x (z')) = E[f(x) | x_S ] \end{align} $$

ここで、

  •  Fは全ての特徴量の集合のindexラベル
    (あるサンプルの特徴量を配列として考えたときのindexと考えれば良い)
  •  fは学習をさせた機械学習のモデル
  •  z' \in \{ 0, 1 \}^{|S|}、つまり特徴量 iを加える前に既にモデルに投入されている特徴量の数だけの長さの \{0, 1\}ベクトル
  •  h^{-1}_x (z')z'の要素を0ならmissingに、1なら元の特徴量にmapする関数
    (map後のベクトルは[1]ではzと記載)
  •  f_x(S) = E[f(x) | x_S ]S番目の特徴量x_Sを予測モデルf()に入力した時のf()の期待値
    •  f_x(S \cup \{i\})の場合は f_x(S \cup \{i\}) = E[ f(x) | x_{S \cup \{ i \}} ] となる

を表します。

SHAP valueの意味

では(1)式で求められるSHAP valueはどう解釈すればいいのでしょうか。
\sum以降を、

$$ \begin{align} \frac{|S|! (|F| - |S| - 1)!}{|F|!} \tag{2} \end{align} $$

と、

$$ \begin{align} f_x (S \cup\{i\}) - f_x(S) \tag{3} \end{align} $$

の2つに分けると、

  • (3)はS番目の特徴量を x_Sに固定したとき、 x_iを固定したときと固定しなかった時の予測値の差の期待値
  • (2)はi番目の特徴量以外の全特徴量の集合が取りうる組合せの内、(3)で固定した特徴量の組合せSが起きうる割合

を示しています。

よってSHAP valueの計算式は、特徴量x_iを固定した時としなかった時の予測値の差の期待値(3)をその発生確率で重み付けた平均 (4)、 つまり i番目の特徴量x_iを観測値に固定した時としなかった時での、予測値の差の期待値が \phi_iであると考えて良さそうです。 誤解を恐れずにわかり易く言い換えると、「この特徴量 x_iがあることで、あてずっぽう*4に予測をするよりは \phi_iだけ予測が改善した」と言えるでしょう。

説明変数に欠損がある時のfが計算可能であればSHAP valueは本来、特徴量x_iを追加した時の予測値の増減幅の期待値を意味するのですが、モデルへの入力をmissingにすることは出来ないので先述の様な解釈になっています。私の理解があっていれば、これはXGBoostの様にnanを取り扱えるように設計されているモデルについても同様です。 *5

理論上のSHAP valueの解釈は明瞭だと思いますが、実際に計算されているSHAP valueが表している意味をビジネス側の人間に理解してもらうのは難しい様に感じます。

計算例

数式だけ追ってもよくわからないので具体的な例を考えてみましょう。
ここでは例としてscikit-learn内のsklearn.dataset.load_iris()で得られるirisデータの1サンプル目を用います。
データの中身は以下の様になっています。

target sepal length ( := x_1) sepal width ( := x_2) petal length ( := x_3) petal width ( := x_4)
0 (Setosa) 5.1 3.5 1.4 0.2

また、以下では x = [ x_1, x_2, x_3, x_4 ]とします。

ここでは仮に i = 3, S = \{ 5.1, 3.5 \}、 つまりpetal lengthのSHAP value  \phi_3を計算する中で、 sepal widthを 5.1に、sepal lengthを3.5に固定した時に、petal lengthを1.4]に固定した時としなかったときでの 予測値の差のpetal widthに関する期待値、を計算する場合を考えます。 (本来計算したいのは、 「sepal widthとsepal lengthが既に特徴量として入力されている時にpetal lengthを特徴量に加えたときのpetal lengthの予測への貢献度 」 であることに注意)

この時、各数字をSHAP valueの計算式の各変数に当て嵌めると、

  •  F = \{ 1, 2, 3, 4 \}
  •  |F| = 4
  •  S = \{ 1, 2 \}
  •  x_S = \{ 5.1, 3.5 \}
  •  z' = \{ 1, 1 \}
  •  f_x(S \cup \{ i \}) =  E_{x_4}[ f(x) | x_1 = 5.1, x_2 = 3.5, x_3 = 1.4 ]
    • x_4x_{S \cup \{i\}}に含まれていないのでmissingとして扱う必要があるが、計算上はE _ {x_4}として消す
  •  f_x(S ) =  E _ {x_3, x_4}[ f(x) | x_1 = 5.1, x_2 = 3.5 ]
    • こちらでもx_3, x_4x_Sに含まれていないのでmissingとして扱う必要があるが、計算上はE _ {x_3, x_4}として消す

となります。
そして式(2)と(3)はそれぞれ、

$$ \begin{align} (2) = \frac{|S|! (|F| - |S| - 1)!}{|F|!} = \frac{2! 1!}{4!} \end{align} $$

と、

$$ \begin{align} (3) &= f_x (S \cup\{i\}) - f_x(S) \\ &= E_{x_4}[ f(x) | x_1 = 5.1, x_2 = 3.5, x_3 = 1.4 ] \\ & \quad - E_{x_3, x_4}[ f(x) | x_1 = 5.1, x_2 = 3.5] \end{align} $$

となります。

実際にはこの計算をSの取りうる全ての組み合わせに対して、特徴量の数( i)だけ計算することになります。

SHAP valueの満たす望ましい性質

さて、ここまでShpley valueとSHAP valueの相違点と、SHAP valueの計算方法を見てきましたがSHAP valueの良さはどんなところにあるのでしょうか。

過去にもLIMEやDeepLIFTなど、機械学習のモデルを解釈する方法(説明モデルと呼ばれる)は模索されてきましたがどれを使用するのが理論的に良いのかということは明らかになっていませんでした。 しかしAdditive Feature Attribution Methodsという機械学習のモデルを解釈するための説明モデルを考えると、過去に提案された6つの説明モデルはこの枠組みで説明できると筆者達は述べています。
そしてAdditive Feature Attribution Methodsの枠組みの中で以下の3つの望ましい性質をもつユニークな解はSHAP valueのみであることを明らかにしています。

Additive Feature Attribution Methodsとは

モデルf()と説明変数のベクトル xf()を説明するシンプルな説明モデルg()とその入力であるxを単純化したx' があるとします。 この時、Additive Feature Attribution Methodsとは以下のようにx'の線形結合でg()を表すモデルを指します。

$$ \begin{align} g(x') = \phi_0 + \sum_{i=1}^{|F|} \phi_i x'_i \end{align} $$

尚、 Fは全ての特徴量の集合です。

SHAP valueはこのクラスに属する推定量の中で以下の3つの特徴を満たす唯一の解です。

1. Local accuracy

Local accuracyとは任意の入力xに対して、元のモデルと説明モデルの予測値は同じになることを意味します。

言い換えると、予測値を各変数の貢献度に分解でき、かつ貢献度を解釈する際に交互作用の影響を考えなくて良いということなので確かに実用上望ましい性質だと言えそうです。

Local accuracyは数式だと以下のように表されます。

$$ \begin{align} f(x) = g(x') = \phi_0 + \sum_{i=1}^{|F|} \phi_i x'_i \end{align} $$

2. Missingness

Missingnessとは、説明モデルのある特徴量x_iが欠損している場合(SHAPの定義だとx'_i = 0 )、対応する貢献度  \phi_i0になることを意味します。 当たり前ですが、最初から変数が欠損していることはない、つまりSHAPの例だと z_i' x_i'は全て1になっている筈なのですが、理論上は両者に最初から0が含まれている(欠損がある)場合が許されてしまいます。

この条件はそういった場合でもLocal accuracyを成立させるための条件であり、証明の都合上導入された性質であって実用上望ましい性質というわけではない様です(著者がそのようなことを述べている。[4][5] )。

Missingnessは数式だと、

$$ \begin{align} x_i' = 0 \Longrightarrow \phi_i = 0 \end{align} $$

となります。

3. Consistency

Consistencyとは、「現在のモデル fからある特徴量x_iにより依存するようなモデル f'にモデルを変更した時、 f'に於けるx_iの貢献度は fに於けるそれ以上で無けれなばならない」ということを意味します。

Consistencyが成り立つことにより、モデル間で特徴量の貢献度同士を比較することが可能になります。

Consistencyを数式で表すと以下の様になります。

$$ \begin{align} If \quad f_x'(S \cup\{i\}) - f_x'(S) \geq f_x(S \cup\{i\}) - f_x(S) \text{ for all } S \in F \setminus \{i\} \quad \\ then \quad \phi_i(f', x) \geq \phi_i(f, x) \end{align} $$

SHAP valueを計算する壁

上述したようにSHAP valueは3つの望ましい性質を持っていますが、計算するには2つの壁があります。

1. 説明変数の数に対して指数的に増える計算量

 D個の説明変数があるとき、SHAP valueをn番目のサンプルに対して計算することを考えましょう。
このとき、 |F|個の貢献度 \{ \phi_i \}_{ i = 1 \dots |F| }それぞれについて、 |F|個の特徴量一つ一つを使用する・しないの組合せ(つまり 2 ^{|F|}通り)だけ f_x (S) f_x (S \cup \{ i\})を計算しなければなりません。

2.モデルの予測値を効率的に計算する難しさ

式(2)で出てくる E[ f(x) | x_S ] は機械学習のモデルをサンプルサイズの個数だけ回して、 i番目の特徴量について期待値を取ることを意味しています。しかしモデルによっては推論は決して早いとは言えず、推論を 2 ^D回すのが現実的な時間で終わらない可能性があります。

SHAP valueの効率的な計算方法

著者達はこの問題を解決するために、

  • 論文[1]では説明変数間の独立性やモデルの線形性を仮定した上で、モデルフリー(model-agnostic)なアルゴリズム2種類と一部のクラスのモデルについて効率的に計算が出来るmodel-specificなアルゴリズム4つを提案しています
  • 論文[2]ではDecision Treeとそのアンサンブル手法(XGBoost等)に対して仮定を置かないで効率的な計算が出来るアルゴリズムを提案しています

アルゴリズムの詳細については読んでいないのでここでは触れませんが、筆者達によるpython実装[3]が公開されているためこちらを利用することが出来ます。

SHAPのメリット・デメリット

以下は論文を読んで感じたSHAP valueのメリット・デメリットです。

メリット

  • SHAP value自体は何の仮定も置かずに使える
  • 有名なLIMEを含む幾つかのモデルを統一的に表せるAdditive Feature Attribution Methodsクラスの中でLocal Accuracy、(Missingness、)Consistencyを満たす唯一の解である
  • 貢献度の平均を取っているので解釈の時に特徴量間の交互作用を意識しなくて良い
  • Decision Treeとそのアンサンブルモデルでは高速にSHAP valueが計算できる

デメリット

  • Decision Treeとそのアンサンブルモデル以外でSHAP valueを効率的に求める手法は、いづれも特徴量同士の独立性やモデルの線形性を仮定している。
    しかしこれらが成り立つことは少ないと考えれられるので使いにくい。
  • 理論上のSHAP valueと違い、実際に計算しているSHAP valueが何を表しているのか分かりづらい。
    そのためビジネス側の人間に説明するために使用するのは難しそうに感じる。

よくわからなかった点

  • SHAP valueは理論上はLocal Accuracy、(Missingness、)Consistencyの3つを満たしますが、実際に計算しているSHAP valueがどれだけ理論上のSHAP valueと同じものなのかは分かりませんでした。

スポンサーリンク

まとめ

機械学習を現実に適用するにあたって問題と為る「このサンプルに対してモデルがこの予測を下したのはなぜか」という説明を一定の理論的保障の下で可能としてくれるSHAP valueの提案論文を読みました。 機械学習の応用でよく使われているGBDTでは仮定を置かずに正確な値を高速に計算出来るようなので、今後サンプルレベルでモデルの挙動を見たいときはまづ最初にSHAP valueを使って見るのが良さそうです。

一方で、DNN等決定木とその派生モデル以外のモデルについては特徴量間の独立性やモデルの線形性という強い仮定が無いとSHAP valueは計算出来ません。 これらのモデルについては他の手法も検討する必要がありそうです。

また、SHAP valueは解釈が難しいことに加え、LIMEの様に「この変数がこう変わったらこれくらい予測値が変わる」という言い方は出来ないため、そういう場合には独立性と線形性の仮定を置いた上でKernel SHAPを使うのが良いかも知れません。

今後は実際にSHAP valueを使用したり、[2]の実験結果を読むなどしてさらなる理解を深められればと思います。

参考文献

  1. 原論文1:
    [1705.07874] A Unified Approach to Interpreting Model Predictions
  2. 原論文2:
    [1802.03888] Consistent Individualized Feature Attribution for Tree Ensembles
  3. shap パッケージのGit repo.:
    GitHub - slundberg/shap: A unified approach to explain the output of any machine learning model.
  4. Missingnessに関するissue:
    Question about missingness · Issue #175 · slundberg/shap · GitHub
  5. 著者のブログ記事:
    Interpretable Machine Learning with XGBoost – Towards Data Science
  6. Shapley valueについての東工大講義資料:
    http://www.ocw.titech.ac.jp/index.php?module=General&action=DownLoad&file=201427708-175-0-76.pdf&type=cal&JWC=201427708
  7. One Feature Attribution Method to (Supposedly) Rule Them All: Shapley Values
  8. SHAP for explainable machine learning

*1:先行研究をすべて見たわけではないので間違っているかもしれません。

*2:Aが起業家でB、Cが経理の場合を考えてみましょう。経理が居ないところにBが1人入れば業務は効率化される様になりますが、Cを加えて経理を2人に増やしても経理が0人のときから1人に増えたときほど業務は効率化されないでしょう。

*3:ここでは原論文[1]ではなく原論文[2]の式を用いていることに注意して下さい。

*4:モデルの予測値の全体平均を予測値とするという意味

*5:XGBoostはnanを取り扱えるように設計されていますが、それはあくまでnanを一つの変数として扱っているからです。SHAP valueでいうmissingはそもそもその変数自体がまるごと存在しないことを表しています。[4]