1. SVMとは
SVM、サポートベクターマシン（サポートベクトルマシン）は、機械学習の教師あり学習のひとつ。SVMは、データ集合に対して、データを分類するためのデータ境界線をひいて、データを2クラス分類するためのアルゴリズム。
とある特徴ベクトル$x$が与えられたときに、クラスAなら、$y=1$、クラスBなら、$y=-1$という結果を出力する決定関数 $ f(x) = w^T x + b$を構築するアルゴリズムといえる。
決定関数 f(x) = w^T x + b \\
y= sign( f(x) ) =
\left\{
\begin{array}{ll}
+1 & (f(x) \gt 0) \\
-1 & (f(x) \lt 0)
\end{array}
\right.
決定関数$f(x)$の結果の正負によって、分類$y$の結果を出している。
$f(x)$は、上の図の場合、真ん中の境界線であるが、実際には、この線は、$f(x)$という平面との交点を示している。$f(x)$は、上の縦横の2次元平面とは別の超平面を示しており、境界線は、$f(x)=0$となる位置。
決定関数の$w$と$b$は未知パラメータなので、これを求める必要がある。
2. 決定境界線の求め方
決定境界線を決めるという事は、決定関数$f(x)$の最適な$w$と$b$を求めることを意味する。
しかしこの境界線は、完全にきれいに分類するための線が引けるとは限らない。どちらか分からないというグレーゾーンが発生する。このため、完全に分類出来る場合と出来ない場合の2種類の考え方がある。
- ハードマージン
- ソフトマージン
2.1. マージン最大化
SVMは、分類境界線から、２クラスのデータまでの距離（マージン）が大きく離れていれば離れているほど精度よく分類することができる。このため、出来るだけマージンを最大化する$w$と$b$を求めることをマージンの最大化という。
実際には、分類境界線から、一番近くにあるデータ$x_i$との距離を最大化するような境界線になる$w$と$b$を求める。
この距離は以下で表現される。
距離D=
\frac{|f(x_i)|}
{||w||}
=
\frac{|w^T x_i + b|}
{||w||}
\\
||w|| = \sqrt{w_1^2 + w_2^2+ \cdots + w_n^2}
$||w||$は、L2ノルム（ユークリッド距離：普通の距離）である。
この距離の求め方は、平面と点の距離の公式である。
2.1.1. 平面と点の距離公式
ちょっと公式の復習をしておく。
平面p_0 : ax + by + cz + d= 0 \\
点A :(x_0, y_0, z_0) \\
平面p_0と点Aの距離D
=
\frac{|ax_0 + by_0 + cz_0+d|}
{\sqrt{a^2+b^2+c^2}}
2.2. ハードマージン
データ集合をきれいに分類出来る境界線を引く考え方をハードマージンという。
これは、境界線の中にデータが入ることを許容しないということである。
これは、つまり、あるデータ$x_i$に関する決定関数$f(x)$の結果がプラスなら、分類結果$y$も必ずプラスになるということである。逆もしかり。つまりいかが成り立つ。
ハードマージンの前提条件 \\
y_i f(x_i)>0 (i=1,2, \cdots,n)
正しく分類できない場合、符号が逆になるので上記が満たされない。
2.2.1. サポートベクトル
分類境界線から最も近いデータ$x_i$をサポートベクトルと呼ぶ。
サポートベクトルは、境界の正負それぞれにあるので、最低でも2個ある。
このサポートベクトル$x_i$までの距離Dは次のようになる。
サポートベクトルまでの距離D =
\min_i
\frac{|f(x_i)|}
{||w||}
=
\min_i
\frac{|w^T x_i + b|}
{||w||}
各データ点$x$と境界までの距離のなかで一番近いものをminで求めている。
そして、ここで以下の符号の条件を使うと、
ハードマージンの前提条件 \\
y_i f(x_i)>0 (i=1,2, \cdots,n)
次の変形が出来る。
サポートベクトルまでの距離D =
min_i
\frac{|w^T x_i + b|}
{||w||}
=
\min_i
\frac{y_i[w^T x_i + b]}
{||w||} \\
=
\frac{1}{||w||}
\min_i [y_i[w^T x_i + b]] \\
\equiv \frac{M(w,b)}{||w||}
$[ ]$ は、ガウス記号（その数を超えない最大の整数）。
$ \equiv$ は同等。
2.2.2. ハードマージンの最大化
ハードマージンの最大化とは、上記で求まる一番近くのサポートベクトル$x_i$までの距離を最大化することを意味する。
つまり、以下の距離を最大化する$w$と$b$を求めればよい。
max_{w,b}(サポートベクトルまでの距離D) =
\max_{w,b}[
\min_i
\frac{y_i[w^T x_i + b]}
{||w||} ]\\
=
max_{w,b} \frac{M(w,b)}{||w||}
ただし、以下の制約条件が付く。
\min_i {y_i[w^T x_i + b]} = M(w,b)\\
上記より、\\
{y_i[w^T x_i + b]} \gt M(w,b)\\
整理すると、以下の2式を満たす$w$と$b$を求めればよい。これが目的関数である。
\max_{w,b} \frac{M(w,b)}{||w||}\\
{y_i[w^T x_i + b]} \gt M(w,b)\\
2.2.3. 目的関数の標準化（規格化）
上記の目的関数が少しわかりにくいため、規格化すると、以下。
\max_{w,b} \frac{1}{||\tilde{w}||}\\
{y_i[\tilde{w}^T x_i + \tilde{b}]} \gt 1\\
\\
※ \tilde{w} = \frac{w}{M(w,b)}, \tilde{b} = \frac{b}{M(w,b)}
また、$\max_{w,b} \frac{1}{||\tilde{w}||}$は、逆数を取ると$\min_{w,b} ||\tilde{w}||$と等価のため、目的関数を規格化すると以下になる。
\min_{w,b} \frac{1}{2}||\tilde{w}||^2\\
{y_i[\tilde{w}^T x_i + \tilde{b}]} \geq 1\\
ここでチルダはとっておく。
目的関数 \; \; \min_{w,b} \frac{1}{2}||{w}||^2\\
制約条件 \; \; y_i[{w}^T x_i + {b}] \geq 1\\
2.3. ソフトマージン
ハードマージンは、データ集合を奇麗に2分するという考え方だった。しかし現実はそう甘くない。綺麗に分かれてくれないデータも存在する。その際に使うのがソフトマージンという考え方である。簡単に言えば、少しくらい境界線の内側にあるデータがあっても良しとしようという考え方である。
ハードマージンの時は、境界線と各データの制約条件として以下があった。
y_i[w^T x_i + b] \geq 1\\
この制約条件を少し緩和するために、スラック変数$ \xi $ （グザイ）を入れる。このスラック変数は、マージンより中に入ってきてしまったデータ点$x_i$の、マージンからの距離を表している。つまり、マージン線より中に入ってきている点も、制約条件を満たせるような数式になる。
制約条件 \; \; y_i[w^T x_i + b] \geq 1 - \xi_i \; \; (i=1, \cdots ,n)\\
よって、ソフトマージンの時の目的関数と制約条件は以下のようになる。
目的関数 \; \; \min_{w,b, \xi} \left[\frac{1}{2}||{w}||^2 + C \sum_{i=1}^n \xi_i \right]\\
制約条件 \; \; y_i[w^T x_i + b] \geq 1 - \xi_i \; \; (i=1, \cdots ,n)\\
目的関数の第1項は、マージンを最大化する役割。第2項は、スラック変数$\xi$が小さくなるようにする。つまり誤分類を少なくする役割。
Cはハイパーパラメータなので、調整が必要。Cを大きくするとハードマージンに近づき、マージン内に訓練データが入ることや誤分類を一切許容しなくなる。このため、線形分離出来ないデータ集合に対してCを大きくすると、計算おかしくなる。またこれは、訓練データに特化。つまり過学習することになる。
逆に、Cを小さくすると、誤分類が多くなる。しかし、過学習防止のためには、Cは小さいほうがよい。
3. SV分類の主問題と双対問題
サポートベクターマシンは、前節までのソフトマージン、ハードマージンの目的関数の最適化問題に帰着する。
しかし実際の現場では、この最適化問題をそのまま解かずに、これと等価な別の問題を解く。理由は、計算を簡単にするためである。
3.1. 主問題
線形分離可能なデータ、線形分離不可能なデータに関して、以下の最適化問題を解く必要がある。これを主問題という。
ハードマージンの場合
目的関数 \; \; \min_{w,b} \frac{1}{2}||{w}||^2\\
制約条件 \; \; y_i[{w}^T x_i + {b}] \geq 1 \; \; (i=1, \cdots ,n)\\
ソフトマージンの場合
目的関数 \; \; \min_{w,b, \xi} \left[ \frac{1}{2}||{w}||^2 + C \sum_{i=1}^n \xi_i \right]\\
制約条件 \; \; y_i[w^T x_i + b] \geq 1 - \xi_i \; \; (i=1, \cdots ,n)\\
3.2. 双対問題
主問題と等価だが、変数を減らすことができる双対問題を解くことが計算的には楽である。
3.2.1. ソフトマージンの場合の双対問題
ソフトマージンの目的関数のハイパーパラメータCを∞に大きくするとハードマージンと同じになるため、まずはソフトマージンの双対問題を考える。
ソフトマージンの場合の主問題の最適化問題
目的関数 \; \; \min_{w,b, \xi} \left[ \frac{1}{2}||{w}||^2 + C \sum_{i=1}^n \xi_i \right]\\
制約条件 \; \; y_i[w^T x_i + b] \geq 1 - \xi_i \; \; (i=1, \cdots ,n)\\
ソフトマージンの場合の双対問題
上記の主問題を解く双対問題として、ラグランジュ関数を利用する。
ここで出てくる$\alpha、 \mu$は、ラグランジュ未定乗数法では、ラグランジュ乗数といわれる。
L(w,b, \xi, \alpha , \mu) =
\frac{1}{2} ||w||^2 +
C \sum_{i=1}^n \xi_i -
\sum_{i=1}^n \alpha_i \left[ y_i [ w^T x_i + b] -1 + \xi_i \right] -
\sum_{i=1}^n \mu_i \xi_i \\
\\
\alpha_i \geqq 0, \; \mu_i \geqq 0 \;\; (i=1,\cdots , n) \\
このラグランジュ関数の最適解問題が双対問題である。主問題とは違って、制約条件はない。
目的関数： \; \max_{\alpha, \mu} \left[ \min_{w,b, \xi} L(w,b, \xi, \alpha, \mu) \right] \\
A1:極値問題（最小）
まずラグランジュ関数に対して、$w,b,\xi$で最小値を求めるので、極値問題と考えられる。偏微分の値が０になるところを求める。
\frac{\partial}{\partial w} L(w,b, \xi, \alpha, \mu) |_{w=w^*} = w^* - \sum_{i=1}^n \alpha_i y_i x_i = 0 \\
\frac{\partial}{\partial b} L(w,b, \xi, \alpha, \mu) |_{b=b^*} = - \sum_{i=1}^n \alpha_i y_i = 0 \\
\frac{\partial}{\partial \xi_i} L(w,b, \xi, \alpha, \mu) |_{\xi_i=\xi_i^*} = C - \alpha_i - \mu_i = 0 \\
A2:極値問題（最小）の反映
A1にて、$w,b,\xi$が定数として求まっているので、それを反映すると、$\alpha,\mu$の関数となる。
目的関数： \; \max_{\alpha, \mu} \left[ \min_{w,b, \xi} L(w,b, \xi, \alpha, \mu) \right]
=
\max_{\alpha, \mu} L (w^*,b^*, \xi^*, \alpha, \mu)
これをもとのラグランジュ関数として展開して、偏微分の結果を代入すると、
L (w^*,b^*, \xi^*, \alpha, \mu) =
\frac{1}{2} w^{*T} w^* -
\sum_{i=1}^n \alpha_i y_i w^{*T} x_i -
b^* \sum_{i=1}^n \alpha_i y_i +
\sum_{i=1}^n \alpha_i +
\sum_{i=1}^n \left[ C - \alpha_i -\mu_i \right] \xi_i^* \\
=
- \frac{1}{2} \sum_{i=1}^n \sum_{j=1}^n \alpha_i \alpha_j y_i y_j x_i^T x_j + \sum_{i=1}^n \alpha_i \\
A3:極値問題（最大）
A2の結果を見ると、最終的には$\alpha$だけの関数になっている。これを元の式に反映すると。
目的関数： \; \max_{\alpha, \mu} \left[ \min_{w,b, \xi} L(w,b, \xi, \alpha, \mu) \right]
=
\max_{\alpha, \mu} L (w^*,b^*, \xi^*, \alpha, \mu) \\
= \max_{\alpha}
\left[
- \frac{1}{2} \sum_{i=1}^n \sum_{j=1}^n \alpha_i \alpha_j y_i y_j x_i^T x_j + \sum_{i=1}^n \alpha_i
\right] \\
制約条件： \; \sum_{i=1}^n \alpha_i y_i = 0, \; \; 0 \leqq \alpha_i \leqq C \; \; (i=1,\cdots, n) \\
ハードマージンの場合、Cを∞に考えればよい。つまり無視できる。
4. 非線形データの場合の別次元への射影
線形分離が不可能なデータ集合を分離する場合、射影関数で別次元へと写像（高次元の特徴空間への変換）を行う。
これは例えば、2次元データでは、分離出来なくとも、3次元にデータ拡張（写像）してやれば、高さ方向の超平面で分離が可能になるという考え方である。
写像関数： \; \phi{(x)} \\
(x_1,x_2) \; \; →写像→ \; \; (x_1, x_2, x_1^2 + x_2^2)
この写像を使うことで、非線形データの双対問題は以下のように書ける。
目的関数：
= \max_{\alpha}
\left[
- \frac{1}{2} \sum_{i=1}^n \sum_{j=1}^n \alpha_i \alpha_j y_i y_j x_i^T x_j + \sum_{i=1}^n \alpha_i
\right] \\
= \max_{\alpha}
\left[
- \frac{1}{2} \sum_{i=1}^n \sum_{j=1}^n \alpha_i \alpha_j y_i y_j \phi(x_i)^T \phi{(x_j)} + \sum_{i=1}^n \alpha_i
\right] \\
ここで、写像を使った内積計算$\phi(x_i)^T \phi(x_j)$ は、莫大な演算になる。このため、カーネル関数Kで置き換える。これによって簡単な内積計算にして計算コストを下げる。これがカーネルトリックである。
K(x_i,x_j) = \phi(x_i)^T \phi(x_j) \\
\\
目的変数： \; \; \max_{\alpha}
\left[
- \frac{1}{2} \sum_{i=1}^n \sum_{j=1}^n \alpha_i \alpha_j y_i y_j K(x_i,x_j) + \sum_{i=1}^n \alpha_i
\right] \\
\\
制約条件： \; \; \sum_{i=1}^n \alpha_i y_i = 0 \\
4.1. カーネル関数
カーネル関数にはいくつかの種類がある。
- 多項式カーネル
- ガウスカーネル（RBFカーネル）
- シグモイドカーネル
4.1.1. 多項式カーネル
K(x_i,x_j)= \left[ x_i^T x_j + c \right]^d
c,dはハイパーパラメータである。
4.1.2.ガウスカーネル（RBFカーネル）
最もよく使われるカーネル関数になる。
K(x_i,x_j)= exp ( - \gamma || x_i - x_j ||^2 )
$\gamma $はハイパーパラメータである。個々のデータの影響範囲を調整する値になる。
個々のデータの影響範囲の半径の逆数である。
よって、値を小さくすれば、影響が強くなる。
逆に、 値を大きくすれば、影響が弱くなる。(個々のデータの特徴に引っ張られ決定境界線が複雑になる。）
$\gamma = \frac{1}{2 \sigma^2}$ なので、以下のように表現されるときもある。
K(x_i,x_j)= exp ( \frac{- || x_i - x_j ||^2}{2 \sigma^2} )
4.1.3.シグモイドカーネル
K(x_i,x_j)= \tanh \left( b x_i^T x_j + c \right)
cはハイパーパラメータである。