カーネル法のお話

14086 ワード
カーネル法 関数解析 機械学習 Python Python テキストリンク

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

発想

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

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

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

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

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

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

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

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}$に対して

\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}$で生成されるベクトル空間を

\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}$に対し、

\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$に対し、

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)$に変換する事を考える。（カーネルトリック）
この変換先の空間こそが、上で構成した再生核ヒルベルト空間である。
ちなみに、この変換する際の写像

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

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

問題設定

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

\{\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)$と直交分解できる。よって、再生核等式より

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$の値は同じである。したがって、この問題を考える上で

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

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

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)

は行列を用いると

\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)$は

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$が求まれば、

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

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

python3での実装例

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

k(\boldsymbol{x}, \boldsymbol{y})=\exp(-\gamma\|\boldsymbol{x}-\boldsymbol{y}\|_{\mathbb{R}^d}^{2})

で$\gamma = 0.25$としたものを用いた。

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()

参考文献

機械学習のための関数解析入門　瀬戸道生・伊吹竜也・畑中健志

カーネル法入門　統計数理研究所