データ生成過程の学習：因果推論・特徴選択へのアプローチ

構造方程式モデルによるデータ生成過程の学習- 特に非ガウス性の利用
清水昌平 (大阪大学)

2Abstract• 構造方程式モデルはデータ生成過程のモデル– 反実仮想＋構造方程式モデルÆ因果分析• データ生成過程が未知の時に、構造方程式モデルを学習する方法を概観する(連続変数の場合)• まずは、基本となる線形モデル• 最後、非線形の方法にも触れる3

イントロ (1/2)• データ行列 X が次のどちらかのデータ生成過程からランダムに生成されたとしよう (b21 , b12 ≠ 0 ) ：モデル 2:

モデル 1:

x1 = e1x1

e1x2 = b21 x1 + e2x2e2

orx1 = b12 x2 + e1x1

e1x2 = e2x2e2

ここで e1 と e2 は独立な潜在変数 (外的影響, かく乱項、誤差)• データ行列Xのみを用いて、データXを生成したのがモデル1 なのか モデル2 なのかを同定したい4

イントロ (2/2)• 「同定はできない」と長らく思われていた• 実は、「ほとんどの場合に同定可能」ということが最近分かってきた (Shimizu et al., 2006)– e1とe2がガウス分布に従うとダメ• 非線形＋加法誤差でもポジティブな結果(Hoyer et al., 2009; Zhang & Hyvarinen, 2009)モデル 4:

モデル 3:

x1 = e1x1

e1x2 = f 2 ( x1 ) + e2 x2e2

orx1 = f ( x2 ) + e1x1

e1x2 = e2x2e2

5

因果効果: モデル1が正しいとき(cf. Pearl, 2000)•x1 を定数 c から d へ変化させたときの x2 への因果効果= E( x2 | 母集団の全員の x1 を強制的に d にする )- E( x2 |・・・を強制的に c にする )= E (b21 d + e2 ) − E (b21 c + e2 )= b21 (d − c )モデル1’:

モデル1:

x1 = e1x1

e1x1 = dx1

dx2 = b21 x1 + e2x2

e2x2 = b21 d + e2x2e2

6

因果効果: モデル2が正しいとき(cf. Pearl, 2000)•

x1 を定数 c から d へ変化させたときの x2 への因果効果= E( x2 | 母集団の全員の x1 を強制的に d にする )- E( x2 |・・・を強制的に c にする )= E (e2 ) − E (e2 )
= 0
モデル2:

モデル2’:

x1 = b12 x2 + e1x1e1x1 = dx1dx2 = e2x2e2x2 = e2x2e2

問題の定式化

8Basic problem setup (1/3)• 仮定: 連続な観測変数 xi のデータ生成過程が、グラフィカルには非巡回有効グラフ (DAG)である– ループがない
非巡回有向グラフの例(DAG):

巡回有向グラフの例:

x3e3x3e3x1

e1x1

e1x2e2x2e2(□（四角）で囲まれているのは観測変数)

9

Basic problem setup (2/3)• さらに、 xi の線形関係を仮定すると
線形非巡回構造方程式モデル (Wright, 1921; Bollen, 1989):

xi =∑ b x +eij

jior

x = Bx + ej: xiの親– ei は、モデル内で規定されない(外的)連続な潜在変数：
ここでは、外的影響と呼ぶ (かく乱変数、誤差変数).
– ei は、非ゼロの分散を持ち、互いに独立

10

例• 3変数の場合:

x1 = 1.5 x3 + e1
x2 = −1.3 x1 + e2x3 = e3

or0 1.5⎤ ⎡ x1 ⎤ ⎡ e1 ⎤⎡ x1 ⎤ ⎡ 0⎢ x ⎥ = ⎢− 1.3 0 0 ⎥ ⎢ x ⎥ + ⎢e ⎥⎢ 2⎥ ⎢⎥⎢ 2 ⎥ ⎢ 2 ⎥⎢⎣ x3 ⎥⎦ ⎢⎣ 00 0 ⎥⎦ ⎢⎣ x3 ⎥⎦ ⎢⎣e3 ⎥⎦1442443

