木構造である場合の厳密解
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/02/25 02:50 UTC 版)
「確率伝搬法」の記事における「木構造である場合の厳密解」の解説
確率伝搬法の最も簡単な形は、対象の因子グラフが木構造となる場合である。この場合、確率伝搬法は周辺分布の厳密解を計算でき、以下の2段階のステップの後に終了する。 このアルゴリズムを開始する前に、対象のグラフの内一つのノードを根として定める。また、任意の根でない、一つのノードしか接続されていないノードを葉と呼ぶ。 一段階目のステップでは、メッセージの計算を葉ノードから始める。各々のノードはエッジを通して、受けとったメッセージを根ノードに向けて伝搬する。グラフは木構造であるため、対象のノードにメッセージを渡す前に、他のすべての近接ノードからメッセージを受けとれることが保証される。この伝搬則は、根ノードがすべての近接ノードからメッセージを受け取るまで繰り返される。 二段階目のステップでは、根ノードから葉ノードに向けてメッセージを送信する。この場合、メッセージは前回とは逆の方向から伝搬される。すべての葉ノードがメッセージを受け取った際に、このアルゴリズムは終了する。 計算が完了した後、各々のノードの周辺分布は隣接している因子ノードからのメッセージの積に比例する: p X v ( x v ) ∝ ∏ u ∈ N ( v ) μ u → v ( x v ) . {\displaystyle p_{X_{v}}(x_{v})\propto \prod _{u\in N(v)}\mu _{u\to v}(x_{v}).} 同様に、ある因子に属している変数の集合の周辺分布は、変数からのメッセージとその因子の積に比例する: p X u ( x u ) ∝ f u ( x u ) ∏ v ∈ N ( u ) μ v → u ( x u ) . {\displaystyle p_{X_{u}}(\mathbf {x} _{u})\propto f_{u}(\mathbf {x} _{u})\prod _{v\in N(u)}\mu _{v\to u}(x_{u}).} これらの計算は数学的帰納法によって証明できる。
※この「木構造である場合の厳密解」の解説は、「確率伝搬法」の解説の一部です。
「木構造である場合の厳密解」を含む「確率伝搬法」の記事については、「確率伝搬法」の概要を参照ください。
- 木構造である場合の厳密解のページへのリンク
