信念伝搬法をKLダイバージェンスのBethe近似と変分法から導出するノートです。

計算ノート（PDF）

信念伝搬法について

信念伝搬法を用いて周辺分布を計算する目的は色々ありますが、その中でも重要な目的は、最大事後周辺確率 (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$ の周辺事後分布を近似計算します。

アルゴリズム (信念伝搬法):

  1. 各辺 $(i,a)$ について、メッセージ $m_{i \to a}^{[0]}(x_i)$ と $\hat{m}_{a \to i}^{[0]}(x_i)$ を初期化する。

  2. メッセージの変化が十分に小さくなるまで繰り返す:

    1. 変数から因子へのメッセージを更新する。

      $$ m_{i \to a}^{[t+1]}(x_i) \propto \prod_{b \in \partial i \setminus \{a\}}\hat{m}_{b \to i}^{[t]}(x_i). $$

    2. 因子から変数へのメッセージを更新する。

      $$ \hat{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). $$

  3. 収束したメッセージから、周辺分布を近似計算する。

    $$ p(x_i \mid \bm{y}) \approx b_i(x_i) = \frac{1}{Z_i}\prod_{a \in \partial i}\hat{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}) $$

と表せる場合は、次のアルゴリズムを使えます。

アルゴリズム (単項因子を分離した信念伝搬法):

  1. 各辺 $(i,a)$ について、メッセージ $m_{i \to a}^{[0]}(x_i)$ と $\hat{m}_{a \to i}^{[0]}(x_i)$ を初期化する。

  2. メッセージの変化が十分に小さくなるまで繰り返す:

    1. 変数から因子へのメッセージを更新する。

      $$ m_{i \to a}^{[t+1]}(x_i) \propto \psi_i(x_i) \prod_{b \in \partial i \setminus \{a\}}\hat{m}_{b \to i}^{[t]}(x_i). $$

    2. 因子から変数へのメッセージを更新する。

      $$ \hat{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). $$

  3. 収束したメッセージから、周辺分布を近似計算する。

    $$ p(x_i \mid \bm{y}) \approx b_i(x_i) = \frac{1}{Z_i} \psi_i(x_i) \prod_{a \in \partial i}\hat{m}_{a \to i}^{[t]}(x_i). $$

解釈

木の場合とループを含むグラフの場合

因子グラフが木である場合、葉から内側へ向かうメッセージと、内側から葉へ向かうメッセージを順番に計算することによって、有限回の更新で正確な周辺分布を得られます。この場合、$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\}}\hat{m}_{b \to i}(x_i) $$

このメッセージは、因子ノード $a$ を取り除いたグラフにおける $x_i$ の周辺分布に対応すると解釈できます。このように、あるノード $a$ を取り除く操作によって生じた空所はキャビティと呼ばれます。このことから $m_{i \to a}(x_i)$ は、しばしばキャビティ周辺分布またはキャビティメッセージと呼ばれます。

一方、因子から変数へのメッセージ $\hat{m}_{a \to i}(x_i)$ は、因子 $a$ と、$a$ に接続する $i$ 以外の変数 $j \in \partial a \setminus \{i\}$ から送られてきた情報をまとめたものです。したがって、$\hat{m}_{a \to i}(x_i)$ は、因子 $a$ が変数 $x_i$ に与える情報を表しています。

木構造をもつ因子グラフでは、送信先から来たメッセージを除外することにより、同じ情報が一つのメッセージ内で重複して使用されることを防いでいると解釈できます。例えば、変数ノード $i$ が因子ノード $a$ にメッセージを送るとき、$a$ から受け取ったメッセージまで掛け合わせて送り返してしまうと、因子 $a$ に由来する情報がそのまま $a$ に戻ります。更新式で $\partial i \setminus \{a\}$ を用いる理由は、このような情報の即時的な折り返しを除くためであると解釈できます。