複製系の信念伝搬法とレプリカ対称性の仮定からサーベイ伝搬法を導出する

複製系の信念伝搬法を構成し、そこにレプリカ対称性を仮定することでサーベイ伝搬法の更新式を導出する計算ノートです。

サーベイ伝搬法について

通常の信念伝搬法 (belief propagation, BP) では、以下のように因子の積で表される確率分布に対し、一つのBP固定点を求め、その固定点から各変数の周辺分布を近似します。

P(\bm{x}) \propto \prod_i \psi_i(x_i) \prod_\mu f_\mu(\bm{x}_{\partial \mu}).

問題設定によっては、問題サイズの大きい極限において、有効的に確率分布が複数のGibbs分布の混合に分裂していくような振る舞いを見せる場合があります。

P(\bm{x}) \underset{(N \to \infty)}{\propto} \sum_\alpha w_\alpha P_\alpha(\bm{x}).

こういうとき、大雑把には「配置」$\bm{x}$ がクラスターを成していて、それぞれのクラスターが1つのGibbs分布 $P_\alpha(\bm{x})$ に対応する、というようなイメージを持つことができます。

純粋状態と内部のクラスタリング性 — (上図) Gibbs分布が多数のクラスターに分かれる。(下図) クラスターの内部では、十分遠く離れた変数どうしの相関が小さくなる傾向にある。

クラスターが多数乱立している場合、それぞれのクラスターごとに異なるBPメッセージが成立し、したがって異なるBP固定点が対応すると考えることができます。通常のBPを一度実行して得られるのは、そのうち一つの固定点です。そのため、通常のBPだけでは、多数のクラスターの様子をうまく表現できないと考えられます。

そこで、一つのBP固定点を求める代わりに、異なるクラスターにわたるBPメッセージの分布を考え、そのBPメッセージの分布を近似的に計算していくというアプローチが考えられます。このようなアプローチを実現するアルゴリズムが、サーベイ伝搬法 (SP) です。

本記事では、元の確率分布を複数個複製した確率モデルを構成し、その複製系に通常のBPを適用します。そして、複製系のBPメッセージにレプリカ対称な形を仮定することで、BPの更新式からサーベイの更新式を導出します。

信念伝搬法

BPでは、次の因子分解を持つ確率分布の周辺分布を近似的に計算します。

P(\bm{x}) = \frac{1}{Z} \prod_i \psi_i(x_i) \prod_\mu f_\mu(\bm{x}_{\partial \mu}).

ここで、$\psi_i(x_i)$ は変数 $x_i$ のみに依存する単項因子、$f_\mu(\bm{x}_{\partial \mu})$ は複数の変数に依存する因子です。この確率分布に対するBPの更新式は

\begin{aligned} \hat{m}_{\mu\to i}^{[t+1]}(x_i) &\propto \int d\bm{x}_{\partial \mu\setminus\{i\}}\, f_\mu(\bm{x}_{\partial \mu}) \prod_{j\in\partial \mu\setminus\{i\}} m_{j\to \mu}^{[t]}(x_j), \\ m_{i\to \mu}^{[t+1]}(x_i) &\propto \psi_i(x_i) \prod_{\nu\in\partial i\setminus\{\mu\}} \hat{m}_{\nu\to i}^{[t]}(x_i). \end{aligned}

十分な回数の更新を行って1つの固定点に収束した時、最終的に次式で周辺分布を近似します。

\begin{aligned} P(x_i) &\propto b_i(x_i) = m_{i\to \mu}^{[t]}(x_i) \end{aligned}

サーベイ伝搬法

SPでは、各辺についてBPメッセージそのものを一つ保持する代わりに、そのメッセージの確率分布 $\pi_{i\to \mu}[m_{i\to\mu}]$、$\hat{\pi}_{\mu\to i}[\hat{m}_{\mu\to i}]$ を保持します。

アルゴリズム (サーベイ伝搬法):

