【JDLA E資格】カーネル回帰

#はじめに
JDLA E資格試験で出題されるカーネル回帰について解説した記事です。
E資格試験の機械学習パートでは、カーネル法の考え方やカーネル関数の種類、カーネルトリックなどが出題されます。

なお、他パートの具体的な解説については、下記をご覧ください。
[E資格試験に関する私の投稿記事リスト][link-1]
[link-1]:https://qiita.com/fridericusgauss/items/5a97f2645cdcefe15ce0

###目次

1. 機械学習の分類
2. 基底展開法に基づく非線形回帰と課題
3. カーネル法
4. カーネル回帰-1
5. おわりに

#機械学習の分類
E資格試験で登場する機械学習モデル・アルゴリズムは下記表のように分類されます。

モデル	学習タイプ	タスク
線形回帰	教師あり	回帰
ロジスティック回帰	教師あり	分類
SVM	教師あり	分類
k-近傍法	教師あり	分類
k-means	教師なし	クラスタリング
k-means++	教師なし	クラスタリング
主成分分析	教師なし	次元削減
動的計画法	強化学習	ー
モンテカルロ法	強化学習	ー
Q-Learning	強化学習	ー
SARSA	強化学習	ー

###カーネル回帰
カーネル回帰は、データの非線型性に対応するために、線形回帰にカーネル法を導入したモデルです。
基底展開法に基づく非線形回帰モデルの発展版として捉えられます。
なお、線形回帰や基底展開法に基づく非線形回帰の解説については、下記をご覧ください。
[線形回帰][link-2]
[基底展開法に基づく非線形回帰][link-3]
[link-2]:https://qiita.com/fridericusgauss/items/42b5cd0bf8ea4b79b86a
[link-3]:https://qiita.com/fridericusgauss/items/3052ba024521f50bd666

#基底展開法に基づく非線形回帰と課題
###基底展開法に基づく非線形回帰のモデルと学習
基底展開法に基づく非線形回帰モデルは式(1)で表されます。

y=\boldsymbol{w}^{\mathrm{T}}\boldsymbol{\phi}(\boldsymbol{x})+w_{0}
=\sum_{j=1}^{H}w_j\phi_j(\boldsymbol{x})+w_{0}
\tag{1}

$y\in \mathbb{R}$は目的変数、$\boldsymbol{x}=(x_1,\cdots,x_M)^{\mathrm{T}}$は説明変数、$\boldsymbol{w}=(w_1,\cdots,w_H)^{\mathrm{T}},w_{0}$はモデルパラメータ、$\boldsymbol{\phi}(\boldsymbol{x})=(\phi_1(\boldsymbol{x}),\cdots,\phi_H(\boldsymbol{x}))^{\mathrm{T}}$で、$\phi_j(\boldsymbol{x})$は基底関数です。
ダミー変数を用いて、式(1)は式(2)に変形できます。

y=\boldsymbol{w}^{\prime \mathrm{T}}\boldsymbol{\phi}^{\prime}(\boldsymbol{x})
=\sum_{j=1}^{H+1}w_j^{\prime}\phi_j^{\prime}(\boldsymbol{x})
\tag{2}

\begin{align}
\boldsymbol{w}^{\prime}=&(w_1 ,\cdots,w_H ,w_0 )^{\mathrm{T}}\\
\boldsymbol{\phi}^{\prime}(\boldsymbol{x})=&(\phi_{1}(\boldsymbol{x}) ,\cdots,\phi_{H}(\boldsymbol{x}) ,1)^{\mathrm{T}}
\end{align}

基底関数は事前に種類を決定しておき、説明変数を非線形変換することが可能です。
つまり、非線型性がある空間上でデータに適合するように線型モデルを学習するのではなく、データを基底関数によって別の空間に写像した後、その空間上でデータに適合するように線型モデルを学習します。

基底展開法に基づく非線形回帰モデル（式(2)）による目的変数の出力を$\hat{y}$、学習データを$D=\{({\boldsymbol{x}}_{1},y_{1}),\cdots,({\boldsymbol{x}}_{N},y_{N})\}$と表します。
学習では、学習データ$D$を与え、最小二乗法によって誤差関数を最小化する問題を解くことで、モデルパラメータを求めます。

基底展開法に基づく非線形回帰の場合、2乗和誤差関数は式(3)で与えられます。

L(\boldsymbol{w}^{\prime};D)
=\frac{1}{2}\sum_{n=1}^N(y_n-\boldsymbol{w}^{\prime \mathrm{T}}\boldsymbol{\phi}^{\prime}(\boldsymbol{x}_n))^2
=\frac{1}{2}(\boldsymbol{y}-\boldsymbol{\Phi}\boldsymbol{w}^{\prime})^{\mathrm{T}}(\boldsymbol{y}-\boldsymbol{\Phi}\boldsymbol{w}^{\prime})
\tag{3}

