DEIM2020 P2-23 (day2 p96)

説明可能な機械学習のための拡張シャープレイ値の厳密指数時間アルゴリズム
大泉

翼†

博紀††

有村

† 北海道大学工学部 〒 060-0814 札幌市北区北 14 条西 9 丁目†† 北海道大学大学院情報科学研究院 〒 060-0814 札幌市北区北 14 条西 9 丁目
E-mail: †monkukui@eis.hokudai.ac.jp, ††arim@ist.hokudai.ac.jp
あらましシャープレイ値は，経済学の投票指数として提案されたが，この数年，機会学習モデルにおける単一の変数の重要性尺度として，深層ニューラルネット等の非線形予測モデルを対象に，シャープレイ値の計算方法が集中的に研究され始めている．本論文では，シャープレイ値を複数の変数の組合せに拡張した「拡張シャープレイ値」を新たに定義し，与えられた予測モデルと入力データから，すべての変数の組合せに対する拡張シャープレイ値の値を一度に計算する問題を考察する．この問題に高速ゼータ変換を適用することで，素朴な O ∗ (3n ) 時間アルゴリズムを高速化して，O ∗ (2n ) 時間アルゴリズムを与える．ここに，n は予測モデルの変数の数である．
キーワード 機械学習，シャープレイ値，解釈可能性，動的計画法，高速ゼータ変換•

1 はじめに
1. 1 背景と目的
近年では機械学習手法により学習された予測モデルの解釈可能性（interpretability）の研究に注目が集まりつつある．一般に，機械学習モデルの性能は予測精度で評価され，誤差が小さいほど良いとされる．一方で，機械学習モデルの予測を意思決定に用いるとき，その予測根拠の提示が必要とされる場合がある．機械学習モデルの予測根拠を正しく提示することができれば，応用上での信頼を獲得することや，モデルの改善方法を発見する手助けになること，モデル化されるまでの過程を理解す
るのを助けることにつながる．これまでには，機械学習モデルの解釈可能性に関する研究が数多くなされている [1] [2] [3] [4]．
本研究では，特定の予測結果に対する，単一変数の重要性尺度を表すシャープレイ値に焦点を当てる．
シャープレイ値（Shapley value）[5] [6] とは，ゲーム理論において，プレーヤーの貢献度を表す指標であり，1953 年に Lloyd

S. Shapley によって提案された．近年，深層学習等の機械学習モデルの予測結果に対する単一の変数の重要性尺度として，
シャープレイ値が広く注目されている [2]．単一の変数だけで変数集合 P = {1, . . . , n} と，集合関数 v : 2P → R，変数組 ∆ ⊆ P に対して，拡張シャープレイ値 ϕ∆ ( P, v) を定義した．

•

すべての変数組 ∆ ⊆ P に対して，拡張シャープレイ値ϕ∆ ( P, v) を計算する問題 ESV を定義した．
•

ESV を効率よく解くアルゴリズムを与えた．

拡張シャープレイ値 ϕ∆ ( P, v) を 1 つ計算するのは O ∗ (n2 )時間かかる．ナイーブなアルゴリズムでは，O(2n ) 個ある変数組 ∆ それぞれに対して拡張シャープレイ値を計算するのでO ∗ (4n ) 時間を要する．これを改善するために，厳密指数時間
アルゴリズム分野で知られている高速ゼータ変換 [7] を適用することで，時間計算量 O ∗ (2n ) と空間計算量 O ∗ (2n ) でこの問題を解くことができた．ここに，O ∗ ( f (n)) とは，多項式因子を無視した表記法である．より正確には，関数 f と g に対して， f (n) = O( g(n)Poly(n)) であるとき， f (n) = O ∗ ( g(n)) と表される．ここに，Poly(n) は n に関する多項式である．

2 準

備

2. 1 特性関数形ゲーム
協力ゲームにはいくつかの表現方法が存在するが，ここでは特性関数形ゲームの定義を与える．

なく，複数の変数組に対する重要度を計算することができれば，非負整数 n に対して，プレイヤー集合を P = {1, . . . , n} とす

学習モデルの予測根拠により妥当な解釈を与えることができる

る．プレイヤー集合 P の各要素はプレイヤー（player）と呼び，と考えた．

部分集合 S ⊆ P を提携（coalition），集合関数 v : 2P → R を特本研究では，複数の変数組に対する拡張シャープレイ値を定性関数（characteristic function）と呼ぶ．それぞれの S ⊆ P に義し，すべての変数組に対する拡張シャープレイ値を計算する

対して v(S) は，提携 S に属するプレイヤーたちが協力して行問題を考察する．さらに，その問題を解く効率良いアルゴリズ

動した際に S 全体が得ることができる利得を表す．よって以降

