一般化線形モデルの複製系に対する信念伝搬法 (belief propagation, BP) を、大自由度極限で近似することで、一般化近似サーベイ伝搬法 (generalized approximate survey propagation, GASP) を導出する計算ノートです。

計算ノート（PDF）

GASPについて

通常のBPでは一つのキャビティ分布を伝搬させるのに対し、サーベイ伝搬法 (survey propagation, SP) では、異なるクラスターにわたるキャビティ分布の分布を扱います。ただし、その分布を各辺についてそのまま保持し、更新していくのは大変です。

GASPでは、一般化線形モデルの密な相互作用を利用して、この更新を少数のパラメータで近似します。GAMPの導出と同じく、キャビティ場をガウス分布で近似し、その後に辺依存のキャビティ量を消去します。違いは、複製系を考えるため、ガウス分布にレプリカ間の相関が含まれるという点です。

問題設定

測定行列を $\bm{A}=(A_{\mu i})\in\mathbb{R}^{M\times N}$、観測データを $\bm{y}\in\mathbb{R}^M$ とし、次の目的関数を考えます。

$$ H_{\bm y,\bm A}(\bm x) = \sum_\mu \ell(y_\mu,[\bm A\bm x]_\mu) + \sum_i J(x_i). $$

$\ell(y,z)$ はoutput側の損失関数、$J(x)$ はinput側の正則化関数です。この目的関数に対応するGibbs分布を複製し、レプリカ番号を $a=1,\ldots,s$ とします。導出は $s>1$ の整数から始めます。また、$N,M\to\infty$ で $M/N\to\alpha\in(0,\infty)$ とし、$A_{\mu i}=O(N^{-1/2})$ を仮定します。

複製系のキャビティメッセージにレプリカ置換対称性を仮定し、その一次と二次のモーメントを次のように表します。

$$ \begin{aligned} \langle x_j^a\rangle_{j\to\mu} &=\widehat{x}_{j\to\mu}, \\ \langle x_j^a x_j^b\rangle_{j\to\mu} &=\widehat{x}_{j\to\mu}^2+v_{0,j\to\mu}+\delta_{ab}v_{1,j\to\mu}. \end{aligned} $$

すなわち、異なるレプリカに共通する共分散を $v_0$、各レプリカに固有の分散を $v_1$ として、二種類の揺らぎを扱います。

自由エントロピー

標準ガウス測度を $D\xi=e^{-\xi^2/2}d\xi/\sqrt{2\pi}$ とします。output側とinput側の自由エントロピーを、それぞれ次のように定義します。

$$ \begin{aligned} \phi^{\mathrm{out}}(y,\omega,V_0,V_1) &\coloneqq \frac{1}{s}\log\int D\xi_0 \left[ \int D\xi_1\, \exp\!\left\{-\beta\ell\!\left(y,\omega+\sqrt{V_0}\xi_0+\sqrt{V_1}\xi_1\right)\right\} \right]^s, \\ \phi^{\mathrm{in}}(B,\Lambda_0,\Lambda_1) &\coloneqq \frac{1}{s}\log\int D\xi \left[ \int dx\, \exp\!\left\{-\frac{\Lambda_1}{2}x^2+(B+\sqrt{\Lambda_0}\xi)x-\beta J(x)\right\} \right]^s. \end{aligned} $$

output側では、全レプリカに共通する揺らぎ $\xi_0$ と、レプリカごとに独立な揺らぎ $\xi_1$ が現れます。input側では、共通のガウス変数によって有効場 $B$ が揺らぐ形になっています。

GASPの更新式

辺添字を消去した更新は、次のようにまとめられます。ここでは計算ノートと同様に反復時刻の添字を省略します。$\phi_\mu^{\mathrm{out}}$ は $(y_\mu,\omega_\mu,V_{0,\mu},V_{1,\mu})$ で、$\phi_i^{\mathrm{in}}$ は $(B_i,\Lambda_{0,i},\Lambda_{1,i})$ で評価した自由エントロピーを表します。

