因子グラフ

因子グラフは、関数の因数分解を表す二部グラフです。確率論とその応用において、因子グラフは確率分布関数の因数分解を表すために使用され、積和アルゴリズムによる周辺分布の計算など、効率的な計算を可能にします。因子グラフと積和アルゴリズムの重要な成功例の 1 つは、LDPCやターボ コードなどの容量に近づく誤り訂正コードのデコードです。

因子グラフは制約グラフを一般化します。値が 0 または 1 である因子は制約と呼ばれます。制約グラフは、すべての因子が制約である因子グラフです。因子グラフの最大積アルゴリズムは、制約処理の弧一貫性アルゴリズムの一般化として考えることができます。

因子グラフは関数の因数分解を表す2部グラフである。関数の因数分解が与えられると、 ${\displaystyle g(X_{1},X_{2},\dots,X_{n})}$

${\displaystyle g(X_{1},X_{2},\dots ,X_{n})=\prod _{j=1}^{m}f_{j}(S_{j}),}$

ここで、対応する因子グラフは、変数頂点 、因子頂点、および辺で構成されます。 辺は、次のように因数分解に依存します。の場合、因子頂点と変数頂点の間には無向辺が存在します。 関数は暗黙的に実数値であると 想定されます。${\displaystyle S_{j}\subseteq \{X_{1},X_{2},\dots ,X_{n}\}}$${\displaystyle G=(X,F,E)}$${\displaystyle X=\{X_{1},X_{2},\dots ,X_{n}\}}$ ${\displaystyle F=\{f_{1},f_{2},\dots ,f_{m}\}}$${\displaystyle E}$${\displaystyle f_{j}}$${\displaystyle X_{k}}$${\displaystyle X_{k}\in S_{j}}$${\displaystyle g(X_{1},X_{2},\dots ,X_{n})\in \mathbb {R} }$

因子グラフをメッセージ パッシング アルゴリズムと組み合わせると、周辺分布などの関数の特定の特性を効率的に計算できます。 ${\displaystyle g(X_{1},X_{2},\dots ,X_{n})}$

次のように因数分解する関数を考えます。

${\displaystyle g(X_{1},X_{2},X_{3})=f_{1}(X_{1})f_{2}(X_{1},X_{2})f_{3}(X_{1},X_{2})f_{4}(X_{2},X_{3})}$、

対応する因子グラフが右側に示されています。因子グラフにサイクルがあることに注目してください。単一の因子にマージすると、結果の因子グラフはツリーになります。これは重要な区別です。メッセージ パッシング アルゴリズムは通常、ツリーに対しては正確ですが、サイクルのあるグラフに対しては近似値にしかならないためです。 ${\displaystyle f_{2}(X_{1},X_{2})f_{3}(X_{1},X_{2})}$

因子グラフ上の一般的なメッセージパッシングアルゴリズムは、関数の個々の変数のすべての周辺値を効率的に計算する和積アルゴリズムです。特に、変数の周辺値は次のように定義されます。 ${\displaystyle X_{k}}$

${\displaystyle g_{k}(X_{k})=\sum _{X_{\bar {k}}}g(X_{1},X_{2},\dots ,X_{n})}$

ここで、 という表記は、を除くすべての変数に対して合計が実行されることを意味します。 和積アルゴリズムのメッセージは、概念的には頂点で計算され、辺に沿って渡されます。 変数頂点からのメッセージまたは変数頂点へのメッセージは、常にその特定の変数の関数です。 たとえば、変数がバイナリの場合、対応する頂点に付随する辺上のメッセージは、長さ 2 のベクトルとして表すことができます。最初のエントリは 0 で評価されたメッセージ、2 番目のエントリは 1 で評価されたメッセージです。 変数が実数体 に属する場合、メッセージは任意の関数になる可能性があり、その表現には特別な注意が必要です。 ${\displaystyle X_{\bar {k}}}$ ${\displaystyle X_{k}}$

実際には、和積アルゴリズムは統計的推論に使用されます。ここで、 は結合分布または結合尤度関数であり、因数分解は変数間の 条件付き独立性に依存します。${\displaystyle g(X_{1},X_{2},\dots ,X_{n})}$

ハマーズリー・クリフォードの定理は、ベイジアンネットワークやマルコフネットワークなどの他の確率モデルが因子グラフとして表現できることを示しています。後者の表現は、信念伝播を使用してそのようなネットワーク上で推論を実行するときに頻繁に使用されます。一方、ベイジアンネットワークはモデルの因果関係を直接表現できるため、生成モデルに適しています。

• 信念の伝播
• ベイズ推論
• ベイジアンプログラミング
• 条件付き確率
• マルコフネットワーク
• ベイジアンネットワーク
• ハマーズリー・クリフォード定理

• Loeliger, Hans-Andrea (2004 年 1 月)、「ファクター グラフ入門」(PDF)、IEEE Signal Processing Magazine、21 (1): 28–41、Bibcode :2004ISPM...21...28L、doi :10.1109/MSP.2004.1267047、S2CID  7722934
• dimple は、MATLAB で因子グラフを構築および解決するためのオープンソース ツールであり、Wayback Machineで 2016-01-06 にアーカイブされています。
• Loeliger, Hans-Andrea (2008)、「ファクターグラフ入門」(PDF)

• クリフォード (1990)、「統計におけるマルコフ確率場」、グリメット、GR、ウェルシュ、DJA (編)、物理システムの無秩序、JM ハマーズリー記念論文集(追記)、オックスフォード大学出版局、pp. 19–32、ISBN 9780198532156
• Frey, Brendan J. (2003)、「因子グラフの拡張による有向および無向グラフィカル モデルの統合」、Jain, Nitin (編)、UAI'03、人工知能における不確実性に関する第 19 回会議議事録、Morgan Kaufmann、pp. 257–264、arXiv : 1212.2486、ISBN 0127056645
• Kschischang, Fr​​ank R. ; Frey, Brendan J.; Loeliger, Hans-Andrea (2001)、「Factor Graphs and the Sum-Product Algorithm」、IEEE Transactions on Information Theory、47 (2): 498–519、CiteSeerX  10.1.1.54.1570、doi :10.1109/18.910572。
• ウィメルシュ、ヘンク（2007）、反復受信機設計、ケンブリッジ大学出版局、ISBN 978-0-521-87315-4