カーネル法による正則化最小二乗法（１） - 機械学習に詳しくなりたいブログ

先回、カーネル法でカーネル関数の定義を確認しました。今回は正則化最小二乗法の誤差関数を式変形する過程でカーネル関数が現れるっていうことを確認します。

さて、線形回帰における正則化最小二乗法の誤差関数は

$E(\mathbf{w}) = \displaystyle \frac{1}{2} \|\mathbf X \mathbf w - \mathbf t \|^2 + \frac{\lambda}{2}\| \mathbf{w}\|^2 \tag{1}$

でした。式(1)は、

$\displaystyle E(\mathbf{w}) = \frac{1}{2} (\mathbf{w}^{T}\mathbf{X}^{T} \mathbf X \mathbf w - \mathbf{w}^{T}\mathbf{X}^{T}\mathbf{t} -\mathbf{t}^{T}\mathbf X \mathbf w +\mathbf{t}^{T}\mathbf{t})+\frac{1}{2}\lambda \mathbf{w}^{T}\mathbf{w} \tag{2}$

のように展開できます。途中の式は最小二乗法の解の導出の式(6)～(7)とほとんど同じですので省略します。

ここで誤差関数の勾配はベクトルの微分より、

$\begin{eqnarray*} \displaystyle \frac{\partial E(\mathbf{w})}{\partial \mathbf{w}} &=& \displaystyle \frac{1}{2} (\mathbf{X}^{T}\mathbf{X}+(\mathbf{X}^{T}\mathbf{X})^{T} )\mathbf{w} - \mathbf{X}^{T}\mathbf{t} +\lambda \mathbf{w}\tag{3} \\ &=& \mathbf{X}^{T}\mathbf{X}\mathbf{w} - \mathbf{X}^{T}\mathbf{t} +\lambda \mathbf{w}\tag{4} \end{eqnarray*}$

と計算できますから、 $\displaystyle \frac{\partial E(\mathbf{w})}{\partial \mathbf{w}} = 0$ とすると

$\displaystyle \mathbf{w} = -\frac{1}{\lambda}\mathbf{X}^{T}(\mathbf{t}-\mathbf X \mathbf w ) \tag{5}$

と変形できます（式(5)は右辺にも $\mathbf{w}$ が入っているので、解が求まったわけではありません）。ここで

$\displaystyle \mathbf{a} = -\frac{1}{\lambda}(\mathbf{t}-\mathbf X \mathbf w ) \tag{6}$

とおくと、

$\displaystyle \mathbf{w} = \mathbf{X}^{T}\mathbf{a}\tag{7}$

となります。これを式(2)に代入すると、

$\begin{eqnarray*} \displaystyle E(\mathbf{a}) &=& \frac{1}{2} (\mathbf{a}^{T}\mathbf{X}\mathbf{X}^{T}\mathbf{X}\mathbf{X}^{T}\mathbf{a} - \mathbf{a}^{T}\mathbf{X}\mathbf{X}^{T}\mathbf{t}-\mathbf{t}^{T}\mathbf{X}\mathbf{X}^{T}\mathbf{a} +\mathbf{t}^{T}\mathbf{t}) +\frac{\lambda}{2} \mathbf{a}^{T}\mathbf{X}\mathbf{X}^{T}\mathbf{a} \tag{8}\\ &=& \frac{1}{2} \mathbf{a}^{T}\mathbf{X}\mathbf{X}^{T}\mathbf{X}\mathbf{X}^{T}\mathbf{a} - \mathbf{a}^{T}\mathbf{X}\mathbf{X}^{T}\mathbf{t}+ \frac{1}{2}\mathbf{t}^{T}\mathbf{t} +\frac{\lambda}{2} \mathbf{a}^{T}\mathbf{X}\mathbf{X}^{T}\mathbf{a} \tag{9}\\ \end{eqnarray*}$

となります。 $\mathbf{w}$ の式を $\mathbf{a}$ で書き換えたことを双対表現と呼ぶそうです。呼び方はいいんですが、１つ１つ式を追っていけば、式(9)となることはそんなに難しい計算ではありません。

ここで式(9)に多数現れている $\mathbf{X}\mathbf{X}^{T}$ を考えます。 $\mathbf{X}$ とはそもそも何だったかというと、 $N$ 個の訓練データを行で並べたものでした。列はモデルの次元です。そして $\mathbf{X}\mathbf{X}^{T}$ の $ij$ 成分は、 $i$ 番目のデータと $j$ 番目のデータの内積となっています。特徴ベクトルの内積をカーネル関数と定義しましたので、 $\mathbf{K}=\mathbf{X}\mathbf{X}^{T}$ とすれば、

