PRML復活の呪文 part23 (6.1 - 6.3.1)

# TL;DR

- ある2つの入力$x, x'$の特徴ベクトルが$ \phi(x), \phi(x') $だとしたとき、
カーネル関数は$k(x, x') = \phi(x)^T \phi(x') $（ベクトルの内積）で与えられる。
**特徴ベクトルどおしが似ているときにカーネル関数の値は大きくなり、
特徴ベクトル間の類似度のようなもの**である。
- カーネル関数は特徴ベクトルの中身（基底関数）を具体的に考えずとも
高次元（あるいは無限次元）の特徴ベクトル間の類似度を簡単に求めることに相当している。
このテクニックは**カーネルトリック**と呼ばれる
- 入力$x$から出力$y$を予測する回帰問題において、$y(x)$はカーネル関数の足し合わせで表現できる。
つまり、訓練データ$ \{ (x_1, y_1), (x_2, y_2) \} $が与えられたとき、任意の$x$における$y(x)$の値というのは
$k(x, x_1), k(x, x_2) $という2つのカーネル関数の足し合わせで表現できる。
これを**カーネル回帰**という。
- 基底関数の値がその関数の中心$\mu$からの距離だけで決まる（$ \phi_j(x) = h( ||x - \mu_j || ) $）
形式の関数を**RBF** (radial basis function) とよぶ

# 6 カーネル法

ある2つの入力$x, x'$の特徴ベクトルが$ \phi(x), \phi(x') $だとする。
カーネル関数 (kernel function) は
$$
k(x, x') = \phi(x)^T \phi(x') \tag{6.1}
$$
で与えられる。
これは特徴ベクトルどおしの内積なので$ \phi(x), \phi(x') $が似ていると$k(x,x')$の値も大きくなる。
※高校数学で、直行する2ベクトルの内積はゼロ、とか習ったことを思い出す
つまり、特徴ベクトル間の類似度の指標のようなものになっている。また、$k(x, x') = k(x', x)$である。

行列$K$の$ (n,m) $要素が$ k(x_n, k_m) $であるような、
カーネル関数を並べた行列をグラム行列 (Gram matrix) $K$と呼ぶ。
ここで、計画行列$\Phi$が
```math
\begin{align}

\Phi = 

\begin{pmatrix}
\phi_0(x_1) & \cdots & \phi_{M-1} (x_1) \\\
\vdots \\\
\phi_0(x_N) & \cdots & \phi_{M-1} (x_N) \\\
\end{pmatrix}


\end{align}
```

であることと$K_{nm} = k(x_n, k_m) $であることから$K = \Phi \Phi^T $と書ける。

### カーネル法の何がうれしいの？

