BayesfiI‡É“ÅfiK‡È−w‘K‡Ì‡½‡ß‡ÌChow-Liu…A…‰…S…−…Y…•

. . 確率変数が有限の場合 . . 一般の確率変数の場合 . . まとめ Bayes的に最適な学習のためのChow-Liuアルゴリズム 鈴木 譲 大阪大学 . .

.

. . 確率変数が有限の場合 . . 一般の確率変数の場合 . . まとめ Kruscalのアルゴリズム V : 有限集合 wi ,j ∈ R: wi ,j = wj ,i i ̸= j . Kruscalのアルゴリズム(wi ,j ≥ 0のとき) . . . .. . . . .

.

.

.

3 _while(E ̸= ϕ) for w_{i ,jが最大となる}{i, j} ∈ E

.

.

.

.

. . 確率変数が有限の場合 . . 一般の確率変数の場合 . . まとめ wi ,j = I (i , j )(相互情報量) のとき i 1 1 2 1 2 3 j 2 3 3 4 4 4 I (i , j ) 12 10 8 6 4 2         X(2) _X(4) X(1) _X(3)         X(2) _X(4) X(1) _X(3)         X(2) X(4) X(1) _X(3)         X(2) X(4) X(1) _X(3) @ @_@ . .

.

. . 確率変数が有限の場合 . . 一般の確率変数の場合 . . まとめ Dendroid分布 G := (V , E )木 V :={1, · · · , N} Q1,··· ,N(x(1),· · · , x(N)) = ∏ {i,j}∈EPi ,j(x(i ), x(j )) ∏ i∈VPi(x(i ))di−1 di :=|{j ∈ V |{i, j} ∈ E}| . .

.

. . 確率変数が有限の場合 . . 一般の確率変数の場合 . . まとめ Chow-Liuアルゴリズム: 近似 真の分布P1,··· ,N をDendroid分布Q1,··· ,N で近似 . Chow-Liu, 1968 . . . .. . . . 重みとしてwi ,j := I (i , j )を用いて、Kruscalのアルゴリズムを適 用すると、D(P1,··· ,N||Q1,··· ,N) が最小になる − ∑ x(1)_{,··· ,x}(N) P1,··· ,N(x(1),· · · , x(N)) log Q1,··· ,N(x(1),· · · , x(N)) = ∑ i∈V H(i )− ∑ {i,j}∈E I (i , j ) . .

.

. . 確率変数が有限の場合 . . 一般の確率変数の場合 . . まとめ Chow-Liuアルゴリズム: 最尤推定 {(X(1) i ,· · · , X (N) i )}∞i =1: i.i.d P1,··· ,Nは未知 n組のサンプル{(xi(1),· · · , x (N) i )}ni =1が利用可能 In(i , j ): X(i ), X(j )の経験的相互情報量 ˆ P1,··· ,N: P1,··· ,Nの最尤推定 .

.

.

.

. . 確率変数が有限の場合 . . 一般の確率変数の場合 . . まとめ {x(i ) k }nk=1, {(x (i ) k , x (j ) k )}nk=1の予測分布 Rn(i ), Rn(i , j ) A(i ): X(i )の取りうる値の集合 α(i ):=|A(i )| cn[x ]: {x_k(i )}nk=1におけるx ∈ A(i )の頻度 cn[x , y ]: {(x_k(i ), x_k(j ))}n_k=1における(x , y )∈ A(i )× A(j )の頻度   パラメータの分布としてDirechlet(a = 1/2)を仮定 Rn(i ) := Γ(n + α (i )_a)Γ(a)α(i ) Γ(α(i )_a)∏ x∈A(i )Γ(cn[x ] + a) Rn(i , j ) := Γ(n + α (i )_α(j )_a)Γ(a)α(i )α(j ) Γ(α(i )_α(j )_a)∏ x∈A(i )Γ(cn[x , y ] + a) . .

.