更新式 (GASP):

  1. output側の平均と二種類の分散を求める。

    $$ \begin{aligned} V_{0,\mu}&=\sum_i A_{\mu i}^2v_{0,i}, \\ V_{1,\mu}&=\sum_i A_{\mu i}^2v_{1,i}, \\ \omega_\mu&=\sum_i A_{\mu i}\widehat{x}_i-g_\mu(V_{1,\mu}+sV_{0,\mu}). \end{aligned} $$

  2. output側の応答を求める。

    $$ \begin{aligned} g_\mu&=\partial_\omega\phi_\mu^{\mathrm{out}}, \\ \Gamma_{0,\mu} &=\frac{1}{s-1}\left[\partial_\omega^2\phi_\mu^{\mathrm{out}}-2\partial_{V_1}\phi_\mu^{\mathrm{out}}+g_\mu^2\right], \\ \Gamma_{1,\mu} &=\frac{1}{s-1}\left[\partial_\omega^2\phi_\mu^{\mathrm{out}}-s\left(2\partial_{V_1}\phi_\mu^{\mathrm{out}}-g_\mu^2\right)\right]. \end{aligned} $$

  3. input側の有効場と二種類の二次係数を求める。

    $$ \begin{aligned} \Lambda_{0,i}&=\sum_\mu A_{\mu i}^2\Gamma_{0,\mu}, \\ \Lambda_{1,i}&=\sum_\mu A_{\mu i}^2\Gamma_{1,\mu}, \\ B_i&=\sum_\mu A_{\mu i}g_\mu+\widehat{x}_i(\Lambda_{1,i}-s\Lambda_{0,i}). \end{aligned} $$

  4. 変数ごとの平均と二種類の分散を求める。

    $$ \begin{aligned} \widehat{x}_i&=\partial_B\phi_i^{\mathrm{in}}, \\ v_{0,i}&=\frac{1}{s-1}\left[\partial_B^2\phi_i^{\mathrm{in}}+2\partial_{\Lambda_1}\phi_i^{\mathrm{in}}+\widehat{x}_i^2\right], \\ v_{1,i}&=\partial_B^2\phi_i^{\mathrm{in}}-sv_{0,i}. \end{aligned} $$

これらは、$(\widehat{x}_i,v_{0,i},v_{1,i})$ からoutput側の量を求め、その応答をinput側へ戻す循環を構成します。反復として実行するときは、$\omega_\mu$ の反作用項に前回の $g_\mu$ を用い、その後に新しいoutput応答とinput側の量を順に更新します。

導出過程

大まかな流れは、GAMPの導出とよく似ています。

$$ \text{複製系のBP} \quad \underset{\text{相関を持つガウス分布での近似}}{\longrightarrow} \quad \text{rSP} \quad \underset{\text{キャビティ量の消去}}{\longrightarrow} \quad \text{GASP} $$

複製系のBPからrSPへ

因子 $\mu$ から変数 $i$ へのキャビティ場は、各レプリカについて次式で与えられます。

$$ u_{\mu\to i}^a=\sum_{j\ne i}A_{\mu j}x_j^a. $$

この場を、レプリカ間に相関を持つ多変量ガウス分布で近似します。先ほどのモーメントの仮定を用いると、次のように表せます。

$$ u_{\mu\to i}^a \simeq \omega_{\mu\to i} +\sqrt{V_{0,\mu\to i}}\xi_0 +\sqrt{V_{1,\mu\to i}}\xi_1^a. $$

ここで、$\xi_0,\xi_1^1,\ldots,\xi_1^s$ は独立な標準ガウス変数です。$\omega_{\mu\to i}$ は $\sum_{j\ne i}A_{\mu j}\widehat{x}_{j\to\mu}$、$V_{0,\mu\to i}$ と $V_{1,\mu\to i}$ はそれぞれ $\sum_{j\ne i}A_{\mu j}^2v_{0,j\to\mu}$ と $\sum_{j\ne i}A_{\mu j}^2v_{1,j\to\mu}$ です。

