属性間の依存関係の推定と実装 - ERATO 湊離散構造処理系プロジェクト

.
属性間の依存関係の推定と実装
.
鈴木譲
大阪大学
2014 年 9 月 9 日
ERATO 湊離散構造処理系ワークショップ (礼文島)
鈴木譲 (大阪大学)
属性間の依存関係の推定と実装
2014 年 9 月 9 日 ERATO 湊離散構造処理系ワ
/ 27
目次
目次
1.
BN の構造学習
2.
確率変数が存在する場合
3.
一般的な場合
4.
BN 構造学習の実際
5.
まとめ
鈴木譲 (大阪大学)
属性間の依存関係の推定と実装
2014 年 9 月 9 日 ERATO 湊離散構造処理系ワ
/ 27
BN の構造学習
P(X , Y , Z ) の因数分解は、11 通り
X , Y , Z : (離散) 確率変数
P(X )P(Y )P(Z ), P(X )P(Y , Z ), P(Y )P(Z , X ),
P(Z )P(X , Y ),
P(X , Y )P(X , Z ) P(X , Y )P(Y , Z )
,
,
P(X )
P(Y )
P(X , Z )P(Y , Z ) P(Y )P(Z )P(X , Y , Z ) P(Z )P(X )P(X , Y , Z )
,
,
,
P(Z )
P(Y , Z )
P(Z , X )
P(X )P(Y )P(X , Y , Z )
, P(X , Y , Z ) ,
P(X , Y )
鈴木譲 (大阪大学)
属性間の依存関係の推定と実装
2014 年 9 月 9 日 ERATO 湊離散構造処理系ワ
/ 27
BN の構造学習
Bayesian ネットワーク: 条件付き独立性を有向非巡回グラフで
m
(1) X
m
(2) X
m
(3) X
m
(4) X
m
(5) X
m
(6) X
m
(7) X
m
(8) X
m
(9) X
m
(10) X
m
(11) X
AK
A
m
m
m
m
m
Y
Z
Y
Z
Y
Zm Ym Zm
A
KA
AK
AU
A
A
m
m
m
m
m
m
m
Y
Z
Y
Z
Y
Z
Y
Zm
A
A
AU
U
A
m
m
m
m
m
Y
Z
Y
Z
Y - Zm
(5)
Xm
Xm
Xm
A
A
AK
AU
AU
A
m
m
m
m
m
Y
Z Y
Z Y
Zm
鈴木譲 (大阪大学)
属性間の依存関係の推定と実装
(8)
Xm
KA
A
m
Y
Zm
2014 年 9 月 9 日 ERATO 湊離散構造処理系ワ
/ 27
BN の構造学習
定式化
n 組の例
X = x1 Y = y1 Z = z1
X = x2 Y = y2 Z = z2
..
..
..
.
.
.
X = xn Y = yn Z = zn









