ベイジアンネットワーク概説 4.2.5 Loopy Belief Propagation 茨城大学工学部 佐々木稔 4.2.3 ジャンクションツリーアルゴリズム 4.2.4 サンプリング法 4.2.5 Loopy Belief Propagation 茨城大学工学部 佐々木稔
複結合ネットワーク 複結合ネットワーク リンクを単純にたどる場合 １ ４ ２ ３ ５ 向きを考慮せずパスにループが含まれるネットワーク 確率計算の収束性が保障されない １ ４ ２ ３ ５
ジャンクションツリーアルゴリズム 複結合ネットワークの確率計算方法 手順 事前に単結合に変換して確率計算 単結合の場合、確率計算は収束 モラル化(moralization) 三角化(triangulation) ジャンクションツリーの生成 確率計算
モラル化(Moralization) ベイジアンネットワークをモラルグラフに変換する モラルグラフ １ ４ ２ ３ ５ １ ４ ２ ３ ５ 有効グラフに対して 共通の子供を持つ親ノードをつなげる 有向グラフを無向グラフにする １ ４ ２ ３ ５ １ ４ ２ ３ ５
三角化(triangulation) モラルグラフに辺を加える 長さ4以上のサイクルをなくす １ ４ ２ ３ ５
ジャンクションツリーの生成 {1, 2, 3} {2, 3, 4} {3, 5} 3-クリークを見つける １ ４ ２ ３ ５ クリーク 相異なる2点間に少なくとも１つの枝を持つノード集合 3-クリークは2-クリークを含む １ ４ ２ ３ ５ {1, 2, 3} {2, 3, 4} {3, 5}
ジャンクションツリーの生成 {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
ジャンクションツリーアルゴリズムの問題点 ノード数の増加により、計算コストが増加 最大クリーク問題は、NP困難 グラフ構造の性質により変換できない場合がある 巨大なクラスタが生じる可能性もある クラスタ内の確率計算に多くの計算量とメモリが必要
サンプリング法 グラフ構造を変換しない確率推論 stochastic logic sampling (Henrion ’88) 入力 処理 ネットワークから得られる観測データ（エビデンス） 各ノードが取る各状態で結合確率を適当に決める 処理 適当に決めた確率をもとにサンプルを生成 観測データと一致するものだけを対象にサンプルの頻度を計算 対象とする確率変数の事後確率 P(X|e) を求める
サンプリング法 サンプルの生成方法 確率的なランダムサンプリング マルコフ連鎖モンテカルロ法 決定論的サンプリング手法 システムサンプリング 尤度重み付け
Markov Chain Monte Carlo (MCMC) 確率分布 P(X) に従うように点 X をサンプリング マルコフ連鎖 直前の点 X(t-1) のみから新しい点 X(t) を決定 これによりできる集合 {X} が確率分布 P(X) に従う 分布関数の収束するために 点 X から点 X’ への遷移確率 W(X → X’) を決定 メトロポリスの遷移確率
Markov Chain Monte Carlo (MCMC) アルゴリズム 初期設定 : 任意の初期状態 X(0) を選ぶ 次候補 : 点 X からランダムに変化させた点 X’ を作る 遷移確率計算 : 遷移コスト P(X’)/P(X) を計算 更新 : 一様乱数 r ∈ [0, 1] を生成し、X(t+1) を決定 ステップ1に戻る
Loopy Belief Propagation 複結合ネットワークの確率計算 確率伝播法を強引に適用 局所的な確率伝播を繰り返すと判別可能 事後確率最大の状態に収束 ノード値が振動 解の精度、収束性にいまだ課題が残る