各辺についてサーベイメッセージ $\pi_{i\to \mu}^{[0]}[m_{i\to\mu}]$ と $\hat{\pi}_{\mu\to i}^{[0]}[\hat{m}_{\mu\to i}]$ を初期化する。
サーベイメッセージの変化が十分に小さくなるまで繰り返す:
1. 因子から変数へのサーベイを更新する。
  $\begin{aligned} \hat{\pi}_{\mu\to i}^{[t+1]}[\hat{m}_{\mu\to i}] &\propto \int \prod_{j\in\partial \mu\setminus\{i\}} \mathcal{D}m_{j\to \mu}\, \delta\!\left[ \hat{m}_{\mu\to i} - \hat{\mathcal{M}}_{\mu\to i} \right] \hat{z}_{\mu \to i}^{s} \prod_{j\in\partial \mu\setminus\{i\}} \pi_{j\to \mu}^{[t]}\!\left[ m_{j\to \mu} \right], \end{aligned}$
  ただし
  $\begin{aligned} \hat{\mathcal{M}}_{\mu\to i} &= \frac{1}{\hat{z}_{\mu \to i}} \int d\bm{x}_{\partial \mu\setminus\{i\}}\, f_\mu(\bm{x}_{\partial \mu}) \prod_{j\in\partial \mu\setminus\{i\}} m_{j\to \mu}(x_j). \end{aligned}$
2. 変数から因子へのサーベイを更新する。
  $\begin{aligned} \pi_{i \to \mu}^{[t+1]}[m_{i\to\mu}] &\propto \int \prod_{\nu\in\partial i\setminus\{\mu\}} \mathcal{D}\hat{m}_{\nu\to i} \, \delta\!\left[ m_{i\to\mu} - \mathcal{M}_{i \to \mu} \right] z_{i\to \mu}^{s} \prod_{\nu\in\partial i\setminus\{\mu\}} \hat{\pi}_{\nu\to i}^{[t]}\!\left[ \hat{m}_{\nu \to i} \right], \end{aligned}$
  ただし
  $\begin{aligned} \mathcal{M}_{i\to \mu} &= \frac{1}{z_{i\to \mu}} \psi_i(x_i) \prod_{\nu\in\partial i\setminus\{\mu\}} \hat{m}_{\nu\to i}(x_i). \end{aligned}$

ここで $\hat{z}_{\mu \to i}$ と $z_{i\to \mu}$ は対応する正規化定数、指数 $s$ はレプリカ数です。

解釈

パラメータ $s$ について

SPの更新式には、$\hat{z}_{\mu \to i}^{s}$ と $z_{i\to \mu}^{s}$ という2種類の重みがあります。この $s$ は、元々はレプリカ数を表す正の整数として、導出過程において次のような形で更新式に挿入されます

\begin{aligned} \prod_{\alpha=1}^{s} \left[z\,m(x^\alpha)\right] &= z^s \prod_{\alpha=1}^{s} m(x^\alpha) \end{aligned}

ところが、サーベイ更新式の形は、もはや $s$ が正の整数であることに依存しない形になっています。

\begin{aligned} \hat{\pi}_{\mu\to i}[\hat{m}_{\mu\to i}] &\propto \int \prod_{j\in\partial \mu\setminus\{i\}} \mathcal{D}m_{j\to \mu}\, \delta\!\left[ \hat{m}_{\mu \to i} - \hat{\mathcal{M}}_{\mu\to i} \right] \hat{z}_{\mu \to i}^{s} \prod_{j\in\partial \mu\setminus\{i\}} \pi_{j\to \mu}[m_{j\to \mu}], \\ \pi_{i\to \mu}[m_{i\to\mu}] &\propto \int \prod_{\nu\in\partial i\setminus\{\mu\}} \mathcal{D}\hat{m}_{\nu\to i}\, \delta\!\left[ m_{i\to\mu}-\mathcal{M}_{i\to\mu} \right] z_{i\to\mu}^{s} \prod_{\nu\in\partial i\setminus\{\mu\}} \hat{\pi}_{\nu\to i}[\hat{m}_{\nu\to i}]. \end{aligned}