ただし、式(3)中の文字は下記の通りです。

\begin{align}
\boldsymbol{y}=&(y_1,\cdots,y_N)^{\mathrm{T}}\\
\boldsymbol{\Phi}=&[\boldsymbol{\phi} ^{\prime}(\boldsymbol{x}_1),\cdots,\boldsymbol{\phi}^{\prime}(\boldsymbol{x}_N) ]^{\mathrm{T}}（\Phi_{nj}=\phi_j^{\prime}(\boldsymbol{x}_n)）
\end{align}

$L(\boldsymbol{w}^{\prime};D)$が最小となるような、モデルパラメータはラグランジュ未定乗数法によって導出できます。
ラグランジュ未定乗数法では、$L(\boldsymbol{w}^{\prime};D)$を各モデルパラメータで偏微分したものが$0$となる連立方程式を立てて、それを満たすモデルパラメータを求めます。
その連立方程式は式(4)で表されます。

\begin{align}
\frac{\partial L(\boldsymbol{w}^{\prime};D)}{\partial \boldsymbol{w}^{\prime}}
=&\frac{1}{2}\frac{\partial }{\partial \boldsymbol{w}^{\prime}}
(\boldsymbol{y}-\boldsymbol{\Phi}\boldsymbol{w}^{\prime})^{\mathrm{T}}(\boldsymbol{y}-\boldsymbol{\Phi}\boldsymbol{w}^{\prime})\\
=&-\boldsymbol{\Phi}^{\mathrm{T}}(\boldsymbol{y}-\boldsymbol{\Phi}\boldsymbol{w}^{\prime})\\
=&-\boldsymbol{\Phi}^{\mathrm{T}}\boldsymbol{y}+\boldsymbol{\Phi}^{\mathrm{T}}\boldsymbol{\Phi}\boldsymbol{w}^{ \prime}=\boldsymbol{0}\\
\Leftrightarrow & \boldsymbol{\Phi}^{\mathrm{T}}\boldsymbol{\Phi}\boldsymbol{w}^{ \prime} = \boldsymbol{\Phi}^{\mathrm{T}}\boldsymbol{y}
\end{align}
\tag{4}

式(4)を解くと、モデルパラメータは式(5)で表されます。なお、式(5)はE資格試験では出題されません。

\boldsymbol{w}^{\prime}=(\boldsymbol{\Phi}^{\mathrm{T}}\boldsymbol{\Phi})^{-1}\boldsymbol{\Phi}^{\mathrm{T}}\boldsymbol{y}
\tag{5}

###基底展開法に基づく非線形回帰の課題
式(2)のモデルは、$H$個（有限個）の基底関数を組合せて、データの非線型性を表現します。
しかしながら、基底関数の個数は有限なので、モデルの表現能力に限界があります。
そこで、基底関数を増やしてより高い表現能力を得たいところですが、そうすると基底関数の準備が大変になります。
例えば、RBFでは基底関数毎に中心ベクトル（パラメータ）を設定する必要があるため、基底関数の個数を増やすことに伴い、手動で決定するパラメータも増えます。
他にも、多項定理を用いた多項式基底関数では、各説明変数同士の積や累乗を含めると、基底関数の個数が膨大となり、それに伴い、写像先での計算量も膨大となります。
以上のように、基底関数を導入することで、モデルの表現力は高められる一方、データに適合しており、かつ、計算量も手頃となるような、適切な基底関数の決定は容易ではありません。

#カーネル法
そこで、カーネル関数を用いて以上の問題を解消する方法が__カーネル法__です。
カーネル法は、データを別の空間に写像してモデルの表現能力を高める点については、基底展開法と同様ですが、データ集合に合致した、無限次元（超高次元）の空間に写像するため、上記のような限界がありません。
この特徴から、カーネル法は、非常に表現力の高いモデルが作れる方法として知られています。
カーネル法は、線形回帰（カーネル回帰）以外に、SVM（カーネルSVM）やベイズ線形回帰（ガウス過程）に導入されるケースが有名です。

###カーネル法のポイント
カーネル法のポイントは、下記の二点です。

• データ集合とカーネル関数を利用して、無限次元空間への写像を作ること
• カーネルトリックによって、計算量を抑えられること