i.i.d.
から、BN の構造を推定 ((1)-(11) のいずれであるかを特定)
鈴木譲 (大阪大学)
属性間の依存関係の推定と実装
2014 年 9 月 9 日 ERATO 湊離散構造処理系ワ
/ 27
BN の構造学習
従来の研究
独立性検定によるもの: PC アルゴリズム (Spirtes, 2000) 他
Bayes によるもの
各測度のスコアの計算:
離散のみ: Cooper (1991), Suzuki (1993) 以降多数、ほとんどがこれ
Gauss のみ: 共分散を計算
離散と連続が混在: Bottcher の R パッケージなど
連続はすべて Gauss を仮定、性能の保証がない
各測度のスコアの値から各構造のスコアを求め、最適な構造を見出す
[今回の検討の対象外]
鈴木譲 (大阪大学)
属性間の依存関係の推定と実装
2014 年 9 月 9 日 ERATO 湊離散構造処理系ワ
/ 27
BN の構造学習
本研究: 離散や連続を区別しない BN の構造推定
.
従来
.
レ
. コードの全部の項目が有限個の値をとる
(X , Y , Z ) = (性別, 昭和・大正・平成, 都道府県)
A = {0, 1}, B = {0, 1, 2}, C = {0, 1, · · · , 46}
難しい問題から逃げている
.
提案
.
レ
. コードの各項目が離散、連続、どちらでもないも可
(X , Y , Z ) = (身長, 年齢, 性別)
A = [0, 1), B = {1, 2, · · · }, C = {0, 1}
鈴木譲 (大阪大学)
属性間の依存関係の推定と実装
2014 年 9 月 9 日 ERATO 湊離散構造処理系ワ
/ 27
BN の構造学習
ベイズによる独立性検定
x n = (x1 , · · · , xn ), y n = (y1 , · · · , yn ) から、
P(X ), P(Y ), P(X , Y ) が、事前確率 w (·) のパラメータ θ で表現
∫
∫
n n
n n
n n
Q (x ) := P (x |θ)w (θ)dθ , Q (y ) := P n (y n |θ)w (θ)dθ ,
∫
n
n
n
Q (x , y ) :=
P n (x n , y n |θ)w (θ)dθ ,
X ⊥⊥ Y の事前確率を p として、x n , y n のもとでの X ⊥⊥ Y の事後確率:
P(X ⊥⊥ Y |x n , y n ) =
pQ n (x n )Q(y n )
,
pQ n (x n )Q(y n ) + (1 − p)Q n (x n , y n )
X ⊥⊥ Y であるか否かの決定ルール:
X ⊥⊥ Y ⇐⇒ pQ n (x n )Q(y n ) ≥ (1 − p)Q n (x n , y n ) .
鈴木譲 (大阪大学)
属性間の依存関係の推定と実装
2014 年 9 月 9 日 ERATO 湊離散構造処理系ワ
/ 27
BN の構造学習
(1)-(11) の構造の同定
p1 , · · · , p11 : 構造の事前確率
x n = (x1 , · · · , xn ), y n = (y1 , · · · , yn ), z n = (z1 , · · · , zn )
p1 Q n (x n )Q n (y n )Q(z n ),
p2 Q n (x n )Q n (y n , z n ), p3 Q n (y n )Q n (z n , x n ), p4 Q n (z n )Q n (x n , y n ),
p5
Q n (x n , y n )Q n (X , z n )
Q n (x n , y n )Q n (y n , z n )
Q n (x n , z n )Q n (y n , z n )
,
p
,
p
,
6
7
Q n (x n )
Q n (y n )
Q n (z n )
p8
Q n (y n )Q n (z n )Q(x n , y n , z n )
Q n (z n )Q n (x n )Q n (x n , y n , z n )
,
p
,
9
Q n (y n , z n )
Q n (z n , x n )
p10
Q n (x n )Q n (y n )Q n (x n , y n , z n )
, p11 Q n (x n , y n , z n )
Q n (x n , y n )
鈴木譲 (大阪大学)
属性間の依存関係の推定と実装
2014 年 9 月 9 日 ERATO 湊離散構造処理系ワ
/ 27
BN の構造学習
x n を gzip で圧縮したときの長さを l(x n ) として、Q = 2−l(x
Kraft の不等式:
∑
n)
Q n (x n ) ≤ 1
xn
. n
Q はユニバーサル
.
P(X |θ) の θ がどのような値であっても、 n → ∞ で確率 1 で
1
P n (x n |θ)
log n n → 0
n
Q (x )
.
n → ∞ で、決定ルールが
モデルの事前確率 {pi }、パラメータの事前確率 w (·) によらない
鈴木譲 (大阪大学)
属性間の依存関係の推定と実装
2014 年 9 月 9 日 ERATO 湊離散構造処理系ワ
/ 27
確率変数が存在する場合
X に確率密度関数 f が存在するとき (Ryabko の方法)
A0 := {A}
Aj+1 は、Aj の細分化
(j)
(j)
各レベル j で、x n = (x1 , · · · , xn ) を (a1 , · · · , an ) に量子化
(1)
A1
-
g1n (x n ) =
A2
-
g2n (x n ) =
-
gjn (x n )
..
.
..
.
(1)
(1)
(2)
(2)
λ(a1 (2)
) · · · λ(an(2))
Q2n (a1 , · · · , an )
λ(a1 ) · · · λ(an )
(j)
Aj
..
.
..
.
λ: Lebesgue 測度 (区間の幅)
鈴木譲 (大阪大学)
属性間の依存関係の推定と実装
=
(1)
Q1n (a1 , · · · , an )
(j)
Qjn (a1 , · · · , an )
(j)
(j)
λ(a1 ) · · · λ(an )
2014 年 9 月 9 日 ERATO 湊離散構造処理系ワ
/ 27
確率変数が存在する場合
∑
j
wj = 1, wj > 0 を用いて、
g n (x n ) :=
∞
∑
wj gjn (x n )
j=1
g n (y n ),
g n (z n ),
g n (x n , y n ),
g n (x n , z n ),
g n (y n , z n ), g n (x n , y n , z n ) も同様。
p1 g n (x n )g n (y n )g (z n ), p2 g n (x n )g n (y n , z n ), p3 g n (y n )g n (z n , x n ),
g n (x n , y n )g n (X , z n )
g n (x n , y n )g n (y n , z n )
,
p
,
6
g n (x n )
g n (y n )
...
n
n
n
n
n
n
g (x )g (y )g (x , y n , z n )
p10
, p11 g n (x n , y n , z n ) ,
g n (x n , y n )
p4 g n (z n )g n (x n , y n ), p5
鈴木譲 (大阪大学)
属性間の依存関係の推定と実装
2014 年 9 月 9 日 ERATO 湊離散構造処理系ワ
/ 27
確率変数が存在する場合
予測確率密度 g n のユニバーサル性
f : 確率密度関数
fj (レベル j の確率密度関数)
f n (x n ) := f (x1 ) · · · f (xn )
.
Ryabko 2009
.
D(f ||fj ) → 0 (j → ∞) なる f について、n → ∞ で確率 1 で
1
f n (x n )
log n n → 0
n
g (x )
.
鈴木譲 (大阪大学)
属性間の依存関係の推定と実装
2014 年 9 月 9 日 ERATO 湊離散構造処理系ワ
/ 27
一般的な場合
X に確率密度関数が存在しないとき (Suzuki 2011)
B1 := {{1}, {2, 3, · · · }}
B2 := {{1}, {2}, {3, 4, · · · }}
...
Bk := {{1}, {2}, · · · , {k}, {k + 1, k + 2, · · · }}
...
(k)
(k)
各レベル k で、x n = (x1 , · · · , xn ) を (b1 , · · · , bn ) に量子化
η({k}) =
1
1
−
k
k +1
(k)
gkn (y n ) :=
∑
ωk = 1, ωk > 0, g n (x n ) :=
(k)
Qkn (b1 , · · · , bn )
(k)
(k)
η(b1 ) · · · η(bn )
∞
∑
ωk gkn (x n )
k=1
鈴木譲 (大阪大学)
属性間の依存関係の推定と実装
2014 年 9 月 9 日 ERATO 湊離散構造処理系ワ
/ 27
一般的な場合
D(f ||fj ) → 0 (j → ∞) にならない例 (その 1)
∫
1
f (x)dx > 0
1
2
C0
C1
C2
C3
..
.
鈴木譲 (大阪大学)
0
..
.
..
.
属性間の依存関係の推定と実装
1
-
x
2014 年 9 月 9 日 ERATO 湊離散構造処理系ワ
/ 27
一般的な場合
D(f ||fj ) → 0 (j → ∞) にならない例 (その 2)
∫
∞
f (x)dx > 0
1
C0
C1
C2
C3
..
.
0
鈴木譲 (大阪大学)
..
.
..
.
1
属性間の依存関係の推定と実装
-
x
2014 年 9 月 9 日 ERATO 湊離散構造処理系ワ
/ 27
一般的な場合
ユニバーサルヒストグラム列 (D(f ||fj ) → 0 がつねに満足される)
ユニバーサルなヒストグラム列 {Ck }∞
k=0
C0
C1
C2
C3
..
.
..
.
−σ µ
..
.
σ
-
x
.
Suzuki 2013
.
任意の (一般化) 確率密度関数 f について、n → ∞ で確率 1 で、
1
f n (x n )
log n n → 0
n
g (x )
.
鈴木譲 (大阪大学)
属性間の依存関係の推定と実装
2014 年 9 月 9 日 ERATO 湊離散構造処理系ワ
/ 27
一般的な場合
2 変数以上の場合
(j)
gjkn (x n , y n )
∑
:=
n
jk
(j)
(k)
(k)
n (a , · · · , a , b
Qjk
1
1
1 , · · · , bn )
(j)
(j)
(k)
(k)
λ(a1 ) · · · λ(an )η(b1 ) · · · η(bn )
n
n
ωjk = 1, ωjk > 0, g (x , y ) :=
∞
∑
ωjk gjkn (x n , y n )
k=1
g n (y n ), g n (z n ), g n (x n , y n ), g n (x n , z n ), g n (y n , z n ), g n (x n , y n , z n ) も同様。
p1 g n (x n )g n (y n )g (z n ), p2 g n (x n )g n (y n , z n ), p3 g n (y n )g n (z n , x n ),
g n (x n , y n )g n (y n , z n )
g n (x n , y n )g n (X , z n )
,
p
,
6
g n (x n )
g n (y n )
...
n
n
n
n
n
n
g (x )g (y )g (x , y n , z n )
p10
, p11 g n (x n , y n , z n ) ,
g n (x n , y n )
p4 g n (z n )g n (x n , y n ), p5
鈴木譲 (大阪大学)
属性間の依存関係の推定と実装
2014 年 9 月 9 日 ERATO 湊離散構造処理系ワ
/ 27
BN 構造学習の実際
スコアと構造の評価値の計算
N: ノード数 (2N − 1 個のスコアを計算)
M(N): 構造の候補数 (例: M(3) = 11)
STEP 1: 2N − 1 個の測度のスコアを計算。(11) なら
1
{− log p11 − log g n (x n ) − log g n (y n ) − log g n (x n , y n , z n ) + log g n (x n , y n )}
n
− n1 log g n (·)
X
1.617
Y
1.533
(X , Y )
3.249
Z
1.647
(X , Z )
3.318
(Y , Z )
3.290
(X , Y , Z )
4.943
STEP 2: M(N) 個の候補のスコアを計算。N = 3 なら
(1)
4.799
(2)
4.908
(3)
4.852
鈴木譲 (大阪大学)
(4)
4.897
(5)
4.950
(6)
5.006
(7)
4.962
属性間の依存関係の推定と実装
(8)
4.833
(9)
4.890
(10)
4.845
(11)
4.943
2014 年 9 月 9 日 ERATO 湊離散構造処理系ワ
/ 27
BN 構造学習の実際
スコア計算のアルゴリズム
入力 x n ∈ An , 出力 g n (x n )
1. For each k = 1, · · · , K , g n (x n ) := 0
k
2. For each k = 1, · · · , K and each a ∈ A , c (a) := 0
k
k
3. For each i = 1, · · · , n, for each k = 1, · · · , K
. Find ai ∈ Ak from xi ∈ A
ck (ai ) + 1/2
n n
n n
2. gk (x ) := gk (x ) − log
+ log(ηX (ai ))
i − 1 + |Ak |/2
3. ck (ai ) := ck (ai ) + 1
1
. g n (x n ) :=
4
1
K
∑K
n n
k=1 gk (x )
Qkn (x n )
=
n
(k)
∏
c(a ) + 1/2
i
i=1
鈴木譲 (大阪大学)
i − 1 + |A|/2
属性間の依存関係の推定と実装
2014 年 9 月 9 日 ERATO 湊離散構造処理系ワ
/ 27
BN 構造学習の実際
計算量の評価 max{n2N K , M(N)} = O(M(N))
.
スコア計算
.
1. 測度のスコアで O(nK )、2N − 1 個で O(n2N K )
1 変数の場合: サンプル数 n に比例
2N − 1 個のスコアを計算
(1)
(2)
(K )
ai 7→ ai 7→ · · · 7→ ai が 2 分探索で実現
2 変数以上の場合: j = k として実現すれば、同じ計算量が得られる
g n (x n , y n ) :=
∞
∑
ωjk gjkn (x n , y n )
k=1
.
事後確率最大の構造を求める
.
O(M(N))
.
M(N) 個の候補の中での最大値
鈴木譲 (大阪大学)
属性間の依存関係の推定と実装
2014 年 9 月 9 日 ERATO 湊離散構造処理系ワ
/ 27
BN 構造学習の実際
実験 1
. X , Y ∈ {0, 1} (X ⊥⊥ Y ): 確率 0.5, U ∼ N(x + y , 1), V ∼ N(x − y , 1)
2. X , Y ∼ N(0, 1) (X ⊥
⊥ Y ), U, V ∈ {0, 1} s.t.
1

 0,
