ベイジアンネットワーク概説 3.6 構造の探索アルゴリズム 茨城大学工学部 佐々木稔

はじめに 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 ネットワーク構造の探索アルゴリズム すべての構造から最適な構造を選択 n=3 の場合、合計25通り（向きなしで以下の8種） 1 2 3 1 2 3 1 2 3 1 2 3 1種類 2種類 2種類 2種類 1 2 3 1 2 3 1 2 3 1 2 3 4種類 4種類 4種類 6種類

探索するネットワークの数 変数の数 n でのネットワークの数 f(n) 探索計算量を減らす工夫が必要 は2項係数、 nCi と同じ

遺伝アルゴリズムによる探索 j i i j 全順序関係の情報がない場合 遺伝的アルゴリズムを用いて構造を探索 構造マトリックスを用意 行列の各要素を遺伝子とみなす 最適な構造を学習 j i j i

K2アルゴリズム X1 X2 X3 > X1 X2 X3 X1 X2 X3 X1 X2 X3 ヒューリスティックによる構造の探索 変数間の親子関係を表した全順序関係が必要 X1 > X2 > ・・・ > XN この関係から半順序関係を抽出する X1 X2 X3 > の場合、以下の順序から選択 X1 X2 X3 X1 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 とも呼ばれる

K2アルゴリズムの動作 変数 A, B, C で、A>B>C (A が子)が既知 A について B が親の場合と、独立な場合のP(Xi|pa(Xi)) を計算 値の大きい A ← B を採用 C と B → A を比較 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 2 3 4 5 6 7 8 9 10

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 親候補が存在しないので繰返しは終了し、 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

K2アルゴリズムの動作2-3 i=2 で、親ノード候補 {x1} r2= 2 （ {’0’, ’1’} の 2 種類 ） 親ノード候補の取る値の数 q2 = 2 （x1=0） と （x1=1） の 2 種類 N211 = 4 （x1=0, x2=0 なのは {3, 5, 8, 10}） N212 = 1 （x1=0, x2=1 なのは {6} ） N221 = 1 （x1=1, x2=0 なのは {1}） N222 = 4 （x1=1, x2=1 なのは {2, 4, 7, 9}） N21 = N211 + N212 = 5 N22 = N221 + N222 = 5

K2アルゴリズムの動作2-4 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

K2アルゴリズムの動作3-3 i=3 で、親ノード候補 {x1} r3= 2 （ {’0’, ’1’} の 2 種類 ） 親ノード候補の取る値の数 q3 = 2 （x1=0） と （x1=1） の 2 種類 N311 = 3 （x1=0, x3=0 なのは {5, 8, 10}） N312 = 2 （x1=0, x3=1 なのは {3, 6} ） N321 = 1 （x1=1, x3=0 なのは {1}） N322 = 4 （x1=1, x3=1 なのは {2, 4, 7, 9}） N31 = N311 + N312 = 5 N32 = N321 + N322 = 5

K2アルゴリズムの動作3-4

K2アルゴリズムの動作3-5 i=3 で、親ノード候補 {x2} r3= 2 （ {’0’, ’1’} の 2 種類 ） 親ノード候補の取る値の数 q3 = 2 （x2=0） と （x2=1） の 2 種類 N311 = 4 （x2=0, x3=0 なのは {1, 5, 8, 10}） N312 = 1 （x2=0, x3=1 なのは {3} ） N321 = 0 （x2=1, x3=0 なのは {}） N322 = 5 （x2=1, x3=1 なのは {2, 4, 6, 7, 9}） N31 = N311 + N312 = 5 N32 = N321 + N322 = 5

K2アルゴリズムの動作3-6 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, x3=0 なのは {5, 8, 10}） N312 = 1 （x1=0, x2=0, x3=1 なのは {3} ） N322 = 1 （x1=0, x2=1, x3=1 なのは {6}） N332 = 1 （x1=1, x2=0, x3=0 なのは {1}） N342 = 4 （x1=1, x2=1, x3=1 なのは {2, 4, 7, 9}） N31 = N311 + N312 = 4 N32 = N321 + N322 = 1 N33 = N331 + N332 = 1 N34 = N341 + N342 = 4

K2アルゴリズムの動作3-8 Pnew < Pold より、Pa（x3）= {x2} のまま

K2アルゴリズムの動作3-9 以上の処理から、 したがって、求める構造は x1 → x2 → x3 x1 の親ノードは φ