. . 確率変数が有限の場合 . . 一般の確率変数の場合 . . まとめ {(x(1) k ,· · · , x (N) k )}nk=1の記述長 L − log Rn_{(i )≈ nH} n(i ) + α(i )− 1 2 log n − log Rn_{(i , j )≈ nH} n(i , j ) + α(i )α(j )− 1 2 log n − log Rn_{(i , j ) + logR}n_{(j )} ≈ n{Hn(i , j )− Hn(j ) + α(j )_(α(i )_{− 1)} 2n log n} = n{Hn(i ) + α(i )− 1 2n log n− In(i , j ) + (α(j )− 1)(α(i )− 1) 2n log n} L ≈ n∑ i∈V {Hn(i ) + α(i )− 1 2n log n} −n ∑ {i,j}∈E {In(i , j )− 1 2n(α (i )_{− 1)(α}(j )_{− 1) log n}} . .

.

.

. . 確率変数が有限の場合 . . 一般の確率変数の場合 . . まとめ Chow-Liuアルゴリズム: 記述長最小 Jn(i , j ) := In(i , j )− 1 2n(α (i )_{− 1)(α}(j )_{− 1) log n} Jn(i , j )は負になりうるので、拡張版 Kruscal のアルゴリズムを適用 (V , E )は、木ではなく、一般的な森 .

.

.

.

.

.

. . 確率変数が有限の場合 . . 一般の確率変数の場合 . . まとめ i j In(i , j ) α(i ) α(j ) Jn(i , j ) 1 2 12 5 2 8 1 3 10 5 3 2 2 3 8 2 3 6 1 4 6 5 4 -6 2 4 4 2 4 1 3 4 2 3 4 -4         X(2) _X(4) X(1) _X(3)         X(2) _X(4) X(1) _X(3)         X(2) X(1) X(4) X(3)         X(2) _X(4) X(1) _X(3) . .

.

.

. . 確率変数が有限の場合 . . 一般の確率変数の場合 . . まとめ Radon-Nikodymの定理 (Ω,F): 可測空間 µ, ν: F 上の測度 B: RのBorel集合 µがνに対して絶対連続(µ << ν) 各A∈ Fについて、 ν(A) = 0 =⇒ µ(A) = 0 νがσ-有限 Ω =∪iAi かつν(Ai) <∞なるAi ∈ F, i = 1, 2, · · · が存在 f : Ω→ RがF可測 任意のD ∈ Bについて、 {ω ∈ Ω|X (ω) ∈ D} ∈ F . Radon-Nikodymの定理 . . . . . µ, νがσ有限で、 µ≪ νのとき、各A∈ F でµ(A) = ∫ A fd νと なるような、F可測な d µ d ν := f ≥ 0が存在 . .

.

.

. . 確率変数が有限の場合 . . 一般の確率変数の場合 . . まとめ Kullback-Leibler情報量 (Ω,F, µ): 確率空間 . X : Ω→ Rが確率変数 . . . .. . . . XがF可測 離散、連続、どちらでもないものが存在する FX(x ) =    0 x <−1 1 2 −1 ≤ x < 0 1 2+ ∫x 0 1 2g (t)dt 0≤ x . Kullback-Leibler情報量 . . . . . µ≪ νのとき、 D(µ||ν) := ∫ log(d µ d ν)d µ . .

.

.

. . 確率変数が有限の場合 . . 一般の確率変数の場合 . . まとめ 一般の Chow-Liu アルゴリズム: 近似 D(1),· · · , D(N)∈ B µi(D(i )) := µ(X(i ) ∈ D(i )) µij(D(i ), D(j )) := µ(X(i )∈ D(i ), X(j )∈ D(j )) µ1,··· ,N(D(1),· · · , D(N)) := µ(X(i )∈ D(i ), i = 1,· · · , N) µ1⊗ · · · ⊗ µN(D(1),· · · , D(N)) := N ∏ i =1 µi(D(i )) . .

.

.

. . 確率変数が有限の場合 . . 一般の確率変数の場合 . . まとめ µij ≪ µi⊗ µj のとき、相互情報量I (i , j ) := D(µij||µi⊗ µj)が定義 d ν1,··· ,N(x(1),· · · , x(N)) = ∏ {i,j}∈E d µi ,j(x(i ), x(j )) ∏ i∈V d µi(x(i ))di−1 . 定理1 . . . .. . . . D(µ1,··· ,N||ν1,··· ,N) = D(µ1,··· ,N||µ1⊗ · · · ⊗ µN)− ∑ {i,j}∈E I (i , j ) . .

.