そこで、$s$ を実数に解析接続し、異なるBP固定点をどのような重みでサーベイに寄与させるかを制御するパラメータとみなすことができます。

とくに $s=0$ とすると、正規化定数による再重み付けが消滅し、すべてのBP固定点を等しい重みでサーベイに寄与させることになります。SPという場合、一般的にはこの形を指すことが多いと思います。

\begin{aligned} \hat{\pi}_{\mu\to i}[\hat{m}_{\mu\to i}] &\propto \int \prod_{j\in\partial \mu\setminus\{i\}} \mathcal{D}m_{j\to \mu}\, \delta\!\left[ \hat{m}_{\mu \to i} - \hat{\mathcal{M}}_{\mu\to i} \right] \prod_{j\in\partial \mu\setminus\{i\}} \pi_{j\to \mu}[m_{j\to \mu}], \\ \pi_{i\to \mu}[m_{i\to\mu}] &\propto \int \prod_{\nu\in\partial i\setminus\{\mu\}} \mathcal{D}\hat{m}_{\nu\to i}\, \delta\!\left[ m_{i\to\mu}-\mathcal{M}_{i\to\mu} \right] \prod_{\nu\in\partial i\setminus\{\mu\}} \hat{\pi}_{\nu\to i}[\hat{m}_{\nu\to i}]. \end{aligned}

BPとSPの関係

BPでは次のようなメッセージの更新が行われていきます。

\{m_{j\to \mu}\} \overset{\hat{\mathcal{M}}_{\mu\to i}}{\longmapsto} \hat{m}_{\mu\to i}

他方、SPではメッセージ $\{m_{j\to \mu}\}$ 自体を、更なる高階の分布であるサーベイ分布に従う確率変数と考え、サーベイを更新していくこととなります。

\{\pi_{j\to \mu}\} \longmapsto \hat{\pi}_{\mu\to i}

キャビティ法という観点からも似た解釈ができます。通常のBPでは、1つの辺 $(i, \mu)$ に対して $m_{i\to \mu}(x_i)$ という一つのキャビティ分布を計算するのに対し、SPでは、次のように様々なBP固定点に対応する多数のキャビティ分布を扱っているのだと考えることができます。

m_{i\to \mu}^{(1)}, m_{i\to \mu}^{(2)}, m_{i\to \mu}^{(3)}, \ldots

そしてSPではこれらの分布を $\pi_{i\to \mu}[m]$ と書いて、それを伝搬させていっています。キャッチーに言うなら次のようなものでしょう。

BPでは、キャビティ分布を伝搬させる
SPでは、キャビティ分布の分布を伝搬させる

おまけ: 周辺分布のサーベイについて

BPでは最終的に周辺分布を近似する $b_i(x_i)$ を計算します。これに対応して、SPでも各辺のBPメッセージの分布を計算することによって「周辺分布の分布」を形式的に構成できます。

因子から変数へのメッセージを $\{\hat{m}_{\mu\to i}\}_{\mu\in\partial i}$ とすると、$b_i$ の更新結果は次式で表されます。

\begin{aligned} b_i(x_i) &= \frac{1}{z_i} \psi_i(x_i) \prod_{\mu\in\partial i} \hat{m}_{\mu\to i}(x_i), \\ z_i &= \int dx_i\, \psi_i(x_i) \prod_{\mu\in\partial i} \hat{m}_{\mu\to i}(x_i). \end{aligned}

上の第1式右辺を $\mathcal{B}_i(x_i)$ と書くことにします。すると、周辺分布の分布 $\pi_i[b_i]$ は、次のように定義できます。

\begin{aligned} \pi_i[b_i] &\propto \int \prod_{\mu\in\partial i} \mathcal{D}\hat{m}_{\mu\to i}\, z_i^s \delta \left[ b_i(x_i) - \mathcal{B}_i(x_i) \right] \prod_{\mu\in\partial i} \hat{\pi}_{\mu\to i}[\hat{m}_{\mu\to i}] \end{aligned}