カーネル多変量分析を読んでいます。前回から第二章を読み始めました。
第一章はこちら

このシリーズの目次はこちら

おさらい

n個のパラメータを持つ$${x=(x_1,x_2,…x_n)}$$から$${y}$$を推測したいというゴールを決めます。m個のサンプルデータ、$${x^{(1)},x^{(2)},…x^{(m)}}$$とその結果$${y^{(1)},y^{(2)},…y^{(m)}}$$を使って学習し、$${x^{(new)}}$$を与えると予想値$${y^{(new)}}$$を返す$${f(x)}$$が作りたいです。

第一章ではカーネル法を使った$${f(x)}$$の計算の仕方をみました。$${x,x'}$$間の類似度を示すカーネル関数$${k(x,x')}$$を使って行列$${K}$$を作ると、あとは簡単な計算で$${f(x)}$$が求まりました。

第二章では、2つのデータの類似度を示すカーネル関数$${k(x,x')}$$とは何かという話です。どうも$${x,x'}$$をそれぞれ多次元空間に写像した$${\phi(x),\phi(x')}$$の内積と定義するとよさそうだという話になってきました。

ただ、この$${\phi(x)}$$が曲者で、なるべく多くの次元に射像できれば予想がよくなるものの、次元を増やすと計算量が増えちゃいます。どんな$${\phi(x)}$$を決めると、良い感じになるんでしょうか？

この記事のゴール

どんな$${\phi(x)}$$を持ってくると、射影する次元数と計算量のバランスがよくなるか？という問いに「無限に射影するけど計算量は最低限にする$${\phi(x)}$$がある」という回答があるそうです。まじっすか。

そのスゴい例の一つが、第１章で出てきたガウスカーネル。この記事では1次元のガウスカーネルを例に、$${\phi(x)}$$が無限に射影するのに$${k(x,x')}$$計算量は増えないという魔法を見たいと思います。

ガウスカーネル以外にはどんなものがあるの？という問題は6章で話すような感じがします（正定値性とか再生性とか）。ので、ここでは本当にそんな関数があるんだ、というのを見学します。

「無限に射影するけど計算量増えない」の見学

$${x=(x_1)}$$から$${y}$$を導き出す一次元の問題を考えます。そのままだとただの一次関数$${f(x)=ax_1+b}$$になっちゃうので、前回考えたみたいに高次元に射像します。この射影する関数を$${\phi(x)=(\phi_1(x), \phi_2(x), …\phi_n(x))}$$とします（n次元に射影する）。

で、ここでどんな$${\phi_i(x)}$$を決めればいいですかね？という問いにどこからともなく来たこの関数にします。ぱっと見ゴツい。
$${\phi_z(x)=\alpha exp(-2\beta(z-x)^2)}$$

$${\alpha, \beta}$$は適当に決める値です。$${z}$$は実数です。

この$${\phi_z(x)}$$を$${z}$$の数だけ射像します。$${z}$$は実数なので$${\phi_z(x)}$$の射影を$${z}$$の数だけ並べた$${\phi(x)}$$は、$${x=(x_1)}$$を無限次元に射影するわけです。

この無限射影する関数$${\phi(x)}$$を使ってカーネル関数を計算するということは、こういう積分をすることになります。
$${k(x, x')=\phi(x)\phi(x')=\int^{\infty}_{-\infty} \phi_z(x)\phi_z(x')dz}$$

無限次元の各項の積$${\phi_z(x)\phi_z(x')}$$を足し合わせるので積分になるのです。これを展開すると（面倒臭かったら斜め読みでいいです）
$${k(x, x')=\int^{\infty}_{-\infty} \phi_z(x)\phi_z(x')dz}$$
$${=\int^{\infty}_{-\infty} \alpha exp(-2\beta(z-x)^2)\alpha exp(-2\beta(z-x')^2)dz}$$
$${=\alpha^2 \int^{\infty}_{-\infty}exp(-2\beta(z-x)^2-2\beta(z-x')^2)dz}$$
$${=\alpha^2 \sqrt{\pi/4\beta} exp(-\beta(x-x')^2)}$$

$${\alpha}$$は適当に決めてよい値だったので$${\alpha^2=\sqrt{4\beta/\pi}}$$とおくと$${\alpha^2 \sqrt{\pi/4\beta}=1}$$で式から消せます。

よって
$${k(x, x')=\phi(x)\phi(x')=\int^{\infty}_{-\infty} \phi_z(x)\phi_z(x')dz=exp(-\beta(x-x')^2)}$$

おぉ？

この式変形はこういうことを言っています。

「無限の次元に射影する関数$${\phi(x)}$$を使ったときの$${x^{(i)},x^{(j)}}$$の類似度$${k(x^{(i)},x^{(j)})}$$」
＝「無限の大きさのベクトル$${\phi(x^{(i)})}$$と$${\phi(x^{(j)})}$$の内積」
＝「無限回の掛け算$${\phi_z(x^{(i)})\phi_z(x^{(j)})}$$を行い、それを足し合わせた結果」
＝「射影を一度も行わなくても$${||x^{(i)}-x^{(j)}||}$$だけで計算可」

つまり、「無限次元に射影して」「無限次元特微ベクトルの内積をとった」結果を「無限次元に射影しないで」計算できちゃうのです。少なくともそういうガウスカーネルはそういう関数なのです。

ちなみに、最初の記事で「そういうもんだと思ってください」と$${k(x, x')}$$に書き込んだ式がまさに$${exp(-\beta(x-x')^2)}$$でした。裏側では「無限に射影した特徴ベクトルの内積の和がこの式であらわせる」というトリックを使っていたのです。

import numpy as np

def gaus(x1, x2, beta=1):
	return np.exp(-1 * beta * ((x1 - x2) ** 2))

この「カーネル関数を使うことで、高次元射影した結果の特微ベクトルの内積が、射影しないで計算できてしまう」ことをカーネルトリックというそうです。

ということで、ここまで4回の中身をざっくりまとめると。

• $${x=(x_1,x_2,…x_n)}$$から$${y}$$を推測できるようにするため、m個のサンプルデータ、$${x^{(1)},x^{(2)},…x^{(m)}}$$とその結果$${y^{(1)},y^{(2)},…y^{(m)}}$$を使って学習することを考える

• カーネル法はサンプルデータ間の類似度を計算し$${f(x)}$$を作成、新しいデータ$${x^{new}}$$に対しても、各データとの類似度を計算することで予想値を計算できる

• 類似度は$${x,x'}$$それぞれを高次元射影して内積の和をとることで計算する

• ガウスカーネル関数などは、高次元射影して内積の和をとるという面倒な計算を大幅にショートカットできる（カーネルトリック）

ってことでした。これで第二章は終わりです。書籍にはもっと理論的にきちんと書いてありますので気になる人は読んでくださいー（たぶん書いてあることの3割程度しか取り上げてないです）。

さてこのあとは。

少し寄り道をしようと思います。この本を一回離れて、次元削減の手法を見ていこうと思います。理由は二つ

• 次元削減の手法を知っていることが当たり前のこととして第3章が書かれているから

• 今回コードなくてちょっと寂しいから

ということで下の本の5章「次元削減でデータを圧縮する」を読んでみますー。