ムを与える．

では，v(S) を S の利得と呼ぶ．ここで，特性関数形ゲームの定1. 2 主 結 果
本研究の主結果を以下に示す．

義を述べる．
定義 1. 特性関数形ゲームとは，プレイヤー集合 P = {1, . . . , n}と特性関数 v : 2P → R の組 ( P, v) である．ここに，n は非負表1

P = {1, 2, 3} におけるプレイヤー 1 の限界貢献度

表2

P = {1, 2, 3} におけるプレイヤー組 {1, 2} の限界貢献度の例
全体提携の形成過程 プレイヤー組 {1, 2}

全体提携の形成過程 プレイヤー 1

1→2→3

0

1→2→3

0

1→3→2

0

1→3→2

0

2→1→3

v({1, 2}) − v({2})

2→1→3

0

2→3→1

v({1, 2, 3}) − v({2, 3})

2→3→1

0

3→1→2

v({1, 3}) − v({3})

3→1→2v({1, 2, 3}) − v({3})

3→2→1v({1, 2, 3}) − v({2, 3})

3→2→1v({1, 2, 3}) − v({3})

さらに，すべての ∆ ⊆ P に対して，拡張シャープレイ値

整数である．

ϕ∆ ( P, v) を計算する問題（ESV ）を定義する．

2. 2 シャープレイ値
特性関数形ゲーム ( P, v) において， P の利得 v( P) を，各プ

3. 1 拡張シャープレイ値

レイヤー間でどのように分配するかについて考える．提携に対非負整数 n に対して， P = {1, . . . , n} をプレイヤー集合とするプレイヤーの貢献度に応じて利得を分配する方法が，1953

し，v : 2P → R を提携 S ⊆ P の利得を表す集合関数とする．

年に Lloyd S. Shapley によって定義された．

プレイヤー i ∈ P に対するシャープレイ値 ϕi ( P, v) を拡張し，任意のプレイヤー i ∈ P と任意の提携 S ⊆ P \ {i } に対して，

複数のプレイヤーの組合せ ∆ ⊆ P に対する拡張シャープレイ

v(S ∪ {i }) − v(S) を S に対するプレイヤー i の限界貢献度と値（extended Shapley value）ϕ∆ ( P, v) を以下のように導入する．

呼ぶ．これは，プレイヤー i が提携 S に加わることによって生任意のプレイヤー組 ∆ ⊆ P と任意の提携 S ⊆ P \ ∆ に対しじる利得の増分と解釈できる．それぞれのプレイヤーが順番にて，v(S ∪ ∆) − v(S) を S に対するプレイヤー組 ∆ の限界貢献

加わっていく | P|! 通りの提携形成が等確率で起こることを仮度と呼ぶ．これは，複数のプレイヤーからなるプレイヤー組 ∆定する．このとき，プレイヤー i ∈ P の限界貢献度の期待値

が提携 S に同時に加わることによって生じる利得の増分と解釈

E[v(S ∪ {i }) − v(S)] が，シャープレイ値 ϕi ( P, v) であり，次できる．それぞれのプレイヤーが順番に加わっていく | P|! 通りのように定義する．

の提携形成が等確率で起こることを仮定する．このとき，プレ定義 2. プレイヤー集合を P = {1, . . . , n} とし，v を集合関数

v : 2P → R とする．このとき，特性関数形ゲーム ( P, v) におけるプレイヤー i ∈ P のシャープレイ値 ϕi ( P, v) とは，

ϕi ( P, v) :=イヤー組 ∆ ⊆ P の限界貢献度の期待値 E[v(S ∪ ∆) − v(S)] が，拡張シャープレイ値 ϕ∆ ( P, v) であり，次のように定義する．
定義 4. プレイヤー集合を P = {1, . . . , n} とし，v を集合関数|S|!|(| P| − |S| − 1)!
(v(S ∪ {i }) − v(S))| P|!
S⊆ P\{i }

∑

(1)
である．

v :→ R とする．このとき，特性関数形ゲーム ( P, v) におけるプレイヤー組 ∆ ⊆ P の拡張シャープレイ値 ϕ∆ ( P, v) とは，ϕ∆ ( P, v) :=|S|!|∆|! (| P| − |S| − |∆|)!
(v (S ∪ ∆) − v (S))| P|!
S⊆ P\∆∑(2)
定義 3. すべてのプレイヤー i ∈ P に対する，シャープレ
イ値 ϕi P, v を並べた n 個の要素からなるベクトル ϕ(v, P) =と定義する．

(ϕi (v, P))i∈ P を，特性関数形ゲーム ( P, v) におけるシャープレ

定義 5. すべてのプレイヤー組 ∆ ⊆ P に対する，拡張シャー