$\mathbf{K} = \mathbf{X}\mathbf{X}^{T} = \left( \begin{array}{cccc} k(\mathbf{x}_{0},\mathbf{x}_{0}) & k(\mathbf{x}_{0},\mathbf{x}_{1}) & \ldots & k(\mathbf{x}_{0},\mathbf{x}_{N-1}) \\ k(\mathbf{x}_{1},\mathbf{x}_{0}) & k(\mathbf{x}_{1},\mathbf{x}_{1}) & \ldots &k(\mathbf{x}_{1},\mathbf{x}_{N-1}) \\ \vdots & \vdots & \ddots & \vdots \\ k(\mathbf{x}_{N-1},\mathbf{x}_{0}) & k(\mathbf{x}_{N-1},\mathbf{x}_{1}) & \ldots & k(\mathbf{x}_{N-1},\mathbf{x}_{N-1}) \end{array} \right) \tag{10}$

のようにカーネル関数を使って書くことができます。

さて、式(10)を式(9)に代入すれば、

$\displaystyle E(\mathbf{a}) = \frac{1}{2} \mathbf{a}^{T} \mathbf{K} \mathbf{K} \mathbf{a} - \mathbf{a}^{T} \mathbf{K} \mathbf{t}+ \frac{1}{2}\mathbf{t}^{T}\mathbf{t} +\frac{\lambda}{2} \mathbf{a}^{T} \mathbf{K} \mathbf{a} \tag{11}$

となります。式(11)を最小とする $\mathbf{a}$ は、 $\displaystyle \frac{\partial E(\mathbf{a})}{\partial \mathbf{a}} = 0$ を解けば良いので、 $\mathbf{K}=\mathbf{K}^{T}$ であることに注意すれば、ベクトルの微分より

$\begin{eqnarray*} \displaystyle \frac{\partial E(\mathbf{a})}{\partial \mathbf{a}} &=& \frac{1}{2}(\mathbf{K}\mathbf{K} + (\mathbf{K}\mathbf{K})^{T})\mathbf{a} -\mathbf{K}\mathbf{t} +\frac{\lambda}{2}(\mathbf{K} + \mathbf{K}^{T})\mathbf{a} \tag{12} \\ &=& \mathbf{K}\mathbf{K} \mathbf{a} - \mathbf{K}\mathbf{t} +\lambda \mathbf{K}\mathbf{a} \tag{13} \end{eqnarray*}$

となりますから、

$\begin{eqnarray*} \mathbf{K}\mathbf{K} \mathbf{a} - \mathbf{K}\mathbf{t} +\lambda \mathbf{K}\mathbf{a} &=& 0 \tag{14} \\ (\mathbf{K} + \lambda \mathbf{I})\mathbf{a} &=& \mathbf{t} \tag{15} \\ \mathbf{a} &=& (\mathbf{K} + \lambda \mathbf{I})^{-1}\mathbf{t} \tag{16} \\ \end{eqnarray*}$

と求められます。

さて、正則化最小二乗法で求めたかったのは新たな入力 $\mathbf{x}$ に対する予測値 $y(\mathbf{x})$ でした。

$y(\mathbf{x}) = \mathbf{w}^{T} \mathbf{x} \tag{17}$

とモデル化していましたので、式(7)より

$y(\mathbf{x}) =\mathbf{a}^{T}\mathbf{X} \mathbf{x} \tag{18}$

となります。

$\mathbf{X} \mathbf{x} = \left( \begin{array}{c} k(\mathbf{x}_{0},\mathbf{x})\\ k(\mathbf{x}_{1},\mathbf{x}) \\ \vdots \\ k(\mathbf{x}_{N-1},\mathbf{x}) \end{array} \right) \tag{19}$

ですから、式(18)の予測値はカーネル関数と係数 $a$ の線形結合となっていることがわかります。

で、これの何が嬉しいのかというと。行列 $\mathbf{K}$ は訓練データ数 $N$ の正方行列となりますので、式(16)による解はモデルがいかに高次元になっても $N\times N$ の行列演算です。一方、通常の正則化最小二乗法では、モデルの次元が高くなればなるほど計算量が増えていきます。極端な話、100万次元のモデルを考えると100万×100万の行列を扱わないといけないのでもはや計算不可能です。しかしカーネル法を使えば、100万次元のモデルだろうが訓練データ数が現実的な数字なら計算可能になります。この辺の高次元の話の恩恵はあんまり実感が沸かないというか、これが必要となる場面がまだ具体的に想像できませんが、、、。次回カーネル法を使って線形回帰を解いてみたいと思います。→カーネル法による正則化最小二乗法（２）