カーネルトリックと呼ばれるテクニックが有名。
$ k(x, x') = (x^T x' + 1)^2 $と定義すれば、$x=(x_1, x_2)^T, x'=(x'_1, x'_2)^T $のときに
$$ k(x, x') = (x_1 x'_1 + x_2 x'_2 + 1 )^2 \tag{A} $$

となる。この式を展開すると、


```math
\begin{align}
(x_1 x'_1 + x_2 x'_2 + 1 )^2 &= x_1^2 {x'}_1^2 + x_2^2 {x'}_2^2 + 2 x_1 x_2 x'_1 x'_2 + 2 x_1 x'_1 + 2 x_2 x'_2 + 1 \\\
&= (x_1^2, x_2^2. \sqrt2 x_1 x_2, \sqrt2 x_1, \sqrt2 x_2, 1) \cdot
({x'}_1^2, {x'}_2^2. \sqrt2 {x'}_1 {x'}_2, \sqrt2 {x'}_1, \sqrt2 {x'}_2, 1)
\end{align}
```
と書けるため、特徴ベクトルを
$$ \phi(x) = (x_1^2, x_2^2. \sqrt2 x_1 x_2, \sqrt2 x_1, \sqrt2 x_2, 1) $$
と考えているときの（6次元の）特徴ベクトル間の内積を求めたことと等しい。

しかし、カーネルトリックを使うことで特徴ベクトルの中身を明示的に考えずに
特徴ベクトル間の内積を求めることができるのが大きなメリット。
上の例では、6次元の特徴ベクトルだが、
カーネル関数を工夫すればもっと高次元（あるいは無限次元）の
特徴ベクトル間の内積を、特徴ベクトルの中身を考えずに求めることができる。

実際、6次元の2ベクトルの内積を真面目に計算すると6回の掛け算と5回の足し算が必要になるが
式(A)だと3回の掛け算（$ x_1 x'_1, x_2 x'_2$と2乗の掛け算）と2回の足し算で済み、計算量が小さくなっている。


> このセクションは下記の本を参考にさせていただきました
> ガウス過程と機械学習 (機械学習プロフェッショナルシリーズ)[^1]

[^1]: https://www.kspub.co.jp/book/detail/1529267.html

# 6.1 双対表現

回帰や分類に用いられる多くの線形モデルは、双対表現（そうついひょうげん）とよばれる
等価な別の表現に式変形することでカーネル関数が自然に表れてくるらしい。
ここでは、線形回帰モデルでパラメータが正則化された二乗和誤差を
最小化する問題の双対表現を考えよう。

正則化された二乗和誤差関数は
$$
J(w) = \frac{1}{2} \sum_n \left\\{ w^T \phi(x_n) - t_n \right\\}^2 + \frac{\lambda}{2} w^t w
\tag{6.2}
$$

$J(w)$の$w$についての勾配をゼロとおくと
$$
\frac{ \partial J(w) }{ \partial w } = \sum_n \left\( w^T \phi(x_n) - t_n \right\) \cdot
\phi(x_n) + \lambda w = 0
$$


```math
\begin{align}

\therefore w &= - \frac{1}{\lambda} \sum_n ( w^T \phi(x_n) - t_n ) \phi(x_n)\\\
&= \sum_n ( - \frac{1}{\lambda} w^T \phi(x_n) - t_n ) \phi(x_n) \\\
&= \sum_n a_n \phi(x_n) \\\
&= \Phi^T a \tag{6.3} \\

a_n = - \frac{1}{\lambda} { w^T \phi(x_n) - t_n } \tag{6.4}

\end{align}
```

ここで$\Phi$は計画行列、$a = (a_1, \cdots, a_N)^T $である。
つづいて、式(6.3)の$w = \Phi^T a $を$J(w)$を式(6.2)に代入して式変形を行うための準備をする。
式(6.2)のかっこを展開して


```math
\begin{align}

J(w) &= \frac{1}{2} \sum_n \left\{ w^T \phi(x_n) - t_n \right\}^2 + \frac{\lambda}{2} w^t w \\
&= \frac{1}{2} \sum_n ( w^T \phi(x_n) ) ^2 - \sum_n w^T \phi t_n + \frac{1}{2} \sum_n t_n^2 
+ \frac{\lambda}{2} w^t w \\

\end{align}
```

スカラー2乗のシグマはベクトルの内積でかけること、$ \sum_n ( w^T \phi(x_n) ) ^2 = ( \Phi w )^2 
= w^T \Phi^T \Phi w$と
変形できる線形代数の知識を使えば

$$
J(a) = \frac{1}{2} a^T K K a - a^T K t + \frac{1}{2} t^T t + \frac{\lambda}{2} a^T K a \tag{6.8}
$$

が導出できる（左辺は$J(\Phi^T a)$となるはずだが、$ \Phi^T $はどうしたのか不明・・・）。

つづいて、式(6.3)を式(6.4)に代入して$w$を消して$a$について解いていく。

```math
\begin{align}

a_n &= \frac{1}{\lambda} \left\{ (\Phi^T a)^T \phi(x_n) - t_n \right\} \\
- \lambda a_n = (\Phi^T a)^T \phi(x_n) - t_n \\
t_n = \lambda a_n + (\Phi^T a)^T \phi(x_n)

\end{align}
```

いま両辺がスカラーであるものをベクトルに拡張する。左辺は$t$ベクトルになる。
右辺の$ a^T \Phi \phi(x_n) $項（スカラー）をベクトルに変形したい。
ベクトル$a, b$の内積であるスカラ$a^T b$をベクトルに拡張すると$B a$（Bは行列）となることを
頭にいれながら変形すると$ (\Phi^T a)^T \phi(x_n) $は$ \Phi \Phi^T a$となる。
よって、

```math
\begin{align}

t = \lambda a + \Phi \Phi^T a = \lambda a + K a = (K + \lambda I_N )a \\
\therefore a = (K + \lambda I_N )^{-1} t \tag{6.8}

\end{align}
```

これを線形下記モデルに代入しなおすと

$$
y(x) = w^T \phi(x) = \phi(x)^T w = \phi(x)^T \Phi^T a = k(x)(K + \lambda I_N )^{-1} t \tag{6.9}
$$

ここで、$ \phi^T(x) \Phi^T $は行ベクトル$ \phi^T(x) $と行列の積なのでスカラーになるが
転置計画行列の列は特徴ベクトルが並んだものなので、結局特徴ベクトルと特徴ベクトルの内積となり
カーネル関数$k(x)$と書くことができる。

以上の式変形から、たしかに線形回帰モデルは、双対表現とよばれる式変形を行うことで
カーネル関数が自然に表れてくることが分かった。
この特性はパーセプトロンなど別のモデルでも見られるようだが、
どう嬉しいかはこれから明らかになるようだ。

# 6.2 カーネル関数の構成

6.1節でみたように、カーネル関数がでる形で（線形）モデルを式で表現することを
カーネル置換というようだ。
カーネル置換を行うためにはどんな関数でもOKというわけにはいかず、
ある一定の数学的な性質を持つものをカーネル関数として設定する必要がある。

具体的な性質として式(6.13)から(6.22)が紹介されているが、
実務上は一からカーネル関数を設計することはあまりなく、
賢い人が考えてくれた有名カーネル関数を使うことがほとんどなので
このあたりはふーんと読み流しておく。

よく使われるカーネル関数のひとつとして、**ガウスカーネル**が紹介されている。

$$ k(x, x') = \exp ( - || x - x'||^2 / 2 \sigma^2 ) \tag{6.23} $$

expの中身は負なので、かっこの中身の値が小さいほど$k(x, x')$の値は大きくなるが
ベクトル$x$と$x'$が近いほどかっこの中身の値が小さくなり、$k(x, x')$の値が大きくなるので
やはり特徴ベクトル間の類似度の指標のようなものになっている。

### 演習6.11 ガウスカーネルは無限次元の特徴ベクトルの内積で表されることを示せ

式(6.23)のかっこ中身の平方を展開すると

$$
||x - x'||^2 = x^T x + (x')^T x - 2x^T x' \tag{6.24}
$$