イ値という．

プレイ値 ϕ∆ ( P, v) を並べた 2n 個の要素からなるベクトル

とりうる | P|! 通りの順列すべてを考えたとき，提携 S に対する
プレイヤー i の貢献度 v(S ∪ {i }) − v(S) は |S|!(| P| − |S| − 1)!
回出現する．すなわち，定義 2 は，P \ {i } の部分集合すべてに対して，|S|!(| P| − |S| − 1)!(v(S ∪ {i }) − v(S)) を足し合わせて | P|! で割ったものである．

P = {1, 2, 3} のときのプレイヤー 1 の限界貢献度の例を表 1に示す．

3 拡張シャープレイ値と全部分集合シャープレイ値問題
本節では，単一のプレイヤー i ∈ P に対するシャープレイ値

Φ(v, P) = (ϕ∆ ( P, v))∆⊆ P を，特性関数形ゲーム ( P, v) における拡張シャープレイ値と呼ぶ．
とりうる | P|! 通りの順列すべてを考えたとき，提携 S に対する
プレイヤー組 ∆ の限界貢献度 v(S ∪ ∆) − v(S) は |S|!|∆|!(| P| −|S| − |∆|)! 回出現する．すなわち，定義 5 は， P \ ∆ の部分集
合すべてに対して，|S|!|∆|!(| P| − |S| − |∆|)!(v(S ∪ ∆) − v(S))
を足し合わせて | P|! で割ったものである． P = {1, 2, 3} のときのプレイヤー組 {1, 2} の限界貢献度の例を，表 2 に示す．

3. 2 全部分集合拡張シャープレイ値問題
本論文で考察する問題を述べる．

ϕi ( P, v) を拡張し，複数のプレイヤー組 ∆ ⊆ P に対する拡張

定義 6. 全部分集合拡張シャープレイ値問題（all subset extended

シャープレイ値 ϕ∆ ( P, v) を定義する．

Shapley value problem, ESV ）とは，全体集合 P = {1, . . . , n} とAlgorithm 1 ESV を解くナイーブアルゴリズム

Algorithm 2 ESV を解く提案アルゴリズム

Require: 変数集合 P = {1, . . . , n}，集合関数 v．

Require: 変数集合 P = {1, . . . , n}，集合関数 v．

Ensure: 拡張シャープレイ値 Φ(v, P)

Ensure: 拡張シャープレイ値 Φ(v, P)

1: init_factorial(); // 階乗テーブルを構築する

1: すべての ∆ ⊆ P に対して，α(∆) を計算する;

2: for ∆ ⊆ P do

2: すべての ∆ ⊆ P に対して， β(∆) を計算する;

3:

E ← 0;

4:for S ⊆ P \ ∆ do

3: for ∆ ⊆ P do

5:

E ← E+|S|!|∆|!(| P|−|S|−|∆|)!
(v(S ∪ ∆) − v(S));
| P|!

6:

end for7:「ϕ∆ ( P, v) = E」と出力する;「ϕ∆ ( P, v) = (α(∆) − β(∆)) · |∆|!」と出力する;

4:

5: end forn∑ n Ck · 2k

8: end fork =0n= ∑ n Ck · 2k · 1n−k集合関数 v : 2P → R を入力として受け取り，拡張シャープレ

k =0

イ値 Φ(v, P) = (ϕ∆ ( P, v))∆⊆ P を出力する問題である．

= (2 + 1) n上の定義で，ベクトル Φ(v, P) の長さは 2n なので，この問題= 3nを解くための時間計算量は Ω(2n ) である．

3. 3 ナイーブアルゴリズム
ESV を解くナイーブな方法を Algorithm 1 に示す．Algorithm 1と式変形ができるので，Algorithm 1 の 5 行目は 3n 回実行される．よって，Algorithm 1 の時間計算量は O(3n · t f (n)) とな
る．

は，すべての ∆ ⊆ P に対して，拡張シャープレイ値 ϕ∆ ( P, v)
を一つずつ計算する．Algorithm 1 の 1 行目の init_factorial では，0! から n! までの階乗値を持つ階乗テーブル facti := i! を，4 提案アルゴリズム

すべての i ⊆ {0, 1, . . . , n} に対して構築する．fact0 = 1 とさだ

全部分集合拡張シャープレイ値問題（ESV ）に対して高速ゼー

め，それぞれの i ⊆ {1 . . . , n} に対して，facti = facti−1 · i に

タ変換を適用することで，Algorithm 1 より高速なアルゴリズム

したがって階乗テーブルを計算する．以降では，階乗テーブル

を与える．

facti を参照することで，1 から n までの階乗値を得ることができる．Algorithm 1 の 3 行目で，E ← 0 として，拡張シャープレ

