確率伝搬法
確率伝搬法は因子グラフ上で実行するアルゴリズムである。ここで、因子グラフとは変数Vと因子Uによって構成されている2部グラフであり、変数と因子の間にはエッジが張られている。このグラフを用いることで、以下の結合確率質量関数を書き下せる。
p ( x ) = ∏ u ∈ U f u ( x u ) {\displaystyle p(\mathbf {x} )=\prod _{u\in U}f_{u}(\mathbf {x} _{u})}
ここで、xuは因子ノードuに隣接している変数を表すベクトルである。任意のベイジアンネットワークとマルコフ確率場は因子グラフの形で表現できる。
このアルゴリズムはメッセージと呼ばれる、変数xvを引数にとる関数をノード間のエッジに沿って伝搬させる。これらのメッセージはある変数が他の変数に影響を与える『相互作用』を含む。メッセージには2種類存在する:
変数ノードvから因子ノードuへ渡すメッセージ。メッセージの計算は隣接しているすべての因子グラフの積を取ることによって表現される(ただし、対象の因子ノードからのメッセージは除くものとする。
確率伝搬法の最も簡単な形は、対象の因子グラフが木構造となる場合である。この場合、確率伝搬法は周辺分布の厳密解を計算でき、以下の2段階のステップの後に終了する。
このアルゴリズムを開始する前に、対象のグラフの内一つのノードを根として定める。また、任意の根でない、一つのノードしか接続されていないノードを葉と呼ぶ。
一段階目のステップでは、メッセージの計算を葉ノードから始める。各々のノードはエッジを通して、受けとったメッセージを根ノードに向けて伝搬する。グラフは木構造であるため、対象のノードにメッセージを渡す前に、他のすべての近接ノードからメッセージを受けとれることが保証される。この伝搬則は、根ノードがすべての近接ノードからメッセージを受け取るまで繰り返される。
二段階目のステップでは、根ノードから葉ノードに向けてメッセージを送信する。この場合、メッセージは前回とは逆の方向から伝搬される。すべての葉ノードがメッセージを受け取った際に、このアルゴリズムは終了する。