1点目は、基底展開法の場合、基底関数の種類を指定して、学習データを使わずに、有限次元空間への写像を与えることに対して、__カーネル法の場合、カーネル関数の種類を指定し、学習データの特徴を上手く把握することで、無限次元空間への写像を与える__ことを指しています。
2点目は、基底展開法の場合、基底関数の個数（写像先の次元）がそのまま計算量の増加に繋がっていたことに対して、__カーネル法の場合、写像先の次元に限界はなく、それが計算量の増加には繋がらない__ことを指しています。ただし、代わりにデータの個数がそのまま計算量に直結します。
特に、SVMにおいては1点目が大きな問題で、線形分離可能なデータでしか、分類モデルを学習できませんでしたが、カーネル関数の導入により、線形分離不可能なデータでも分類モデルを上手く学習できるようになりました。

###カーネル関数
式(4)のように、基底関数を導入した場合、モデルパラメータの導出には、基底関数同士の内積が多く含まれます。
この基底関数同士の内積を、データ同士のカーネル関数の計算によって上手く代替することが可能です。
このテクニックを__カーネルトリック__と言います。

カーネル関数の定義は、式(6)のグラム行列$\boldsymbol{K}\in \mathbb{R}^{N\times N}$が半正定値であり、かつ、対称性を満たす関数$k:\mathbb{R}^N \times \mathbb{R}^N \rightarrow \mathbb{R}$をカーネル関数といいます。なお、この定義はE資格試験では出題されません。

\begin{eqnarray}
\boldsymbol{K}=
\left(
\begin{array}{ccc}
k(\boldsymbol{x}_{1},\boldsymbol{x}_{1}) & \ldots & k(\boldsymbol{x}_{1},\boldsymbol{x}_{N}) \\
k(\boldsymbol{x}_{2},\boldsymbol{x}_{1}) & \ldots & k(\boldsymbol{x}_{2},\boldsymbol{x}_{N}) \\
\vdots & \ddots & \vdots \\
k(\boldsymbol{x}_{N},\boldsymbol{x}_{1}) & \ldots & k(\boldsymbol{x}_{N},\boldsymbol{x}_{N})
\end{array}
\right)
\end{eqnarray}
\tag{6}

カーネル関数の解釈としては、__データ（ベクトル）同士の類似度を表す尺度__と考えるのが良いと思います。
実際に、データ同士の距離が近い場合、カーネル関数の値は大きく、遠い場合、カーネル関数の値は小さくなります。

この定義を満たすカーネル関数は大きく二つのタイプが経験的に知られており、実際にはそれを利用することが多いです。
一つ目は、式(7)で表されるように、基底関数を直接定義し、その基底関数同士の内積です。

k(\boldsymbol{x}_{i},\boldsymbol{x}_{j})=\boldsymbol{\phi}^{\prime}(\boldsymbol{x}_{i})^{\mathrm{T}}\boldsymbol{\phi}^{\prime}(\boldsymbol{x}_{j})
\tag{7}

二つ目は、代表的な関数を直接定義する方法です。
代表的なカーネル関数として、式(8)の多項式カーネル、式(9)のガウスカーネル（RBFカーネル）などが挙げられます。

\begin{align}
k(\boldsymbol{x}_{i},\boldsymbol{x}_{j})&=(\boldsymbol{x}_{i}^{\mathrm{T}}\boldsymbol{x}_{j})^s
\tag{8}\\
k(\boldsymbol{x}_{i},\boldsymbol{x}_{j})&=\exp{\left(-\frac{\|\boldsymbol{x}_{i}-\boldsymbol{x}_{j}\|^2}{2\sigma^2}\right)}
\tag{9}
\end{align}

ただし、式(8)の$s\in \mathbb{N}$、式(9)の$\sigma^2 >0$はパラメータです。

なお、式(9)のガウスカーネルを選択する場合、式(7)を満たす基底関数は下記を要素とするベクトルとなります。

\phi_r(\boldsymbol{x})=\left(\frac{2}{\sigma^2\pi}\right)^{\frac{1}{4}}\exp{\left(-\frac{\|\boldsymbol{x}-r\boldsymbol{1}\|^2}{\sigma^2}\right)}

ただし、$r\in \mathbb{R}$のため、$H$は$\infty$（無限次元）です。

これらのカーネル関数が、定義を満たすことに関する証明は割愛します。

#カーネル回帰
###カーネル回帰モデル
カーネル法を導入した線型回帰モデルである、カーネル回帰について説明します。
線形回帰モデルを__双対表現__で表すと、カーネル関数が出現します。
双対表現とは、別の変数によって関数やモデルを表現し直す方法です。

カーネル回帰モデルは式(10)で表されます。

y=\sum_{i=1}^{N}\alpha_i k(\boldsymbol{x}, \boldsymbol{x}_i)
=\boldsymbol{\alpha}^{\mathrm{T}}\boldsymbol{k}(\boldsymbol{x})
\tag{10}

