カーネル法のお話

ガウス過程回帰やSVMで出てくるカーネル法に関する簡単なメモ。
数学的な証明は省きます。

#発想

回帰問題と分類問題を考えてみる。
以下の2つの例は1次関数で回帰、分類ができる。

<p>
<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/352082/000a7186-19b4-add7-a324-3c71ad3756dd.png", width=40%>
<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/352082/797a622c-e026-9776-1309-ffdc55b1b2f3.png", width=40%>
</p>

しかし、以下の例では1次関数での回帰、分類ができない。

<p>
<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/352082/12c970d7-4ab4-c6ef-a75a-7c8ff8969dc8.png", width=40%>

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/352082/09e37c57-a87c-347f-432a-d673891c90f1.png", width=40%>
</p>

1次関数での取り扱いは簡単なので、下2つの例でも1次関数での回帰、分類がしたい。
そこで、1次関数での回帰、分類ができるようにデータを別の空間に変換する。



#カーネル関数から定まる再生核ヒルベルト空間の構成

流れ
カーネル関数を定義
↓
カーネル関数から構成されるベクトル空間 $\mathcal{V}$ の定義
↓
$\mathcal{V}$ に内積を定める
↓
$\mathcal{V}$ の内積の完備化(再生核ヒルベルト空間の構成)

まずカーネル関数を定義しよう。
$X$を集合とし、$k$を$X$上の2変数関数とする。$k$が以下の2つの条件を満たすとき
$k$は$X$上の**カーネル関数**という。

条件１（**対称性**）
　任意の$x,y\in X$に対して

```math
k(x,y) = k(y,x)
```

　が成り立つ。

条件２（**半正定値性**）
　任意の$n\in \mathbb{N}, \\{x_1,\cdots,x_n\\} \subset X ,\\{c_1, \cdots ,c_n\\}\subset \mathbb{R}$に対して

```math
\sum_{i,j=1}^{n}c_i c_j k(x_i, x_j) \geq 0
```

　が成り立つ。


カーネル関数から内積を構成しよう。まず、カーネル関数$k$に対して、$k_x(y)=k(y,x)$とおき、$k_x$を１変数関数として扱う。$\\{k_x\\}_{k\in X}$で生成されるベクトル空間を

```math
\mathcal{V} = \Biggl\{ \sum_{j=1}^{n}a_j k_{x_j} \quad | \quad x_j \in X, a_j \in \mathbb{R}, n \in \mathbb{N} \Biggr\}
```

とおく。
次に、$f=\sum_i a_i k_{x_i}, g=\sum_j b_j k_{y_j} \in \mathcal{V}$に対し、

```math
\langle f,g\rangle_{\mathcal{V}} = \langle \; \sum_{i}a_i k_{x_i}, \sum_{j}b_j k_{y_j} \; \rangle_{\mathcal{V}}=\sum_{i,j}a_i b_j k(y_j, x_i)
```

と定めると、$\langle \cdot ,\cdot \rangle_{\mathcal{V}}$はwell-definedであり、内積の定義を満たす。この内積に基づいた完備化を考えれば、カーネル関数$k$から構成される**再生核ヒルベルト空間**$\mathcal H_k$が得られる。

再生核ヒルベルト空間では以下の等式が成り立つ
**再生核等式**
　任意の$x \in X$と任意の$f\in \mathcal H_k$に対し、

```math
f(x) = \langle f, k_x \rangle_{\mathcal{H}_k}
```

　が成り立つ。すなわち、関数$f\in \mathcal H_k$に点$x\in X$を代入する操作が$k_x=k(\cdot,x)$との内積で表される。この$k_x$は再生核とよばれる。


#カーネル法による回帰例

回帰問題において、データ$\boldsymbol x_1, \cdots \boldsymbol x_n\in \mathbb R^d$と$y_1, \cdots y_n \in \mathbb R$が与えられたとする。このとき、データ$\boldsymbol x_j$を$k_{\boldsymbol x_j}=k(\cdot,\boldsymbol x_j)$に変換する事を考える。（カーネルトリック）
この変換先の空間こそが、上で構成した再生核ヒルベルト空間である。
ちなみに、この変換する際の写像

```math
\Phi ： \boldsymbol{x}_j \mapsto k_{\boldsymbol{x}_j}
```

は特徴写像とよばれる。一般に、変換先の空間の事を特徴空間とよぶ。

###問題設定

$k$を$\mathbb{R}^d$上のカーネル関数とし、$\mathcal H_k$を$k$から構成される再生核ヒルベルト空間とする。このとき、

```math
\{\boldsymbol{x_1}, \cdots ,\boldsymbol{x_n} \} \subset \mathbb{R}^d, \boldsymbol{y}=(y_1,\cdots,y_n)^T \in \mathbb{R}^nに対し、\\ L(f) = \sum_{j=1}^{n}|f(\boldsymbol{x_j})-y_j|^2 (f\in\mathcal{H}_k)\\を最小化するf\in\mathcal{H}_kを求めよ。
```
###解法

$P$を$\mathcal H_k$内で $\\{ k_{\boldsymbol x_1},\cdots,k_{\boldsymbol x_n}\\}$ により張られる空間への直交射影とする。このとき、ヒルベルト空間内での射影定理から$f$は$f=Pf+(f-Pf)$と直交分解できる。よって、再生核等式より

