Sum-productアルゴリズムの概要
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/02/25 02:50 UTC 版)
「確率伝搬法」の記事における「Sum-productアルゴリズムの概要」の解説
確率伝搬法は因子グラフ上で実行するアルゴリズムである。ここで、因子グラフとは変数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へ渡すメッセージ。メッセージの計算は隣接しているすべての因子グラフの積を取ることによって表現される(ただし、対象の因子ノードからのメッセージは除くものとする。除く代わりに、対象の因子ノードからのメッセージは"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以外のすべての変数について周辺化を行うことで表現される: μ 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})} とする。 明らかに、確率伝搬法の名前の由来は上の公式から来るものである。このアルゴリズムによって、結合確率分布に対する周辺分布の計算という困難な問題が、単純なメッセージの積と和の計算に減少できる。
※この「Sum-productアルゴリズムの概要」の解説は、「確率伝搬法」の解説の一部です。
「Sum-productアルゴリズムの概要」を含む「確率伝搬法」の記事については、「確率伝搬法」の概要を参照ください。
- Sum-productアルゴリズムの概要のページへのリンク
