仮定
以下の議論では,モデルの持つすべての変数は離散的であると仮定します。
また、もともとのグラフは無向木、有向木あるいは多重木のいずれかであると仮定します。
すると、これを変換してできる因子グラフは木構造を持ちます。
因子グラフにおける同時分布
ある特定の変数ノード 上の周辺分布 を求める問題から考えます。
周辺分布 は、以下のようになります。
ここで、 は の変数集合から変数 を除いたものを示します。
グラフが木構造を持つので、同時分布の因子を変数ノード に
隣接する各因子ノードごとにグループ分けすることができます。
同時分布は以下の形の積で書けます。
ここで、 は に隣接する因子ノードの集合を表し、
は因子ノード を通して、変数ノード に接続される部分木に属する全ての変数を表します。
また、 は因子 に関連するグループのすべての因子の積を表します。
因子ノードから変数ノードへのメッセージ
式 を式 に代入します。
式 で、 としました。( に隣接する因子ノードを としました。)
式 で、以下で定義される関数 を導入しました。
式 は因子ノード から変数ノード へのメッセージと解釈できます。
式 のイメージを以下の図1に記しました。
図1: のイメージ
式 から式 の式変形で積と和を入れ替わっていますが、これが積和アルゴリズムの肝です。
この積和の入れ替えが成り立つのは、木構造の因子モデルだからです。
実はこれに似た考え方を、連鎖における推論の式 で既に説明しています。
分かりにくい場合は、そちらを参照してみてください。
変数ノードから因子ノードへのメッセージ
各因子 も因子(部分)グラフによって記述されるので、以下のように書けます。
ここで、 とともに因子 に関連する変数を としました。
は因子ノード に隣接する変数ノード集合であり、 はその集合から を除いたものです。
は変数ノード を通して、因子ノード に接続される部分木に属する全ての変数を表します。
は変数ノード に接続される 以外の因子に関連するグループのすべての因子の積を表します。
式 を式 に代入します。
ここで、変数ノードから因子ノードへのメッセージ を定義しました。
ここまでのイメージを図2に記しました。
図2
また、以下の図3より、 は次のように書けます。
図3
式 を式 に代入します。
式 で、 としました。( に隣接する を除く因子ノードを としました。)
式 より、
因子ノードから変数ノードへのメッセージ を変数ノードから因子ノードへのメッセージ で表すことができ、
その逆も表すことができることが分かりましたので、各メッセージは他のメッセージを用いて再帰的に計算できます。
葉ノードから辿る
を根ノードとみなして、全ての葉ノードから辿ることを考えます。
葉ノードが変数ノードの場合のメッセージは、以下で与えられます。
式 のイメージは、以下の図4です。
図4
葉ノードが因子ノードの場合のメッセージは、以下で与えられます。
式 のイメージは、以下の図5です。
図5
後は、式 を用いれば、再帰的にメッセージを計算できるので、周辺分布 が計算できます。
全てのノードに対して、周辺分布を計算する
グラフの各変数ノード上の周辺分布を、すべてのノードに対して計算したいとします。
これは単に、上のアルゴリズムをノードごとに実行し直せば実現できますが、効率が悪いので、次のようにします。
まず始めに,任意の(変数あるいは因子)ノードを選んでそれを根ノードとします。
そして、先の場合と同様に、すべての葉ノードから根ノードに向けてメッセージを伝播させます。
この時点で根ノードはすべての隣接ノードからメッセージを受け取ったことになるので、
すべての隣接ノードにメッセージを送ることができます。
根ノードからその隣接ノードにメッセージが送られると、
今度は根ノードの隣接ノードが(それら自身の)すべての隣接ノードからメッセージを受け取ったことになり、
根ノードから遠ざかる方向のすべてのリンクに沿ってメッセージを送ることができます。
このようにメッセージパッシングすると、計算せねばならないメッセージの数はグラフのリンク数の 倍であり、
周辺分布を つだけ計算する場合の 倍で済みます。
このメッセージ‘パッシングの手続きがうまく機能する証明については、PRML演習問題 8.20(基本) wwwをご覧ください。
つの因子に関連する変数集合全体上の周辺分布
つの因子に関連する変数集合全体上の周辺分布 を計算したいとします。
( だと思います。)
上と同様の議論を行えば、ある因子に関連する変数上の周辺分布が、
その因子ノードに到達するすべてのメッセージと、そのノードに対応する
(局所的な)因子との積で与えられることを、示すことができます。
式 の証明については、PRML演習問題 8.21(標準) wwwをご覧ください。
具体例
PRML演習問題 8.25(標準) に積和アルゴリズムの具体例を用いた問題があります。