$\boldsymbol{\alpha}=(\alpha_1,\cdots,\alpha_N)^{\mathrm{T}}$はモデルパラメータ、$\boldsymbol{k}(\boldsymbol{x})=(k(\boldsymbol{x},\boldsymbol{x}_1),\cdots,k(\boldsymbol{x},\boldsymbol{x}_N))^{\mathrm{T}}$で、$k(\boldsymbol{x}, \boldsymbol{x}_i)$は$\boldsymbol{x}_i$に対するカーネル関数です。

式(2)は$H$個の基底関数と$H$個のモデルパラメータの線形結合で表されることに対して、カーネル回帰（式(10)）は$N$個のカーネル関数と$N$個のモデルパラメータの線形結合で表されます。

###カーネル回帰の学習
カーネル回帰の場合、2乗和誤差関数は式(11)で与えられます。

L(\boldsymbol{\alpha};D)=\frac{1}{2}(\boldsymbol{y}-\boldsymbol{K}\boldsymbol{\alpha})^{\mathrm{T}}(\boldsymbol{y}-\boldsymbol{K}\boldsymbol{\alpha})
\tag{11}

$L(\boldsymbol{\alpha};D)$が最小となるような、モデルパラメータはラグランジュ未定乗数法によって導出できます。
ラグランジュ未定乗数法では、$L(\boldsymbol{\alpha};D)$を各モデルパラメータで偏微分したものが$0$となる連立方程式を立てて、それを満たすモデルパラメータを求めます。
その連立方程式は下記のように変形できます。

\begin{align}
\frac{\partial L(\boldsymbol{\alpha};D)}{\partial \boldsymbol{\alpha}}
=&\frac{1}{2}\frac{\partial }{\partial \boldsymbol{\alpha}}(\boldsymbol{y}-\boldsymbol{K}\boldsymbol{\alpha})^{\mathrm{T}}(\boldsymbol{y}-\boldsymbol{K}\boldsymbol{\alpha})\\
=&-\boldsymbol{K}^{\mathrm{T}}(\boldsymbol{y}-\boldsymbol{K}\boldsymbol{\alpha})\\
=&-\boldsymbol{K}^{\mathrm{T}}\boldsymbol{y}+\boldsymbol{K}^{\mathrm{T}}\boldsymbol{K}\boldsymbol{\alpha}=\boldsymbol{0}\\
\Leftrightarrow & \boldsymbol{K}^{\mathrm{T}}\boldsymbol{K}\boldsymbol{\alpha} = \boldsymbol{K}^{\mathrm{T}}\boldsymbol{y}
\end{align}

この連立方程式を解くと、モデルパラメータは式(12)で表されます。なお、式(12)はE資格試験では出題されません。

\begin{align}
\boldsymbol{\alpha} 
=& (\boldsymbol{K}^{\mathrm{T}}\boldsymbol{K})^{-1}\boldsymbol{K}^{\mathrm{T}}\boldsymbol{y}\\
=& \boldsymbol{K}^{-1}(\boldsymbol{K}^{\mathrm{T}})^{-1}\boldsymbol{K}^{\mathrm{T}}\boldsymbol{y}\\
=& \boldsymbol{K}^{-1}\boldsymbol{y}
\end{align}
\tag{12}

ここで、注意したい点は、モデルパラメータ$\boldsymbol{\alpha}$が、グラム行列$\boldsymbol{K}$と目的変数の学習データ$\boldsymbol{y}$のみに依存していることです。
特に、グラム行列$\boldsymbol{K}$はカーネル関数$k$と説明変数の学習データ$\boldsymbol{x}_n$から与えられています。
よって、有限個の基底関数を明示的に与えずに、無限次元に写像可能なカーネル関数を指定し、計算するだけでモデルパラメータを求めることができます。

一方、新たな説明変数のデータ$\boldsymbol{x}_{\mathrm{new}}$に対する予測値$\boldsymbol{\hat{y}}$の計算のためには、新たなデータ$\boldsymbol{x}_{\mathrm{new}}$と学習データ$\boldsymbol{x}_n$の間のカーネル関数を新たに計算する必要があります。
したがって、カーネル法で予測する場合、計算済のモデルパラメータだけを保持するのではなく、学習データも同時に保持する必要があります。

カーネル回帰の導出や効果は下記を参考にしてください。
[カーネル回帰][link-4]
[link-4]:https://qiita.com/wsuzume/items/09a59036c8944fd563ff

#おわりに
E資格向けのカーネル回帰について解説しました。
なお、上記は、2021年2月時点における内容であることにご注意ください。

[E資格試験に関する私の投稿記事リスト][link-1]