カーネル法

machine-learning

素性ベクトルの次元数がデータ数より大きいとき、カーネル法を使うべし。

線形回帰

まずは、ストレートに考える。

f(\vec{x}) = \vec{w}^{\top} \vec{x}

素性ベクトル $\vec{x}$ の次元数は $L$ とする。

重み付き最小自乗法

各データに対する重要度 $w_{i}$ と、$\vec{w}$ のノルムが大きくなりすぎないようにする正則化をつけて定式化する。

\begin{aligned}
\vec{w}^{*}
  &= \textrm{argmin}_{\vec{w}} \left[ \frac{1}{2} \sum_{i=1}^{N} w_{i} \left(\vec{w}^{\top} \vec{x}_{i} - f_{i} \right)^2 + \frac{\lambda}{2} \vec{w}^{\top} \vec{w} \right] \\
  &= \textrm{argmin}_{\vec{w}} L(\vec{w})
\end{aligned}

ここで、$N$ はデータ数、$w_{i}$ $(> 0)$ は各データの重み、$f_{i} = f(\vec{x}_{i})$ (入力データ)、$\lambda$ は正則化の強さを調整するパラメータとする。

勾配を求める。

\begin{aligned}
\nabla_{\vec{w}} L(\vec{w})
  &= \sum_{i=1}^{N} w_{i} \left(\vec{w}^{\top} \vec{x}_{i} - f_{i} \right) \vec{x}_{i} + \lambda \vec{w} \\
  &= \sum_{i=1}^{N} w_{i} \left[(\vec{w}^{\top} \vec{x}_{i}) \vec{x}_{i} - f_{i}  \vec{x}_{i} \right] + \lambda \vec{w} \\
  &= \sum_{i=1}^{N} w_{i} \left[\vec{x}_{i} \vec{x}_{i}^{\top} \vec{w} - f_{i}  \vec{x}_{i} \right] + \lambda \vec{w} \\
\end{aligned}

勾配が $0$ になる $\vec{w}$ を求める。

\begin{aligned}
                \nabla_{\vec{w}} L(\vec{w}) &= 0 \\
\Leftrightarrow \sum_{i=1}^{N} w_{i} \left[\vec{x}_{i} \vec{x}_{i}^{\top} \vec{w} - f_{i}  \vec{x}_{i} \right] + \lambda \vec{w} &= 0 \\
\Leftrightarrow \sum_{i=1}^{N} w_{i} \left[\vec{x}_{i} \vec{x}_{i}^{\top} \vec{w} \right] + \lambda \vec{w} &= \sum_{i=1}^{N} w_{i} f_{i} \vec{x}_{i} \\
\Leftrightarrow \left\{ \sum_{i=1}^{N} w_{i} \left[\vec{x}_{i} \vec{x}_{i}^{\top} \right] + \lambda I \right\} \vec{w} &= \sum_{i=1}^{N} w_{i} f_{i} \vec{x}_{i} \\
\Leftrightarrow \left\{ X W X^{\top} + \lambda I \right\} \vec{w} &= X W \vec{f} \\
\Leftrightarrow \vec{w} &= \left\{ X W X^{\top} + \lambda I \right\}^{-1} X W \vec{f} \\
\end{aligned}

ここで、$X$ は素性ベクトルをならべた L 行 N 列の行列、$\vec{f}$ は $f_{i}$ をならべた N 次元列ベクトル、$W$ は重み $w_{i}$ を対角要素にならべた N 行 N 列の行列とした。

別の形式

f(\vec{x}) = \sum_{i=1}^{N} \alpha_{i} (\vec{x}_{i}^{\top} \vec{x})

という形で回帰を考える。

最小自乗法

上記と同様に最小自乗法で解く。

\begin{aligned}
\vec{\alpha}^{*}
  &= \textrm{argmin}_{\vec{\alpha}} \left[ \frac{1}{2} \sum_{j=1}^{N} \left(f(\vec{x}_{j}) - f_{j} \right)^2 \right] \\
  &= \textrm{argmin}_{\vec{\alpha}} \left[ \frac{1}{2} \sum_{j=1}^{N} \left(\sum_{i=1}^{N} \alpha_{i} (\vec{x}_{i}^{\top} \vec{x}_{j}) - f_{j} \right)^2 \right] \\
  &= \textrm{argmin}_{\vec{\alpha}} L(\vec{\alpha})
\end{aligned}

ここで、$\vec{\alpha}$ は $a_{i}$ をならべた $N$ 次元列ベクトルとした。

勾配は

\begin{aligned}
\nabla_{\vec{\alpha}} L(\vec{\alpha})
  &= \sum_{j=1}^{N} \left[ \left(\sum_{i=1}^{N} \alpha_{i} (\vec{x}_{i}^{\top} \vec{x}_{j}) - f_{j} \right) X^{\top} \vec{x}_{j} \right]
  
\end{aligned}

となる。

