ベイジアンネットワーク概説
3.6 構造の探索アルゴリズム
茨城大学工学部
佐々木稔
はじめに

ネットワーク構造の探索アルゴリズム


すべての構造から最適な構造を選択
n=3 の場合、合計25通り(向きなしで以下の8種)
1
2
1
3
1種類
2
2
4種類
3
2種類
1
2
2
4種類
3
2
1
1
3
2
4種類
3
2種類
2種類
1
3
1
1
3
2
6種類
3
探索するネットワークの数

変数の数 n でのネットワークの数 f(n)
n
f n    1
i 1
i 1
 n  i ( n i )
f n  i 
 i 2
 
n 
  i  は2項係数、 nCi と同じ




n=2 のとき、 f(n)=3
n=3 のとき、 f(n)=25
n=5 のとき、 f(n)=29,281
探索計算量を減らす工夫が必要
遺伝アルゴリズムによる探索

全順序関係の情報がない場合


遺伝的アルゴリズムを用いて構造を探索
構造マトリックスを用意


下図のように変数 i から j に矢印があれば 1、なければ 0
行列の各要素を遺伝子とみなす

最適な構造を学習
j
i
j
i





 1 





K2アルゴリズム
ヒューリスティックによる構造の探索
 変数間の親子関係を表した全順序関係が必要



X1 > X2 > ・・・ > XN
この関係から半順序関係を抽出する
X 1 > X2 > X3
の場合、以下の順序から選択
X1
X1
X2
X3
X2
X3
X1
X2
X3
K2アルゴリズム(backward版)
for i = 1:n {
pa(Xi) = φ;
P(Xi | pa(Xi))=0.0;
for j = i:n {
Xj を pa(Xi) に加える;
P(Xi | pa(Xi)) を計算;
Xj のない場合の P(Xi | pa(Xi)) と比較 {
大きい場合は、 Xj を含めた pa(Xi) を採用;
それ以外は、 Xj を含めない pa(Xi) を採用;
}
}
}
K2アルゴリズムの情報量基準

Cooper の事前分布確率

Bayesian Dirichlet Metric とも呼ばれる
qi
p X i | pa X i   
j 1
ri 1!
ri 1
N

N  r 1!
ij
i
k 0
ijk
!
K2アルゴリズムの動作

1.
変数 A, B, C で、A>B>C (A が子)が既知
A について

B と比較
•
•

C と B → A を比較
•
•
2.
B が親の場合と、独立な場合のP(Xi|pa(Xi)) を計算
値の大きい A ← B を採用
C が親の場合と、独立な場合のP(Xi|pa(Xi)) を計算
値の大きい B → A ← C を採用
B → A → C が生成され、 B → A ← C と比較

値の大きい B → A → C を採用
K2アルゴリズム(forward版)
for i = 1:n {
pa(Xi) = φ;
Pold = P(Xi | pa(Xi));
OKtoProceed = True;
while (OKtoProceed || |pa(Xi)|<u) {
P(Xi|{pa(Xi)∪{Xj}}) が最大となる親ノード候補 Xj を抽出;
Pnew = P(Xi | {pa(Xi)∪{Xj}});
if (Pnew > Pold) {
Pold = Pnew;
pa(Xi) = pa(Xi)∪{Xj};
} else
OKtoProceed = False;
}
}
K2アルゴリズムの入力データ
• 全順序付ノード集合
{x1, x2, x3},
n=3
• データベース D
(データ10個)
• 親ノードの上限 u
u=2
データ
1
2
3
4
x1
x2
x3
1
1
0
1
0
1
0
1
0
1
1
1
5
6
7
0
0
1
0
1
1
0
1
1
8
9
10
0
1
0
0
1
0
0
1
0
K2アルゴリズムの動作1-1

i=1 のとき、 x1が対象



r1= 2 ( {’0’, ’1’} の 2 種類 )
pa(x1) = φ
親ノード候補の取る値の数 q1 = 0 (独立)




独立の場合は、 j は無視して i と k のみ考える
N1_1 = 5 (x1=0 なのは {3, 5, 6, 8, 10})
N1_2 = 5 (x1=1 なのは {1, 2, 4, 7, 9} )
N1_ = N1_1 + N1_2 = 10
K2アルゴリズムの動作1-2
Pold  P(x1|  )
  j 1
q1

N
r1  1!
1j
2  1!

 r  1!
10  2  1!
r1
k 1
N1 jk !
1
 N1_1! N1_ 2 !
1
1

 5! 5! 
11!
2772
• 親候補が存在しないので繰返しは終了し、
pa(x1) = φ
K2アルゴリズムの動作2-1

i=2 のとき、 x2が対象



r2= 2 ( {’0’, ’1’} の 2 種類 )
pa(x2) = φ
親ノード候補の取る値の数 q2 = 0 (独立)




独立の場合は、 j は無視して i と k のみ考える
N2_1 = 5 (x2=0 なのは {1, 3, 5, 8, 10})
N2_2 = 5 (x2=1 なのは {2, 4, 6, 7, 9} )
N2_ = N2_1 + N2_2 = 10
K2アルゴリズムの動作2-2
Pold  P(x2 |  )
  j 1
q2

N
r2  1!
2j
2  1!
 r2
10  2  1!

 1!
r2
k 1
N 2 jk !
 N 2 _1! N 2 _ 2 !
1
1

 5! 5! 
11!
2772
K2アルゴリズムの動作2-3

i=2 で、親ノード候補 {x1}


r2= 2 ( {’0’, ’1’} の 2 種類 )
親ノード候補の取る値の数 q2 = 2