```math
f(\boldsymbol x_i)=\langle f, k_{\boldsymbol x_i}\rangle_{\mathcal H_k}=\langle Pf+(f-Pf),k_{\boldsymbol x_i}\rangle_{\mathcal H_k}=\langle Pf,k_{\boldsymbol x_i}\rangle_{\mathcal H_k}=(Pf)(\boldsymbol x_i)
```

が成り立つ。すなわち、各$\boldsymbol x_i$上での$f$と$Pf$の値は同じである。したがって、この問題を考える上で

```math
f=Pf=\sum_{j=1}^{n}c_j k_{\boldsymbol x_j}
```

と仮定してよい。（一次関数で表せて嬉しい！！）

```math
f(\boldsymbol x_i)=\langle f,k_{\boldsymbol x_i}\rangle_{\mathcal H_k}=\langle\sum_{j=1}^{n}c_j k_{\boldsymbol x_j},k_{\boldsymbol x_i}\rangle_{\mathcal H_k} =\sum_{j=1}^{n}c_j k(\boldsymbol x_i,\boldsymbol x_j)
```

は行列を用いると

```math
\begin{pmatrix}
f(\boldsymbol x_1) \\
\vdots \\
f(\boldsymbol x_n)
\end{pmatrix}
=
\begin{pmatrix}
k(\boldsymbol x_1, \boldsymbol x_1)　& \cdots & k(\boldsymbol x_1, \boldsymbol x_n) \\
\vdots & \ddots & \vdots \\
k(\boldsymbol x_n, \boldsymbol x_1)　& \cdots & k(\boldsymbol x_n, \boldsymbol x_n)
\end{pmatrix}
\begin{pmatrix}
c_1 \\
\vdots \\
c_n
\end{pmatrix}
```

ここで、$K=(k(\boldsymbol x_i, \boldsymbol x_j)), \boldsymbol c = (c_1, \cdots ,c_n)^T$とおくと$L(f)$は

```math
L(f)=\sum_{j=1}^{n}|f(\boldsymbol x_j)-y_j|^2 = \|K\boldsymbol{c} -\boldsymbol{y} \|_{\mathbb{R}^n}^{2}
```

と表される。この右辺を最小にするベクトル$\boldsymbol c \in \mathbb{R}^n$を求める問題は通常の線形代数の範囲で解くことができる。実際、$K$に逆行列が存在すれば$\boldsymbol c = K^{-1}\boldsymbol y$とすればよい。

このようにして$\boldsymbol c = (c_1, \cdots , c_n)^T$が求まれば、

```math
f = \sum_{j=1}^{n}c_j k_{\boldsymbol{x}_j} \in \mathcal{H}_k
```

が問題の解として得られる。


###python3での実装例

カーネル関数は様々あるが、この例ではガウスカーネル

```math
k(\boldsymbol{x}, \boldsymbol{y})=\exp(-\gamma\|\boldsymbol{x}-\boldsymbol{y}\|_{\mathbb{R}^d}^{2})
```
で$\gamma = 0.25$としたものを用いた。


```python
import numpy as np
import matplotlib.pyplot as plt

def kernel(x, y):
  return np.exp(-0.5*(x - y)**2 / 2)

def f(x):
  return 2 * x + 5 * np.cos(x)

np.random.seed(seed=4)

n = 13
m = 100

X = np.linspace(0, 10, m)
y_truth = f(X)
x = 0.5 + 8.5 * np.random.rand(n)
y = f(x)

K = np.array([[kernel(x[i], x[j]) for j in range(n)] for i in range(n)])
c = np.linalg.inv(K) @ y

y_pred = []
for i in range(m):
  sum = 0
  for j in range(n):
    sum += c[j] * kernel(x[j], X[i])
  y_pred.append(sum)
y_pred = np.array(y_pred)

fig, ax = plt.subplots()
ax.scatter(x, y, label="data")
ax.plot(X, y_pred, color="red", label="predict")
ax.plot(X, y_truth, label="ground truth")
ax.legend()
plt.show()
```

![ダウンロード (5).png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/352082/41a02d6b-59ce-d560-af30-3408f699ab37.png)

#参考文献
[機械学習のための関数解析入門　瀬戸道生・伊吹竜也・畑中健志](https://www.amazon.co.jp/%E6%A9%9F%E6%A2%B0%E5%AD%A6%E7%BF%92%E3%81%AE%E3%81%9F%E3%82%81%E3%81%AE%E9%96%A2%E6%95%B0%E8%A7%A3%E6%9E%90%E5%85%A5%E9%96%80-%E3%83%92%E3%83%AB%E3%83%99%E3%83%AB%E3%83%88%E7%A9%BA%E9%96%93%E3%81%A8%E3%82%AB%E3%83%BC%E3%83%8D%E3%83%AB%E6%B3%95-%E7%80%AC%E6%88%B8-%E9%81%93%E7%94%9F/dp/4753601714)

[カーネル法入門　統計数理研究所](https://www.ism.ac.jp/~fukumizu/OsakaU2014/OsakaU_1intro.pdf)