異常検知と変化検知 (機械学習プロフェッショナルシリーズ) の第6章の輪読資料です。
前半の続きの資料です。

前回の流れ

サポートベクトルデータによる異常検知

データを囲う、中心bと半径Rの球を最適化して、球からはみ出た距離を異常度として定義しよう！
制約条件がたくさんあって最適化しづらいから、別の問題にして最適化しよう（双対問題）
双対問題ができた！

\max_{\alpha} \bigl\{ \sum^N_{n=1}\alpha_n K_{n,n} - \sum^N_{n=1,n'=1}  \alpha_n \alpha_{n'} K_{n,n'} \big \} \\
\quad subject \quad to \quad 0 \leq \alpha_n \leq C \quad (n=1\cdots N) \tag{6.8}

カーネルトリック

本質的に非線形の問題を線形分離しようとすると、うまく分離できない。今回の問題は、そもそも球面なので、線形で分離するのに無理がある。そこで、非線形空間に非線形変換して、そこで問題を解こうという話になる。

非線形の基底関数$\varphi(x) \quadただし\quad \varphi(x) = [ \varphi_1, \varphi_2, \cdots, \varphi_{K} ]^T$

を考えると、内積は、$\varphi(x) \varphi(x')^T$のように表せる。
ここで基底関数の次元$K$は、元々のxの次元より次元が大きくなっている。
基底関数の次元$K$をサンプル数程度にまでしないと、十分に線形分離できなくなってしまう。
すると、非線形空間での内積の計算量が膨大になってしまう。

今回の最適化問題では、xに関わるものがいい感じに内積のみになっているので、非線形空間への写像$\varphi(x)$や$\varphi(x')$を計算せず、

K(x,x') = \phi(x) \phi(x')^T

のようにx,x'だけで非線形空間内の内積だけを計算できれば、効率がよい。

ここで、RBF(動径基底関数)と呼ばれる、基底関数が、その中心$\mu_{{j}}$からの動径にのみ依存する、

\phi_j(x) = h(||x-\mu_j||)

のような形式のものをとると、内積が、

K(x,x') = exp\{- \sigma ||x - x'||^2\}

と計算できる。
つまり、内積の定義を上記のものに置き換えるだけで、非線形に写像して内積を計算したことになる。これをカーネルトリックという。
一般的にこのように置き換える関数のことをカーネル、上記のようにRBFを基底関数としたカーネルをガウスカーネルと呼ぶ。

ガウスカネールをテーラー展開すると、無限次元への写像に対応する形になるので、ガウスカーネルに置き換えるだけで無限次元の非線形空間で線形分離ができてしまうということ。すごい。

カーネルの分かりやすい説明
カーネルとは直感的に説明するとなんなのか？
カーネルトリック

カーネルトリックで遊べるとこ

最適化手法 SMO法の概要

Sequential Minimal Optimization algorithm (逐次最小問題最適化法)

step 1: 観測データ集合$ \mathcal{D} $を、適当な部分集合$ \mathcal{D_1},\cdots \mathcal{D_J} $に分割する
step 2: $a_n=0 \quad (n=1, \cdots,N) $に初期化する
step 3: 適当な$\mathcal{D_j}$を選び、$\mathcal{D_{now}}$とする
step 4: repeat
　　　　step4-1 : $\mathcal{D_{now}}$についての最適問題を解く
　　　　step4-2 : KKT条件を満たさない観測データを含む新たな部分集合を選び、これを$\mathcal{D_{now}}$とする
step 5: until 停止条件を満たす
step 6: ${a_n} (n=1, \cdots, N)$を結果として出力して終了

pythonでの実装
http://d.hatena.ne.jp/se-kichi/20100306/1267858745

スライド
SMO徹底入門 - SVMをちゃんと実装する

解の性質と分類

本を写してやります。