この近似によって、因子更新に含まれる多数の変数についての積分が、共通のガウス変数と各レプリカ固有のガウス変数についての積分に置き換わります。さらに、残された摂動 $A_{\mu i}x_i^a$ について因子メッセージの対数を二次まで展開します。

レプリカ置換対称性により、二次の係数は対角成分と非対角成分の二種類に分かれます。これを整理すると、変数側の複製メッセージは次の形になります。

$$ M_{i\to\mu}(\bm{x}_i) \propto \exp\!\left\{ -\frac{\Lambda_{1,i\to\mu}}{2}\sum_a(x_i^a)^2 +\frac{\Lambda_{0,i\to\mu}}{2}\left(\sum_a x_i^a\right)^2 +B_{i\to\mu}\sum_a x_i^a -\beta\sum_a J(x_i^a) \right\}. $$

$\Lambda_0$ の項がレプリカどうしを結合しています。この項をHubbard–Stratonovich変換によって共通のガウス変数で表すと、先ほど定義したinput自由エントロピーが得られます。その微分から平均と二種類の分散を計算することで、辺ごとの量について更新が閉じます。この段階が緩和サーベイ伝搬法 (relaxed survey propagation, rSP) です。

rSPからGASPへ

rSPでは、まだ辺 $(\mu,i)$ ごとのキャビティ量が残っています。そこで、辺に依存しない量のまわりで展開します。有効場の差は $O(N^{-1/2})$、分散や二次係数の差は $O(N^{-1})$ なので、平均と応答の展開では有効場の一次の変化が主要な寄与となります。

$$ \begin{aligned} \widehat{x}_{i\to\mu} &=\widehat{x}_i-A_{\mu i}g_\mu(v_{1,i}+sv_{0,i})+O(N^{-1}), \\ g_{\mu\to i} &=g_\mu+A_{\mu i}\widehat{x}_i(\Gamma_{1,\mu}-s\Gamma_{0,\mu})+O(N^{-1}). \end{aligned} $$

これらを場の定義に代入すると、辺添字が消え、GASPの更新式が得られます。保持するメッセージの量は、辺ごとの $O(MN)$ 個から、因子ごと・変数ごとの $O(M+N)$ 個になります。ただし、密な測定行列を用いる場合、行列そのものの保持や行列ベクトル積に必要な計算は残ります。

ポイント

二種類の分散と感受率

GAMPでは一つの分散 $v_i$ を扱っていましたが、GASPでは $v_{0,i}$ と $v_{1,i}$ を区別します。一つのレプリカの分散は $v_{0,i}+v_{1,i}$ ですが、共通の有効場 $B_i$ に対する平均の応答は次式で与えられます。

$$ \partial_B\widehat{x}_i =\partial_B^2\phi_i^{\mathrm{in}} =v_{1,i}+sv_{0,i}. $$

$B_i$ は全レプリカに同時に作用するため、他のレプリカとの共分散も応答に寄与します。

Onsager反作用項

キャビティ量を消去すると、次のOnsager反作用項が現れます。

$$ -g_\mu(V_{1,\mu}+sV_{0,\mu}), \qquad \widehat{x}_i(\Lambda_{1,i}-s\Lambda_{0,i}). $$

input側の感受率に対応して、output側でも次の関係が成り立ちます。

$$ \Gamma_{1,\mu}-s\Gamma_{0,\mu} =-\partial_\omega^2\phi_\mu^{\mathrm{out}}. $$

GAMPと同様に、自分自身の寄与が更新を介して戻ってくる効果を補正しています。ただし、複製系では共通の揺らぎがあるため、補正に入る係数にも $s$ が現れます。

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

自由エントロピーには、局所的な分配関数を $s$ 乗してからガウス積分する形が現れます。これは、共通の場の各値を、その場のもとでの分配関数に応じて再重み付けしていると見ることができます。

導出では $s>1$ の整数を用いましたが、得られた積分の形をもとに、$s$ を実数のパラメータとして扱うことも考えられます。ただし、ここで示した応答や分散の式には $1/(s-1)$ が含まれるため、$s=1$ をそのまま代入することはできません。その場合は、自由エントロピーの定義に戻って極限を扱う必要があります。