(x1=0) と (x1=1) の 2 種類
N211 = 4 (x1=0, x2=0
N212 = 1 (x1=0, x2=1
N221 = 1 (x1=1, x2=0
N222 = 4 (x1=1, x2=1
N21 = N211 + N212 = 5
N22 = N221 + N222 = 5
なのは
なのは
なのは
なのは
{3, 5, 8, 10})
{6} )
{1})
{2, 4, 7, 9})
K2アルゴリズムの動作2-4
Pnew  P(x2 | x1)
  j 1
2
N
r2  1!
2j
 r2

 1!
2
k 1
N 2 jk !
2
2


2  1!
2  1!

N !
N !


k 1 21k
k 1 22 k
5  2  1!
5  2  1!
1
1
1
  4!1!  1! 4! 
6!
6!
900
• P(x2|{x1}) が最大値で、Pnew>Pold より、
Pa(x2)={x1}
K2アルゴリズムの動作3-1

i=3 のとき、 x3が対象



r3= 2 ( {’0’, ’1’} の 2 種類 )
pa(x3) = φ
親ノード候補の取る値の数 q3 = 0 (独立)




独立の場合は、 j は無視して i と k のみ考える
N3_1 = 4 (x3=0 なのは {1, 5, 8, 10})
N3_2 = 6 (x3=1 なのは {2, 3, 4, 6, 7, 9})
N3_ = N3_1 + N3_2 = 10
K2アルゴリズムの動作3-2
Pold  P(x3|  )
  j 1
q3

N
r3  1!
3j
2  1!

 r  1!
10  2  1!
r3
k 1
N 2 jk !
3
 N 3 _1! N 3 _ 2 !
1
1

 4! 6! 
11!
2310
K2アルゴリズムの動作3-3

i=3 で、親ノード候補 {x1}


r3= 2 ( {’0’, ’1’} の 2 種類 )
親ノード候補の取る値の数 q3 = 2







(x1=0) と (x1=1) の 2 種類
N311 = 3 (x1=0, x3=0
N312 = 2 (x1=0, x3=1
N321 = 1 (x1=1, x3=0
N322 = 4 (x1=1, x3=1
N31 = N311 + N312 = 5
N32 = N321 + N322 = 5
なのは
なのは
なのは
なのは
{5, 8, 10})
{3, 6} )
{1})
{2, 4, 7, 9})
K2アルゴリズムの動作3-4
Pnew  P(x3| x1)
  j 1
2
N
r3  1!
3j

 r  1!
2
k 1
N 3 jk !
3
2
2


2  1!
2  1!

N !
N !


k 1 31k
k 1 32 k
5  2  1!
5  2  1!
1
1
1
  3! 2!  1! 4! 
6!
6!
1800
K2アルゴリズムの動作3-5

i=3 で、親ノード候補 {x2}


r3= 2 ( {’0’, ’1’} の 2 種類 )
親ノード候補の取る値の数 q3 = 2







(x2=0) と (x2=1) の 2 種類
N311 = 4 (x2=0, x3=0
N312 = 1 (x2=0, x3=1
N321 = 0 (x2=1, x3=0
N322 = 5 (x2=1, x3=1
N31 = N311 + N312 = 5
N32 = N321 + N322 = 5
なのは
なのは
なのは
なのは
{1, 5, 8, 10})
{3} )
{})
{2, 4, 6, 7, 9})
K2アルゴリズムの動作3-6
Pnew  P(x3| x 2)
  j 1
2
N
r3  1!
3j

 r  1!
2
k 1
N 3 jk !
3
2
2


2  1!
2  1!

N !
N !


k 1 31k
k 1 32 k
5  2  1!
5  2  1!
1
1
1
  4!1!  0! 5! 
6!
6!
180
• P(x3|{x2}) が最大値で、 Pnew > Pold より、
Pa(x3)= {x2}, Pold=1/180
K2アルゴリズムの動作3-7

i=3で、決定済み親ノード{x2}、親ノード候補{x1}


r3= 2 ( {’0’, ’1’} の 2 種類 )
親ノード候補の取る値の数 q3 = 4











(x1=0, x2=0), (x1=0, x2=1),
(x1=1, x2=0), (x1=1, x2=1) の 4 種類
N311 = 3 (x1=0, x2=0,
N312 = 1 (x1=0, x2=0,
N322 = 1 (x1=0, x2=1,
N332 = 1 (x1=1, x2=0,
N342 = 4 (x1=1, x2=1,
N31 = N311 + N312 = 4
N32 = N321 + N322 = 1
N33 = N331 + N332 = 1
N34 = N341 + N342 = 4
x3=0
x3=1
x3=1
x3=0
x3=1
なのは
なのは
なのは
なのは
なのは
{5, 8, 10})
{3} )
{6})
{1})
{2, 4, 7, 9})
K2アルゴリズムの動作3-8
Pnew  P(x3| x1, x 2)
  j 1
2
N
r3  1!
3j
2  1!

 r  1!
2
k 1
N 3 jk !
3
2

2  1!

N !
N !


k 1 31k
k 1 32 k
4  2  1!
1  2  1!
2
2


2  1!
2  1!

N !
N !


k 1 33 k
k 1 34 k
1  2  1!
4  2  1!
2
1
1
1
1
1
  3!1!  0!1!  1! 0!  0! 4! 
5!
2!
2!
5!
400
•Pnew < Pold より、Pa(x3)= {x2} のまま
K2アルゴリズムの動作3-9

以上の処理から、



x1 の親ノードは φ
x2 の親ノードは {x1}
x3 の親ノードは {x2}
したがって、求める構造は
 x1 → x2 → x3

ダウンロード

n - 茨城大学