SVM(サポートベクターマシーン)についてまとめてみた

学生の頃から、いつかまとめようと思っていたSVM(サポートベクターマシーン)に関してまとめてみる。

SVM (サポートベクターマシーン)
---

サポートベクターマシーンとはそもそも何か？という話なんですが、 
大きな枠でいうと**データ集合を分類する識別関数**のことです。

関数なので、何かブラックボックスf(x)に入力を入れるとそれに対応する出力(-1 か 1)が出るわけです。

```math
f({\bf x}) = {\rm sgn}(g({\rm x})) = -1\ {\rm or}\ 1\\
g({\rm x}) = {\bf w}^{\rm T}{\bf x} + b
```
※xは入力、wは結合荷重(入力にかかる重み)、bはバイアス項(接線)、sgnは[符号関数](https://ja.wikipedia.org/wiki/%E7%AC%A6%E5%8F%B7%E9%96%A2%E6%95%B0)
(中が正なら1, 負なら-1を返す関数のこと)

入力 x に対して 1 か -1を識別してあげる関数なので識別関数と考えれば問題ないかと。 
そして、**識別関数の出力がいい感じの出力になるようにwとbを求める問題**に発展するわけです。
(例：文字認識なら、文字に対応したラベルなど)
ちなみにこのようなイメージ図になるわけです。

<img width="300px" alt="SVM" src="https://qiita-image-store.s3.amazonaws.com/0/211139/43cf70e0-b1f4-486b-262e-119777c1eda0.png">

これだけだと線形二分器と呼ばれている[単純パーセプトロン](https://ja.wikipedia.org/wiki/%E3%83%91%E3%83%BC%E3%82%BB%E3%83%97%E3%83%88%E3%83%AD%E3%83%B3)と何ら変わりないのです。

何が違うのかというと、**サポートベクトルの概念**を取り入れていることなんですね。
そもそも、上の図で何気なく識別平面(上図直線のこと)を引いてデータを二分割してますが、
**本当にデータにとっていい識別平面**ってなんだろう？という疑問が出てくるわけです
<img width="300px" alt="こんな風に一杯識別線が引けちゃう" src="https://qiita-image-store.s3.amazonaws.com/0/211139/904f19e1-3002-d186-da28-12b0d0abdbe8.png">

(こんな風にたくさん識別平面が引けるわけです。)
結論からいうと、**データにとって良い識別線とは、未知のデータが入ったときに正しく分類される包容力のある線**
なんです。かっこよく言うと*汎化能力*とか言っちゃったりします。

そこで出てくるのが**サポートベクトル**で、識別平面に最も近いデータがサポートベクトルになるわけです。
(枠で囲っている点2つが今回のサポートベクトルになる)
そうして決まったサポートベクトルと識別平面の距離(マージン)が最大になるwとbを求めることになります。
<img width="250px" alt="マージン最大化" src="https://qiita-image-store.s3.amazonaws.com/0/211139/156945c9-0701-2d7f-d227-829672010fa4.png">

マージンの求め方
---

マージン、つまり*[識別平面との垂線の長さ](http://w3e.kanazawa-it.ac.jp/math/category/kika/zutohouteisiki/henkan-tex.cgi?target=/math/category/kika/zutohouteisiki/suisen-no-nagasa.html)*を求めるためには、三角比などを用いる必要があります。

ここで、`g(x)=1`となるような場合の範囲と`g(x)=-1`となるような範囲は以下のように決まります
(g(x)がy軸と考えればわかりやすいかと)

```math
正:g({\rm x}) \leqq 1\\
負:g({\rm x}) \geqq -1
```

負の式に-1を両辺にかけて、正負の記号tを置いてあげると、二つの式は一緒くたにまとめれます。

```math
tg({\rm x}) \leqq 1\\
\leftrightarrow t({\bf w}^{\rm T}{\bf x} + b) \leqq 1\\
t = (1, -1)
```

サポートベクトルの推薦の長さは上記の結果と*[識別平面との垂線の長さ](http://w3e.kanazawa-it.ac.jp/math/category/kika/zutohouteisiki/henkan-tex.cgi?target=/math/category/kika/zutohouteisiki/suisen-no-nagasa.html)*の知見から

```math
\frac{1}{\|{\bf w}\|}
```
となり、正のデータのサポートベクトルと負のデータのサポートベクトルのマージンの差は、
2/|w|となるので、このマージン最大化問題は以下のように定式化できますね

```math
t({\bf w}^{\rm T}{\bf x} + b) \leqq 1の制約で\\
{\bf w}の最小値、つまり\frac{2}{\|{\bf w}\|}の最大値を求める
```
wが小さくなればなるほど、上の下段式が大きくなっていきます。
また、wの評価関数を与えてあげるとこういう問題になります。

```math
1/2{\bf w}^{\rm T}{\bf w}
```

この制約付き問題を解くために、ラグランジュの未定乗数をつけてあげて解きますが、
今回は体力的な事情で省略します(苦笑い)。

そうすると、双対問題に発展してくるのですが、そのあたりは
[僕のおざなりな発表資料](https://www.slideshare.net/secret/r9BEPhSIRRmpxP)を見ていただくと、双対問題とは？？というのがわかるかと思います。

ざっくり説明すると、ラグランジュの未定乗数をつけると、解くべき問題(今回だとwとbを求める問題)が未定乗数に出てくる変数を求める問題([参項](http://www.sist.ac.jp/~kanakubo/research/neuro/supportvectormachine.html))に置き換わります。
解くべき問題を**主問題**、置き換えた後の問題を**補問題**と呼び、どちらを解いても(双対している)解がもとまるので双対問題と呼びます。

ソフトマージンとハードマージン
---

先ほどまでもとめていたマージン最大化はデータ集合自体が線形分離可能な場合のみ、使える技なのです。
<img width="250px" alt="線形分離不可能な場合" src="https://qiita-image-store.s3.amazonaws.com/0/211139/d0b21f25-f9a6-6a21-45cf-2ac73f1a0cf9.png">

上図のようなノイズが載ってまとまってないようなデータ集合の場合はいつまでたっても最適なwを求められない問題が生じてきます。マージンに対して厳密に分けようとするからハードマージンなんて言ったりします。
(※本当は別の意味で数式の解釈でハードマージンと呼ぶのですが直感的解釈でおｋ)

**ハードがあるならソフト**もある、ということでソフトマージンの考えが導入されます。

```math
t({\bf w}^{\rm T}{\bf x} + b) \leqq 1 - \xiの制約で\\
1/2{\bf w}^{\rm T}{\bf w} + C\sum_{i=1}^{n}\xi_{n} の評価関数の最大化を行うwを求める
```
ここで`C`と`ξ`というパラメータが出てきました。

`ξ`がどれだけ識別平面を緩和してあげるかという*スラック変数*
`C`がどれだけ厳しくマージンを決めるかという*パラメータ*になります。

この場合のSVMはパラメータCを用いるのでC-SVMなんて呼ばれたりします。

**最終的にはハードマージンと同様の形の双対問題を解くことになり、めでたしめでたしです。**

12/24のエキサイトアドベントカレンダーではpythonのscikit-learnを用いてC-SVMのパラメータ調節をまとめます。