カーネル主成分分析をゆるふわに理解する(1/2)
（「カーネル多変量解析」をゆるふわに読むシリーズの第3章です。）
前々回と前回、主成分分析について書きました。主成分分析は前処理の一種で、サンプルデータのバラツキが最大になるような軸を主成分として取り出すことにより次元圧縮をするものでした。
ただ、主成分分析ではあまりうまくいかない例があります。例えば下の2つの図。どのように軸をとっても、赤と青はうまく分離しませんよね。
そこでカーネル主成分分析という方法が使えるそうです。今回は「カーネル主成分分析の概要紹介」と「手順の導出」を見ていきたいと思います。
なお、今回は式変形盛りだくさんですが、式変形の意味をちまちま書いているので、追いやすいかなと思います。
カーネル主成分分析とは何か？
データの次元では良い感じの主成分をとることが難しい場合（上の二つとか）、データを高次元に飛ばすことでその高次元で良い感じの主成分をとれるのではないか、というのがカーネル主成分分析の考え方です。
普通の主成分分析と比較するとイメージしやすいかもしれません。主成分分析は「k次元の$${x}$$を、d本の主成分に射影することでd次元に次元圧縮する」方法です。カーネル主成分分析は「k次元の$${x}$$を、一旦m次元まで高次元射影し、そこからd本の主成分に射影することでd次元に次元圧縮する」方法です。あげて、さげる。
カーネル主成分分析をもう少し具体的に見るために、第2章で出てきた射影関数$${\phi(x)}$$を簡単に復習します。この関数は、k次元ベクトル$${x=(x_1,x_2,…,x_k)}$$を$${\phi(x)}$$にいれると、m次元ベクトル$${\phi(x)＝(\phi_1(x),\phi_2(x),…,\phi_m(x))}$$に射影した結果を返します（$${\phi_i(x)}$$は$${x}$$内の特微量をいくつか組み合わせる関数です）。k<mとすると、k次元をより高次元であるm次元に射影していることになります。
射影関数$${\phi(x)}$$を用いてカーネル主成分分析の”原理通りの”手順を考えるとこうなります。
1) k次元の$${x}$$とその結果の$${y}$$について、n個のサンプル$${x^{(1)},x^{(2)},…,x^{(n)}}$$を用意する
2) 良い感じの射影関数$${\phi(x)}$$を持ってきて、各データ点をm次元まで高次元射影する（$${\phi(x^{(i)})}$$）
3) $${\phi(x^{(i)})}$$を用いて、m次元における主成分分析を行う
4) 主成分をd本選んで、各データ点を$${\phi(x)}$$で射影後それぞれの主成分に射影すると、d次元まで次元圧縮されたデータが取得できる
このとき、ピッタリの$${\phi(x)}$$が思いつけばいいですが、そんなことは期待できないので、第2章のように無限次元に飛ばすような$${\phi(x)}$$を考えることがよさそうです。
ただ、そうすると計算量が膨大になってしまうという大きな問題が生じます。
この膨大な計算量を避けるため、カーネル主成分分析では”原理通り”ではない手順、"実際の"手順で計算を行います。具体的には、カーネルトリックを使ってk>m>d次元への移動をk>d次元の移動の計算だけで終わらせてしまいます。第2章のときと同じ考え方です。
その"実際の"手順をここで書いて終わりでもいいのですが、せっかくなので”実際の”手順をゆるふわに導出してみようと思います。
カーネル主成分分析の手順の導出
突然ですが、次元削減を行う前処理は関数$${f(x)}$$と書くことができます。前回の最後には、逐次特微量選択と主成分分析の処理を行列で示しましたが、まさにあれが$${f(x)}$$でした。
カーネル主成分分析の結果として得たいものは以下の$${f(x)}$$です。
k次元ベクトル$${x}$$を食わせると、d次元ベクトルに圧縮して返す関数$${f(x)}$$ (k>d)。
この$${f(x)}$$を得るために以下ではこう進めていきます。
k次元からm次元への変換関数$${\phi(x)}$$があるものとし、n個のサンプルデータをm次元上に射影することでm次元上の主成分を導出
主成分を使って、k次元の$${x}$$がm次元に射影され更に主成分に射影されたときの式$${g(x)}$$(k次元からm次元への変換の関数)を計算（一部パラメータが不完全バージョン）
n個のサンプルデータをm次元上に射影し、更に主成分に射影した結果が、主成分上で最もバラつくように$${g(x)}$$を同定
$${g(x)}$$はm個の主成分全てへの変換が行われるもののため、優先すべき主成分をd個選び出し、k次元からd次元への射影を行う$${f(x)}$$を導出
やってみましょう。
まず「(1) k次元からm次元への変換関数$${\phi(x)}$$があるものとし、n個のサンプルデータをm次元上に射影することでm次元上の主成分を導出」します。
その求める主成分ベクトルを$${w}$$とします。$${w}$$はm次元の単位ベクトルとします。この$${w}$$は$${\phi(x)}$$からどう導けるでしょうか？
主成分ベクトル$${w}$$は、前回と同じく「各データとの距離の二乗和が最小の直線方向のベクトル」です（下図の赤）。
三平方の定理を使うと、「点との距離の二乗」は$${|\phi(x^{i})|^2 - |w\phi(x^{i})|^2}$$です。つまり、$${w}$$は下記を最小にするもの。
$${1/n\sum^n_i(|\phi(x^{i})|^2 - |w\phi(x^{i})|^2)}$$
$${1/n\sum^n_i(|\phi(x^{i})|^2)}$$は固定値なので、$${1/n\sum^n_i( - |w\phi(x^{i})|^2)}$$を最小化するような$${w}$$が主成分ベクトルです。これをラグランジュの未定乗数法で解きます。いつも省略するのでたまには解いてみます（ベクトルの微分に慣れてない人向けに細かく書くので興味なければ飛ばしてください）。
$${-1/n\sum^n_i( w^T\phi(x^{i}))^2+\lambda(|w|^2-1)}$$の極値を求めます。ここで、$${\sum^n_i( w^T\phi(x^{i}))^2}$$を$${w}$$で微分するということは、$${\sum^n_i\begin{pmatrix}d/dw_1(w^T\phi(x^{i}))^2)\\d/dw_2(w^T\phi(x^{i}))^2)\\…\\d/dw_m(w^T\phi(x^{i}))^2)\end{pmatrix}}$$ですこの一行目を取り出すと、$${d/dw_1(w^T\phi(x^{i}))^2)}$$=$${d/dw_1(w_1\phi_1(x^{(i)})+w_2\phi_2(x^{(i)})+…+w_m\phi_m(x^{(i)}))^2}$$=$${2\phi_1(x^{(i)}) (w_1\phi_1(x^{(i)})+w_2\phi_2(x^{(i)})+…+w_m\phi_m(x^{(i)}))}$$=$${2\phi_1(x^{(i)})(w^T\phi(x^{(i)}))}$$よって、さっきの行列は$${2\sum^n_i\begin{pmatrix}\phi_1(x^{(i)})(w^T\phi(x^{(i)}))\\ \phi_2(x^{(i)})(w^T\phi(x^{(i)}))\\…\\ \phi_m(x^{(i)})(w^T\phi(x^{(i)}))\end{pmatrix}}$$= $${2\sum^n_iw^T\phi(x^{(i)})\phi(x^{(i)})}$$元の値の$${w}$$での微分は、$${-2/n\sum^n_iw^T\phi(x^{(i)})\phi(x^{(i)})+2\lambda w}$$
$${w}$$による偏微分の結果は$${-2/n\sum^n_iw^T\phi(x^{(i)})\phi(x^{(i)})+2\lambda w=0}$$。この式より、主成分ベクトル$${w}$$は下記だと導かれます。
$${w=1/n\lambda\sum^n_iw^T\phi(x^{(i)})\phi(x^{(i)})}$$
ここから「(2)主成分を使って、k次元の$${x}$$がm次元に射影され更に主成分に射影されたときの式$${g(x)}$$(k次元からm次元への変換の関数)を計算（一部パラメータが不完全バージョン）」します。
ある$${x}$$がm次元に射影され（$${\phi(x)}$$）、更に主成分$${w}$$上に射影されたときの式は、$${w^T\phi(x)}$$です。(1)で導かれた主成分ベクトルの式を$${w}$$を代入して式変形すると
$${w^T\phi(x)}$$= $${(1/n\lambda\sum^n_iw^T\phi(x^{(i)})\phi(x^{(i)}))^T\phi(x)}$$
ここで、$${w^T\phi(x^{(i)})}$$はスカラー量なので、
= $${(1/n\lambda\sum^n_i(w^T\phi(x^{(i)}))\phi(x^{(i)})^T\phi(x)}$$
=$${\sum^n_i(1/n\lambda(w^T\phi(x^{(i)})))k(x^{(i)}, x)}$$
カーネル関数が出てきました（$${\phi(x^{(i)})^T\phi(x)=k(x^{(i)}, x)}$$）
ここで、$${a_i=1/n\lambda(w^T\phi(x^{(i)}))}$$とおくと、
$${g(x)=\sum^n_ia_ik(x^{(i)},x)}$$
これが$${x}$$をm次元に飛ばして主成分に射影する式です。だいぶスッキリしました。
ん？でもいきなり出てきた$${a_i}$$って何？
$${a_i=1/n\lambda(w^T\phi(x^{(i)}))}$$って式をみると、iに依存したスカラー量であるとわかります。ので、$${a=(a_1, a_2, …, a_n)}$$はスカラー量のベクトルです。この$${a}$$の値はこの時点ではまだ解りません。
さて、「(3)n個のサンプルデータをm次元上に射影し、更に主成分に射影した結果が、主成分上で最もバラつくように$${g(x)}$$を同定」します。要するに$${a}$$を同定します。
「n個のサンプルデータをm次元上に射影し、更に主成分に射影した結果」の計算は簡単。さっき求めた$${\sum^n_ia_ik(x^{(i)},x)}$$にいれるだけです。例えば$${x^1}$$の射影は$${\sum^n_ia_ik(x^{(i)},x^1)}$$です。各サンプルデータとの類似度に$${a_i}$$で重みづけして足し合わせたものですね。これを行列で表すと
$${\begin{pmatrix}k(x^1,x^1)&k(x^2,x^1)& …&k(x^n,x^1)\end{pmatrix}}$$$${\begin{pmatrix}a_1\\a_2\\…\\a_n\end{pmatrix}}$$
面倒なので$${x^1}$$から$${x^n}$$まで一気に計算しましょう
$${\begin{pmatrix}k(x^1,x^1)&k(x^2,x^1)& …&k(x^n,x^1)\\k(x^1,x^2)&k(x^2,x^2)& …&k(x^n,x^2)\\…&…& …&…\\k(x^1,x^n)&k(x^2,x^n)& …&k(x^n,x^n)\end{pmatrix}}$$$${\begin{pmatrix}a_1\\a_2\\…\\a_n\end{pmatrix}}$$
この左側は第1章で出てきた行列と同じ形してますね。$${K}$$とおきます。すると上の式は$${Ka}$$とおけます。これが射影結果です。
この$${Ka}$$で得られるベクトルの分散が最大になるような$${a}$$を求めたいわけです。$${Ka}$$の分散を$${1/n|Ka|^2}$$として、またまたラグランジュの未定乗数法を使うと下記を微分することになります（$${w^2=a^TKa}$$も利用しています、また最大化を考えるとき1/nは不要なので消しました）。
$${-a^TK^2a + \lambda(a^TKa - 1)}$$
$${a}$$で微分して極値を求めようとすると、$${-2K^2a+2\lambda Ka=0}$$。$${K}$$が正則のとき$${K^{-1}}$$をかけて得られるのは$${Ka=\lambda a}$$。
主成分上のサンプルデータ写像の分散が最大になるのは、$${a}$$が$${K}$$の固有ベクトルになるときだとわかりました。
固有ベクトルはm本あり、それらは直行して空間を張ります。そのm本の固有ベクトルを$${a^1, a^2,…,a^m}$$とおくと、$${g(x)}$$は、
$${g(x)}$$=$${\sum^n_i\begin{pmatrix}a^1_i\\a^2_i\\…\\a^m_i\end{pmatrix}k(x^{(i)},x)}$$というm次元のベクトルを返す関数になります。
なお、固有値$${\lambda}$$の大きい順に分散も大きくなるので、固有値最大のときの固有ベクトル$${a^i}$$が主成分になります。これは主成分分析のときの結果に似てますね。
大詰めです。「(4)$${g(x)}$$はm個の主成分全てへの変換が行われるもののため、優先すべき主成分をd個選び出し、k次元からd次元への射影を行う$${f(x)}$$を導出」。
これ、そのまんまですね。さっきの$${g(x)}$$=$${\sum^n_i\begin{pmatrix}a^1_i\\a^2_i\\…\\a^m_i\end{pmatrix}k(x^{(i)},x)}$$から、固有値の大きい順にd個$${a}$$を選ぶだけです。つまり
$${f(x)}$$=$${\sum^n_i\begin{pmatrix}a^1_i\\a^2_i\\…\\a^d_i\end{pmatrix}k(x^{(i)},x)}$$
ということで、"実際の"手順が導出されました。
1) k次元の$${x}$$とその結果の$${y}$$について、n個のサンプル$${x^{(1)},x^{(2)},…,x^{(n)}}$$を用意する
2) カーネル関数を決め（例えばガウスカーネル）、n個のサンプルから$${K}$$を計算する
3) $${K}$$の固有ベクトル$${a}$$を計算する
4) 固有値が大きい順にd個の固有ベクトルを取得して並べる
5) 求めたいデータに対して各サンプルデータと$${k(x^{(i)}, x)}$$を計算し、4)の行列をかければd次元の主成分上の点を示す値が得られる
この過程には$${\phi(x)}$$が出てきていません。また$${K}$$を計算するときにカーネルトリックが使えるため、多次元射影の結果の内積がスキップできます（第二章参照）。
やり残し
ということで、カーネル主成分分析の手順を導出しました。
が、実は以上の説明には大きな誤魔化しがあります。それは「(3)n個のサンプルデータをm次元上に射影し、更に主成分に射影した結果が、主成分上で最もバラつくように$${g(x)}$$を同定」の中に出てきた「$${Ka}$$の分散を$${1/n|Ka|^2}$$として」です。k次元における$${x}$$が標準化されていたとしてもm次元における$${Ka}$$の平均値が0とはいえないはずで、分散は$${1/n|Ka|^2}$$となるとは限りません。
なんで誤魔化したかというと(理由1)説明がごちゃごちゃするから、(理由2)上の流れを理解していると修正するのが簡単だから、です。
ということで、次回はこの修正を行います。またコードを書いて、一番最初に出てきた二つの例がきちんと分離できるのかを確認します。
ではでは。
次 https://note.com/tanuki_112/n/n958f097d5bac
この記事が気に入ったらサポートをしてみませんか？