4. 1 基本アイデア

イ値を計算するための変数を初期化する．Algorithm 1 の 4 行

拡張シャープレイ値 Φ∆ ( P, v) を式変形し，2 つの項に分け

目から 6 行目で，すべての集合 S ⊆ P \ ∆ に対する関数値を，る．それぞれの項に高速ゼータ変換を適用させて，高速に計算式 5 にしたがって E に加算する．Algorithm 1 の 7 行目で，集することを考える．

合 ∆ に対する拡張シャープレイ値 ϕ∆ ( P, v) として，E を出力

拡張シャープレイ値 Φ∆ ( P, v) を，する．

Φ∆ ( P, v)|∆|!

ここで，Algorithm 1 の時間計算量に関する定理を与える．
定理 1. 入力として，全体集合 P = {1, . . . , n} と，集合関数=

v : 2P → R が与えられたとき，Algorithm 1 の時間計算量はO(3n · tv (n)) である．ここに，tv (n) は関数 v を計算するのに=かかる時間である．

の i ⊆ {0, 1, . . . , n} に対して，階乗値 i! を O(1) で得ることができる．Algorithm 1 の 4 行目から 6 行目は，集合 P \ ∆ の部分
集合 S に対する関数値の総和を，式 5 にしたがって計算する．

P \ ∆ の部分集合は 2| P\∆| 個であるため，ループ回数は 2| P\∆|

|S|!(| P| − |S| − |∆|)!
f (S ∪ ∆)| P|!
S⊆ P\∆
|
{z
}

∑

α(∆)

証明. Arigorithm 1 の 1 行目で，階乗テーブルの構築に O(n)時間かかる．以降では，階乗テーブルを参照することで，任意|S|!(| P| − |S| − |∆|)!
[ f (S ∪ ∆) − f (S)]| P|!
S⊆ P\∆∑−|S|!(| P| − |S| − |∆|)!
f (S)
| P|!
S⊆ P\∆
{z
}
|

∑

β(∆)

と式変形し，第 1 項 α(∆) と第 2 項 β(∆) を定め，それぞれ独立に計算することを考える．すべての ∆ ⊆ P に対して，α(∆)

回である．| P \ ∆| = k となる S の通り数は n Ck 通りであるのと β(∆) を計算することができれば，ただちに全部分集合拡張

で，Algorithm 1 の 5 行目は全体を通して ∑nk=0 n Ck · 2k 回実行

シャープレイ問題（ESV ）の解を得ることができる．すべてのされる，∆ ⊆ P に対して，α(∆) と β(∆) を計算することができると仮定して，ESV を解く提案手法を Algorithm 2 に示す．
以降では，α(∆) と β(∆) を計算する手法について説明する．

4. 2 第 1 項 α(∆) の計算

Algorithm 3 ESVSP1 を解く高速なアルゴリズム

4. 2. 1 第 1 項 α(∆) に対する部分問題

Require: 全体集合 P = {1, . . . , n}，集合関数 f : 2P → R．

拡張シャープレイ値の第 1 項 α(∆) を

Ensure: ベクトル [ f α] = ( f α(S))S⊆ P|S|!(| P| − |S| − |∆|)!
α(∆) = ∑v(S ∪ ∆)| P|!
S⊆ P\∆

1: for S ⊆ P do

(3)

2:

f α0,0 (S) ← 0! f (S);3: end forと定義する．次に，すべての ∆ ⊆ P に対して，α(∆) の効率良い計算方法を与える．
集合 T を T = S ∪ ∆ とおき，∑ の S に関するループ条件を，T に関するループ条件に置き換えることを考える．定義より，∆ は P の部分集合であるので，

4: for i ∈ {1, . . . , n} do
5:for j ∈ {0, . . . , n} do

6:for S ⊆ P do

7:

f αi,j (S) =8:9:∅ ⊆ S ⊆ P\∆j · f αfα

i −1,j−1 ( S ∪ {i }) + f αi −1,j ( S ),end for

11: for S ⊆ P do⇐⇒ ∆ ⊆ T ⊆ P

12:

A ← 0;

13:for j ∈ {0, . . . , n} do
A ← A + f αn,j (S);

14:
15:

end forとなり，∅ ⊆ S ⊆ P \ ∆ と ∆ ⊆ T ⊆ P は同値である．加えて，

16:「 f α(S) = A」と出力する;

S ⊆ P \ ∆ より，S = T \ ∆ が成り立つので，α(∆) は

