カーネル法について理解した事 - GA将？開発日記～王理のその先へ～

　http://str.i.kyushu-u.ac.jp/plone/news/7b2c1556de30fc30e030ed30e930df30f330ef30fc30af30b730e730c3-2010-gpw-10-8ad66587767a8868/files/gpw2010.pdf
　http://www.geocities.co.jp/Technopolis/5893/publication/kernel.pdf

　この辺の資料を参考に。

　まず、一般的に線形の関数近似を行う場合*1は以下の様な形になる。 $n$ は特徴ベクトルの次元数、 $w$ は重み係数、 $x$ は特徴量。

　　 $evl \left( x \right) = \sum_{i=1}^n\left( w_i \cdot x_i \right) = w \cdot x$

　パラメータ更新則は一般的に次の様な形になる。 $x^{(j)}$ はj番目の学習データの特徴量、 $\alpha$ は学習率で $\delta$ は学習アルゴリズムによって異なる係数。

　　 $w = w + \alpha \delta x^{(j)}$

　んで、重み $w_i$ の初期値を0とした場合、 $w$ は下記の様に書き換えれる。Mは学習データの数。

　　 $w = \sum_{j=0}^M a_j \cdot x^{(j)}$

　この $w$ を $evl \left( x \right)$ の式に当てはめると、次の様になる。

　　 $evl \left( x \right) = \sum_{j=1}^M \left( a_j \cdot x \cdot x^{(j)} \right)$

　ここで、 $x,x^{\left(j\right)}$ を適当な関数 $\phi$ を用いて $\phi\left(x\right),\phi\left(x^{\left(j\right)}\right)$ に置き換える。

　この時、 $\phi\left(x\right)$ と $\phi\left(x^{\left(j\right)}\right)$ の内積が $K\left(x,x^{\left(j\right)}\right)=\phi\left(x\right)\cdot\phi\left(x^{\left(j\right)}\right)$ となる様に $\phi$ を決める。また、 $\phi$ では元々のn次元のベクトルを、より高次のN次元（n<*2、((0,0,0),0),((0,1,1),1),((1,0,1),1),((1,1,0),0)という4つのサンプルになり、これは線形識別可能になる。

　つまり

n次元の特徴をより高次なN次元の特徴に変換してやれば、線形識別不可能だった問題か識別可能になる
その際、カーネルトリックを用いる事で高速化が可能

という事らしいです。

　ちなみに最初のリンクの資料にある「対応する特徴空間…（中略）…の各次元が、高々d次の単項式に対応する」（つまり、低次元の特徴 $x_i$ の組み合わせが高次の特徴として表れる）って記述については、何でそうなるのかよく分かりません。要勉強です。

　あと、局面評価のたびに過去の訓練データ全部の特徴量を参照するのって速度的にどうなのよ、とか疑問はありますが、まぁぼちぼち勉強していきます。とりあえず今はココまで理解しました、って事で。

　// 06:50追記

　すぐ上の件ですが、 $\sum_{j=0}^M a_j \cdot \phi \left( x^{(j)} \right)$ を事前に計算しておけば、過去の訓練データ全部の特徴量をなめる必要無いかも。

　うーん、やっぱり寝起きの頭じゃ回転遅いのかなぁ…

　// 14:06追記

　あれ？それだとカーネルトリックの意味が無い？

*1:将棋の評価関数とか

*2:0,0),0),((0,1),1),((1,0),1),((1,1),0)という4つのサンプルがある場合、これは線形識別不可能。　だけど、 $\phi\left(x,y\right)=\left(x,y,\left(x+y\right)%2\right)$ という関数を用いれば((これが関数φとして適切なのかどうかは不明。あくまで一例として。