確率伝搬法
除く代わりに、対象の因子ノードからのメッセージは"1"を送るものとして計算することもできる):
μ v → u ( x v ) = ∏ u ∗ ∈ N ( v ) ∖ { u } μ u ∗ → v ( x v ) . {\displaystyle \mu _{v\to u}(x_{v})=\prod _{u^{*}\in N(v)\setminus \{u\}}\mu _{u^{*}\to v}(x_{v}).}
ここで、N(v)は変数ノードvに隣接する、すべての因子ノードの集合とする。 N ( v ) ∖ { u } {\displaystyle N(v)\setminus \{u\}} が空集合であるならば、 μ v → u ( x v ) {\displaystyle \mu _{v\to u}(x_{v})} は一様分布として計算する。
因子ノードuから変数ノードvへ渡すメッセージ。メッセージの計算は隣接している他のノードからのメッセージの積をとり、xv以外のすべての変数について周辺化を行うことで表現される:
このアルゴリズムは1982年にジューディア・パールにより提案されたもので、当初は木構造上のグラフィカルモデルで作用するアルゴリズムであったものを、後に一般的な構造のモデルにおいても作用できるように拡張した。現在では、このアルゴリズムがループを含む一般のグラフ構造においても良い近似を与えることが示されている。
一例を示す。X=(Xv)を結合確率質量関数pをもつ離散的な確率変数の集合とすると、単体のノードの確率を表す周辺分布Xiは、単純にpをXi以外のノードについて和をとることで表現できる:
p X i ( x i ) = ∑ x ′ : x i ′ = x i p ( x ′ ) . {\displaystyle p_{X_{i}}(x_{i})=\sum _{\mathbf {x} ':x'_{i}=x_{i}}p(\mathbf {x} ').}
しかし、この計算は仮に確率変数が100個の二値変数であったとしても、この確率変数全体の場合の数は2 ≈ 6.338 × 10と非常に多くなるため、コンピュータ上で計算することは相当な困難を伴うものである。確率伝搬法では対象の確率変数のグラフ構造を利用することによって、この周辺分布の計算をより効率的に行う。
μ u → v ( x v ) = ∑ x u ′ : x v ′ = x v f u ( x u ′ ) ∏ v ∗ ∈ N ( u ) ∖ { v } μ v ∗ → u ( x v ∗ ′ ) . {\displaystyle \mu _{u\to v}(x_{v})=\sum _{\mathbf {x} '_{u}:x'_{v}=x_{v}}f_{u}(\mathbf {x} '_{u})\prod _{v^{*}\in N(u)\setminus \{v\}}\mu _{v^{*}\to u}(x'_{v^{*}}).}
ここで、N(u)は因子ノードuに隣接する、すべての変数ノードの集合とする。 N ( u ) ∖ { v } {\displaystyle N(u)\setminus \{v\}} が空集合であるならば、 μ u → v ( x v ) = f u ( x v ) {\displaystyle \mu _{u\to v}(x_{v})=f_{u}(x_{v})} とする。
明らかに、確率伝搬法の名前の由来は上の公式から来るものである。このアルゴリズムによって、結合確率分布に対する周辺分布の計算という困難な問題が、単純なメッセージの積と和の計算に減少できる。