17: end for|S|!(| P| − |S| − |∆|)!
v(S ∪ ∆)
| P|!
∅⊆S⊆ P\∆∑=| T \ ∆|!(| P| − | T \ ∆| − |∆|)!
v( T )| P|!
∆⊆ T ⊆ P=| T \ ∆|!(| P| − | T | + |∆| − |∆|)!
v( T )| P|!
∆⊆ T ⊆ P=| T \ ∆|!(| P| − | T |)!
v( T )| P|!
∆⊆ T ⊆ P=

動的計画法のアルゴリズムを与える．すべての S ⊆ P と，i ∈ {0, . . . , n}， j ∈ {0, . . . , n} に対して，ゼータ変換テーブル∑

f αi,j (S) を
f αi,j (S) :=

∑

∑

∑

∆⊆ T ⊆ P

if i ∈ S.

i −1,j ( S ),end for

10: end for⇐⇒ ∅ ∪ ∆ ⊆ S ∪ ∆ ⊆ ( P \ ∆) ∪ ∆α(∆) =∑| X \ S | ! f ( X ).

(5)

S⊆ X ⊆S∪{1,...,i },| X \S|= jと定義する．ゼータ変換テーブル f αi,j (S) は，X \ S のサイズ j
によって値を区別して保持している．ゼータ変換テーブルの定| T \ ∆|!g( T )義より，α(S) = ∑nj=0 f αn，j (S) である．アルゴリズムは，動的と式変形できる．ここに，g( T ) :=(| P|−| T |)!
v( T ) とおいた．す| P|!

べての ∆ ⊆ P に対して ∑∆⊆ T ⊆ P | T \ ∆|!g( T ) の値を計算することができれば，ただちに，すべての ∆ ⊆ P に対する α(∆) の値が求まる．よって，以下で問題を新たに定義し，その問題を解くことを考える．

計画法によってゼータ変換テーブル f αi,j (S) を順に計算していくことにより，すべての S ⊆ P に対する α(S) を得る．
動的計画法によるゼータ変換テーブルの更新方法について述べる．まず，ステージ 0 で，すべての S ⊆ P に対して

f α0,0 (S) = 0! f (S) とテーブルを初期化する．つぎに，ステージi>= 1 で，以下の漸化式にしたがって，すべての j ∈ {0, 1, . . . , n}

定義 7. 拡張シャープレイ値部分問題 1（extended Shapley Valueとすべての S ⊆ P に対する f αi,j (S) を計算する．

subproblem 1, ESVSP1）とは，全体集合 P = {1, . . . , n} と集合関数 f : 2P → R を入力として受け取り，すべての S ⊆ P に対する f α(S) からなるベクトル [ f α] = ( f α(S))S⊆ P を出力する問

f αi,j (S) =j · f αfα

i −1,j−1 ( S ∪ {i }) + f αi −1,j ( S ),i −1,j ( S ),題である．ここに，f α(S) =if i ∈/ S,

if i ∈/ S,
if i ∈ S．
(6)∑

S⊆ X ⊆ P| X \ S|! f (S)

(4)

である．

4. 2. 2 第 1 項 α(∆) に対するアルゴリズム
高速ゼータ変換を用いて ESVSP1 を解く方法を Algorithm 3に示す．
アルゴリズムの基本アイデアを述べる．高速ゼータ変換に基づいた動的計画法によって，所望の値を得る．

最後に ，ステージ n が完了したときに，定義より α(S) =∑nj=0 f αn,j (S) なので，すべての S ⊆ P に対して ESVSP1 の解が得られる．
アルゴリズムの動作例として，P = {1, 2} の時の，高速ゼータ変換により得られる f αi,j (S) のテーブルを表 3 に示す．階乗の値によって，j が一意に定まるため，j に関するセルは陽に区
別せずまとめて表示する．また表を簡潔にするため，ここではg({1, 2}) を単に g{1, 2} と表記するものとする．

P = {1, 2} における αi,j (∆) テーブル

表3

Algorithm 4 ESVSP2 を解く高速なアルゴリズム

i αi {}

α i {1}Require: 全体集合 P = {1, . . . , n}，集合関数 f : 2P → R．

0 0!g{}

0!g{1}

1 0!g{} + 1!g{1}0!g{1}

Ensure: ベクトル [ f β(S)] = ( f β(S))S⊆ P
1: for S ⊆ P do

2 0!g{} + 1!g{1} + 1!g{2} + 2!g{1, 2} 0!g{1} + 1!g{1, 2}

2:i ϕi {2}ϕi {1, 2}

3: end for

0 0!g{2}0!g{1, 2}

4: for i ∈ {1, . . . , n} do

1 0!g{2} + 1!g{1, 2}0!g{1, 2}

5:

for j ∈ {0, . . . , n} do

2 0!g{2} + 1g!{1, 2}0!g{1, 2}

6:

for S ⊆ P do