となることを利用して、

$$
k(x, x') = \exp (-x^T x / 2 \sigma^2 ) \exp (-x^T x' /  \sigma^2 ) \exp (- (x')^T x' / 2 \sigma^2 ) \tag{6.25}
$$

と変形できる。この中で、$ \exp (-x^T x' /  \sigma^2 ) $にて2ベクトルの内積を計算していることになるが
テイラー展開を適用すると

$$ \exp (-x^T x' /  \sigma^2 ) = \sum_{m=0}^{\infty} \frac{ (-x^T x' / \sigma^2 )^m }{m!} $$

となり、無限個の項の足し算と変形できる。
さらに、シグマの中身は式(6.15)の性質から多項式と考えることができるみたいなので
ある特徴ベクトルの内積で求まっていると考えると

$$ \exp (-x^T x' /  \sigma^2 ) = \sum_{m=0}^{\infty} \phi_m(x) \phi_m(x') $$

これは$m$個の特徴ベクトルの内積で$m$が無限なので、
ガウスカーネルは無限次元の特徴ベクトルの内積で表されることを意味している。

---

このあともカーネル関数を定義する方法の説明が続くが、この本の説明だけで理解するのは
難しいし、この後の理解にあまり影響なので流しておく。

# 6.3 RBFネットワーク

3章の線形回帰モデルでは、固定された基底関数を使ったが、
具体的に基底関数としてどのような形のものを使ったらいいかを考える。
一般には、**RBF** (radial basis function) と呼ばれる、基底関数の値が
その関数の中心$\mu_j$からの距離だけで決まる形式のものがつかわれる。
式で表すと$ \phi_j(x) = h( ||x - \mu_j || ) $である。 
具体例として、分散をある値に固定したガウス分布を関数として考えると、
ガウス分布の平均$\mu$からの距離 $ ||x - \mu || $だけで関数の値が決まるのでRBFである。

RBFを使う動機のひとつとして、関数補間がある。
これは入力ベクトル集合$ \\{ x_1, \cdots, x_N \\} $と目的変数の集合$ \\{ t_1, \cdots, t_N \\} $が
与えられたときに、（入力集合に含まれない）任意の$x$において目的変数の値を再現できる
滑らかな関数$ f(x) $を求めることが目的である。

入力変数にノイズが含まれる場合の関数補間を考える。
入力変数に含まれるノイズが確率分布$p(z)$に従う確率変数$z$で表されるとき、二乗和誤差関数は：
$$
E = \frac{1}{2} \sum_n \int \\{ y(x_n + z) - t_n \\}^2 p(z) dz \tag{6.39}
$$
とかける。
難しそうな形をしているが、入力変数$x_n$にノイズ$z$がのった$x_n + z $が関数$y$に入力されていて、
目的変数$t_n$との二乗和誤差をとっている。この二乗和誤差が確率$p(z)$で重みづけされていて、
あらゆる$z$に対して足し合わせをしている演算が積分記号で表現されている、と解釈できる。

この二乗和誤差関数の最小化には変分法という難しい計算をしないといけないので
計算過程は追わず結果だけ確認する。


```math
\begin{align}

y(x) &= \sum_n t_n h(x - x_n) \tag{6.40} \\
h(x - x_n) &= \frac{ \nu(x-x_n) }{ \sum_n \nu(x-x_n) } \tag{6.41}

\end{align}
```

式(6.40)より、（入力集合に含まれない）任意の$x$において目的変数の値が再現できるようになっており、
式(6.41)で示されるRBFの足し合わせで計算できることが分かる。
このようなモデルは**Nadaraya-Watsonモデル**とよぶらしい（私はPRML以外で聞いたことがない・・・）

# 6.3.1 Nadaraya-Watsonモデル

式変形（導出）は難しくて分からないので結論だけさらっと押さえておこう。
訓練集合を$ \\{ x_n, t_n\\}$として、同時分布$p(x, t)$がRBFな関数$f$の足し合わせで表現されているとする。
$$ p(x,t) = \frac{1}{N} \sum_n f(\cdot) \tag{6.42} $$

回帰関数$y(x)$はParzen推定法なるものを用いて、いろいろと式変形をしていくと


```math
\begin{align}

y(x) &= \sum_n k(x, x_n) t_n \tag{6.45} \\
k(x, x_n) &= \frac{ g(x-x_n) }{ \sum_m g(x - x_m) } \tag{6.46} \\
g(x) &= \int f(x,t) dt \tag{6.47}

\end{align}
```

となるようだ。
式(6.40), (6.41)と似た形になっていて、（入力集合に含まれない）任意の$x$において
目的変数の値が再現できるようになっていて、
$y(x)$がRBFなカーネル関数の足し合わせで計算できることが分かる。
ということで、式(6.45)の結果はNedaraya-Watsonモデルになっていることが分かった。

また、回帰関数をカーネル関数$ k(x, x_n) $の足し合わせで
表現していることから**カーネル回帰**とも呼ばれる。
*なぜ式(6.46), (6.47)がカーネル関数、RBFなのかよく分からないが、数学的に示されてるんだろうか・・*