ベイジアンネットワーク 概説 4.2.3 ジャンクションツリーアルゴリズム 4.2.4 サンプリング法 4.2.5 Loopy Belief Propagation 茨城大学工学部 佐々木稔 複結合ネットワーク 複結合ネットワーク 向きを考慮せずパスにループが含まれるネットワーク リンクを単純にたどる場合 確率計算の収束性が保障されない 1 2 3 4 5 ジャンクションツリーアルゴリズム 複結合ネットワークの確率計算方法 事前に単結合に変換して確率計算 単結合の場合、確率計算は収束 手順 1. 2. 3. 4. モラル化(moralization) 三角化(triangulation) ジャンクションツリーの生成 確率計算 モラル化(Moralization) ベイジアンネットワークをモラルグラフに変換する モラルグラフ 有効グラフに対して 共通の子供を持つ親ノードをつなげる 有向グラフを無向グラフにする 1 2 1 2 3 4 5 3 4 5 三角化(triangulation) モラルグラフに辺を加える 長さ4以上のサイクルをなくす 1 2 3 4 5 ジャンクションツリーの生成 3-クリークを見つける クリーク 相異なる2点間に少なくとも1つの枝を持つノード集合 3-クリークは2-クリークを含む 1 2 3 4 5 {1, 2, 3} {2, 3, 4} {3, 5} ジャンクションツリーの生成 ジャンクションツリーの生成 クリークをノードとする 元ネットワークで共有ノードがあれば、ノード間をつなぐ {1, 2, 3} {2, 3, 4} {3, 5} 123 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’) を決定 メトロポリスの遷移確率 P( X ' ) W ( X X ' ) min1, P( X ) Markov Chain Monte Carlo (MCMC) アルゴリズム 1. 2. 3. 4. 初期設定 : 任意の初期状態 X(0) を選ぶ 次候補 : 点 X からランダムに変化させた点 X’ を作る 遷移確率計算 : 遷移コスト P(X’)/P(X) を計算 更新 : 一様乱数 r ∈ [0, 1] を生成し、X(t+1) を決定 X 5. ( t 1) X ' if r P X ' P X (t ) (t ) otherwise X ステップ1に戻る Loopy Belief Propagation 複結合ネットワークの確率計算 局所的な確率伝播を繰り返すと判別可能 確率伝播法を強引に適用 事後確率最大の状態に収束 ノード値が振動 解の精度、収束性にいまだ課題が残る
© Copyright 2024 ExpyDoc