f β 0,0 (S) ← 0! f (S);f β i，j (S) =7:

4. 2. 3 部分問題 1 に関する計算量解析
9:

補題 1. 入力として，全体集合 P = {1, . . . , n} と集合関数

f : 2P → R が与えられたとき，Algorithm 3 の時間計算量はO(2n (t f (n) + n2 )) であり，空間計算量は O(2n · n + s f (n)) である．ここに，t f (n) は関数 f を計算するのにかかる時間であり，s f (n) は関数 f を計算するのに必要なスペースである．
証明. 時間計算量について議論する．Algorithm 3 の 1 行目のループ回数は 2n であり，f α0,0 (S) の初期化にかかる時間計算量if i ∈ S.

end for

11: for S ⊆ P do
12:

B ← 0;

13:for j ∈ {0, . . . , n} do
B ← B + f β n,j (S);

14:
15:

end for16:「 f β(S) = B」と出力する;

17: end forβ(∆) =から 10 行目では，すべての i ∈ {1, . . . , n} と，j ∈ {0, 1, . . . , n}，

S ⊆ P に対して，漸化式にしたがって f αi,j (S) を計算しており，る時間計算量は O(2n (t f (n) + n2 )) である．

|S|!(| P| − |S| − | P \ U |)!
v(S)
| P|!
∅ ⊆ S ⊆U=

|S|!(|U | − |S|)!
v(S)
| P|!
∅ ⊆ S ⊆U

空間計算量について議論する．式 (4.4) より，ステージ i での漸化式の計算に必要な値は，ステージ i − 1 の結果のみであるの|S|!(| P| − |S| − |∆|)!
v(S)
| P|!
∅⊆S⊆ P\∆∑=O(2n · n2 ) 時間かかる．以上により，Algorithm 3 の実行にかか

∑

∑

=

∑

∅ ⊆ S ⊆Uで，アルゴリズムを通して必要な作業領域は O(2n · n + t f (n))
である．

i −1,j ( S \ {i }) + f β i −1,j ( S ),10: end forは O(2n · t f (n)) である．Algorithm 3 の 7 行目の漸化式を計算するのにかかる時間計算量は O(1) である．Algorithm 3 の 4 行目

if i ∈/ S,

i −1，j ( S ),

j · f β

end for

8:

Algorithm 3 の計算量に関する定理を与える．

fβ|U \ S|!h(S)|S|!

以上により，Algorithm 3 の時間計算量は O(2n (t f (n) + n2 ))であり，空間計算量は O(2n · n + s f (n)) であることが示された．

と式変形できる．ここに，h(S) := | P|! v(S) とおいた．すべての U ⊆ P に対して ∑S⊆U |U \ S|!h(S) を計算することができれ
ば，ただちに，すべての ∆ ⊆ P に対する β(∆) が求まる．よって，以下で問題を新たに定義し，その問題を解くことを考える．

4. 3 第 2 項 β(∆) の計算

定義 8. 拡張シャープレイ値部分問題 2（extended Shapley Value

4. 3. 1 第 2 項 β(∆) に対する部分問題

subproblem 2, ESVSP2）とは，全体集合 P = {1, . . . , n} と集合

拡張シャープレイ値の第 2 項 β(∆) を

関数 f : 2P → R を入力として受け取り，すべての S ⊆ P に対|S|!(| P| − |S| − |∆|)!
v(S)
| P|!
S⊆ P\∆∑(7)

する f β(S) からなるベクトル [ f β(S)] = ( f β(S))S⊆ P を出力する問題である．ここに，f β(S) = ∑ | X \ S|! f (S)と定義する．次に，すべての ∆ ⊆ P に対して， β(∆) の効率良い計算方法を与える．
集合 U を U = P \ ∆ とおく．このとき，S ⊆ P \ ∆ より，∆ = P \ U が成り立つので， β(∆) は

(8)

X ⊆S

である．

4. 3. 2 第 2 項 β(∆) に対するアルゴリズム
高速ゼータ変換を用いて ESVSP1 を解く方法を Algorithm 4に示す．
アルゴリズムの基本アイデアを述べる．Algorithm 4 と同様に，ゼータ変換テーブルを，集合 X \ S のサイズの情報を保持できる形で定義する．そうすることにより，動的計画法の計算が可能になる．

動的計画法のアルゴリズムを与える．すべての S ⊆ P と，i ∈ {0, 1, . . . , n}， j ∈ {0, 1, . . . , n} に対して，ゼータ変換テー
ブル f β i,j (S) を

時間と O(2n · n + s f (n)) メモリで計算可能である．したがって，本論文の主結果である，次の定理を与える．
定理 2. 入力として，全体集合 P = {1, . . . , n} と集合関数

