（今更ながら）Support Vector Machineの授業を書き起こす
このMITの授業がとてもわかりやすく、何度も戻っては聞いているので、自分のメモ用として、文字に起こしておく。
この授業は、新しい手法が産まれてくる理由を、きちんと説明してくれているのが良い。
ある日、突然頭良い人がふっと思いつくんじゃないよって。
フーリエとかと違って、SVMなら作った人に聞けるしね～とのこと。
まずは、データを２つに分けてみようと思う
2種類のデータがある。これを直線で分けてみたい。そこで、2種類のデータの間に道路を描いて、この道幅が一番広いのが良いんじゃなかろうかと考えた。
この道があったとして、道に直角なベクトル$\vec{w}$が分かれば、どんな点$u$が来ても、
$\vec{w} \cdot \vec{u} + b \ge 0$
で、どちら側にいるかがわかって良くね？
ということで、$\vec{w}$と$b$が知りたい。
わかっていることは、プラスのデータ$\vec{x_+}$とマイナスのデータ$\vec{x_-}$に対して、
$\vec{w} \cdot \vec{x_+} + b \ge 1$
$\vec{w} \cdot \vec{x_-} + b \le -1$
であるということ。
ここで、数学的に簡単になるというそれだけの理由で、$y_i$という変数を導入。これは、プラスのデータでは1、マイナスのデータだと-1になる。上の式の両辺にこいつをかけると、2式は両方とも同じ
$y_i(\vec{w} \cdot \vec{x_i} + b) \ge 1$
となる。あら、便利。さらに、条件を追加して、道路端では、
$y_i(\vec{w} \cdot \vec{x_i} + b) - 1 = 0$
としてみよう。
データを２つに分けた道幅を知りたい
データを二つに分けた道の幅を計算してみたい。プラスデータ側の道路端$\vec{x_+}$、マイナス側の道路端$\vec{x_-}$から、２つのベクトルの差$\vec{x_+}-\vec{x_-}$が求まる。
これと、道路と直交しているベクトル$\vec{w}$を使えば道幅は
$道幅 = (\vec{x_+}-\vec{x_-}) \cdot \frac {\vec{w}} {|| \vec{w} ||} $
と表せる。で、さっき、道路端の条件を増やしたから、それを使うと$\vec{w} \cdot \vec{x_+}$は$1-b$で、$\vec{w} \cdot \vec{x_-}$は$1+b$となるので、道幅は
$道幅 = \frac {2} {|| \vec{w} ||} $
となる。この道幅を最大にしたい！ 数学的に簡単になるので、問題文を
⇒ $|| \vec{w} ||$を最小化したい！
⇒ $\frac {1}{2} || \vec{w} ||^2$を最小化したい！
と変更。こうなると、よくある条件付きの最小問題になるので、ラグランジュの未定乗数法で解ける。1801年に考えられたこの手法が産みだされた理由は置いておいて、
$L = \frac {1}{2} || \vec{w} ||^2 - \sum{\alpha_i (y_i(\vec{w} \cdot \vec{x_i} + b) - 1)}$
の極値を探す。あとは、数値計算屋さんに渡せば計算しておいてくれる。
とはいえ、データの依存関係を知りたいので、もうちょっと頑張ってみる。
$\frac {\partial L}{\partial \vec{w}} = \vec{w} - \sum{\alpha_i y_i \vec{x_i}} = 0$
$\frac {\partial L}{\partial b} = \sum{\alpha_i y_i} = 0$
なので、これを元の$L$に放り込むと、
$L = \sum{\alpha_i} - \frac {1}{2} \sum_i{\sum_j{\alpha_i \alpha_j y_i y_j x_i \cdot x_j}}$
となり、$L$はデータの内積にのみ依存していることがわかる。一番最初に知りたかった、あるデータがどちらに属すかを表す式
$\vec{w} \cdot \vec{u} + b \ge 0 \Rightarrow \sum{\alpha_i y_i \vec{x_i}} \cdot \vec{u} + b \ge 0$
も同様で、内積にのみ依存する。
直線で２つにわけられないデータの場合はどうするか？
直線の道路で分けると考えると、分けられないこともある。そこで、データがある空間が悪いから分けられないのではないか？ という予想の元、データを全部、別の空間に飛ばす$\phi$を考えてみる。データはすべて内積しかされていなかったことを思い出すと、
$K(x_i, x_j) = \phi(x_i) \cdot \phi(x_j)$
という式があれば、十分計算が出来てしまう！ で、便利なことに、こういうのをカーネル関数と言って、いろいろある。人気のあるカーネルは、以下：
- 多項式カーネル: $K(x_i, x_j) = (x_i \cdot x_j+1)^n$
- Gaussian RBF カーネル: $K(x_i, x_j) = e^{- \frac {|| x_i-x_j ||}{\sigma}}$
これで、簡単に別の空間に持って行って計算ができて、極地解に落ちずに全体最適解が求まる。とはいえ、オーバーフィッティングなどの問題がなくなるというわけではない。
歴史の勉強
SVMを作ったVladimir Vapnikという人は、SVMのアイディアを、60年代初頭にモスクワ大学で博士論文で出したけど、コンピューターもないし、どうにもならずにそのまま放置。1990年にソ連からアメリカに移住。アメリカのベル研究所に来てから、1992年くらいにNIPSに論文3本投稿したけど、全部リジェクトされる。そのころ、手書き文字認識でニューラルネットワークが使われ始めていたけど、SVMのが良いだろうと思い、同僚と晩飯を賭ける。2次の多項式カーネルで、当時のニューラルネットワークを打ち負かし、SVMがやっと世の中に出る。アイディアが出てから使われるまでは得てして時間がかかるものです。とのこと。