(z + 1)/2,
P(U = 1|X + Y = z) = P(V = 1|X − Y = z) =

1,
X ∈ {0, 1} Y ∈ {0, 1}
(a)
H
H
?
?
HH
j
U ∼ N(0, 1)V ∼ N(0, 1)
鈴木譲 (大阪大学)
z < −1
−1 ≤ z ≤ 1
z >1
X ∼ N(0, 1)Y ∼ N(0, 1)
(b)
H
H
?
?
HH
j
U ∈ {0, 1} V ∈ {0, 1}
属性間の依存関係の推定と実装
2014 年 9 月 9 日 ERATO 湊離散構造処理系ワ
/ 27
BN 構造学習の実際
Bayesian Networks
(a)
4.224
(b)
3.372
鈴木譲 (大阪大学)
n
g n (x n , y n , u n , v n )
KL divergence
execution time (sec)
g n (x n , y n , u n , v n )
KL divergence
execution time (sec)
100
5.009
0.785
1.079
4.435
1.063
0.601
属性間の依存関係の推定と実装
200
4.858
0.634
1.276
4.191
0.819
0.849
500
4.626
0.402
1.939
4.002
0.630
1.721
1000
4.616
0.392
4.596
3.867
0.495
2.582
2000
4.552
0.328
7.047
3.771
0.399
4.619
2014 年 9 月 9 日 ERATO 湊離散構造処理系ワ
/ 27
BN 構造学習の実際
実験 2
(1) X , Y , Z ∼ N(0, 1).
(2)(3)(4) X , U ∼ N(0, 1), Y = ρX +
√
1 − ρ2 U, Z ∼ N(0, 1).
√
(5)(6)(7) X , U, V ∼ √
N(0, 1), Y = ρa X + 1 − ρ2a U,
Y = ρx +
1 − ρ2b U.
(8)(9)(10) X , U ∼ N(0,√
1), Y = ρa X +
Z = ρb X +
√
1 − ρ2a U,
1 − ρ2b V .
(11) X , U, V ∼ N(0, 1), √
Y = ρa X +
Z = ρb X + ρc Y +
鈴木譲 (大阪大学)
√
1 − ρ2a U,
1 − ρ2b − ρ2c V .
属性間の依存関係の推定と実装
2014 年 9 月 9 日 ERATO 湊離散構造処理系ワ
/ 27
BN 構造学習の実際
true
structure
(1)
(2)(3)(4)
(5)(6)(7)
(8)(9)(10)
(11)
diﬀerential
entropy
4.256816
4.033672
3.810528
3.810528
3.766401
鈴木譲 (大阪大学)
n = 100
score error
4.875 0.28
4.699 0.42
4.732 0.34
4.710 0.32
4.731 0.14
n = 200
score
error
4.645
0.02
4.573
0.12
4.565
0.14
4.498
0.12
4.5431 0.06
属性間の依存関係の推定と実装
n = 500
score error
4.480 0.00
4.434 0.10
4.385 0.10
4.370 0.06
4.335 0.02
n = 1000
score error
4.417 0.00
4.350 0.02
4.289 0.02
4.282 0.00
4.261 0.00
2014 年 9 月 9 日 ERATO 湊離散構造処理系ワ
/ 27
BN 構造学習の実際
実験 3
R のデータセットについて、実行時間を測定
data.frame
faithful
quakes
attitude
longley
USJudgeRatings
N
2
5
7
7
12
data.type
c,d
c,c,d,d,c
d,d,d,d,d,d,d
c,c,c,c,c,c,d
c,c,c,c,c,c,c,c,c,c,c,c
n
272
1000
30
16
43
time (sec)
6.08
60.77
27.66
44.63
1946.63
time (sec)/2N
3.04
1.90
0.216
0.349
1.90
N が大きいと、スコアを求める計算が大きいのは、連続でも離散でも同じ
鈴木譲 (大阪大学)
属性間の依存関係の推定と実装
2014 年 9 月 9 日 ERATO 湊離散構造処理系ワ
/ 27
まとめ
まとめ
.
離散と連続を区別しない一般的な BN の構造学習の確立
.
アルゴリズムの検討 (計算量の評価を含む)
.
R による実データでの評価
得られた知見
連続でも、ヒストグラムの深さに比例する程度の計算量
構造の比較の計算量 O(M(N)) が O(nK 2N ) より大きい
(n 一定の仮定のもとで)
今後の課題
n, N から、適当な K の値を計算
K に対して指数的なメモリが必要である問題の解決
R パッケージの公開
実データへのさらなる適用
鈴木譲 (大阪大学)
属性間の依存関係の推定と実装
2014 年 9 月 9 日 ERATO 湊離散構造処理系ワ
/ 27

Download Report