.

. . 確率変数が有限の場合 . . 一般の確率変数の場合 . . まとめ ユニバーサル測度 (有限の確率変数の場合) X : 有限集合Aに値をとる確率変数 cn[x ]: 長さnの系列xn:={xk}nk=1∈ Anにおけるx ∈ Aの頻度 Rn(xn) := Γ(n +|A|/2)Γ(1/2) |A| Γ(|A|/2)∏_x∈AΓ(cn[x ] + 1/2) H: Xをi.i.dで発生させたときのエントロピー Xの分布Pによらず、−1 nlog R n_(xn_{)→ H (n → ∞)} Pn(xn): Xn= xnの真の確率 Shannon-McMillan-Breiman定理 Xの分布Pによらず、−1 nlog P n_(xn_{)→ H (n → ∞)} . ユニバーサル測度R . . . . . Xの分布Pによらず、1 nlog Pn(xn) Rn_(xn₎ → 0 (n → ∞) . .

.

.

. . 確率変数が有限の場合 . . 一般の確率変数の場合 . . まとめ ユニバーサル測度 (確率密度関数が存在する場合) X ∈ [0, 1)のとき、A0:={[0, 1)}として A1 = {[0, 1/2), [1/2, 1)} A2 = {[0, 1/4), [1/4, 1/2), [1/2, 3/4), [3/4, 1)} . . . Ak = {[0, 2−(k−1)), [2−(k−1), 2· 2−(k−1)), · · · , [(2k−1_{− 1)2}−(k−1)_{, 1)}} . . . 各レベルの予測分布を幅で割ったものの重みづけ和 . ユニバーサル確率密度 g (Ryabko, 2009) . . . . . Xの確率密度f によらず、1 n log fn_(xn₎ gn_(xn₎ → 0 (n → ∞) . .

.

.

. . 確率変数が有限の場合 . . 一般の確率変数の場合 . . まとめ ユニバーサル測度 (確率密度関数が存在しない場合) η: σ有限, µ≪ η . Suzuki, 2011 . . . .. . . . 確率密度関数f := d µ d λ ではなく、一般の d µ d η を推定 (アルゴリズムとして、λをηに変えるだけ) D(µk||η) → D(µ||η) (k → ∞) =⇒ 1 nlog d µn d νn(x n_{)→ 0 (n → ∞)} (µを、ηに関するユニバーサル測度とよぶ) . .

.

.

. . 確率変数が有限の場合 . . 一般の確率変数の場合 . . まとめ Bayes的な相互情報量の推定 (xn, yn): 確率変数(X , Y )のn個のサンプル µX ≪ ηX, µY ≪ ηY d µn X d η_Xn (x n_),d µnY d η_Yn (y n_), d µnXY d ηn_Xd ηn_Y(x n_{, y}n_)を、 ユニバーサル測度d ν n X d η_Xn(x n_),d νYn d η_Yn(y n_), d νXYn d η_Xnd ηn_Y(x n_{, y}n_)で推定 . 定理2: 提案する相互情報量の一般的な推定量 . . . .. . . . 1 n log d ν_XYn d η_Xnd η_Yn(x n_{, y}n₎ d ν_Xn d ηn_X(x n₎d νYn d η_Yn(y n₎ → I (X , Y ) (1) . .

.

.

. . 確率変数が有限の場合 . . 一般の確率変数の場合 . . まとめ 一般的な意味での記述長最小基準 .

.

.

.

.

. . 確率変数が有限の場合 . . 一般の確率変数の場合 . . まとめ 一般の Chow-Liu アルゴリズム: 記述長最小 Kn(i , j ): X(i ), X(j )のBayes的な相互情報量の推定値 {(x(1) k ,· · · , x (N) k )}nk=1の記述長は ∑ i∈V − logd νin d ηn_i ({x (i ) k } n k=1)− n ∑ {i,j}∈E Kn(i , j ) .

.

.

.

.

.

. . 確率変数が有限の場合 . . 一般の確率変数の場合 . . まとめ まとめ 離散や連続を仮定しない一般の確率変数について、 Bayes的な相互情報量の提案 記述長最小基準の提案 Bayes的な Chow-Liu アルゴリズムの提案 今後の課題: 数値実験 . .

.

.