ガウス過程を理解したい2
ガウス過程と機械学習の第5章、補助変数法でよくわからなくなってしまったので原著を読んだのでまとめます。スパース近似ガウス過程回帰を統一的視点で眺めるという内容になっています。
@matsueushiさんが既に綺麗にまとめてくれているのですが、数弱の自分は式をパッと見ただけでは理解できなかったので、もうちょっと細かいところもまとめていこうと思います(ほぼ翻訳)。
ガウス過程回帰
まずガウス過程回帰についておさらいです。ガウス分布の定義は
任意次元の入力に対する出力の同時分布が多変量ガウス分布に従うもののこと。
でした(厳密な言い方では無いと思いますが)。ガウス過程をベイズ的に眺めると、これから紹介する補助変数法の理解がすっきりします。
導入の詳細は前回の記事を参照してください。
入力と、対応する出力が次のような関係だとします。
\begin{aligned} y_{i}=f\left(\mathbf{x}_{i}\right)+\varepsilon_{i}, \quad \text { where } \quad \varepsilon_{i} \sim \mathcal{N}\left(0, \sigma_{\text {noise }}^{2}\right) \end{aligned}
はノイズを表し はノイズの分散です。以降ではこの関係が前提であるとします。
では、ガウス過程回帰をベイズ的に眺めていきます。ガウス過程回帰とは結局のところ、関数について次のような事前分布を導入することと同義です。
\begin{aligned} p\left(\mathbf{f} | \mathbf{x}_{1}, \mathbf{x}_{2}, \ldots, \mathbf{x}_{n}\right)=\mathcal{N}(\mathbf{0}, K) \end{aligned}
ここで、行列は成分がとなるカーネル行列です。つまり、関数自体が確率変数であると考えるのがガウス過程です。そして、データからその事後分布を推定するのがガウス過程回帰ということになります。
では、関数の事後分布を導出していきます。ベイズの定理より、
\begin{aligned} p\left(\mathbf{f}, \mathbf{f}_{*} | \mathbf{y}\right) &= \frac{p\left(\mathbf{f}, \mathbf{f}_{*}\right) p(\mathbf{y} | \mathbf{f})}{p(\mathbf{y})} \\ p\left(\mathbf{f}_{*} | \mathbf{y}\right) &= \int p\left(\mathbf{f}, \mathbf{f}_{*} | \mathbf{y}\right) \mathrm{d} \mathbf{f} \\ &= \frac{1}{p(\mathbf{y})} \int p(\mathbf{y} | \mathbf{f}) p\left(\mathbf{f}, \mathbf{f}_{*}\right) \mathrm{d} \mathbf{f} \end{aligned}
ここで、
\begin{aligned} p\left(\mathbf{f}, \mathbf{f}_{*}\right | \mathbf{y}) &= \mathcal{N}\left(\mathbf{0},\left[\begin{array}{ll} K_{\mathrm{f}, \mathrm{f}} & K_{*, \mathrm{f}} \\ K_{\mathrm{f}, *} & K_{*, *} \end{array}\right]\right) \\ p(\mathbf{y} | \mathbf{f}) &= \mathcal{N}\left(\mathbf{f}, \sigma_{\mathrm{noise}}^{2} I\right) \end{aligned}
です。条件付き多変量ガウス分布の式から
\begin{aligned} p\left(\mathbf{f}_{*} | \mathbf{y}\right)=\mathcal{N}\left(K_{*, \mathbf{f}}\left(K_{\mathbf{f}, \mathbf{f}}+\sigma_{\text {noise }}^{2} I\right)^{-1} \mathbf{y}, K_{*, *}-K_{*, \mathbf{f}}\left(K_{\mathbf{f}, \mathbf{f}}+\sigma_{\text {noise }}^{2} I\right)^{-1} K_{\mathbf{f}, *}\right) \end{aligned}
となることがわかります。
もちろんこれを直接計算できることに越したことはないのですが、カーネル行列の計算量はです。逆行列に至ってはの計算量とメモリが必要になり、データが多いと計算量が爆発し使い物にならないという問題が発生します。そこで、同時分布を近似しようというのが補助変数法です。ガウス過程回帰だけでなく殆どのスパース近似で用いられる方法とのことです。
補助変数法(Inducing Variable Methodl; IVM)
計算量を減らす近似の手段として、補助変数(inducing variable)を同時分布に導入します。ガウス過程において補助変数を導入するということは、対応する補助入力(inducing inputs)を導入したこと同義です。事後分布では積分消去されるのがミソですが、ただ積分消去するだけでは計算量が増えるだけになってしまいます。そこで、の導入に際しての条件付き独立を仮定し、以下のような近似を行います。
\begin{aligned} p\left(\mathbf{f}_{*}, \mathbf{f}\right) \simeq q\left(\mathbf{f}_{*}, \mathbf{f}\right)=\int q\left(\mathbf{f}_{*} | \mathbf{u}\right) q(\mathbf{f} | \mathbf{u}) p(\mathbf{u}) \mathrm{d} \mathbf{u} \end{aligned}
このを決めようというのが補助変数法です。
また、登場する式のリファレンスとしても便利なので、厳密な条件付き分布についても一度整理しておきましょう。厳密な条件付き分布は
\begin{aligned} p(\mathbf{f} | \mathbf{u}) &=\mathcal{N}\left(K_{f, u} K_{\mathbf{u}, \mathbf{u}}^{-1} \mathbf{u}, \;\; K_{\mathbf{f}, \mathbf{f}}-Q_{\mathbf{f}, \mathbf{f}}\right) \\ p\left(\mathbf{f}_{*} | \mathbf{u}\right) &=\mathcal{N}\left(K_{*, \mathbf{u}} K_{\mathbf{u}, \mathbf{u}}^{-1} \mathbf{u}, \;\;K_{*, *}-Q_{*, *}\right) \\ Q_{\mathbf{a}, \mathbf{b}} &\triangleq K_{\mathbf{a}, \mathbf{u}} K_{\mathbf{u}, \mathbf{u}}^{-1} K_{\mathbf{u}, \mathbf{b}} \end{aligned}
です(に関してはこの後導出します)。
The Subset of Data (SoD) Approximation
データの一部だけを使う方法です。データが多すぎるなら削ればよいということです。これは近似と呼ぶのかわかりませんが、計算量を減らす最も簡単な手法ですね。ただ、せっかく取れているデータを使わないのはもったいありません。以降で紹介する4つ(説明するのは3つ)の方法では、データを捨てずに事後分布を近似していきます。
The Subset of Regressors (SoR) Approximation
SoRは以下の事前重みを持つ線形モデルと解釈することができます。
\begin{aligned} f_* = K_{*, \mathbf{u}}\mathbf{w_u}, \quad \text{with} \quad p(\mathbf{w_u}) = \mathcal{N}\left(\mathbf{0}, K_{\,\mathbf{u, u}}^{-1}\right) \end{aligned}
事前分布の分散をとしているところが重要で、ガウス過程の事前分布が自然と現れます。
\begin{aligned} \mathbf{u}=K_{\mathbf{u}, \mathbf{u}} \mathbf{w}_{\mathbf{u}} \Rightarrow\left\langle\mathbf{u} \mathbf{u}^{\top}\right\rangle= K_{\mathbf{u}, \mathbf{u}}\left\langle\mathbf{w}_{\mathbf{u}} \mathbf{w}_{\mathbf{u}}^{\top}\right\rangle K_{\mathbf{u}, \mathbf{u}}=K_{\mathbf{u}, \mathbf{u}} \end{aligned}
したがって、より、
\begin{aligned} \mathbf{f}_{*}=K_{*, \mathbf{u}} K_{\mathbf{u}, \mathbf{u}}^{-1} \mathbf{u}, \quad \text { with } \quad \mathbf{u} \sim \mathcal{N}\left(\mathbf{0}, K_{\mathbf{u}, \mathbf{u}}\right) \end{aligned}
となり、事後分布と見比べると自然な形で式が得られたことがわかります。以上より、は
\begin{aligned} q_{\mathrm{SoR}}(\mathbf{f} | \mathbf{u}) &= \mathcal{N}\left(K_{\mathrm{f}, \mathbf{u}} K_{\mathbf{u}, \mathbf{u}}^{-1} \mathbf{u}, \mathbf{0}\right) \\ q_{\mathrm{SoR}}\left(\mathbf{f}_{*} | \mathbf{u}\right) &= \mathcal{N}\left(K_{*, \mathbf{u}} K_{\mathbf{u}, \mathbf{u}}^{-1} \mathbf{u}, \mathbf{0}\right) \end{aligned}
で与えられ。
\begin{aligned} q_{\mathrm{SoR}}\left(\mathbf{f}, \mathbf{f}_{*}\right)&=\mathcal{N}\left(\mathbf{0},\left[\begin{array}{ll} Q_{\mathrm{f}, \mathrm{f}} & Q_{\mathrm{f}, *} \\ Q_{*, f} & Q_{*, *} \end{array}\right]\right) \\ Q_{\mathbf{a}, \mathbf{b}} &\triangleq K_{\mathbf{a}, \mathbf{u}} K_{\mathbf{u}, \mathbf{u}}^{-1} K_{\mathbf{u}, \mathbf{b}} \end{aligned}
となることがわかります。このも一応導出しておきましょう。
\begin{aligned} cov\left(q_{\mathrm{SoR}}(\mathbf{f} | \mathbf{u}), q_{\mathrm{SoR}}(\mathbf{f}_* | \mathbf{u})\right) &= K_{\mathbf{f,u}}K_{\mathbf{u,u}}^{-1}\mathbf{u}\left(K_{\mathbf{f,u}}K_{\mathbf{u,u}}^{-1}\mathbf{u}\right)^{\top} \\ &= K_{\mathbf{f,u}}K_{\mathbf{u,u}}^{-1}\mathbf{u}\mathbf{u}^{\text{T}}K_{\mathbf{u,u}}^{-1}K_{\mathbf{u,*}} \\ &= K_{\mathbf{f,u}}K_{\mathbf{u,u}}^{-1}K_{\mathbf{u,*}} \end{aligned}
また、近似された事後分布は、の分散共分散行列の対角成分にノイズを足し、条件付き多変量ガウス分布の式を使えば
\begin{aligned} q_{\mathrm{SoR}}\left(\mathbf{f}_{*} | \mathbf{y}\right) &=\mathcal{N}\left(Q_{*, \mathbf{f}}\left(Q_{\mathbf{f}, \mathbf{f}}+\sigma_{\text {noise }}^{2} I\right)^{-1} \mathbf{y}, Q_{* *}-Q_{*, \mathbf{f}}\left(Q_{\mathbf{f}, \mathbf{f}}+\sigma_{\text {noise }}^{2} I\right)^{-1} Q_{\mathbf{f}, *}\right)\\ &=\mathcal{N}\left(\sigma^{-2} K_{*, u} \Sigma K_{\mathbf{u}, \mathbf{f}},\;\; K_{*, u} \Sigma K_{\mathbf{u}, *}\right) \\ \Sigma &= \left(\sigma^{-2} K_{\mathbf{u}, \mathbf{f}} K_{\mathbf{f}, \mathbf{u}}+K_{\mathbf{u}, \mathbf{u}}\right)^{-1} \end{aligned}
となります。の2つ目の式の形は実装するときにメモリに優しい形になっています(導出は最後にやります)。理解するだけならの1つ目の式がわかれば十分です。式をよく見るとわかるのですが、SoRは結局のところカーネル関数をと置いたガウス過程に対応します(ここ重要)。
さて、自然な形でが決められたわけですが、この近似によって生じるデメリットもあります。
メリット
厳密にガウス過程(これから厳密なガウス過程ではなくなっていくのでメリットとした)
デメリット
たまたま得られたデータのばらつきが小さかった時に予測分散が過剰に小さくなるなど、補助変数を介する条件付き分布を導入したことによる自由度の制約を受けます。
以下の手法はこのデメリットを緩和しようとするもので、分散が過剰に小さくならないよう、さらに前提を追加していきます(理論的には破綻するので厳密にはガウス過程ではなくなる)。
The Deterministic Training Conditional (DTC) Approximation
DTCは、以下のような近似を行います。
\begin{aligned} q_{\mathrm{DTC}}(\mathbf{f} | \mathbf{u}) &= \mathcal{N}\left(K_{\mathrm{f}, \mathbf{u}} K_{\mathbf{u}, \mathbf{u}}^{-1} \mathbf{u}, \mathbf{0}\right) \\ q_{\mathrm{DTC}}\left(\mathbf{f}_{*} | \mathbf{u}\right) &= p\left(\mathbf{f}_{*} | \mathbf{u}\right) \end{aligned}
式を見ればわかる通り、SoRとの本質的な違いはとしている部分だけです。すなわち、近似された同時分布は
\begin{aligned} q_{\mathrm{DTC}}\left(\mathbf{f}, \mathbf{f}_{*}\right)=\mathcal{N}\left(\mathbf{0},\left[\begin{array}{ll} Q_{\mathrm{f}, f} & Q_{\mathrm{f}, *} \\ Q_{*, \mathrm{f}} & K_{*, *} \end{array}\right]\right) \end{aligned}
となります。の中にが混ざっていることからもわかる通り、この時点で厳密にはガウス過程ではなくなっています。あとは、SoRの時と同様に事後分布を計算すれば、
\begin{aligned} q_{\mathrm{DTC}}\left(\mathbf{f}_{*} | \mathbf{y}\right) &=\mathcal{N}\left(Q_{*, \mathbf{f}}\left(Q_{\mathbf{f}, \mathbf{f}}+\sigma_{\text {noise }}^{2} I\right)^{-1} \mathbf{y}, K_{*, *}-Q_{*, \mathbf{f}}\left(Q_{\mathbf{f}, \mathbf{f}}+\sigma_{\text {noise }}^{2} I\right)^{-1} Q_{\mathbf{f}, *}\right.\\ &=\mathcal{N}\left(\sigma^{-2} K_{*, u} \Sigma K_{\mathbf{u}, \mathbf{f}} \mathbf{y},\;\; K_{*, *}-Q_{*, *}+K_{*, \mathbf{u}} \Sigma K_{*, \mathbf{u}}^{\top}\right) \end{aligned}
となります。SoRの事後分布と見比べると、分散共分散行列の式中のがになっていることがわかります。が正定値であることから、SoRよりもDTCの法が予測分の分散が大きくなります。
メリット
SoRよりも予測分散が大きくなることが保証される。
デメリット
厳密なガウス過程ではなくなる。
The Fully Independent Training Conditional (FITC) Approximation
スパースガウス過程とも呼ばれ、以下のように近似を行います。
\begin{aligned} q_{\mathrm{FTTC}}(\mathbf{f} | \mathbf{u}) &= \prod_{i=1}^{n} p\left(f_{i} | \mathbf{u}\right) = \mathcal{N}\left(K_{\mathrm{f}, \mathbf{u}} K_{\mathbf{u}, \mathbf{u}}^{-1} \mathbf{u}, \operatorname{diag}\left[K_{\mathrm{f}, \mathrm{f}}-Q_{\mathrm{f}, \mathrm{f}}\right]\right)\\ q_{\mathrm{FITC}}\left(f_{*} | \mathbf{u}\right) &= p\left(f_{*} | \mathbf{u}\right) \end{aligned}
DTCと異なるのは、の分散共分散行列の部分です。FITCがDTCより優れている点は、と見比べるとよくわかります。FITCは対角成分以外を捨ててはいるものの、厳密なガウス過程の分散共分散行列の情報を使って近似を行っています(それでもとしてるので厳密なガウス過程ではない)。
後は今まで通り計算していくと、
\begin{aligned} q_{\mathrm{FITC}}\left(\mathbf{f}, f_{*}\right) &= \mathcal{N}\left(\mathbf{0},\left[\begin{array}{cc} Q_{\mathrm{f}, \mathbf{f}}-\operatorname{diag}\left[Q_{\mathrm{f}, \mathrm{f}}-K_{\mathrm{f}, \mathrm{f}}\right] & Q_{\mathrm{f}, *} \\ Q_{*, \mathrm{f}} & K_{*, *} \end{array}\right]\right) \\ q_{\mathrm{FITC}}\left(f_{*} | \mathbf{y}\right) &=\mathcal{N}\left(Q_{*, \mathbf{f}}\left(Q_{\mathrm{f}, \mathbf{f}}+\Lambda\right)^{-1} \mathbf{y}, K_{*, *}-Q_{*, \mathbf{f}}\left(Q_{\mathrm{f}, \mathbf{f}}+\Lambda\right)^{-1} Q_{\mathrm{f}, *}\right) \\ &=\mathcal{N}\left(K_{*, \mathbf{u}} \Sigma K_{\mathbf{u}, \mathbf{f}} \Lambda^{-1} \mathbf{y}, K_{*, *}-Q_{*, *}+K_{*, \mathbf{u}} \Sigma K_{\mathbf{u}, *}\right) \\ \Sigma &= \left(K_{\mathbf{u}, \mathbf{u}}+K_{\mathbf{u}, \mathbf{f}} \Lambda^{-1} K_{\mathbf{f}, \mathbf{u}}\right)^{-1} \\ \Lambda &=\operatorname{diag} \left[K_{\mathrm{f}, \mathrm{f}}-Q_{\mathrm{f}, \mathrm{f}}+\sigma_{\mathrm{noise}}^{2} I\right] \end{aligned}
となります。
The Partially Independent Training Conditional (PITC) Approximation
書籍「ガウス過程と機械学習」の取り扱い範囲を超えているので今回は取り扱いません。ただ、ここまで読み進めてくれた方ならわかると思いますが、さっきは相関を捨てていましたが、ある程度相関を拾ってあげることで近似精度を上げようという方法です。
最後に
メモリに優しい形の式を導出します。見やすさのために式を再掲しておきます。
\begin{aligned} q_{\mathrm{SoR}}\left(\mathbf{f}_{*} | \mathbf{y}\right) &=\mathcal{N}\left(Q_{*, \mathbf{f}}\left(Q_{\mathbf{f}, \mathbf{f}}+\sigma_{\text {noise }}^{2} I\right)^{-1} \mathbf{y}, Q_{* *}-Q_{*, \mathbf{f}}\left(Q_{\mathbf{f}, \mathbf{f}}+\sigma_{\text {noise }}^{2} I\right)^{-1} Q_{\mathbf{f}, *}\right) \\ &=\mathcal{N}\left(\sigma^{-2} K_{\mathbf{*, u}} \Sigma K_{\mathbf{u,f}},\;\; K_{\mathbf{*, u}} \Sigma K_{\mathbf{u, *}}\right) \\ \end{aligned}
[導出]
上記で与えられたを使って
\begin{aligned} \Sigma &= \left(\sigma^{-2} K_{\mathbf{u}, \mathbf{f}} K_{\mathbf{f}, \mathbf{u}}+K_{\mathbf{u}, \mathbf{u}}\right)^{-1} \\ \Sigma^{-1} &= \sigma^{-2} K_{\mathbf{u}, \mathbf{f}} K_{\mathbf{f}, \mathbf{u}}+K_{\mathbf{u}, \mathbf{u}} \\ \sigma^{2} \Sigma^{-1} &= K_{\mathbf{u}, \mathbf{f}} K_{\mathbf{f}, \mathbf{u}}+\sigma^{2} K_{\mathbf{u}, \mathbf{u}} \\ \sigma^{2} \Sigma^{-1} K_{\mathbf{u}, \mathbf{u}}^{-1} &= K_{\mathbf{u}, \mathbf{f}} K_{\mathbf{f}, \mathbf{u}} K_{\mathbf{u}, \mathbf{u}}^{-1} + \sigma^{2} I \\ \sigma^{2} \Sigma^{-1} K_{\mathbf{u}, \mathbf{u}}^{-1} K_{\mathbf{u}, \mathbf{f}} &= K_{\mathbf{u}, \mathbf{f}} K_{\mathbf{f}, \mathbf{u}} K_{\mathbf{u}, \mathbf{u}}^{-1} K_{\mathbf{u}, \mathbf{f}} + \sigma^{2} K_{\mathbf{u}, \mathbf{f}} \\ \sigma^{2} \Sigma^{-1} K_{\mathbf{u}, \mathbf{u}}^{-1} K_{\mathbf{u}, \mathbf{f}} &= K_{\mathbf{u}, \mathbf{f}} Q_{\mathbf{f}, \mathbf{f}} + \sigma^{2} K_{\mathbf{u}, \mathbf{f}} \\ \sigma^{2} \Sigma^{-1} K_{\mathbf{u}, \mathbf{u}}^{-1} K_{\mathbf{u}, \mathbf{f}} &= K_{\mathbf{u}, \mathbf{f}} \left( Q_{\mathbf{f}, \mathbf{f}} + \sigma^{2} I \right) \\ K_{\mathbf{u}, \mathbf{u}}^{-1} K_{\mathbf{u}, \mathbf{f}} &= \sigma^{-2} \Sigma K_{\mathbf{u}, \mathbf{f}} \left( Q_{\mathbf{f}, \mathbf{f}} + \sigma^{2} I \right) \\ \end{aligned}
くどすぎますが、徹底的に式変形を書いておきました。
これを使って を変形していきましょう。
\begin{aligned} Q_{*, \mathbf{f}}\left(Q_{\mathbf{f}, \mathbf{f}}+\sigma^{2} I\right)^{-1} &= K_{*, \mathbf{u}} K_{\mathbf{u, u}}^{-1} K_{\mathbf{u,f}} \left(Q_{\mathbf{f}, \mathbf{f}}+\sigma^{2} I \right)^{-1} \\ &= K_{\mathbf{*,u}} \sigma^{-2} \Sigma K_{\mathbf{u}, \mathbf{f}}\left(Q_{\mathbf{f}, \mathbf{f}}+\sigma^{2} I\right) \left(\mathbf{Q}_{\mathbf{f}, \mathbf{f}}+\sigma^{2} \mathbf{I}\right)^{-1} \\ &=\sigma^{-2} K_{*, \mathbf{u}} \Sigma K_{\mathbf{u}, \mathbf{f}} \end{aligned}
では分散共分散行列も導出していきましょう。
\begin{aligned} Q_{*,*}-Q_{*, \mathbf{f}}\left(Q_{\mathbf{f}, \mathbf{f}}+\sigma_{\text {noise }}^{2} I\right)^{-1} Q_{\mathbf{f}, *} \end{aligned}
において、は既に求めたので、
\begin{aligned} Q_{*,*}-Q_{*, \mathbf{f}}\left(Q_{\mathbf{f}, \mathbf{f}}+\sigma_{\text {noise }}^{2} I\right)^{-1} Q_{\mathbf{f}, *} &= K_{\mathbf{*,u}} K_{\mathbf{u,u}}^{-1} K_{\mathbf{u,*}} -\sigma^{-2} K_{\mathbf{*,u}} \Sigma K_{\mathbf{u,f}} K_{\mathbf{f,u}} K_{\mathbf{u,u}}^{-1} K_{\mathbf{u,*}} \\ &= K_{\mathbf{*,u}} \left\{I - \sigma^{-2} \Sigma K_{\mathbf{u,f}} K_{\mathbf{f,u}} \right\} K_{\mathbf{u,u}}^{-1} K_{\mathbf{u,*}} \\ &= K_{\mathbf{*,u}} \Sigma \left\{\Sigma^{-1} - \sigma^{-2} K_{\mathbf{u,f}} K_{\mathbf{f,u}} \right\} K_{\mathbf{u,u}}^{-1} K_{\mathbf{u,*}} \\ &= K_{\mathbf{*,u}} \Sigma \left\{\sigma^{-2} K_{\mathbf{u,f}} K_{\mathbf{f,u}} + K_{\mathbf{u,u}} - \sigma^{-2} K_{\mathbf{u,f}} K_{\mathbf{f,u}} \right\} K_{\mathbf{u,u}}^{-1} K_{\mathbf{u,*}} \\ &= K_{\mathbf{*,u}} \Sigma \left\{K_{\mathbf{u,u}} \right\} K_{\mathbf{u,u}}^{-1} K_{\mathbf{u,*}} \\ &= K_{\mathbf{*,u}} \Sigma K_{\mathbf{u,*}} \end{aligned}
と導けます。以上でメモリに優しい式の形を導出できました。