B• Bのゼロ/非ゼロパターンが、１つのDAGに対応する:
x3e3x1

e1x2

e2

1.5
-1.3

bij = 0 ⇒ x j から xi に有向辺がない
bij ≠ 0 ⇒ x j から xi に有向辺がある11

非巡回性の仮定• 非巡回の場合は、パス係数行列Bを下三角にする
ような変数 xi の順序が必ず存在する (Bollen, 1989).
0 1.5⎤ ⎡ x1 ⎤ ⎡ e1 ⎤⎡ x1 ⎤ ⎡ 0⎢ x ⎥ = ⎢− 1.3 0 0 ⎥ ⎢ x ⎥ + ⎢e ⎥⎢ 2⎥ ⎢⎥⎢ 2 ⎥ ⎢ 2 ⎥⎢⎣ x3 ⎥⎦ ⎢⎣ 00 0 ⎥⎦ ⎢⎣ x3 ⎥⎦ ⎢⎣e3 ⎥⎦1442443

00⎡ x3 ⎤ ⎡ 00
00 0⎤ ⎡ x3 ⎤ ⎡e3 ⎤⎢ x ⎥ = ⎢1.5⎥⎢ x ⎥ + ⎢e ⎥000
⎢ 1⎥ ⎢⎥⎢ 1 ⎥ ⎢ 1 ⎥⎢⎣ x2 ⎥⎦ ⎢⎣ 0 − 1.3 0⎥⎦ ⎢⎣ x2 ⎥⎦ ⎢⎣e2 ⎥⎦1442443

B permBx3e3

そんな順序は例えば:x3 < x1 < x2 .

x1e1x3 は、x1 , x2の祖先でもよいが,x2e2逆はない.

1.5-1.3

12

外的影響の独立性の仮定• 「未観測交絡変数がない」ことを意味する(Spirtes et al. 2000)– 未観測交絡変数とは、2つ以上の観測変数の親であるような潜在変数:
e1’e2’

x1fx2• 未観測交絡変数があると、外的影響が従属
x1e1x2e2Basic problem setup (3/3):
線形構造方程式モデルの学習13• 仮定：データ行列 X は、モデルからランダムに生成される:

x = Bx + ex1

e1x2e2b21• Goal: データ行列Xの情報のみを使って、パス係数行列 B を推定する!
– Bのゼロ/非ゼロパターンが、１つのDAGに対応する

推定原理

15

伝統的な推定原理:
Causal Markov condition• もしデータ生成過程が、(線形)非巡回構造方程式モデルなら、Causal Markov condition が成り立つ:– 各観測変数 xi は、親で条件付けると非子孫と独立(Pearl & Verma, 1991) :x3e3x1e1x2e2pp(x ) = ∏ p (xi | xiの親 )i =1• ノンパラメトリックの場合でも使える原理だが、一意に同定できないモデルが多い16

例• 有向辺の向きが反対の2つのモデル:
モデル 2:

モデル 1:

x1 = e1x1

e1x1 = 0.8 x2 + e1x1

e1x2 = 0.8 x1 + e2x2

e2x2 = e2x2e2

E (e1 ) = E (e2 ) = 0, var(x1 ) = var(x2 ) = 1• どちらのモデルでも、(条件付き)独立になる変数はない:

cov(x1 , x2 ) = 0.8 ≠ 0• Causal Markov condition では、２つのモデルを区別できない

17

新しい推定原理：外的影響の独立性(Shimizu, Hyvarinen, Hoyer & Kerminen, JMLR, 2006)• 「外的影響 ei が独立である」ことを利用– 単に無相関ではなく• 線形構造方程式モデル＋非ガウス性(LiNGAMモデル):xi =∑ b x +eij