f β i,j (S) :=∑v : 2P → R が与えられたとき，Algorithm 2 の時間計算量は| S \ X | ! f ( X ).

S\{1,...,n}⊆ X ⊆S,|S\ X |= jO(2n (tv (n) + n2 )) であり，空間計算量は O(2n · n + sv (n)) でと定義する．ゼータ変換テーブル f β i,j (S) は，S \ X のサイズある．ここに，tv (n) は関数 v を計算するのにかかる時間であり，sv (n) は関数 v を計算するのに必要なスペースである．

j によって値を区別して保持している．ゼータ変換テーブルの定義より，β(S) = ∑nj=0 f β n，j (S) である．アルゴリズムは，動証明. 補題 1 と補題 2 より，明らか．

的計画法によってゼータ変換テーブル f β i,j (S) を順に計算していくことにより，すべての S ⊆ P に対する β(S) を得る．

5 実

験

動的計画法を用いたテーブルの更新方法について述べる．まず，ステージ 0 で，すべての S ⊆ P に対して f β 0,0 (S) = 0! f (S)本節では，提案手法の実験結果を示し，その考察を行う．

とテーブルを初期化する．つぎに，ステージ i >= 1 で，以下全部分集合拡張シャープレイ値問題（ESV ）を解くための 2の漸化式にしたがって，すべての j ∈ {0, 1, . . . , n} とすべてのつのアルゴリズムに対して，入力の全体集合 P = {1, . . . , n} のS ⊆ P に対する f β i,j (S) を計算する．

サイズを変化させて実行し，速度を計測した．ナイーブな手法

f β i,j (S) =fβi −1,j ( S ),

j · f βi −1,j ( S \ {i }) + f β i −1,j ( S ),である Algorithm 1 と提案手法である Algorithm 2 を比較した．

if i ∈/ S,
if i ∈ S.

(9)

最後に，ステージ n が完了したときに，定義より β(S) =∑nj=0 f β n，j (S) なので，すべての S ⊆ P に対して ESVSP2 の解が得られる．

4. 3. 3 部分問題 2 に関する計算量解析
Algorithm 4 の計算量に関する定理を与える．

6 環境および設定
本研究の実験で用いた計算機の環境は以下の通りである．

CPU は Intel(R) Core(TM) i5-7360U CPU @ 2.30GHz，メモリは8 GiB，OS は macOS Mojave 10.14.6 である．すべてのプログラ
ムは Apple LLVM version 10.0.1 (clang-1001.0.46.4) を用いてコンパイルした．オプションに -O3 を用いた．
本研究の実験で扱う全部分集合シャープレイ値問題（ESV ）補題 2. 入力として，全体集合 P = {1, . . . , n} と集合関数

は，入力として全体集合 P = {1, . . . , n} と集合関数 f : 2P → R

f : 2P → R が与えられたとき，Algorithm 4 の時間計算量はを受け取る．本研究の実験において，ESV の入力である集合関O(2n (t f (n) + n2 )) であり，空間計算量は O(2n · n + s f (n)) で

数 f ： Rn → R として，二層ニューラルネットワークを用いある．ここに，t f (n) は関数 f を計算するのにかかる時間であた．入力に対して関数値 f を計算するのにかかる時間計算量をり，s f (n) は関数 f を計算するのに必要なスペースである．

t f (n) で表すと，t f (n, k) = O(nk ) である．ここに，k はニュー

証明. 時間計算量について議論する．Algorithm 4 の 1 行目のループ回数は 2n であり，f β 0,0 (S) の初期化にかかる時間計算量
は O(2n · t f (n)) である．Algorithm 4 の 7 行目の漸化式を計算するのにかかる時間計算量は O(1) である．Algorithm 4 の 4 行目
から 10 行目では，すべての i ∈ {1, . . . , n} と，j ∈ {0, 1, . . . , n}，

S ⊆ P に対して，漸化式にしたがって f β i,j (S) を計算しており，O(2n · n2 ) 時間かかる．以上により，Algorithm 4 の実行にかかる時間計算量は O(2n (t f (n) + n2 )) である．
空間計算量について議論する．式 (4.7) より，ステージ i での漸化式の計算に必要な値は，ステージ i − 1 の結果のみであるので，アルゴリズムを通して必要な作業領域は O(2n · n + s f (n))
である．
以上により，Algorithm 4 の時間計算量は O(2n (t f (n) + n2 ))であり，空間計算量は O(2n · n + s f (n)) であることが示された．

ラルネットワークのユニット数とする．
入力サイズ n に対して，ナイーブな手法である Algorithm 1
は，O(3n · t f (n)) 時間かかる手法であり，提案手法である Al-

