ベイジアンネットワーク概説 Loopy Belief Propagation 茨城大学工学部 佐々木稔

Presentation on theme: "ベイジアンネットワーク概説 Loopy Belief Propagation 茨城大学工学部 佐々木稔"— Presentation transcript:

1 ベイジアンネットワーク概説 4.2.5 Loopy Belief Propagation 茨城大学工学部 佐々木稔
4.2.3 ジャンクションツリーアルゴリズム サンプリング法 4.2.5 Loopy Belief Propagation 茨城大学工学部 佐々木稔

2 複結合ネットワーク 複結合ネットワーク リンクを単純にたどる場合 １ ４ ２ ３ ５ 向きを考慮せずパスにループが含まれるネットワーク
確率計算の収束性が保障されない １ ４ ２ ３ ５

3 ジャンクションツリーアルゴリズム 複結合ネットワークの確率計算方法 手順 事前に単結合に変換して確率計算 単結合の場合、確率計算は収束
モラル化(moralization) 三角化(triangulation) ジャンクションツリーの生成 確率計算

4 モラル化(Moralization) ベイジアンネットワークをモラルグラフに変換する モラルグラフ １ ４ ２ ３ ５ １ ４ ２ ３ ５
有効グラフに対して 共通の子供を持つ親ノードをつなげる 有向グラフを無向グラフにする １ ４ ２ ３ ５ １ ４ ２ ３ ５

5 三角化(triangulation) モラルグラフに辺を加える 長さ4以上のサイクルをなくす １ ４ ２ ３ ５

6 ジャンクションツリーの生成 {1, 2, 3} {2, 3, 4} {3, 5} 3-クリークを見つける １ ４ ２ ３ ５ クリーク
相異なる2点間に少なくとも１つの枝を持つノード集合 3-クリークは2-クリークを含む １ ４ ２ ３ ５ {1, 2, 3} {2, 3, 4} {3, 5}

7 ジャンクションツリーの生成 {1, 2, 3} {2, 3, 4} {3, 5} 123 234 35 ジャンクションツリーの生成 23 3
クリークをノードとする 元ネットワークで共有ノードがあれば、ノード間をつなぐ 123 {1, 2, 3} {2, 3, 4} {3, 5} 23 234 3 35

8 ジャンクションツリーアルゴリズムの問題点
ノード数の増加により、計算コストが増加 最大クリーク問題は、NP困難 グラフ構造の性質により変換できない場合がある 巨大なクラスタが生じる可能性もある クラスタ内の確率計算に多くの計算量とメモリが必要

9 サンプリング法 グラフ構造を変換しない確率推論 stochastic logic sampling (Henrion ’88) 入力 処理
ネットワークから得られる観測データ（エビデンス） 各ノードが取る各状態で結合確率を適当に決める 処理 適当に決めた確率をもとにサンプルを生成 観測データと一致するものだけを対象にサンプルの頻度を計算 対象とする確率変数の事後確率 P(X|e) を求める

10 サンプリング法 サンプルの生成方法 確率的なランダムサンプリング マルコフ連鎖モンテカルロ法 決定論的サンプリング手法 システムサンプリング
尤度重み付け

11 Markov Chain Monte Carlo (MCMC)
確率分布 P(X) に従うように点 X をサンプリング マルコフ連鎖 直前の点 X(t-1) のみから新しい点 X(t) を決定 これによりできる集合 {X} が確率分布 P(X) に従う 分布関数の収束するために 点 X から点 X’ への遷移確率 W(X → X’) を決定 メトロポリスの遷移確率

12 Markov Chain Monte Carlo (MCMC)
アルゴリズム 初期設定 : 任意の初期状態 X(0) を選ぶ 次候補 : 点 X からランダムに変化させた点 X’ を作る 遷移確率計算 : 遷移コスト P(X’)/P(X) を計算 更新 : 一様乱数 r ∈ [0, 1] を生成し、X(t+1) を決定 ステップ1に戻る

13 Loopy Belief Propagation
複結合ネットワークの確率計算 確率伝播法を強引に適用 局所的な確率伝播を繰り返すと判別可能 事後確率最大の状態に収束 ノード値が振動 解の精度、収束性にいまだ課題が残る