信念の伝播

信念伝播（和積メッセージパッシングとも呼ばれる）は、ベイジアンネットワークやマルコフ確率場などのグラフィカルモデルで推論を実行するためのメッセージパッシングアルゴリズムです。観測されたノード（または変数）を条件として、観測されていない各ノード（または変数）の周辺分布を計算します。信念伝播は人工知能や情報理論でよく使用され、低密度パリティチェックコード、ターボコード、自由エネルギー近似、充足可能性など、数多くのアプリケーションで実証的な成功を収めています。^{[ 1 ]}

このアルゴリズムは、1982年にジュデア・パールによって初めて提案され^{[ 2 ]} 、木構造に対する厳密な推論アルゴリズムとして定式化され、後に多木構造に拡張されました^{[ 3 ]}。このアルゴリズムは一般的なグラフに対しては厳密ではありませんが、有用な近似アルゴリズムであることが示されています^{[ 4 ] 。}

有限個の離散確率変数が与えられた場合${\displaystyle X_{1},\ldots ,X_{n}}$結合確率質量関数${\displaystyle p}$一般的なタスクは、周辺分布を計算することです。${\displaystyle X_{i}}$単一の周辺${\displaystyle X_{i}}$と定義される

${\displaystyle p_{X_{i}}(x_{i})=\sum _{\mathbf {x} ':x'_{i}=x_{i}}p(\mathbf {x} ')}$

どこ${\displaystyle \mathbf {x} '=(x'_{1},\ldots ,x'_{n})}$は、可能な値のベクトルです。${\displaystyle X_{i}}$、そして表記法${\displaystyle \mathbf {x} ':x'_{i}=x_{i}}$合計はそれらの範囲で取られることを意味します${\displaystyle \mathbf {x} '}$だれの${\displaystyle i}$th座標は${\displaystyle x_{i}}$。

この式を用いて周辺分布を計算すると、変数の数が増えるにつれて計算コストが急激に高くなります。例えば、100個の二値変数がある場合${\displaystyle X_{1},\ldots ,X_{100}}$単一の周辺値を計算する${\displaystyle X_{i}}$使用${\displaystyle p}$そして上記の式では、合計することが含まれます。$2^{99}\approx 6.34\times 10^{29}}$可能な値${\displaystyle \mathbf {x} '}$確率質量関数が既知である場合${\displaystyle p}$要因を便利な方法で考慮することで、信念伝播により周辺値をはるかに効率的に計算できるようになります。

信念伝播アルゴリズムの変種は、いくつかのタイプのグラフィカルモデル（特にベイジアンネットワークとマルコフ確率場^{[ 5 ]} ）に対して存在します。ここでは、ファクターグラフ上で動作する変種について説明します。ファクターグラフは、変数に対応するノードを含む二部グラフです。${\displaystyle V}$および要因${\displaystyle F}$変数と、それらが現れる因子との間にエッジが存在する。結合質量関数は次のように記述できる。

${\displaystyle p(\mathbf {x} )=\prod _{a\in F}f_{a}(\mathbf {x} _{a})}$

どこ$\displaystyle \mathbf {x} _{a}}$は、因子ノードに隣接する変数ノードのベクトルです。${\displaystyle a}$任意のベイジアンネットワークまたはマルコフ確率場は、各ノードとその親ノード、または各ノードとその近傍ノードをそれぞれ因子として用いることで、因子グラフとして表現できます。^{[ 6 ]}

このアルゴリズムは、ノード間のエッジに沿ってメッセージと呼ばれる実数値関数を渡すことによって機能します。より正確には、${\displaystyle v}$は変数ノードであり、${\displaystyle a}$は、${\displaystyle v}$因子グラフでは、次にメッセージが${\displaystyle \mu _{v\to a}}$から${\displaystyle v}$に${\displaystyle a}$そしてメッセージ${\displaystyle \mu _{a\to v}}$から${\displaystyle a}$に${\displaystyle v}$実数値関数${\displaystyle \mu _{v\to a},\mu _{a\to v}:\operatorname {Dom} (v)\to \mathbb {R} }$の定義域は、 に関連付けられた確率変数が取り得る値の集合である。${\displaystyle v}$、と表記される${\displaystyle \operatorname {ドム} (v)}$これらのメッセージには、ある変数が別の変数に及ぼす「影響」が含まれています。メッセージは、メッセージを受信するノードが変数ノードか因子ノードかによって計算方法が異なります。同じ表記法を使用します。

• メッセージ${\displaystyle \mu _{v\to a}:\operatorname {Dom} (v)\to \mathbb {R} }$可変ノードから${\displaystyle v}$ファクターノードへ${\displaystyle a}$定義される$${\displaystyle \mu _{v\to a}(x_{v})=\prod _{a^{*}\in N(v)\setminus \{a\}}\mu _{a^{*}\to v}(x_{v})}$$のために${\displaystyle x_{v}\in \operatorname {Dom} (v)}$、 どこ${\displaystyle N(v)}$は、${\displaystyle v}$。 もし${\displaystyle N(v)\setminus \{a\}}$空の場合は${\displaystyle \mu _{v\to a}(x_{v})}$一様分布に設定されます${\displaystyle \operatorname {ドム} (v)}$。

• メッセージ${\displaystyle \mu _{a\to v}:\operatorname {Dom} (v)\to \mathbb {R} }$ファクターノードから${\displaystyle a}$可変ノードへ${\displaystyle v}$は、 と他のすべてのノードからのメッセージの積として定義され、 に関連付けられた変数を除くすべての変数について周辺化されます。${\displaystyle v}$、$${\displaystyle \mu _{a\to v}(x_{v})=\sum _{\mathbf {x} '_{a}:x'_{v}=x_{v}}\left(f_{a}(\mathbf {x} '_{a})\prod _{v^{*}\in N(a)\setminus \{v\}}\mu _{v^{*}\to a}(x'_{v^{*}})\right)}$$のために${\displaystyle x_{v}\in \operatorname {Dom} (v)}$、 どこ${\displaystyle N(a)}$は、隣接する（変数）ノードの集合です。${\displaystyle a}$。 もし${\displaystyle N(a)\setminus \{v\}}$空の場合、${\displaystyle \mu _{a\to v}(x_{v})=f_{a}(x_{v})}$この場合${\displaystyle x_{v}=x_{a}}$。

前述の式で示されているように、完全な周辺化は、完全な同時分布に現れる項よりも単純な項の積の和に還元されます。これが、信念伝播が「積和メッセージ伝達」または「積和アルゴリズム」と呼ばれることがある理由です。

通常の実行では、各メッセージは隣接するメッセージの前の値に基づいて繰り返し更新されます。メッセージの更新には、さまざまなスケジューリング方法を使用できます。グラフィカルモデルがツリーの場合、各メッセージを一度だけ計算すると最適なスケジューリングが収束します（次のサブセクションを参照）。ファクターグラフにサイクルがある場合、このような最適なスケジューリングは存在しないため、各反復で全てのメッセージを同時に更新するのが一般的な方法です。

収束した場合（収束が起こった場合）、各ノードの推定周辺分布は、隣接する因子からのすべてのメッセージの積に比例します（正規化定数は省略）。

${\displaystyle p_{X_{v}}(x_{v})\propto \prod _{a\in N(v)}\mu _{a\to v}(x_{v}).}$

同様に、ある因子に属する変数群の推定同時周辺分布は、その因子と変数からのメッセージの積に比例する。

${\displaystyle p_{X_{a}}(\mathbf {x} _{a})\propto f_{a}(\mathbf {x} _{a})\prod _{v\in N(a)}\mu _{v\to a}(x_{v}).}$

因子グラフが非巡回グラフ（つまり、木構造または森構造）である場合、これらの推定周辺分布は有限回の反復で真の周辺分布に収束します。これは数学的帰納法によって示すことができます。

因子グラフが木構造である場合、信念伝播アルゴリズムは正確な周辺値を計算します。さらに、メッセージ更新を適切にスケジューリングすることで、木構造全体を2回通過した後に処理を終了します。この最適なスケジューリングは次のように説明できます。

開始する前に、グラフは1つのノードをルートとして指定することによって方向付けられます。ルート以外のノードで、他の1つのノードにのみ接続されているノードはリーフと呼ばれます。

最初のステップでは、メッセージは内側に向かって渡されます。葉ノードから始まり、各ノードは（一意の）エッジに沿ってルートノードに向かってメッセージを転送します。ツリー構造により、メッセージを転送する前に、他のすべての隣接ノードからメッセージを取得できることが保証されます。これは、ルートノードがすべての隣接ノードからメッセージを取得するまで続きます。

第2段階では、メッセージを逆方向に渡していきます。ルートノードから始めて、メッセージを逆方向に渡していくのです。すべてのリーフノードがメッセージを受信すると、アルゴリズムは完了します。

信念伝播アルゴリズムは元々非巡回グラフモデル向けに設計されましたが、一般的なグラフにも使用できます。グラフには通常サイクル、つまりループが含まれるため、このアルゴリズムはループ信念伝播と呼ばれることもあります。グラフには葉が含まれていない可能性があるため、メッセージ更新の初期化とスケジューリングは（前述の非巡回グラフのスケジュールと比較して）若干調整する必要があります。代わりに、すべての変数メッセージを 1 に初期化し、上記と同じメッセージ定義を使用して、すべてのメッセージを各反復で更新します（ただし、既知の葉または木構造のサブグラフからのメッセージは、十分な反復後には更新する必要がなくなる場合があります）。木構造の場合、この修正された手順のメッセージ定義は、木の直径に等しい反復回数内で、上記のメッセージ定義のセットに収束することが容易に示せます。

ループ状の信念伝播が収束する正確な条件はまだ十分に理解されていません。単一のループを含むグラフではほとんどの場合収束することが知られていますが、得られた確率は間違っている可能性があります。^{[ 7 ]}ループ状の信念伝播が単一の固定点に収束するための十分条件（ただし必要条件ではない）がいくつか存在します。^{[ 8 ]}収束しない、または繰り返し反復中に複数の状態間で振動するグラフが存在します。EXITチャートなどの手法は、信念伝播の進行状況を近似的に視覚化し、収束を近似的にテストすることができます。

周辺化のための近似手法には、変分法やモンテカルロ法など、他にもいくつか存在する。

一般グラフにおける厳密な周辺化手法の一つに、ジャンクションツリーアルゴリズムと呼ばれるものがある。これは、ツリー構造となるように修正されたグラフ上での信念伝播法に他ならない。基本的な考え方は、サイクルを単一のノードに集約することでサイクルを除去することである。

同様のアルゴリズムは一般的にビタビアルゴリズムと呼ばれていますが、最大積アルゴリズムまたは最小和アルゴリズムの特殊なケースとしても知られており、関連する最大化問題、または最も可能性の高い説明を解決します。周辺分布を解こうとするのではなく、ここでは値を求めることが目標です。${\displaystyle \mathbf {x} }$これはグローバル関数（つまり確率的設定における最も可能性の高い値）を最大化するもので、引数 maxを使用して定義できます。

${\displaystyle \operatorname {*} {\arg \max }_{\mathbf {x} }g(\mathbf {x} ).}$

この問題を解決するアルゴリズムは、定義における和を最大値に置き換えただけで、信念伝播とほぼ同じである。^{[ 9 ]}

周辺化や最大化といった推論問題は、グラフィカルモデルでは正確に解くのも近似的に解くのも（少なくとも相対誤差に関しては） NP困難であることに注意すべきである。より正確には、上述の周辺化問題は#P完全であり、最大化問題はNP完全である。

信念伝播のメモリ使用量は、アイランドアルゴリズムを使用することで削減できます（ただし、時間計算量はわずかに増加します）。

和積アルゴリズムは、熱力学における自由エネルギーの計算に関連しています。Zを分配関数とします。確率分布

${\displaystyle P(\mathbf {X} )={\frac {1}{Z}}\prod _{f_{j}}f_{j}(x_{j})}$

（因子グラフ表現によれば）は、システム内に存在する内部エネルギーの尺度として見なすことができ、次のように計算される。

${\displaystyle E(\mathbf {X} )=-\log \prod _{f_{j}}f_{j}(x_{j}).}$

システムの自由エネルギーは次のようになる。

${\displaystyle F=U-H=\sum _{\mathbf {X} }P(\mathbf {X} )E(\mathbf {X} )+\sum _{\mathbf {X} }P(\mathbf {X} )\log P(\mathbf {X} ).}$

すると、和積アルゴリズムの収束点は、そのようなシステムにおける自由エネルギーが最小となる点を表すことが示される。同様に、サイクルを持つグラフにおける反復信念伝播アルゴリズムの固定点は、自由エネルギー近似の定常点であることが示される。^{[ 10 ]}

信念伝播アルゴリズムは通常、変数ノードとその隣接する因子ノード間のメッセージ、およびその逆を含む因子グラフ上のメッセージ更新方程式として表現されます。グラフ内の領域間のメッセージを考慮することは、信念伝播アルゴリズムを一般化する一つの方法です。 ^{[ 10 ]}グラフ内でメッセージを交換できる領域の集合を定義する方法はいくつかあります。1つの方法は、物理学の文献で菊池によって導入されたアイデアを使用しており、^{[ 11 ] [ 12 ] [ 13 ]}菊池のクラスタ変動法として知られています。^{[ 14 ]}

信念伝播アルゴリズムの性能向上は、フィールド（メッセージ）の分布におけるレプリカの対称性を破ることによっても達成できます。この一般化により、サーベイ伝播（SP）と呼ばれる新しいタイプのアルゴリズムが生まれ、充足可能性^{[ 1 ]}やグラフ彩色などのNP完全問題において非常に効率的であることが証明されています。

クラスタ変分法とサーベイ伝播アルゴリズムは、信念伝播に対する2つの異なる改良法である。これら2つの一般化を統合したアルゴリズムには、一般化サーベイ伝播（GSP）という名称が付けられるのを待っている。

ガウス信念伝播は、基となる分布がガウス分布である場合の信念伝播アルゴリズムの変種です。この特殊なモデルを分析した最初の研究は、ワイスとフリーマンの先駆的な研究でした。^{[ 15 ]}

GaBPアルゴリズムは、以下の周辺化問題を解決します。

${\displaystyle P(x_{i})={\frac {1}{Z}}\int _{j\neq i}\exp(-{\tfrac {1}{2}}x^{T}Ax+b^{T}x)\,dx_{j}}$

ここで、Z は正規化定数、Aは対称正定値行列（逆共分散行列、別名精度行列）、bはシフトベクトルです。

同様に、ガウスモデルを用いると、周辺化問題の解はMAP割り当て問題と等価であることが示される。

${\displaystyle {\underset {x}{\operatorname {argmax} }}\ P(x)={\frac {1}{Z}}\exp(-{\tfrac {1}{2}}x^{T}Ax+b^{T}x).}$

この問題は、次の二次形式の最小化問題と同等である。

${\displaystyle {\underset {x}{\operatorname {min} }}\ 1/2x^{T}Ax-b^{T}x.}$

これは線形方程式系にも相当する。

${\displaystyle Ax=b.}$

GaBPアルゴリズムの収束は（一般的なBPの場合と比較して）解析が容易であり、既知の十分な収束条件が2つあります。1つ目は、情報行列Aが対角優位である場合に、Weissらが2000年に定式化しました。2^つ目の収束条件は、行列のスペクトル半径が

${\displaystyle \rho (I-|D^{-1/2}AD^{-1/2}|)<1\,}$

ここでD = diag( A ) である。その後、Su と Wu は、同期 GaBP と減衰 GaBP の必要十分収束条件、および非同期 GaBP の別の十分収束条件を確立した。各ケースについて、収束条件には、1) 集合 (A によって決定される) が空でない、2) ある行列のスペクトル半径が 1 より小さい、3) 特異点の問題 (BP メッセージを信念に変換するとき) が発生しない、の検証が含まれる。^{[ 17 ]}