\begin{aligned}
                \nabla_{\vec{w}} L(\vec{w}) &= 0 \\
\Leftrightarrow \sum_{j=1}^{N} \left[ \left(\sum_{i=1}^{N} \alpha_{i} (\vec{x}_{i}^{\top} \vec{x}_{j}) - f_{j} \right) X^{\top} \vec{x}_{j} \right] &= 0 \\

\Leftrightarrow \sum_{j=1}^{N} \left[ \left(\sum_{i=1}^{N} \alpha_{i} (\vec{x}_{i}^{\top} \vec{x}_{j}) \right)  X^{\top} \vec{x}_{j} - f_{j} X^{\top} \vec{x}_{j} \right] &= 0 \\

\Leftrightarrow \sum_{j=1}^{N} \left(\sum_{i=1}^{N} \alpha_{i} (\vec{x}_{i}^{\top} \vec{x}_{j}) \right)  X^{\top} \vec{x}_{j} &= \sum_{j=1}^{N} f_{j} X^{\top} \vec{x}_{j} \\

\Leftrightarrow \sum_{j=1}^{N} \left(\vec{\alpha}^{\top} X^{\top} \vec{x}_{j} \right)  X^{\top} \vec{x}_{j} &= X^{\top} X \vec{f} \\

\Leftrightarrow \sum_{j=1}^{N} \left(X^{\top} \vec{x}_{j} \right) \left(X^{\top} \vec{x}_{j} \right)^{\top} \vec{\alpha} &= X^{\top} X \vec{f} \\

\Leftrightarrow \sum_{j=1}^{N} \left(X^{\top} \vec{x}_{j} \right) \left(\vec{x}_{j}^{\top} X \right) \vec{\alpha} &= X^{\top} X \vec{f} \\

\Leftrightarrow X^{\top} \left( \sum_{j=1}^{N} \vec{x}_{j} \vec{x}_{j}^{\top} \right) X \vec{\alpha} &= X^{\top} X \vec{f} \\

\Leftrightarrow X^{\top} X X^{\top} X \vec{\alpha} &= X^{\top} X \vec{f} \\

\Leftrightarrow X^{\top} X \vec{\alpha} &= \vec{f} \\

\Leftrightarrow \vec{\alpha} &= \left(X^{\top} X \right)^{-1} \vec{f} \\
\end{aligned}

表現定理

\vec{w} = X \vec{\alpha}

から

\begin{aligned}
\vec{w}
  &= X \vec{\alpha} \\
  &= X \left(X^{\top} X \right)^{-1} \vec{f}
\end{aligned}

となり、$X \left(X^{\top} X \right)^{-1}$ は $X$ の行数が列数より大きいときの擬似逆行列になっている。

カーネル法へ

k(x_{i}, x_{j}) = x_{i}^{\top} x_{j}

として関数化して、右辺の定義を一般化したらカーネル法になる。

つまり、

f(\vec{x}) = \sum_{i=1}^{N} \alpha_{i} k(\vec{x}_{i}, \vec{x})

として回帰するとして、各要素を $k_{i,j} = k(\vec{x}_{i}, \vec{x}_{j})$ とする行列 K を定義して、

\alpha = K^{-1} \vec{f}

をもとめると、カーネル法による回帰ができる。

重みと正則化

\begin{aligned}
\vec{\alpha}^{*}
  &= \textrm{argmin}_{\vec{\alpha}} \frac{1}{2} \sum_{j=1}^{N} w_{j} \left( x_{j}^{\top} X \vec{\alpha} - f_{j} \right)^2 + \frac{\lambda}{2} \vec{\alpha}^{\top} (X^{\top} X) \vec{\alpha} \\
  &= \textrm{argmin}_{\vec{\alpha}} L(\vec{\alpha})
\end{aligned}

勾配は

\begin{aligned}
\nabla_{\vec{\alpha}} L(\vec{\alpha})
  &= (X^{\top} X) W \left[ (X^{\top} X) \vec{\alpha} - \vec{f} \right] + \lambda (X^{\top} X) \vec{\alpha} \\
  &= \left[(X^{\top} X) W (X^{\top} X) + \lambda (X^{\top} X) \right] \vec{\alpha} - (X^{\top} X) W \vec{f}
\end{aligned}

となるので

\begin{aligned}
                \left[(X^{\top} X) W (X^{\top} X) + \lambda (X^T X) \right] \vec{\alpha} &= (X^{\top} X) W \vec{f} \\
\Leftrightarrow \left[W (X^{\top} X) + \lambda I \right] \vec{\alpha} &= W \vec{f} \\
\Leftrightarrow \left[(X^{\top} X) + \lambda W^{-1} \right] \vec{\alpha} &= \vec{f} \\
\Leftrightarrow \vec{\alpha} &= \left[(X^{\top} X) + \lambda W^{-1} \right]^{-1} \vec{f} \\
\end{aligned}

で求められる。