jiorx = Bx + ej: xi の親– 外的影響 ei は非ガウスかつ互いに独立• モデル つまり Bを一意に同定できる

推定アルゴリズム

19

DirectLiNGAM アルゴリズム(Shimizu et al., 2009; Sogawa et al., 2010; Inazumi et al., 2010)• パス係数行列Bが下三角になるような変数 xiの順序を推定する(非巡回にするような順序)⎡ O⎤
x perm = ⎢⎥ x perm + e perm
⎣ 23⎦1B perm

A full DAG
x1x3x2

冗長な有向辺

• 必要なら、枝刈りは既存の方法(e.g.,スパース正則化)が適用可能 (Zou, 2006; Hyvarinen et al. 2010)

20

Basic idea (1/2) :外生変数は、正しい順序のトップに来れる• 外生変数 x j は、親のいない変数 (Bollen, 1989)– ここでは x3– パス係数行列 Bの対応する行の成分は全てゼロ• 外生変数はパス係数行列Bを下三角にするような変数順序のトップに来れる00⎡ x3 ⎤ ⎡ 00
⎢ x ⎥ = ⎢1.500⎢ 1⎥ ⎢⎢⎣ x2 ⎥⎦ ⎢⎣ 0 − 1.30⎤ ⎡ x3 ⎤ ⎡e3 ⎤0⎥⎥ ⎢⎢ x1 ⎥⎥ + ⎢⎢ e1 ⎥⎥0⎥⎦ ⎢⎣ x2 ⎥⎦ ⎢⎣e2 ⎥⎦x3x1x2

21

Basic idea (2/2):
外生変数 x3 の成分を取り除く• 他の変数 xi (i = 1, 2) を外生変数 x3 に回帰して(3 )r
残差 i (i = 1, 2) を計算する
(3 )
(3 )
rと
r– 残差 1
も、LiNGAMモデルを形成する
2– 残差の順序は、元の観測変数の順序と同じ

00⎡ x3 ⎤ ⎡ 00
⎢ x ⎥ = ⎢1.500⎢ 1⎥ ⎢⎢⎣ x2 ⎥⎦ ⎢⎣ 0 − 1.3x3x10⎤ ⎡ x3 ⎤ ⎡e3 ⎤0⎥⎥ ⎢⎢ x1 ⎥⎥ + ⎢⎢ e1 ⎥⎥0⎥⎦ ⎢⎣ x2 ⎥⎦ ⎢⎣e2 ⎥⎦x20⎤ ⎡r1(3) ⎤ ⎡ e1 ⎤⎡r1(3) ⎤ ⎡ 0⎢ ( 3) ⎥ = ⎢⎢ ( 3) ⎥ + ⎢ ⎥⎥⎣r2 ⎦ ⎣− 1.3 0⎦ ⎣r2 ⎦ ⎣e2 ⎦r1(3)r2(3)• 残差 r1(3) が外生なので、 x1 はトップから2番目に来れる22

DirectLiNGAMの流れ• 全ての変数が順序づけられるまで、繰り返し「外生」変数を見つける:1. 外生変数を見つける: x3––x3 を順序のトップに置く回帰して、 x3 の成分を取り除く( 3)

2. 外生的な残差を見つける: r1––x1 を順序のトップから2番目に置く
回帰して、r1( 3)の成分を取り除く

3. x2 を順序のトップから3番目に置いて、終了推定された順序は x3 < x1 < x2
Step. 1x3

x1

Step. 2x2

r1(3)Step. 3r2(3)r2(3,1)23

外生変数の同定• 外的影響が非ガウスの場合• Lemma 1: x j は その残差 ri( j)= xi −cov( xi , x j )xjvar( x j )のどれとも独立 ( i は j以外全部) ⇔ x j は外生変数• 残差と最も独立な変数を見つけることによって、外生変数を同定できる– 独立性の指標 (Bach & Jordan 2002 etc.)– ペアワイズに評価して和をとる

