データ分析関連のまとめ

データ分析・機械学習周りのもくもく会LTやイベント参加をまとめていきます

可視化アルゴリズムSHAPを理解するために、ゲーム理論を調べてまとめました。

技術キャッチアップ

機械学習の可視化アルゴリズムSHAPを理解するために論文を読み進めていたところ、ゲーム理論を多少理解する必要がありそうだったので、ざっくりまとめました。 (理解が間違っている点があったら指摘いただければ幸いです)

なぜゲーム理論を調べることになったのか？

  • 機械学習モデルの可視化アルゴリズムであるSHAPは勾配ブースティング等で作ったモデルでも可視化できる便利なアルゴリズムです。
  • ただ表示される値がSHAP valueなのでその値自体を理解できていないと実際に使えないと思い論文を調べました。

f:id:yhiss:20190921154618p:plain
SHAPによる局所的な可視化結果(https://github.com/slundberg/shapより)
f:id:yhiss:20190921154902p:plain
SHAPによる各変数のモデルへの寄与の可視化結果(https://github.com/slundberg/shapより)

  • 実際にSHAPに関する論文を読んでいる中でSHAP valueはゲーム理論のShapley valueを基にしている記述があったため、最終的にゲーム理論を調べることになりました。

f:id:yhiss:20190921115520p:plain
SHAP論文を読んでいる途中で、ゲーム理論のShapley valuesを理解する機運が高まる
https://arxiv.org/pdf/1802.03888.pdf

読んだ資料はこちら(協力ゲーム理論入門)

http://www.orsj.or.jp/archive2/or60-6/or60_6_343.pdf

ゲーム理論とは？

  • 大きく非協力ゲーム理論と協力ゲーム理論に分かれる。囚人のジレンマ等が有名な模様
  • 非協力ゲーム理論
    • プレイヤー(当事者)たちが様々な目的を達成するために独自に行う合理的な行動の分析
    • 主眼:どのような結果が実現するか？
  • 協力ゲーム理論
    • プレイヤー間で協力して行動することが許されている。
    • 主眼:協力により得られた便益をどう分配するか？分配すべきか？
  • 機械学習モデルの可視化(どの変数が効いているか)をはかるアプローチとしては、協力ゲーム理論が近いと思える。

特性関数形ゲーム

  • n人の当事者が協力して便益を分配する一般的な状況の分析のため、特性関数形ゲームの定義を与える
    • n人のプレイヤーの集合:N
    • Nの非空な部分集合:提携
    • 下記のNの部分集合の集合上での実数値関数:特性関数

 v:2^N \rightarrow \mathbb{R}\

v(S)は提携Sのメンバーが協力することで獲得できる便益(但し、空集合ではv=0)

例を使って定式化

  • 同じ方向に家があるA,B,Cの3人が居酒屋からタクシーに相乗りして帰宅し、最後に下車した人が料金を支払い、翌日に精算する。
    • 居酒屋からそれぞれの家に直接帰宅した場合、A:1,800円、B:2,100円、C:2,900円
    • A~B:1,800円、A~C:2,000円、B~C:2,300円
    • 最も安くなるルートで回るときのそれぞれの負担はいくらにすればよいか？
      プレイヤーの集合は

 N = \{1,2,3\}

特性関数について、全員が協力することで節約できる(A→B→Cのルート)金額は1,800+2,100+2,900-5,900=900円より


 v(\{1,2,3\})=9

同様に2人同士、1人で特性関数を計算した場合、以下のようになる。(単位:100円、1人では節約できる金額が無いので0となる)


 v(\{1,2,3\})=9,v(\{1,2\})=3,v(\{2,3\})=6,v(\{1,3\})=9,v(\{1\})=v(\{2\})=v(\{3\})=0

この例の特性関数:優加法性を満たす。
優加法性:共通するメンバーがいない2つの提携が合流して行動した方が、それぞれ独自に行動するよりも便益が低くならない
居酒屋から帰る時に違う方向の人が相乗りする場合は優加法性を満たさないと考えられます

定義1

特性関数vがS \cap T=\emptysetとなる任意の提携 S,T{\subseteq} Nに対してv(S \cup T) \geq v(S) + v(T)を満たす時、特性関数vは優加法的
考察 機械学習のモデルでは変数を増やしすぎると精度に悪影響を与える場合があるので、変数が多すぎない場合に優加法性を満たすと考えられます。
SHAPにおいてモデルの変数が多い場合にどのような挙動になるかは現時点では不明なため、SHAP本体の論文を読む必要があります

定義2

特性関数形ゲーム(N,v)において、利得ベクトルx=(x_1,x_2,...,x_n)が次の2条件を満たす時、xを配分という
(1) \sum_{i{\in}N}x_i=v(N)...全体合理性:プレイヤー全員でv(N)を全て分配していることを表す
(2) 任意のi{\in}Nに対してx_i \geq v({i})...各プレイヤーの便益が一人だけで獲得できる便益を下回らない

協力ゲーム理論による分析で用いられる解

  • コア、仁、Sharply valueが主要な解となる
  • Sharply value以外は軽く触れます

コア

  • 協力ゲーム理論の分析において最も用いられる解

    定義3

    次の配分の部分集合C(v)を特性関数形ゲーム(N,v)におけるコアという
    C(v)=x {\in}I(v)

  • コアに含まれる配分が満たす条件:提携合理性
  • コアは大きな領域になることもあったり、空集合になることもある。そのため具体的な便益の分配方法が1つ必要な状況では不十分な場合がある

仁

  • コアの考え方を活かしながら、便益の分配方法が必ず1つに定まる解

    定義4

    任意のC(v)=x {\in}I(v)に対して\theta(y){\leq}_{lex}\theta(x)を満たす配分xの集合:特性関数形ゲーム(N,v)における仁という

Sharply value

  • 提携に対するプレイヤーの貢献度の応じて便益を分配する解
  • 任意のi{\in}Nと任意の部分集合S \subseteq N/{i}に対してv(S\cup{i})-v(s):Sに対するプレイヤーiに対する限界貢献度
    • プレイヤーiがSに加わる→便益が変わるのでその差が貢献度と解釈される

      定義5

      任意の部分集合Sに対してSの要素数:sとする
      下記の {\phi}_i(v):特性関数形ゲーム(N,v)におけるプレイヤーiのSharply valueとなる


 {\phi}_i(v) = \sum_{S{\subseteq}N/\{i\}}\frac{s!(n-s-1)!}{n!}(v(S\cup\{i\})-v(S))

また全てのプレイヤーのSharpley valueを並べたベクトル:特性関数形ゲーム(N,v)におけるSharpley valueとなる

これをSHAPにおけるSHAP values(下記)と比較すると


 {\phi}_i(f,x) = \sum_{z^{'}{\subseteq}x^{'}}\frac{|z~{'}|!(M-|z~{'}|-1)!}{M!}(f_x(z^{'})- f_x(z^{'}/i))

式の構成が同じなので、ゲーム理論におけるSharpley valueの解釈がSHAP valueにも利用できそうです。
ゲーム理論におけるプレイヤー:機械学習モデルにおける変数に相当すると解釈可能
特定の変数が無い場合のモデルに対して、変数を入れた場合の貢献度を計算している

まとめ

  • SHAPにおいて重要なSHAP valueはゲーム理論におけるSharpley valueを基にしている
  • 対象となるゲーム理論はプレイヤー間で協力して行動することが想定される協力ゲーム理論
  • Sharpey Value:ゲーム理論における特性関数形ゲームの分析で用いられる解のうちの一つであり、提携に対するプレイヤーの貢献度の応じて便益を分配する解である
  • Sharpey Valueの定義はSHAP valuesと酷似しておりゲーム理論におけるプレイヤーを機械学習モデルにおける変数に置き換えると(個人的に)理解がしやすかった

Next Action

SHAPについての論文をもう1本読みます

https://arxiv.org/pdf/1802.03888.pdf