GaBPアルゴリズムは線形代数領域に関連付けられており、^{[ 18 ]} GaBPアルゴリズムは、情報行列Aとシフトベクトルbで表す線形方程式系Ax = bを解くための反復アルゴリズムとして見なすことができることが示されています。経験的に、GaBPアルゴリズムは、ヤコビ法、ガウス・ザイデル法、逐次過緩和法などの古典的な反復法よりも速く収束することが示されています。 [ 19 ]さらに、 GaBPアルゴリズムは^、前処理付き共役勾配法の数値的問題の影響を受けないことが示されています。^{[ 20 ]}

前述のBPアルゴリズムの説明は、近似周辺確率を計算するコードワードベースの復号法と呼ばれています。${\displaystyle P(x|X)}$受信コードワードが与えられた場合${\displaystyle X}$^{同等の形式[ 21 ]}があり、計算します。${\displaystyle P(e|s)}$、 どこ${\displaystyle s}$受信コードワードの症候群${\displaystyle X}$そして${\displaystyle e}$は復号されたエラーです。復号された入力ベクトルは${\displaystyle x=X+e}$この変化は質量関数の解釈を変えるだけです。${\displaystyle f_{a}(X_{a})}$具体的には、メッセージは

${\displaystyle \forall x_{v}\in \operatorname {Dom} (v),\;\mu _{v\to a}(x_{v})=P(X_{v})\prod _{a^{*}\in N(v)\setminus \{a\}}\mu _{a^{*}\to v}(x_{v}).}$

