カーネルリッジ回帰のお気持ち

カーネルリッジ回帰に関する僕の理解をまとめておきます。

線形回帰とは、

$$y = w^\top x + \varepsilon \quad (\varepsilon \sim N(0, \sigma^2))$$

というモデルを仮定し、観測データに対して $w$ を最尤推定（あるいは最小二乗）する問題である。

ここで入力 $x \in \mathbb{R}^N$ に対し，特徴量写像 $\phi: \mathbb{R}^N \to \mathbb{R}^M$ を考える：

$$\phi(x) = \begin{pmatrix} \phi_0(x) \\ \phi_1(x) \\ \vdots \\ \phi_{M-1}(x) \end{pmatrix}.$$

このとき

$$y = w^\top \phi(x) + \varepsilon$$

というモデルを仮定し，データからパラメータ $w \in \mathbb{R}^M$ を推定する。各 $\phi_i$ を基底関数と呼び，このような回帰手法を基底関数回帰（basis function regression）という。

ところで，学習データ $\{\phi(x_i)\}_{i=1}^n$ によって張られる部分空間を考える。このときパラメータ $w$ は，この部分空間に平行な成分と直交する成分に分解できる。

任意の入力 $x$ に対する出力

$$y = w^\top \phi(x)$$

を考えると，$\phi(x)$ は上記部分空間に属するため，$w$ の直交成分は出力に影響を及ぼさない。また，リッジ回帰では $\|w\|^2$ を正則化項として最小化するため，最適解において直交成分は 0 となる。

よって最適なパラメータ $w^*$ は，高次元特徴空間に写像された入力の線形結合として

$$w^* = \sum_{i=1}^n \alpha_i \phi(x_i)$$

と表される。

（なお，$\phi(x)$ の次元が入力数より小さい場合でも，この場合は自明に $w$ は $\phi(x_i)$ の線形結合として書くことができる。）

これをモデル式に代入すると

$$y = \sum_{i=1}^n \alpha_i \phi(x_i)^\top \phi(x)$$

となる。したがって，$w$ を直接求める代わりに係数 $\alpha_i$ を求めればよい。

ここで特徴量写像 $\phi$ に対し，カーネル関数

$$K(x, x') = \phi(x)^\top \phi(x')$$

を定義する。これは，$\phi$ を明示的に定める代わりに，内積として定義される関数 $K$ を直接与えるという立場である。すなわち，あるカーネル関数 $K$ に対して，これを内積として実現する特徴量写像 $\phi$ が存在すれば十分である。

例えば，カーネル関数として

$$K(x, x') = x^\top x'$$

を採用した場合，対応する特徴量写像 $\phi$ は恒等写像である。(この場合はリッジ回帰と同じ問題設定になるので意味がない)

一般に，適切な条件を満たす任意のカーネル関数に対して，それを内積として表現する特徴量写像 $\phi$ が存在することが知られている。したがって，特徴量写像 $\phi$ を直接定義する代わりに，カーネル関数 $K$ を定義すればよい。

特に，無限次元の特徴空間への写像を考える場合，$\phi$ を明示的に書き下すことは困難であるが，カーネル関数を用いれば $\phi$ を陽に扱うことなく計算を行うことができる。

カーネル関数は $\phi(x)^\top \phi(x')$ として定義されることから，特徴空間における二つの入力 $x, x'$ の類似度を表している。

カーネル関数は入力空間上の関数によって特徴空間の内積を表している。

例えば，$x, x' \in \mathbb{R}^2$ として

$$K(x, x') = (x^\top x')^2$$

と定義すると，

$$\begin{aligned} (x^\top x')^2 &= (x_1 x'_1 + x_2 x'_2)^2 \\ &= x_1^2 {x'_1}^2 + 2 x_1 x_2 x'_1 x'_2 + x_2^2 {x'_2}^2 \\ &= \begin{pmatrix} x_1^2 \\ \sqrt{2} x_1 x_2 \\ x_2^2 \end{pmatrix}^\top \begin{pmatrix} {x'_1}^2 \\ \sqrt{2} x'_1 x'_2 \\ {x'_2}^2 \end{pmatrix} \end{aligned}$$

より，関数 $K$ は入力空間上の計算だけで，三次元の特徴空間への写像

$$\phi(x) = \begin{pmatrix} x_1^2 \\ \sqrt{2} x_1 x_2 \\ x_2^2 \end{pmatrix}$$

における内積を計算していることになる。

カーネル関数が対称かつ半正定値であれば，それに対応する特徴空間が存在することが知られている（Mercerの定理）。

ここで力尽きたので結果だけ書くと，学習データ $(x_1, y_1), \ldots, (x_n, y_n)$ に対してリッジ回帰の解は

$$\alpha = (K + \lambda I)^{-1} y$$

となる。ここで $K$ はグラム行列（$K_{ij} = K(x_i, x_j)$），$\lambda$ は正則化パラメータ，$y = (y_1, \ldots, y_n)^\top$ は出力ベクトルである。

また，任意の入力 $x$ に対する予測は

$$\hat{y} = \sum_{i=1}^n \alpha_i K(x_i, x) = k(x)^\top \alpha$$

と求められる。ここで $k(x) = (K(x_1, x), \ldots, K(x_n, x))^\top$ である。

つまり，予測時には $\alpha$ だけでなく学習データ $\{x_i\}_{i=1}^n$ も保持しておかなければならない。カーネルを使わない通常の回帰ではパラメータ $w$ だけで予測できたので，なんだが残念な気もする。