$d$個の数値を並べた変数$\mathbf{x}=(x_1,x_2,\ldots,x_d)^{\mathrm T}$から、 $y$という変数を推定する多変量の回帰問題を考えます。 サンプルデータは$n$組あるとし、$i$番目のサンプルを$\mathbf{x}^{(i)}, y^{(i)}$と書くことにします。
線形モデル
まず、カーネルを使わない線形モデル
$$y = \mathbf w^\mathrm T \mathbf x$$
を考えましょう。これは、データを原点を通る直線で当てはめることを意味します。 直線からのズレに対して、損失を
$$r(y,\mathbf{x};\mathbf{w}) = (y-\mathbf w^\mathrm T \mathbf x)^2$$
として定義し、全てのサンプルの総和
$$R(\mathbf{w}) = \sum_{j=1}^n r(y,\mathbf{x};\mathbf{w})$$
を考えます。$R(\mathbf{w})$は
$$\mathbf y := \left( \begin{array}{ccc} y^{(1)}\newline y^{(2)}\newline \vdots\newline y^{(n)} \end{array} \right) $$ $$X := \left( \begin{array}{ccc} x_1^{(1)} & \cdots & x_d^{(1)}\newline x_1^{(2)} & \cdots & x_d^{(2)}\newline \vdots& & \vdots\newline x_1^{(n)} & \cdots & x_d^{(n)} \end{array} \right) $$
を用いて、
$$R(\mathbf{w})=(\mathbf y-X\mathbf w)^\mathrm T(\mathbf y-X\mathbf w)$$
と表せます。 これを最小化する重み$\mathbf{\hat w}$は
$$\mathbf{\hat w} = (X^\mathrm T X)^{-1}X^\mathrm T\mathbf y$$
と求めることができます（$R$を$\mathbf w$で微分して、$0$となる点を求める。ここで$X^\mathrm T X$は逆行列を持つとした）。
非線形モデル
さて、このような線形モデルではどう頑張っても$\mathbf x$と$y$の直線的な関係しか表せません。 そこで、$\mathbf x$に何らかの非線形変換$\mathbf{\phi}(\cdot)$を施して
$$y = \mathbf w^\mathrm T \mathbf{\phi}(\mathbf x)$$
というモデルを用いて回帰を行うことを考えます。 ここで$\mathbf{\phi}$はd個の非線形変換$\phi_1, \ldots, \phi_d$を用いて $\mathbf{\phi}(\mathbf x) = ( \phi_1(\mathbf x),\ldots,\phi_d(\mathbf x))$と定義しました（変換前後の特徴ベクトルの次元$d$は必ずしも一致する必要はないが、違う文字を導入するのが面倒なため揃えた）。 例えば、元々1次元の入力$x\in\mathbb R$を用いた場合、$\mathbf{\phi}(x):=(x, x^2,\ldots,x^d)$などの非線形変換が考えられます。
このモデルは、$\mathbf x$については非線形ですが、$\mathbf w$については線形なので、先ほどの線形モデルの場合と 同様な最適化問題に帰着することができます。 すなわち
$$r_\text{}(y,\mathbf{x};\mathbf{w}) = (y-\mathbf w^\mathrm T \mathbf{\phi}(\mathbf x))^2,$$
$$R(\mathbf{w}) = \sum_{j=1}^n r(y,\mathbf{x};\mathbf{w})$$
とすると、$R$を最小化する$\mathbf{\hat w}$は
$$\mathbf{\hat w} = (\Phi^\mathrm T \Phi)^{-1}\Phi^\mathrm T\mathbf y$$
と計算できます（$\Phi$は、$X$と同様にして$\phi$を並べた行列）。
正則化
非線形回帰において、特徴ベクトルは高次元であるほど、データへの当てはめはよくなります。 しかしながら、既知のデータに過度に適合しすぎて、未知の入力への当てはめ（汎化性能）は悪くなってしまうという問題（過学習）も生じてしまいます。 そこで、損失関数$R$に対して、正則化項を加えた
$$R(\mathbf{w}) = \sum_{j=1}^n r(y,\mathbf{x};\mathbf{w}) + \lambda \mathbf{w}^\mathrm T \mathbf{w}$$
を最小化することがよく行われます。 この場合の最適解$\mathbf{\hat w}$は
$$\mathbf{\hat w} = (\Phi^\mathrm T \Phi + \lambda I)^{-1}\Phi^\mathrm T\mathbf y$$
と計算できます（正則化項を加えると、汎化性能が向上するメカニズムについては、今回は省略。いつかまとめたい）。
カーネルを用いた表現
ここでもう一歩踏み込んで、カーネル関数を導入します。 カーネル関数は、2つの入力$\mathbf{x}=(x_1,x_2,\ldots,x_d)^{\mathrm T}$と$\mathbf{x}’=(x_1’,x_2’,\ldots,x_d’)^{\mathrm T}$ から計算される関数$k(\mathbf x, \mathbf x’)$です。
そのもっとも素朴な定義は
$$k(\mathbf x, \mathbf x’) = \mathbf{\phi}(\mathbf x)^\mathrm T \mathbf{\phi}(\mathbf x’)$$
です。このように定義されたカーネル関数ですが、実は先ほどの非線形の回帰の最適解はカーネル関数の線形和を用いて表すことができます。このことは、次のリプレゼンター定理として知られています。
リプレゼンター定理
先ほどの正則化項つきの$R$を最小化した結果得られる重み$\mathbf{\hat w}$は
$$\mathbf{\hat w} = \sum_{i=1}^n\alpha_i\mathbf{\phi}(\mathbf x^{(i)})$$
の形で表せる。
証明については割愛します。
リプリゼンター定理により、回帰問題$\mathbf w$を推定する問題から、$\mathbf\alpha:=(\alpha_1,\ldots,\alpha_n)^\mathrm T$を推定する問題に変化したと言えます。 ここで、$\mathbf w$は$d$次元であるのに対して、$\alpha$は$n$次元です。 したがって、特徴ベクトルの次元より、サンプルのサイズが小さい時に、リプレゼンター定理は、回帰問題の解に「コンパクトな」表現を与えてくれると言えそうです。
実際に$\mathbf \alpha$を推定してみましょう。 今考えるべき関数の形は、リプレゼンター定理により、
$$f(\mathbf x) = \sum_i \alpha_i\mathbf{\phi}(\mathbf x_i)^\mathrm T\mathbf{\phi}(\mathbf x)=\sum_i \alpha_ik(\mathbf x^{(i)},\mathbf x)$$
の形に絞られています。 そこで損失関数を$\mathbf w, \mathbf\phi$を使った表現から、$\mathbf \alpha, k$を用いた表現に書き換えると
$$R(\alpha) = (\mathbf y - K \mathbf\alpha)^\mathrm T(\mathbf y - K \mathbf\alpha) + \lambda\mathbf\alpha^\mathrm TK\mathbf\alpha$$
が得られます。ここで、$K$はグラム行列と呼ばれる行列で、
$$K := \left( \begin{array}{ccc} k(\mathbf x^{(1)},\mathbf x^{(1)}) & \cdots & k(\mathbf x^{(n)},\mathbf x^{(1)})\newline \vdots & & \vdots\newline k(\mathbf x^{(1)},\mathbf x^{(n)}) & \cdots & k(\mathbf x^{(n)},\mathbf x^{(n)}) \end{array} \right) $$
と定義されます。 したがって、もし$K$が正則ならば、先ほどと同様にして
$$\alpha = (K^\mathrm T K + \lambda I)^{-1}K^\mathrm T \mathbf y$$
と解くことができます（実は$K$が対称であることから、$\alpha = (K+\lambda i)^{-1}y$として解くことまで可能です）。
カーネルから特徴ベクトルを導出する
先ほどまでは、元々の特徴ベクトル$\mathbf x$を非線形変換した$\phi(\mathbf x)$を用いて、その内積でカーネル$k(\mathbf x, \mathbf x’)$を導出しました。 実は、逆にある性質を満たす関数をカーネルとして用意してあげれば、それに対応する特徴ベクトルが存在することが知られています。 その性質とは、カーネルが正定値であること、すなわちグラム行列$K$の二次形式が常に非負であることです（マーサーの定理）。 この正定値性をカーネルの定義とすれば、特徴ベクトル$\phi(\mathbf x)$を陽に意識することなく、計算量を削減することができます。 このことを、カーネルトリックと言います。
カーネルトリックの例をあげましょう。
$$k(\mathbf x,\mathbf x’) = \exp (-\beta|\mathbf x - \mathbf x’|^2)$$
とカーネルを定義します。このカーネルはガウスカーネルと呼ばれています。 証明は割愛しますが、ガウスカーネルは正定値であり、1次元の$x$のときに対応する特徴ベクトルは
$$ \mathbf\phi(x) = \left\{ \left(\frac{4\beta}{\pi}\right)^{1/4}\exp(-2\beta(z-x)^2) \mid z\in\mathbb R \right\} $$
という無限次元ベクトルになります。 この場合、積和だった内積は
$$\int_\mathbb R \mathbf\phi_z(x)^{\mathrm T} \mathbf\phi_z(x’)dz$$
という積分の形になります（$\phi_z(x) = \left(\frac{4\beta}{\pi}\right)^{1/4}\exp(-2\beta(z-x)^2)$とおいた）。
省略しますが、$n$次元の場合についても同様のことが言えます。
グラム行列から特徴ベクトルを導出する
実は、さらに強い事実として、つぎのカーネル関数存在定理が成り立ちます。
カーネル関数存在定理
サンプルと同じサイズの任意の正定値行列$K$が与えられたとき、ある特徴ベクトル$\phi(\mathbf x^{(i)})$が存在し、それに対応するカーネル関数の定めるグラム行列が$K$になる。
この定理は、勝手に正定値行列を作ってしまえば、それをカーネル関数のグラム行列としてみなせることを意味しており、非常に強い結果だと言えます。 ただし、適当に正定値行列を作ったとき、それがデータと全く無関係になってしまうこともありうるので、設計に注意が必要です。 また、カーネル関数を設計する場合と違って、全ての入力データに対してグラム行列を作成する必要があるため、使い所は限られると言えるでしょう。