24

外生変数の同定 (２変数の場合)
i) x1 (= e1 ) は外生変数
x1 = e1x2 = b21 x1 + e2

(b21 ≠ 0)

x2 を x1 に回帰して,(1)2r

cov( x2 , x1 )x1
= x2 −var( x1 )= x2 − b21 x1= e2

x1 と r2(1) は独立ii) x1 は外生変数でない
x1 = b12 x2 + e1

(b12 ≠ 0)x2 = e2x2を x1 に回帰して,r2(1) = x2 −cov( x2 , x1 )x1var( x1 )⎧ b cov( x2 , x1 ) ⎫b12 var( x2 )e1−x= ⎨1 − 12
⎬ 2var( x1 ) ⎭var( x1 )
⎩x1 と r2(1) は独立でないDarmois-Skitovitch’ theorem

25(Darmois, 1953; Skitovitch, 1953)
Darmois-Skitovitch’ theorem:
変数 x1 と x2 を次のように定義する：
pp

j =1

j =1

x1 = ∑ a1 j e j , x2 = ∑ a2 j e jii) x1 は外生変数でない
x1 = b12 x2 + 1 ⋅ e1(b12 ≠ 0)x2 = e2x2 を x1 に回帰して,cov( x2 , x1 )x1var( x1 )ここで e j は独立な確率変数.

r2(1) = x2 −もし a1i a2i ≠ 0 となるような非ガウ
スな ei があれば、
x1 と x2 は独立でない

b12 var( x2 )⎧ b cov( x2 , x1 ) ⎫−x= ⎨1 − 12e1
⎬ 2var( x1 ) ⎭var( x1 )⎩

x1 と r2(1) は独立でない26

DirectLiNGAMの大事な性質• DirectLiNGAM は次の2つを繰り返す:– 単回帰– 各変数と残差の独立性評価• Algorithmic parameters がない– ステップサイズ、初期値、収束基準• データがモデルに厳密に従っていれば、変数の数と同じステップ数で正しい解に収束することを保証できる(収束はいつもする)

Causal Markov condition との関係は？
•次の２つの性質は同値:(Zhang & Hyvarinen, ECML09; Hyvarinen et al., JMLR, 2010)

1. 外的影響 ei が互いに独立
2. Causal Markov condition が成り立つ＋ 各変数 xi の親と外的影響 ei が独立

x3

e3x1

e1x2e2

1.5
-1.3

27

非線形の場合

29

非線形＋加法の外的影響• 「非線形＋加法の外的影響」のモデル:– DAG; 未観測交絡変数なし
1.
2.

xi = f i ( xi の親 ) + ei

xi = f i ,−21 ( f i ,1 ( xi の親 ) + ei )-- Hoyer et al. (NIPS08)-- Zhang et al. (UAI09)• 「外的影響の独立性」の推定原理が使える• 2変数の場合、いくつかの非線形性と外的影響の分布の組み合わせを除いて、一意に同定可能30

ノンパラメトリック• DAG + 未観測交絡変数なし:
PC algorithm (Spirtes & Glymour, 1991)

xi = f i ( xi の親 i , ei )• 「外的影響の独立性」の推定原理は使えない• 多くの場合、一意に同定できないが、関数形について事前知識がないのであれば、現状これ

31

おわりに
• データ生成過程が未知の時に、構造方程式モデルを学習する方法を概観した• 線形モデルとノンパラトリックモデルの性質は結構わかってきている– その間: 非線形＋加法の外的影響?
– ナナメ?： 線形＋各種拡長• 非巡回 Æ 巡回 (Lacerda et al., UAI2008)• 単一母集団 Æ 異質な母集団の混合 (Shimizu et al., ICONIP2007)• i.i.d. サンプリング Æ 時間構造 (Hyvarinen et al, JMLR, 2010)• 未観測交絡変数なしÆ あり (Hoyer et al., IJAR, 2008; Kawahara et al. 2010)