信念伝搬法は、グラフ構造を持った確率分布に対する周辺分布を近似的に計算するためのアルゴリズムです。グラフ構造が木である場合には正確な周辺分布を、ループを含むグラフに対しては近似的な周辺分布の計算が可能です。
信念伝搬法を用いて周辺分布を計算する目的は色々ありますが、その中でも重要な目的は、最大事後周辺確率 (maximum posterior marginal, MPM) 推定と呼ばれる推定問題を近似的に解くことです。この推定問題は次のようなものです。ある変数 $\bm{x}$ があって、そこからデータ $\bm{y}$ が $\bm y \sim p(\bm{y} \mid \bm{x})$ と生成されるようなモデルを考えます。観測されたデータ $\bm{y}$ に対して、変数 $\bm{x}$ をベイズ推定したい状況を考えます。変数に $p(\bm{x})$ という事前分布を仮定すると、変数 $\bm{x}$ の事後分布はベイズの定理を用いて次式で得られます。
$$
p(\bm{x} \mid \bm{y}) = \frac{1}{Z(\bm{y})} p(\bm{y} \mid \bm{x}) p(\bm{x}).
$$
MPM推定は、このような事後分布の周辺分布の最頻値を選ぶ方法です。すなわち、変数 $\bm{x}$ のうち、ある成分 $x_i$ については、$x_i$ 以外の変数をすべて積分して周辺化した周辺事後確率を、$x_i$ について最大化するという操作です。
$$
x_i^\text{MPM} = \argmax_{x_i} \int d\bm{x}_{\setminus i} p(\bm{x} \mid \bm{y}).
$$
MPM推定とは別の推定方法もあります。1つは、最大事後確率 (maximum a posteriori, MAP) 推定と呼ばれるものです。これは事後分布の最頻値を選ぶ方法です。MPM推定とは異なり、変数 $\bm{x}$ の同時確率を最大化する必要があります。
$$
\bm{x}^\text{MAP} = \argmax_{\bm{x}} p(\bm{x} \mid \bm{y}).
$$
MPM推定とMAP推定のどちらのほうが良いかは問題によりますし、問題によっては、もっとよい推定方法もあるはずです。
問題設定とアルゴリズム
事後分布が次のような因子と呼ばれる関数の積で表されることを前提とします。
$$
p(\bm{x} \mid \bm{y}) \propto \prod_{a=1}^{M} f_a(\bm{x}_{\partial a}).
$$
$\bm{x}_{\partial a}$ は、因子 $f_a$ に依存する変数の集合です。例えば、$f_2$ が $x_1$ と $x_2$ に依存する場合には、$\bm{x}_{\partial 2} = \{x_1, x_2\}$ となります。以降 $\bm{x}_{\partial a}$ は、ベクトルとして表すこともあれば、集合として表すこともあるとします。また、以下では変数が連続変数である場合を考えます。離散変数である場合、積分は対応する変数についての総和に置き換えます。例えば $x_i \in \{-1,+1\}$ である場合には、$\int dx_i$ を $\sum_{x_i \in \{-1,+1\}}$ に置き換えます。
信念伝搬法では、以下のようなアルゴリズムを用いて、各変数 $x_i$ の周辺事後分布を近似計算します。
アルゴリズム (信念伝搬法):
-
各辺 $(i,a)$ について、メッセージ $m_{i \to a}^{[0]}(x_i)$ と $m_{a \to i}^{[0]}(x_i)$ を初期化する。
-
メッセージの変化が十分に小さくなるまで繰り返す:
-
変数から因子へのメッセージを更新する。
$$
m_{i \to a}^{[t+1]}(x_i)
\propto \prod_{b \in \partial i \setminus \{a\}}m_{b \to i}^{[t]}(x_i).
$$
-
因子から変数へのメッセージを更新する。
$$
m_{a \to i}^{[t+1]}(x_i)
\propto \int d\bm{x}_{\partial a \setminus \{i\}} \;
f_a(\bm{x}_{\partial a})
\prod_{j \in \partial a \setminus \{i\}}m_{j \to a}^{[t]}(x_j).
$$
-
収束したメッセージから、周辺分布を近似計算する。
$$
p(x_i \mid \bm{y})
\approx b_i(x_i)
= \frac{1}{Z_i}\prod_{a \in \partial i}m_{a \to i}^{[t]}(x_i).
$$
$x_i$ にのみ依存する因子 $\psi_i(x_i)$ を分けて
$$
p(\bm{x} \mid \bm{y})
\propto \prod_i \psi_i(x_i) \prod_{a=1}^{M} f_a(\bm{x}_{\partial a})
$$
と表せる場合は、次のアルゴリズムを使えます。
アルゴリズム (単項因子を分離した信念伝搬法):
-
各辺 $(i,a)$ について、メッセージ $m_{i \to a}^{[0]}(x_i)$ と $m_{a \to i}^{[0]}(x_i)$ を初期化する。
-
メッセージの変化が十分に小さくなるまで繰り返す:
-
変数から因子へのメッセージを更新する。
$$
m_{i \to a}^{[t+1]}(x_i)
\propto \psi_i(x_i)
\prod_{b \in \partial i \setminus \{a\}}m_{b \to i}^{[t]}(x_i).
$$
-
因子から変数へのメッセージを更新する。
$$
m_{a \to i}^{[t+1]}(x_i)
\propto \int d\bm{x}_{\partial a \setminus \{i\}} \;
f_a(\bm{x}_{\partial a})
\prod_{j \in \partial a \setminus \{i\}}m_{j \to a}^{[t]}(x_j).
$$
-
収束したメッセージから、周辺分布を近似計算する。
$$
p(x_i \mid \bm{y})
\approx b_i(x_i)
= \frac{1}{Z_i} \psi_i(x_i)
\prod_{a \in \partial i}m_{a \to i}^{[t]}(x_i).
$$
導出
因子グラフの例
$\displaystyle p(\bm{x} \mid \bm{y}) \propto \prod_{a=1}^{M} f_a(\bm{x}_{\partial a})$ のような因子分解を持つ確率分布は、因子グラフと呼ばれるグラフ構造で表すことができます。因子グラフは、変数の集合 $\{x_i\}$ と因子の集合 $\{f_a\}$ の2種類のノードから構成されます。変数ノード $x_i$ と因子ノード $f_a$ の間に辺が存在する場合には、$f_a$ が $x_i$ に依存していることを意味します。
本来の目標は、各変数 $x_i$ に関する周辺事後分布を近似計算することです。
$$
p(x_i \mid \bm{y}) = \int d\bm{x}_{\setminus i} p(\bm{x} \mid \bm{y}).
$$
ところが一般にこの計算は困難です。そこで、まずこの分布 $p(\bm{x} \mid \bm{y})$ を近似する別の分布 $q(\bm{x})$ を導入します。そして、この分布に関する各種の周辺分布を次式で定義しておきます。本メモでは、前者を因子周辺分布、後者を変数周辺分布と呼ぶことにします。
$$
\begin{aligned}
b_a(\bm{x}_{\partial a}) &= \int d\bm{x}_{\setminus \partial a} q(\bm{x}), \\
b_i(x_i) &= \int d\bm{x}_{\setminus i} q(\bm{x}).
\end{aligned}
$$
すると目標は、(1) $q(\bm{x})$ を $p(\bm{x} \mid \bm{y})$ に近づけ、(2) $b_i(x_i)$ を計算する、という2つのステップに分解することができます。
KLダイバージェンスの導入
まず導入した試行分布 $q$ を $p$ に近づけます。そのために、次式のKullback-Leibler (KL) ダイバージェンスを最小化することを目指します。
$$
\begin{aligned}
D_\text{KL}(q \parallel p)
&= \int d\bm{x} \; q(\bm{x}) \log \frac{q(\bm{x})}{p(\bm{x} \mid \bm{y})}.
\end{aligned}
$$
$p$ の因子分解と、$q$ の因子周辺分布の定義を代入すると、次のように書き換えることができます。
$$
\begin{aligned}
D_\text{KL}(q \parallel p)
&= U[q] - S[q] + \text{const},
\end{aligned}
$$
ただし
$$
\left\lbrace
\begin{aligned}
U[q] &= - \sum_a \int d\bm{x}_{\partial a} \; b_a(\bm{x}_{\partial a}) \log f_a(\bm{x}_{\partial a}), \\
S[q] &= - \int d\bm{x} \; q(\bm{x}) \log q(\bm{x}).
\end{aligned}
\right.
$$
Bethe近似
ここまでは、前述の定義のもとで厳密です。ところが一般のグラフにおいて $S[q]$ は依然として計算が困難です。そこで、試行分布 $q(\bm{x})$ の形に次の仮定を置きます。
近似: 試行分布 $q(\bm{x})$ が、因子周辺分布 $b_a(\bm{x}_{\partial a})$ と変数周辺分布 $b_i(x_i)$ を用いて、次の形で近似できると仮定します。
$$
q(\bm{x})
\approx
\frac{\displaystyle
\prod_{a} b_a(\bm{x}_{\partial a})
}{\displaystyle
\prod_i b_i(x_i)^{|\partial i| - 1}
}.
$$
因子周辺分布と変数周辺分布の間には、次の条件を課します。
$$
\begin{aligned}
b_i(x_i)
&= \int d\bm{x}_{\partial a \setminus \{i\}} b_a(\bm{x}_{\partial a})
\quad \forall a \in \partial i.
\end{aligned}
$$
ここで、$|\partial i|$ は変数ノード $i$ に接続する因子ノードの数です。
因子周辺分布と変数周辺分布の間に課される条件を、この記事では 局所整合性条件 (local consistency condition) と呼ぶことにします。この仮定のもと計算される $S[q]$ を $S_\text{B}[q]$ と書くことにすると、次のように計算されます。
$$
\begin{aligned}
S_\text{B}[q]
&= \sum_a S_a[b_a] - \sum_i (|\partial i|-1)S_i[b_i],
\end{aligned}
$$
ただし
$$
\begin{aligned}
S_a[b_a] &= - \int d\bm{x}_{\partial a} \; b_a(\bm{x}_{\partial a}) \log b_a(\bm{x}_{\partial a}), \\
S_i[b_i] &= - \int dx_i \; b_i(x_i) \log b_i(x_i).
\end{aligned}
$$
$S_\text{B}[q]$ はBetheエントロピーと呼ばれます。そして $S[q]$ をBetheエントロピー $S_\text{B}[q]$ で近似することをBethe近似といいます。このBethe近似を導入した結果として、KLダイバージェンスは次式で近似されます。
$$
\begin{aligned}
D_\text{KL}(q \parallel p)
&\approx - \sum_a \int d\bm{x}_{\partial a} \; b_a(\bm{x}_{\partial a}) \log f_a(\bm{x}_{\partial a}) \\
&\qquad {} + \sum_a \int d\bm{x}_{\partial a} \; b_a(\bm{x}_{\partial a}) \log b_a(\bm{x}_{\partial a}) \\
&\qquad {} - \sum_i (|\partial i| - 1) \int dx_i \; b_i(x_i) \log b_i(x_i) + \text{const}.
\end{aligned}
$$
変数 $x_2$ に関して注目している限りにおいては、因子 $f_1, f_2, f_3$ は、局所的には変数 $x_2$ を介してのみ結合していて、それ以外の変数を介した結合は無視できると仮定する。実際には $f_1, f_2$ は $x_1$ も介して結合しているので、この仮定は厳密ではなく、あくまで近似である。
以上の近似は、直感的には情報が局所的に木構造を持つと仮定していると考えることができます。各ノードから近い範囲では、情報が異なる枝に分かれて伝わり、その枝どうしが再び合流しない、というイメージです。
補足: $q$ を表す因子グラフが木である場合、前述の近似は厳密に成立します。以下、このことを見てみましょう。
$q$ が木構造を持つと仮定します。このとき、ある変数ノード $i$ を取り除くと、グラフは $i$ に接続する各因子ノード $a \in \partial i$ の方向ごとに、互いに分離した部分グラフへ分かれます。このうち、因子ノード $a$ の方にある部分グラフに含まれる変数全体を $\bm{x}^{a \to i}$ と書くことにします。
$$
\bm{x}^{a \to i} = \{ x_j \mid j \text{ is a variable node} \land j \in \text{the subtree containing } a \}.
$$
因子グラフが木ですから、異なる $a,a' \in \partial i$ に対応する部分グラフは、互いに $x_i$ のみを介して結合しています。したがって、$x_i$ を固定すると、これらの部分グラフからなる分布同士は、互いに条件付き独立となり、$\displaystyle q(\{ \bm{x}^{a \to i} \}_{a \in \partial i} \mid x_i) = \prod_{a \in \partial i} q(\bm{x}^{a \to i} \mid x_i)$ が成立します。そのため、同時分布 $q(\bm{x})$ は、次のように分解されます。
$$
q(\bm{x}) = b_i(x_i) \prod_{a \in \partial i} q(\bm{x}^{a \to i} \mid x_i).
$$
因子グラフが木である場合、変数ノード $i$ に接続する因子ノード $a \in \partial i$ の方向ごとに、互いに分離した部分木へ分かれる。
部分木もまた同様の性質を持つので、右辺は更に部分木の条件付き分布へと分解可能です。
$$
\begin{aligned}
q(\bm{x}^{a \to i} \mid x_i)
= b_a(\bm{x}_{\partial a} \mid x_i)
\prod_{j \in \partial a \setminus \{i\}}
\prod_{b \in \partial j \setminus \{a\}}
q(\bm{x}^{b \to j} \mid x_j).
\end{aligned}
$$
部分木 $q(\bm{x}^{a \to i} \mid x_i)$ もまた、変数ノード $j$ に接続する因子ノード $b \in \partial j \setminus \{a\}$ の方向ごとに、互いに分離した部分木へ分かれる。
これを最初の分解に代入し、$b_a(\bm{x}_{\partial a} \mid x_i) = \dfrac{b_a(\bm{x}_{\partial a})}{b_i(x_i)}$ であることを利用すれば、次式が得られます。
$$
\begin{aligned}
q(\bm{x})
&=
\frac{\displaystyle
\prod_{a \in \partial i} b_a(\bm{x}_{\partial a})
}{
b_i(x_i)^{|\partial i| - 1}
}
\times
\prod_{a \in \partial i}
\prod_{j \in \partial a \setminus \{i\}}
\prod_{b \in \partial j \setminus \{a\}}
q(\bm{x}^{b \to j} \mid x_j).
\end{aligned}
$$
各部分木 $q(\bm{x}^{b \to j} \mid x_j)$ についても、同じ分解が適用でき、さらにその後の部分木についても同様に分解が繰り返し適用されていきます。
$$
\begin{aligned}
q(\bm{x}) &=
\frac{\displaystyle
\prod_{a \in \partial i} b_a(\bm{x}_{\partial a})
}{
b_i(x_i)^{|\partial i| - 1}
}
\times
\prod_{a \in \partial i}
\prod_{j \in \partial a \setminus \{i\}}
\frac{\displaystyle
\prod_{b \in \partial j \setminus \{a\}}b_b(\bm{x}_{\partial b})
}{
b_j(x_j)^{|\partial j| - 1}
}
\times
\prod_{b \in \partial j \setminus \{a\}}
\prod_{k \in \partial b \setminus \{j\}}
\prod_{c \in \partial k \setminus \{b\}}
q(\bm{x}^{c \to k} \mid x_k) \\
&= \dots.
\end{aligned}
$$
この分解では同じノードに戻ることがないため、この操作は再帰的に葉まで進みます。その結果、すべての因子ノードから一つずつ $b_a(\boldsymbol{x}_{\partial a})$ が現れ、各変数ノード $i$ について $b_i(x_i)$ が $|\partial i|-1$ 回だけ分母に現れる形となり、最終的に次式に帰着します。
$$
\boxed{
\begin{aligned}
q(\bm{x})
=
\frac{\displaystyle
\prod_{a} b_a(\bm{x}_{\partial a})
}{\displaystyle
\prod_i b_i(x_i)^{|\partial i| - 1}
}.
\end{aligned}
}
$$
変分法
以上でKLダイバージェンスの式が書けたので、次に $b_a(\bm{x}_{\partial a})$ および $b_i(x_i)$ を変分的に最適化することを考えます。
$$
\begin{aligned}
& \operatorname*{extremize }_{b_a, b_i} && D_\text{KL}(q \parallel p) \\
& \operatorname{subject\,to }
&& \int d\bm{x}_{\partial a \setminus \{i\}} b_a(\bm{x}_{\partial a}) = b_i(x_i) && \forall a \in \partial i, \forall i.
\end{aligned}
$$
この変分を行うと、次式が得られます。
$$
\begin{aligned}
b_a(\bm{x}_{\partial a}) &\propto f_a(\bm{x}_{\partial a}) \prod_{i \in \partial a} \exp(\lambda_{ai}(x_i)), \\
b_i(x_i)^{|\partial i| - 1} &\propto \prod_{a \in \partial i} \exp(\lambda_{ai}(x_i)).
\end{aligned}
$$
導出: Lagrange汎関数を以下のように定義します。
$$
\begin{aligned}
& \mathcal{L}[b_a, b_i, \lambda_{ai}] \\
&= - \sum_a \int d\bm{x}_{\partial a} \; b_a(\bm{x}_{\partial a}) \log f_a(\bm{x}_{\partial a}) \\
&\qquad {} + \sum_a \int d\bm{x}_{\partial a} \; b_a(\bm{x}_{\partial a}) \log b_a(\bm{x}_{\partial a}) \\
&\qquad {} - \sum_i (|\partial i| - 1) \int dx_i \; b_i(x_i) \log b_i(x_i) \\
&\qquad {} + \sum_{a, i \in \partial a} \int dx_i \lambda_{ai}(x_i) \left( b_i(x_i) - \int d\bm{x}_{\partial a \setminus \{i\}} b_a(\bm{x}_{\partial a}) \right).
\end{aligned}
$$
$b_a(\bm{x}_{\partial a}), b_i(x_i)$ でそれぞれ汎関数微分することによって
$$
\begin{aligned}
\frac{\delta \mathcal{L}}{\delta b_a(\bm{x}_{\partial a})} &= - \log f_a(\bm{x}_{\partial a}) + \log b_a(\bm{x}_{\partial a}) - \sum_{i \in \partial a} \lambda_{ai}(x_i), \\
\frac{\delta \mathcal{L}}{\delta b_i(x_i)} &= - (|\partial i| - 1) \log b_i(x_i) + \sum_{a \in \partial i} \lambda_{ai}(x_i) + \text{const}.
\end{aligned}
$$
第1式、第2式の停留点条件から
$$
\boxed{
\begin{aligned}
b_a(\bm{x}_{\partial a}) &\propto f_a(\bm{x}_{\partial a}) \prod_{i \in \partial a} \exp(\lambda_{ai}(x_i)), \\
b_i(x_i)^{|\partial i| - 1} &\propto \prod_{a \in \partial i} \exp(\lambda_{ai}(x_i)).
\end{aligned}
}
$$
注意: 以下の2つの制約条件は、$b_i$ や $b_a$ の正規化条件に吸収されるので省略しています。
$$
\begin{aligned}
& \int d\bm{x}_{\partial a} b_a(\bm{x}_{\partial a}) = 1 && \forall a, \\
& \int dx_i b_i(x_i) = 1 && \forall i.
\end{aligned}
$$
メッセージの導入
得られた停留点条件において、変数 $i$ から因子 $a$ への「メッセージ」と、因子 $a$ から変数 $i$ への「メッセージ」を、それぞれ次式で定義します。
$$
\begin{aligned}
m_{i \to a}(x_i) &\propto \exp(\lambda_{ai}(x_i)), \\
m_{a \to i}(x_i) &\propto \frac{b_i(x_i)}{m_{i \to a}(x_i)}.
\end{aligned}
$$
メッセージの定数倍は、後で周辺分布を正規化するときに吸収されるため、ここでは比例関係として定義しています。この2種類のメッセージを用いると、停留点条件と局所整合性条件から、信念伝搬法の更新式が得られます。
$$
\boxed{
\begin{aligned}
m_{a \to i}(x_i)
&\propto \int d\bm{x}_{\partial a \setminus \{i\}} \;
f_a(\bm{x}_{\partial a})
\prod_{j \in \partial a \setminus \{i\}}m_{j \to a}(x_j). \\
m_{i \to a}(x_i)
&\propto \prod_{b \in \partial i \setminus \{a\}}m_{b \to i}(x_i).
\end{aligned}
}
$$
そして、上の更新式を繰り返してメッセージが得られたならば、最終的に変数周辺分布が次式で計算されます。
$$
\boxed{
\begin{aligned}
b_i(x_i)
= \frac{1}{Z_i}
\prod_{a \in \partial i}m_{a \to i}(x_i).
\end{aligned}
}
$$
第1式の導出: $m_{i \to a}(x_i) \propto \exp(\lambda_{ai}(x_i))$ を因子周辺分布の停留点条件へ代入すると、
$$
b_a(\bm{x}_{\partial a})
\propto f_a(\bm{x}_{\partial a})
\prod_{j \in \partial a}m_{j \to a}(x_j).
$$
これを局所整合性条件の右辺に代入して整理すると、
$$
\begin{aligned}
b_i(x_i)
&\propto
m_{i \to a}(x_i)
\int d\bm{x}_{\partial a \setminus \{i\}} \;
f_a(\bm{x}_{\partial a})
\prod_{j \in \partial a \setminus \{i\}}m_{j \to a}(x_j).
\end{aligned}
$$
これを $\displaystyle m_{a \to i}(x_i) \propto \frac{b_i(x_i)}{m_{i \to a}(x_i)}$ に代入することで、
$$
\boxed{
\begin{aligned}
m_{a \to i}(x_i)
\propto
\int d\bm{x}_{\partial a \setminus \{i\}} \;
f_a(\bm{x}_{\partial a})
\prod_{j \in \partial a \setminus \{i\}}m_{j \to a}(x_j).
\end{aligned}
}
$$
$b_i$ を得る式の導出: 一方、$m_{a \to i}(x_i)$ の定義を変形して得られる
$$
m_{i \to a}(x_i) \propto \frac{b_i(x_i)}{m_{a \to i}(x_i)}
$$
を、変数周辺分布の停留点条件の右辺に代入して整理すると、両辺から $b_i(x_i)^{|\partial i| - 1}$ が打ち消し合って、
$$
\boxed{
\begin{aligned}
b_i(x_i) \propto \prod_{a \in \partial i}m_{a \to i}(x_i).
\end{aligned}
}
$$
第2式の導出: これを再び $m_{i \to a}(x_i) \propto b_i(x_i) / m_{a \to i}(x_i)$ へ代入すれば、
$$
\boxed{
\begin{aligned}
m_{i \to a}(x_i)
\propto
\prod_{b \in \partial i \setminus \{a\}}m_{b \to i}(x_i).
\end{aligned}
}
$$
単項因子の分離
最後に、因子の集合 $\{f_a\}$ の中に、変数 $x_i$ のみに依存する単項因子 $f_{u_i}(x_i) = \psi_i(x_i)$ が含まれるとして、この因子を明示的に切り離してより扱いやすくしましょう。
単項因子 $u_i$ について、$\partial u_i = \{i\}$ なので、積分する変数は存在しません。よって、$u_i \to i$ のメッセージ更新式は次のように簡略化されます。
$$
\begin{aligned}
m_{u_i \to i}(x_i)
&\propto
\int d\bm{x}_{\partial u_i \setminus \{i\}} \;
f_{u_i}(x_i)
\prod_{j \in \partial u_i \setminus \{i\}}m_{j \to u_i}(x_j) \\
&=
f_{u_i}(x_i).
\end{aligned}
$$
つまり、単項因子から変数へのメッセージは他のメッセージに依存せず、常に単項因子 $f_{u_i}(x_i)$ そのものに比例します。そこで、単項因子 $u_i$ を除いた、変数 $i$ に隣接する因子の集合を $\widetilde{\partial i} = \partial i \setminus \{u_i\}$ と定義します。上で得た関係式を、$i \to a$ ($a \in \widetilde{\partial i}$) のメッセージ更新式と変数周辺分布の式に代入すると、次のように書き換えられます。
$$
\begin{aligned}
m_{i \to a}(x_i)
&\propto
f_{u_i}(x_i)
\prod_{b \in \widetilde{\partial i} \setminus \{a\}}m_{b \to i}(x_i), \\
b_i(x_i)
&\propto f_{u_i}(x_i)
\prod_{a \in \widetilde{\partial i}}m_{a \to i}(x_i).
\end{aligned}
$$
$a \in \widetilde{\partial i}$ である因子から変数へのメッセージの更新式は変わりません。単項因子を分離した後の隣接因子集合 $\widetilde{\partial i}$ を改めて $\partial i$ と書き、$f_{u_i}(x_i) = \psi_i(x_i)$ とすれば、最終的に次の更新式に帰着します。
$$
\boxed{
\begin{aligned}
m_{a \to i}(x_i)
&\propto
\int d\bm{x}_{\partial a \setminus \{i\}} \;
f_a(\bm{x}_{\partial a})
\prod_{j \in \partial a \setminus \{i\}}m_{j \to a}(x_j), \\
m_{i \to a}(x_i)
&\propto \psi_i(x_i)
\prod_{b \in \partial i \setminus \{a\}}m_{b \to i}(x_i), \\
b_i(x_i)
&= \frac{1}{Z_i}\psi_i(x_i)
\prod_{a \in \partial i}m_{a \to i}(x_i)
\end{aligned}
}
$$
解釈
木の場合とループを含むグラフの場合
因子グラフが木である場合、葉から内側へ向かうメッセージと、内側から葉へ向かうメッセージを順番に計算することによって、有限回の更新で正確な周辺分布を得られます。この場合、$b_i(x_i) = p(x_i \mid \bm{y})$ が成立します。
一方、因子グラフがループを含む場合にも、同じメッセージ更新式を反復的に適用できます。この方法は、ループを含む信念伝搬法 (loopy belief propagation) などと呼ばれます。このような場合は、異なる方向から到達したメッセージが、実際にはグラフ内のループを通じて共通する情報を含んでいる可能性があります。したがって、メッセージの積を独立な情報の積として扱う操作は厳密ではありません。
ループを含む場合、そもそも、メッセージが常に収束するとは限りません。それでもメッセージが収束した場合、その固定点は、ここまでに導入したBethe近似のもとでのKLダイバージェンスの停留点に対応します。すなわち、試行分布 $q$ が木構造をもつという仮定のもとで $D_\text{KL}(q \parallel p)$ を変分した結果、という意味における近似解として解釈できます。
なお、ループを含むグラフでは、更新によってメッセージが激しく振動する場合もあります。その場合には、振動を抑えるために新しいメッセージと更新前のメッセージを混ぜるダンピングが用いられることもあります。
キャビティ分布としての解釈
変数から因子へのメッセージでは、因子ノード $a$ から変数ノード $i$ に入る情報が除かれています。
$$
m_{i \to a}(x_i)
\propto \prod_{b \in \partial i \setminus \{a\}}m_{b \to i}(x_i)
$$
このメッセージは、因子ノード $a$ を取り除いたグラフにおける $x_i$ の周辺分布に対応すると解釈できます。このように、あるノード $a$ を取り除く操作によって生じた空所はキャビティと呼ばれます。このことから $m_{i \to a}(x_i)$ は、しばしばキャビティ周辺分布またはキャビティメッセージと呼ばれます。
一方、因子から変数へのメッセージ $m_{a \to i}(x_i)$ は、因子 $a$ と、$a$ に接続する $i$ 以外の変数 $j \in \partial a \setminus \{i\}$ から送られてきた情報をまとめたものです。したがって、$m_{a \to i}(x_i)$ は、因子 $a$ が変数 $x_i$ に与える情報を表しています。
木構造をもつ因子グラフでは、送信先から来たメッセージを除外することにより、同じ情報が一つのメッセージ内で重複して使用されることを防いでいると解釈できます。例えば、変数ノード $i$ が因子ノード $a$ にメッセージを送るとき、$a$ から受け取ったメッセージまで掛け合わせて送り返してしまうと、因子 $a$ に由来する情報がそのまま $a$ に戻ります。更新式で $\partial i \setminus \{a\}$ を用いる理由は、このような情報の即時的な折り返しを除くためであると解釈できます。