ベイジアンネットワーク概説 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
© Copyright 2024 ExpyDoc