gorithm 2 は，O(2n (n2 + t f (n))) 時間かかる手法である．これらの 2 つのアルゴリズムに対して，全体集合 P のサイズ n を変化させて実行し，計算が終了するまでの速度を計測した．

7 実験結果実験の結果を表 4 に示す．実行時間が 1 時間を超えたものについては，計測を打ち切った．
この結果より，提案アルゴリズムの方が高速に動作することがわかる．

7. 1 終 わ り に
本論文では，機械学習モデルの変数重要度として応用される，
シャープレイ値を取り上げ，それを拡張した「拡張シャープレ

4. 4 提案アルゴリズムの計算量解析

イ値」を定義した．加えて，すべての変数組合せに対して，拡以上の議論により，すべての ∆ ⊆ P に対して，シャープレイ値

張シャープレイ値を求める問題（ESV ）を定義し，それを解くの第 1 項 α(∆) と第 2 項 β(∆) が，それぞれ O(2n (tv (n) + n2 ))

効率良いアルゴリズムを与えた．さらに，考案したアルゴリズ

表 4 全部分集合拡張シャープレイ値問題（ESV ）を解くのにかかった
時間（秒）

n

ナイーブアルゴリズム 提案アルゴリズム

1

0.006

0.003

2

0.004

0.003

3

0.003

0.004

4

0.003

0.005

5

0.004

0.006

6

0.008

0.004

7

0.012

0.004

8

0.033

0.005

9

0.096

0.009

10 0.2950.017

11 0.928

0.036

12 2.929

0.074

13 9.229

0.157

14 29.090

0.353

15 91.465

0.778

16 286.771

1.769

17 896.701

3.950

18 2829.511

8.323

19 -

17.67920 -42.64921 -95.68422 -

258.296

23 -

663.746

ムとナイーブな方法を計算機実験により実行速度を比較した．
今後の課題として，拡張シャープレイ値の機械学習への応用を，工学的・理論的に考察することが挙げられる．拡張シャー
プレイ値が，学習モデルの変数組合せの重要度として応用されることを期待して，研究を進める．加えて，拡張シャープレイ
値に対する別の問題を定義し，それを解くアルゴリズムを考察することが挙げられる．例えば，サイズが k 以下の変数組合せに限定して，拡張シャープレイ値を求める問題や，集合関数 fを単純な線形モデルに限定して，拡張シャープレイ値を求める問題などが考えられる．

文

献[1] Marco Tulio Ribeiro, Sameer Singh, and Carlos Guestrin. Anchors:
High-precision model-agnostic explanations. In Thirty-Second AAAI
Conference on Artiﬁcial Intelligence, 2018.
[2] Scott M. Lundberg and Su-In Lee. A uniﬁed approach to interpretingmodel predictions. In Advances in Neural Information Processing
Systems 30, pp. 4765–4774. Curran Associates, Inc., 2017.
[3] Marco Tulio Ribeiro, Sameer Singh, and Carlos Guestrin. " whyshould i trust you?" explaining the predictions of any classiﬁer. In
Proceedings of the 22nd ACM SIGKDD international conference onknowledge discovery and data mining, pp. 1135–1144, 2016.
[4] Pang Wei Koh and Percy Liang. Understanding black-box predictions
via inﬂuence functions. In Proceedings of the 34th International Conference on Machine Learning-Volume 70, pp. 1885–1894. JMLR. org,
2017.
[5] Eyal Winter. The shapley value. Handbook of game theory witheconomic applications, Vol. 3, pp. 2025–2054, 2002.
[6] Lloyd S. Shapley. A value for n-person games. Contributions to the
Theory of Games, Vol. 2, No. 28, pp. 307–317, 1953.

[7] Fedor V. Fomin and Dieter Kratsch. Exact exponential algorithms.
Springer Science & Business Media, 2010.
[8] Anupam Datta, Shayak Sen, and Yair Zick. Algorithmic transparency
via quantitative input inﬂuence: Theory and experiments with learning systems. In 2016 IEEE symposium on security and privacy (SP),pp. 598–617. IEEE, 2016.
[9] Thomas H. Cormen, Charles E. Leiserson, Ronald L Rivest, andCliﬀord Stein. Introduction to algorithms. MIT press, 2009.
[10] Yasuko Matsui and Tomomi Matsui. NP-completeness for calculating power indices of weighted majority games. Theoretical Computer
Science, Vol. 263, No. 1-2, pp. 305–310, 2001.
[11] Takeaki Uno. Eﬃcient computation of power indices for weighted
majority games. In Kun-Mao Chao, Tsan-sheng Hsu, and Der-Tsai
Lee, editors, Algorithms and Computation, pp. 679–689. Springer
Berlin Heidelberg, 2012.