はじめに
$f\sim\mathcal{GP}(0,k)$ から得られる観測を1点ずつ加えて事後分布を $n$ 回逐次更新した結果と、$n$ 点のデータ集合 $\mathcal{D}_n$ をまとめて条件付けて一度に計算した事後分布が同一であることを示します。
設定
次の設定を仮定します。
- $f \sim \mathcal{GP}(0, k)$: 目的関数 $f$ は平均 $0$、カーネル関数 $k(x, x')$ のガウス過程に従う
- $\mathcal{X}$: 有限集合である入力空間
- $x_t$: 入力空間 $\mathcal{X}$ の中で獲得関数を最大化する点 ($t > 1$)
- $y_t = f(x_t) + \varepsilon_t$: 入力点 $x_t$ に対する観測
- $\varepsilon_t \sim \mathrm{i.i.d.}\ \mathcal{N}(0, \sigma^2)$: 観測ノイズ
- $\mathcal{D}_t = \{(x_i, y_i)\}_{i=1}^{t}$: $t$ ステップまでに得られたデータ集合
記号
証明では次の記号を用います。
- $k(x, x')$: カーネル関数
- $\bm{k}_n(x) = [k(x, x_1),\ k(x, x_2),\ \dots,\ k(x, x_n)]^\top$
- $\bm{K}_n$: カーネル行列($(i, j)$ 成分が $k(x_i, x_j)$ である $n \times n$ 行列)
- $\tilde{\bm{K}}_n = \bm{K}_n + \sigma^2 \bm{I}_n$
逐次更新の場合
観測1回目 ($t=1$)
入力空間 $\mathcal{X}$ の中で一様分布に従って $x_1$ を選択します。関数 $f$ は $\mathcal{GP}(0, k)$ に従うので
$$f(x_1) \mid x_1 \sim \mathcal{N}(0, k(x_1, x_1))$$となります。この $x_1$ に対して観測 $y_1 = f(x_1) + \varepsilon_1$ を得ると、データ $\mathcal{D}_1$ が定まります。
$f \mid \mathcal{D}_1$ もガウス過程に従うので、その平均関数・カーネル関数を $\mu_1, k_1$ とすれば
$$ f \mid \mathcal{D}_1 \sim \mathcal{GP}(\mu_1, k_1) $$と書けます。
観測2回目 ($t=2$)
$x_2 = \arg \max_{x \in \mathcal{X}} \alpha(x \mid \mathcal{D}_1)$ として $x_2$ を選択します。従って以下では $\mathcal{D}_1$ で条件付けた状況を考えます。まず $f(x), f(x'), y_2$ の同時分布を書き下し、$y_2$ の観測値で条件付けると、条件付きガウス分布の公式から次のようになります。
$$\begin{bmatrix} f(x) \\ f(x') \end{bmatrix} \mid y_2, \mathcal{D}_1 \sim \mathcal{N}(\bar{\bm{\mu}}, \bar{\bm{\Sigma}})$$$$\bar{\bm{\mu}} = \begin{bmatrix} \mu_1(x) \\ \mu_1(x') \end{bmatrix} + \begin{bmatrix} k_1(x, x_2) \\ k_1(x', x_2) \end{bmatrix} \frac{y_2 - \mu_1(x_2)}{k_1(x_2, x_2) + \sigma^2}$$$$\bar{\bm{\Sigma}} = \begin{bmatrix} k_1(x, x) & k_1(x, x')\\ k_1(x', x) & k_1(x', x') \end{bmatrix} - \begin{bmatrix} k_1(x, x_2) \\ k_1(x', x_2) \end{bmatrix} \frac{\begin{bmatrix} k_1(x_2, x) & k_1(x_2, x') \end{bmatrix}}{k_1(x_2, x_2) + \sigma^2}$$これらは任意の有限個の点について同様に拡張できるため、$f \mid \mathcal{D}_2$ もガウス過程に従います。$\bar{\bm{\mu}}$ と $\bar{\bm{\Sigma}}$ の成分をそのまま読み取ることで、新たな事後分布 $\mathcal{GP}(\mu_2, k_2)$ の平均関数・カーネル関数は次のように求まります。
$$\mu_2(x) = \mu_1(x) + k_1(x, x_2) \frac{y_2 - \mu_1(x_2)}{k_1(x_2, x_2) + \sigma^2}$$$$k_2(x, x') = k_1(x, x') - \frac{k_1(x, x_2) k_1(x_2, x')}{k_1(x_2, x_2) + \sigma^2}$$観測$n$回目 ($t=n$)
ここでは $t = n-1$ の事後分布、すなわち $\mu_{n-1}, k_{n-1}$ が与えられているとして、そこから $\mu_n, k_n$ を導きます。$\mathcal{D}_{n-1}$ で条件付けた状況では $f$ は $\mathcal{GP}(\mu_{n-1}, k_{n-1})$ に従います。$t=2$ のときと同様に、$f(x), f(x'), y_n$ の同時分布を書き下し、$y_n$ の観測値で条件付けると、条件付きガウス分布の公式から次のようになります。
$$\begin{bmatrix} f(x) \\ f(x') \end{bmatrix} \mid y_n, \mathcal{D}_{n-1} \sim \mathcal{N}(\bar{\bm{\mu}}, \bar{\bm{\Sigma}})$$$$\bar{\bm{\mu}} = \begin{bmatrix} \mu_{n-1}(x) \\ \mu_{n-1}(x') \end{bmatrix} + \begin{bmatrix} k_{n-1}(x, x_n) \\ k_{n-1}(x', x_n) \end{bmatrix} \frac{y_n - \mu_{n-1}(x_n)}{k_{n-1}(x_n, x_n) + \sigma^2}$$$$\bar{\bm{\Sigma}} = \begin{bmatrix} k_{n-1}(x, x) & k_{n-1}(x, x') \\ k_{n-1}(x', x) & k_{n-1}(x', x') \end{bmatrix} - \begin{bmatrix} k_{n-1}(x, x_n) \\ k_{n-1}(x', x_n) \end{bmatrix} \frac{\begin{bmatrix} k_{n-1}(x_n, x) & k_{n-1}(x_n, x') \end{bmatrix}}{k_{n-1}(x_n, x_n) + \sigma^2}$$ここから $\bar{\bm{\mu}}$ と $\bar{\bm{\Sigma}}$ の成分を読み取ることで、$f \mid \mathcal{D}_n \sim \mathcal{GP}(\mu_n, k_n)$ の平均関数とカーネル関数は次のように得られます。
$$\mu_n(x) = \mu_{n-1}(x) + k_{n-1}(x, x_n) \frac{y_n - \mu_{n-1}(x_n)}{k_{n-1}(x_n, x_n) + \sigma^2} \tag{1a}$$$$k_n(x, x') = k_{n-1}(x, x') - \frac{k_{n-1}(x, x_n) k_{n-1}(x_n, x')}{k_{n-1}(x_n, x_n) + \sigma^2} \tag{2a}$$事前分布の平均関数とカーネル関数を $\mu_0 = 0, k_0=k$と置けば、この漸化式は $t=1$ の場合も含め、任意の $n \in \mathbb{N}$ について成り立ちます。
$\mathcal{D}_n$ を用いて計算する場合
ガウス過程回帰では、事後分布 $f \mid \mathcal{D}_n \sim \mathcal{GP}(\mu_n, k_n)$ の平均関数・カーネル関数が次のように書けることが知られています。
$$ \mu_n(x) = \bm{k}_n(x)^\top (\bm{K}_n + \sigma^2 \bm{I}_n)^{-1} \bm{y}_n \tag{1b} $$$$ k_n(x, x') = k(x, x') - \bm{k}_n(x)^\top (\bm{K}_n + \sigma^2 \bm{I}_n)^{-1} \bm{k}_n(x') \tag{2b} $$ここで、逐次更新で得た式 (1a)(2a) と、これらの式 (1b)(2b) がそれぞれ一致することを確かめます。方針は、(1b)(2b) が $n-1$ で成り立つと仮定し、そこから $n$ の場合を計算して (1a)(2a) を再現する帰納法です。
準備: カーネル行列の逆行列
$\tilde{\bm{K}}_{n}$ を、最初の $n-1$ 点ぶんのブロックと $n$ 番目の点とに分けてブロック行列として表すと次のようになります。
$$ \tilde{\bm{K}}_{n} = \begin{bmatrix} \bm{K}_{n-1} + \sigma^2 \bm{I}_{n-1} & \bm{k}_{n-1}(x_{n}) \\ \bm{k}_{n-1}(x_{n})^\top & k(x_{n}, x_n) + \sigma^2 \end{bmatrix} $$左上のブロックに関するシューア補行列を $s$ とします。これを計算すると、(2b) を $n-1$ の場合に $x = x' = x_n$ として用いることで、次のように簡単な形になります。
$$ \begin{aligned} s &= k(x_n, x_n) + \sigma^2 - \bm{k}_{n-1}(x_n)^\top \tilde{\bm{K}}_{n-1}^{-1} \bm{k}_{n-1}(x_n) \\ &= k_{n-1}(x_n, x_n) + \sigma^2 \end{aligned} $$これを用いて $\tilde{\bm{K}}_{n}$ の逆行列を表すと
$$ \tilde{\bm{K}}_{n}^{-1} = \begin{bmatrix} \tilde{\bm{K}}_{n-1}^{-1} + \frac{1}{s} \tilde{\bm{K}}_{n-1}^{-1} \bm{k}_{n-1}(x_n) \bm{k}_{n-1}(x_n)^\top \tilde{\bm{K}}_{n-1}^{-1} & -\frac{1}{s} \tilde{\bm{K}}_{n-1}^{-1} \bm{k}_{n-1}(x_n) \\ -\frac{1}{s} \bm{k}_{n-1}(x_n)^\top \tilde{\bm{K}}_{n-1}^{-1} & \frac{1}{s} \end{bmatrix} $$が得られます。
(1a)と(1b)の一致
(1b) の右辺 $\mu_n(x) = \bm{k}_n(x)^\top \tilde{\bm{K}}_n^{-1} \bm{y}_n$ を展開するために、まず $\tilde{\bm{K}}_n^{-1} \bm{y}_n$ を、準備の節で得たブロック逆行列を使って計算します。各ブロックを掛け合わせ、$\mu_{n-1}(x_n) = \bm{k}_{n-1}(x_n)^\top \tilde{\bm{K}}_{n-1}^{-1} \bm{y}_{n-1}$ ((1b) を $n-1$ で適用したもの)を用いて整理すると、
$$ \begin{aligned} \tilde{\bm{K}}_n^{-1} \begin{bmatrix} \bm{y}_{n-1} \\ y_n \end{bmatrix} &= \begin{bmatrix} \tilde{\bm{K}}_{n-1}^{-1}\bm{y}_{n-1} + \frac{1}{s}\tilde{\bm{K}}_{n-1}^{-1}\bm{k}_{n-1}(x_n) \bm{k}_{n-1}(x_n)^\top\tilde{\bm{K}}_{n-1}^{-1}\bm{y}_{n-1} - \frac{1}{s}\tilde{\bm{K}}_{n-1}^{-1}\bm{k}_{n-1}(x_n) y_n \\ -\frac{1}{s}\bm{k}_{n-1}(x_n)^\top\tilde{\bm{K}}_{n-1}^{-1}\bm{y}_{n-1} + \frac{1}{s}y_n \end{bmatrix} \\ &= \begin{bmatrix} \tilde{\bm{K}}_{n-1}^{-1}\bm{y}_{n-1} - \tilde{\bm{K}}_{n-1}^{-1}\bm{k}_{n-1}(x_n) \frac{y_n - \mu_{n-1}(x_n)}{s} \\ \frac{y_n - \mu_{n-1}(x_n)}{s} \end{bmatrix} \end{aligned} $$となります。これを (1b) に代入します。$\bm{k}_n(x)^\top$ も $n-1$ 点ぶんと $n$ 番目に分けて掛けると、$\mu_{n-1}(x) = \bm{k}_{n-1}(x)^\top \tilde{\bm{K}}_{n-1}^{-1} \bm{y}_{n-1}$ がそのまま現れ、残る角括弧の中は (2b) を $n-1$ で適用すると $k_{n-1}(x, x_n)$ になります。
$$ \begin{aligned} \mu_n(x) &= \begin{bmatrix} \bm{k}_{n-1}(x)^\top & k(x, x_n) \end{bmatrix} \tilde{\bm{K}}_n^{-1} \begin{bmatrix} \bm{y}_{n-1} \\ y_n \end{bmatrix} \\ &= \begin{bmatrix} \bm{k}_{n-1}(x)^\top & k(x, x_n) \end{bmatrix} \begin{bmatrix} \tilde{\bm{K}}_{n-1}^{-1}\bm{y}_{n-1} - \tilde{\bm{K}}_{n-1}^{-1}\bm{k}_{n-1}(x_n) \frac{y_n - \mu_{n-1}(x_n)}{s} \\ \frac{y_n - \mu_{n-1}(x_n)}{s} \end{bmatrix} \\ &= \mu_{n-1}(x) + \left[ k(x, x_n) - \bm{k}_{n-1}(x)^\top \tilde{\bm{K}}_{n-1}^{-1}\bm{k}_{n-1}(x_n) \right] \frac{y_n - \mu_{n-1}(x_n)}{s} \\ &= \mu_{n-1}(x) + k_{n-1}(x, x_n) \frac{y_n - \mu_{n-1}(x_n)}{k_{n-1}(x_n, x_n) + \sigma^2} \end{aligned} $$最後の行は (1a) に一致します。
(2a)と(2b)の一致
次に $k_n$ について確かめます。同じ手順で、$\tilde{\bm{K}}_n^{-1}$ を $\bm{y}_n$ のかわりにベクトル $[\bm{k}_{n-1}(x')^\top, k(x_n, x')]^\top$ に掛けます。ブロックごとに整理すると、(2b) を $n-1$ で用いることで $k_{n-1}(x_n, x')$ が現れます。
$$ \begin{aligned} \tilde{\bm{K}}_n^{-1} \begin{bmatrix} \bm{k}_{n-1}(x') \\ k(x_n, x') \end{bmatrix} &= \begin{bmatrix} \tilde{\bm{K}}_{n-1}^{-1}\bm{k}_{n-1}(x') + \frac{1}{s}\tilde{\bm{K}}_{n-1}^{-1}\bm{k}_{n-1}(x_n)\bm{k}_{n-1}(x_n)^\top\tilde{\bm{K}}_{n-1}^{-1}\bm{k}_{n-1}(x') - \frac{1}{s}\tilde{\bm{K}}_{n-1}^{-1}\bm{k}_{n-1}(x_n) k(x_n, x') \\ -\frac{1}{s}\bm{k}_{n-1}(x_n)^\top\tilde{\bm{K}}_{n-1}^{-1}\bm{k}_{n-1}(x') + \frac{1}{s}k(x_n, x') \end{bmatrix} \\ &= \begin{bmatrix} \tilde{\bm{K}}_{n-1}^{-1}\bm{k}_{n-1}(x') - \tilde{\bm{K}}_{n-1}^{-1}\bm{k}_{n-1}(x_n) \frac{k(x_n, x') - \bm{k}_{n-1}(x_n)^\top\tilde{\bm{K}}_{n-1}^{-1}\bm{k}_{n-1}(x')}{s} \\ \frac{k(x_n, x') - \bm{k}_{n-1}(x_n)^\top\tilde{\bm{K}}_{n-1}^{-1}\bm{k}_{n-1}(x')}{s} \end{bmatrix} \\ &= \begin{bmatrix} \tilde{\bm{K}}_{n-1}^{-1}\bm{k}_{n-1}(x') - \tilde{\bm{K}}_{n-1}^{-1}\bm{k}_{n-1}(x_n) \frac{k_{n-1}(x_n, x')}{s} \\ \frac{k_{n-1}(x_n, x')}{s} \end{bmatrix} \end{aligned} $$これを (2b) の二次形式 $\bm{k}_n(x)^\top \tilde{\bm{K}}_n^{-1} \bm{k}_n(x')$ に代入します。$\bm{k}_n(x)^\top$ をブロックに分けて掛けると、$n-1$ の場合の二次形式が現れ、残りは (2b) を $n-1$ で用いて $k_{n-1}(x, x_n)$ にまとまります。
$$ \begin{aligned} \bm{k}_n(x)^\top \tilde{\bm{K}}_n^{-1} \bm{k}_n(x') &= \begin{bmatrix} \bm{k}_{n-1}(x)^\top & k(x, x_n) \end{bmatrix} \tilde{\bm{K}}_n^{-1} \begin{bmatrix} \bm{k}_{n-1}(x') \\ k(x_n, x') \end{bmatrix} \\ &= \begin{bmatrix} \bm{k}_{n-1}(x)^\top & k(x, x_n) \end{bmatrix} \begin{bmatrix} \tilde{\bm{K}}_{n-1}^{-1}\bm{k}_{n-1}(x') - \tilde{\bm{K}}_{n-1}^{-1}\bm{k}_{n-1}(x_n) \frac{k_{n-1}(x_n, x')}{s} \\ \frac{k_{n-1}(x_n, x')}{s} \end{bmatrix} \\ &= \bm{k}_{n-1}(x)^\top \tilde{\bm{K}}_{n-1}^{-1}\bm{k}_{n-1}(x') - \bm{k}_{n-1}(x)^\top \tilde{\bm{K}}_{n-1}^{-1}\bm{k}_{n-1}(x_n)\frac{k_{n-1}(x_n, x')}{s} + k(x, x_n)\frac{k_{n-1}(x_n, x')}{s} \\ &= \bm{k}_{n-1}(x)^\top \tilde{\bm{K}}_{n-1}^{-1}\bm{k}_{n-1}(x') + \left[ k(x, x_n) - \bm{k}_{n-1}(x)^\top \tilde{\bm{K}}_{n-1}^{-1}\bm{k}_{n-1}(x_n) \right] \frac{k_{n-1}(x_n, x')}{s} \\ &= \bm{k}_{n-1}(x)^\top \tilde{\bm{K}}_{n-1}^{-1}\bm{k}_{n-1}(x') + k_{n-1}(x, x_n) \frac{k_{n-1}(x_n, x')}{s} \end{aligned} $$最後にこれを (2b) の定義式に戻します。$k(x, x') - \bm{k}_{n-1}(x)^\top \tilde{\bm{K}}_{n-1}^{-1}\bm{k}_{n-1}(x')$ の部分は、(2b) を $n-1$ で用いるとちょうど $k_{n-1}(x, x')$ になります。
$$ \begin{aligned} k_n(x,x') &= k(x,x') - \bm{k}_n(x)^\top \tilde{\bm{K}}_n^{-1} \bm{k}_n(x') \\ &= k(x,x') - \bm{k}_{n-1}(x)^\top \tilde{\bm{K}}_{n-1}^{-1}\bm{k}_{n-1}(x') - \frac{k_{n-1}(x, x_n)k_{n-1}(x_n, x')}{k_{n-1}(x_n, x_n) + \sigma^2} \\ &= k_{n-1}(x,x') - \frac{k_{n-1}(x, x_n)k_{n-1}(x_n, x')}{k_{n-1}(x_n, x_n) + \sigma^2} \end{aligned} $$これは (2a) に一致します。