一般的なグラフに関しての近似アルゴリズム
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/02/25 02:50 UTC 版)
「確率伝搬法」の記事における「一般的なグラフに関しての近似アルゴリズム」の解説
奇妙な事に、一般的なグラフに関しても木構造と同様のアルゴリズムを用いることができる。このアルゴリズムは対象のグラフが一般にループを含むことから"loopy" belief propagationアルゴリズムと呼ばれることもある。対象のグラフが葉を含んでいないため、このアルゴリズムは確率伝搬法の伝搬規則は僅かながら修正される必要がある。まず、最初にすべての変数間のメッセージを1に初期化する。次に、各反復回数ごとに上の定義を用いたメッセージの更新を、(たとえ十分な反復によって、葉や木構造の部分グラフから既知のメッセージが来た場合においても)すべてのメッセージに対して行う。対象のグラフが木構造である場合、loopy belief propagationの手続きは、対象のグラフの直径に等しい反復回数以内で、本来の確率伝搬法で得られるメッセージへ収束する。 loopy belief propagationアルゴリズムの正確な収束条件は未だに明らかでないが、単一のループを含むグラフにおいては、厳密解ではないにしろ、常に収束することが知られている。その他にもloopy belief propagationが唯一の固定点に収束するための十分条件(必要条件でない)がいくつか存在する。一方で、メッセージが発散したり、各反復回数毎に解が振動するようなグラフも存在する。EXITチャートのような手法を用いて、確率伝搬法の経過やその収束状況について近似的に可視化し、調査することもできる。 周辺化のための近似手法としては、他にも変分法やモンテカルロ法を含むいくつかの手法が提案されている。 一般的なグラフ上で厳密な周辺分布解を求めるための一つとしてジャンクションツリーアルゴリズムが挙げられる。これは対象のグラフを木構造へ修正し、その後に確率伝搬法を適用する。ジャンクションツリーではループを含むクラスタを単一のノードにまとめループを消去することで、確率伝搬法の収束性を保証している。
※この「一般的なグラフに関しての近似アルゴリズム」の解説は、「確率伝搬法」の解説の一部です。
「一般的なグラフに関しての近似アルゴリズム」を含む「確率伝搬法」の記事については、「確率伝搬法」の概要を参照ください。
- 一般的なグラフに関しての近似アルゴリズムのページへのリンク