どこ${\displaystyle P(X_{v})}$変数に対する事前エラー確率は${\displaystyle v}$、

${\displaystyle \forall x_{v}\in \operatorname {Dom} (v),\;\mu _{a\to v}(x_{v})=\sum _{\mathbf {x} '_{a}:x'_{v}=x_{v}}\delta ({\text{syndrome}}({\mathbf {x} }'_{v})={\mathbf {s} })\prod _{v^{*}\in N(a)\setminus \{v\}}\mu _{v^{*}\to a}(x'_{v^{*}}).}$

このシンドロームベースのデコーダは、受信ビットに関する情報を必要としないため、測定シンドロームのみを情報とする量子符号にも適用できる。

バイナリの場合、${\displaystyle x_{i}\in \{0,1\}}$それらのメッセージは、指数関数的な減少を引き起こすように簡略化できます。${\displaystyle 2^{|\{v\}|+|N(v)|}}$複雑さにおいて。^{[ 22 ] [ 23 ]}

対数尤度比を定義する${\displaystyle l_{v}=\log {\tfrac {u_{v\to a}(x_{v}=0)}{u_{v\to a}(x_{v}=1)}}}$、${\displaystyle L_{a}=\log {\tfrac {u_{a\to v}(x_{v}=0)}{u_{a\to v}(x_{v}=1)}}}$、 それから

${\displaystyle v\to a:l_{v}=l_{v}^{(0)}+\sum _{a^{*}\in N(v)\setminus \{a\}}(L_{a^{*}})}$

${\displaystyle a\to v:L_{a}=(-1)^{s_{a}}2\tanh ^{-1}\prod _{v^{*}\in N(a)\setminus \{v\}}\tanh(l_{v^{*}}/2)}$

どこ${\displaystyle l_{v}^{(0)}=\log {\tfrac {P(x_{v}=0)}{P(x_{v}=1)}}={\text{const}}}$

事後対数尤度比は次のように推定できます。${\displaystyle l_{v}=l_{v}^{(0)}+\sum _{a\in N(v)}(L_{a})}$

• Bickson, Danny. (2009). Gaussian Belief Propagation Resource Page —最近の出版物とMatlabソースコードを含むウェブページ。
• ビショップ、クリストファー M. (2006). 「第 8 章: グラフィカル モデル」(PDF) .パターン認識と機械学習. Springer. pp. 359–418 . ISBN  978-0-387-31073-22023年12月2日に取得。
• コフラン、ジェームズ。（2009）。信念伝播入門チュートリアル。
• Löliger, Hans-Andrea (2004). "因子グラフ入門". IEEE Signal Processing Magazine . 21 (1): 28–41 . Bibcode : 2004ISPM...21...28L . doi : 10.1109/MSP.2004.1267047 . S2CID 7722934 . 
• マッケンジー、ダナ（2005）。「通信速度が終端速度に近づく」、ニュー・サイエンティスト、2005年7月9日、第2507号（登録が必要）
• ワイマーシュ、ヘンク（2007）。反復型受信器設計。ケンブリッジ大学出版局。ISBN 978-0-521-87315-4。
• Yedidia, JS; Freeman, WT; Weiss, Y. (2003年1月) 「信念伝播とその一般化の理解」 . Lakemeyer, Gerhard; Nebel, Bernhard (編)『新千年紀における人工知能の探求』 . Morgan Kaufmann. pp. 239–269 . ISBN  978-1-55860-811-52009年3月30日に取得。
• Yedidia, JS; Freeman, WT; Weiss, Y. (2005年7月). 「自由エネルギー近似と一般化信念伝播アルゴリズムの構築」 . IEEE Transactions on Information Theory . 51 (7): 2282–2312 . CiteSeerX 10.1.1.3.5650 . doi : 10.1109/TIT.2005.850085 . S2CID 52835993 .