信念の伝播

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

このアルゴリズムは1982年にJudea Pearlによって初めて提案され、 ^[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}$${\displaystyle x_{i}}$

この式を使用して周辺分布を計算すると、変数の数が増えるにつれて計算量が大幅に増えます。たとえば、100 個のバイナリ変数 が 与えられている場合、と上記の式を使用して1 つの周辺分布を計算するには、の可能な値をすべて合計する必要があります。確率質量関数が便利な方法で因数分解されることがわかっている場合は、信念伝播によって周辺分布をより効率的に計算できます。 ${\displaystyle X_{1},\ldots ,X_{100}}$${\displaystyle X_{i}}$${\displaystyle p}$${\displaystyle 2^{99}\approx 6.34\times 10^{29}}$${\displaystyle \mathbf {x} '}$${\displaystyle p}$

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

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

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

このアルゴリズムは、ノード間のエッジに沿ってメッセージと呼ばれる実数値関数を渡すことによって機能します。より正確には、が変数ノードで、が因子グラフでに接続された因子ノードである場合、から へのメッセージとからへのメッセージは実数値関数 であり、その定義域は に関連付けられたランダム変数が取ることのできる値の集合 (と表記) です。これらのメッセージには、1 つの変数が別の変数に及ぼす「影響」が含まれます。メッセージは、メッセージを受信するノードが変数ノードであるか因子ノードであるかに応じて、異なる方法で計算されます。同じ表記のままにすると、 ${\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 {Dom} (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 {Dom} (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}}$

前の式で示されているように、完全な周辺化は、完全な結合分布に現れるものよりも単純な項の積の合計に縮小されます。これが、信念伝播がsum-product メッセージ パッシングまたはsum-product アルゴリズムと呼ばれることがある理由です。

通常の実行では、各メッセージは隣接するメッセージの前の値から反復的に更新されます。メッセージの更新には、さまざまなスケジューリングを使用できます。グラフィカル モデルがツリーの場合、最適なスケジューリングは、各メッセージを正確に 1 回計算した後に収束します (次のサブセクションを参照)。因子グラフにサイクルがある場合、このような最適なスケジューリングは存在せず、通常は各反復ですべてのメッセージを同時に更新することになります。

収束すると（収束が発生した場合）、各ノードの推定周辺分布は、隣接する要因からのすべてのメッセージの積に比例します（正規化定数は欠落しています）。

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

同様に、1 つの因子に属する変数セットの推定結合周辺分布は、因子と変数からのメッセージの積に比例します。

${\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 番目のステップでは、メッセージを返送します。ルートから始めて、メッセージを逆方向に渡します。すべてのリーフがメッセージを受信した時点で、アルゴリズムが完了します。

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

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

周辺化には、変分法やモンテカルロ法など、他の近似法も存在します。

一般的なグラフにおける正確な周辺化の 1 つの方法は、ジャンクション ツリー アルゴリズムと呼ばれ、ツリーであることが保証された修正されたグラフ上での単純な信念伝播です。基本的な前提は、サイクルを単一のノードにクラスタ化して排除することです。

同様のアルゴリズムは一般にViterbi アルゴリズムと呼ばれますが、最大積アルゴリズムまたは最小和アルゴリズムの特殊なケースとしても知られており、最大化、または最も可能性の高い説明の関連する問題を解決します。限界を解決しようとする代わりに、ここでの目標は、グローバル関数を最大化する値 (つまり、確率設定で最も可能性の高い値) を見つけることであり、引数 max を使用して定義できます。 ${\displaystyle \mathbf {x} }$

${\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]

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

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

クラスター変分法と調査伝播アルゴリズムは、信念伝播に対する 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つの十分な収束条件が知られている。最初の条件は、情報行列Aが対角優勢である場合に2000年にWeissらによって定式化された。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アルゴリズムのこれまでの説明は、コードワードベースのデコードと呼ばれ、受信したコードワード が与えられた場合に、近似的な周辺確率 を計算します。同等の形式として、^[21]があり、 を計算します。ここで、 は受信したコードワードのシンドローム、 はデコードされたエラーです。デコードされた入力ベクトルは です。このバリエーションは、質量関数 の解釈のみを変更します。明示的には、メッセージは次のようになります。 ${\displaystyle P(x|X)}$${\displaystyle X}$${\displaystyle P(e|s)}$${\displaystyle s}$${\displaystyle X}$${\displaystyle e}$${\displaystyle x=X+e}$${\displaystyle f_{a}(X_{a})}$

${\displaystyle \forall x_{v}\in 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 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^{*}}).}$

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

バイナリの場合、これらのメッセージは単純化され、複雑度が指数関数的に減少する^{[22] [23]}${\displaystyle x_{i}\in \{0,1\}}$${\displaystyle 2^{|\{v\}|+|N(v)|}}$

対数尤度比、を定義すると、 ${\displaystyle l_{v}=\log {\frac {u_{v\to a}(x_{v}=0)}{u_{v\to a}(x_{v}=1)}}}$${\displaystyle L_{a}=\log {\frac {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(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). ガウス確率伝播リソース ページ — 最近の出版物と Matlab ソース コードを含む Web ページ。
• ビショップ、クリストファー M. (2006)。「第 8 章: グラフィカル モデル」(PDF)。パターン認識と機械学習。Springer。pp. 359–418。ISBN 978-0-387-31073-2. 2023年12月2日閲覧。
• Coughlan, James. (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 号 (登録が必要)
• Wymeersch, Henk (2007)。反復受信機設計。ケンブリッジ大学出版局。ISBN 978-0-521-87315-4。
• Yedidia, JS; Freeman, WT; Weiss, Y. (2003 年 1 月)。「ビリーフ プロパゲーションとその一般化を理解する」。Lakemeyer, Gerhard、Nebel, Bernhard (編)。新世紀における人工知能の探究。Morgan Kaufmann。239 ～ 269 ページ。ISBN 978-1-55860-811-5. 2009年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.