#SVM(サポートベクトルマシン)
教師あり学習。

2クラス分類問題(与えられた入力データが2つのカテゴリーのどちらに属するかを識別する。1か-1どちらかに分類する)を扱える。

最初は2クラス問題のために考案されたが、実は下記にも応用されている。

回帰問題
教師なし問題

##決定関数
忘れてしまうので、決定関数は下記ですよ。

f(x) = w^Tx+b \\
f(x) = w^T\phi(x)+b \\

この関数の正負で判断する。
分類するときは$ sign (w^Tx+b)$ で判断するので、-1 or 1 で分類する。

##線形サポートベクトル分類(ハードマージン)
分類境界を挟んで2つのクラスがjはなれている距離をマージンと呼ぶ。
マージンを最大化するような分類境界を探す。
訓練データを完璧に分類できる決定関数f(x)が存在するという仮定を置いています。
これ、重要。

分類境界と、点の距離は下記で表せる。

||w|| = \sqrt{w_1^2+w_2^2 + ... + w_n^2}\\
として、\\

\frac{|f(x_i)|}{||w||} = \frac{|w^Tx_i+b|}{||w||}\\
=\frac{y_i[w^Tx_i+b]}{||w||}\\

上記を最大化する。

※ ||w|| はL2ノルムです。

距離に関する式は下記となり。。。

\underset{i}{min}[y_i[w^Tx_i+b]] = M(w,b)

【制約条件】
全ての i に対して$y_i[w^Tx_i+b] \geqq M(w, b) $

元に戻って、この距離を最大化することなので、やりたいことは下記式。

\underset{w,b}{max}\frac{M(w,b)}{||w||}

wとbを規格化すると、

\tilde{w} = \frac{w}{M(w,b)}\\
\tilde{b} = \frac{b}{M(w,b)}

距離の式をゴニョゴニョすると。。。

\underset{w,b}{min}\frac{1}{2}{||w||}^2

【制約条件】
全ての i に対して $y_i[w^Tx_i+b] \geqq 1$

この式を最適化する。
分離可能性を仮定したSV分類のことを一般にハードマージン(hard margin)と呼ぶ。

分類境界に最も近いデータ$x_i$(マージン上のサンプル)をサポートベクトルと呼ぶ。

##線形サポートベクトル分類(ソフトマージン)
線形サポートベクトル分類(ハードマージン)は、訓練データを完璧に分類できる決定関数f(x)が存在するという仮定がある。これを現実に適用すると、そんなことはない。
SV分類を分離可能でないデータに適用できるように拡張したもの。

どうするかというと、制約条件を変える。

y_i[w^Tx_i+b] \geqq 1 -\xi_i

マージン内に入るデータや誤分類されたデータに対する誤差を表す変数 $\xi$ を導入している。

$\xi$ をスラック変数と呼ぶ。

それで、最適化する式は下記となる。

\underset{w,b,\xi}{min} [ \frac{1}{2}{||w||}^2 + C \sum_{i=1}^n \xi_i ]

【制約条件】
全ての i に対して$y_i[w^Tx_i+b] \geqq 1 -\xi_i$ で $\xi \geqq 0$

Cを正則化係数という。
Cが大きいほど誤分類が少なく良い分類境界を構成できる。
Cが無限大に近くなると、誤判定は許さないよ！(過学習気味。ハードマージンと変わらない)
Cが小さいと、多少の誤判別許すよ。まあ、いいじゃん的な。(汎化寄り。未学習)

Cが大きすぎるとデータが分離可能でない場合、あらゆる分離境界に対して目的関数が発散する可能性がある。
Cはちょうど良い値を決める必要がある。

最適化する式を、SV分類の主問題(primal problem)と呼ぶ。
でも、等価な相対問題(dual problem) を解くのが一般的。

下記のメリットがある。

双対問題の方が変数を少なくできる
分類境界の非線形化を考えうと、双対問題の形式(双対形式)の方が良い。

##双対問題

ラグランジュ関数を導入して、これを解く。

L(w,b,\xi,\alpha,\mu) = \frac{1}{2}||w||^2 + C\sum_{i=1}^n\xi_i - \sum_{i=1}^n\alpha_i[y_i[w^Tx_i + b]-1+\xi_i]-\sum_{i=1}^n\mu_i\xi_i\\
\alpha = (\alpha_1,...,\alpha_n)^T\\
\mu = (\mu_1,...,\alpha_n)^T\\

やりたいことは、下記を最大化すること。

\underset{w,b,\xi}{min}L(w,b,\xi,\alpha,\mu)

色々、ゴニョゴニョすると、要するに。。。

\underset{\alpha,\mu}{max}L(w,b,\xi,\alpha,\mu) =
\underset{\alpha}{max}[-\frac{1}{2}\sum_{i=1}^n\sum_{j=1}^n\alpha_i\alpha_jy_iy_jx_i^Tx_j + \sum_{i=1}^n\alpha_i]

ただし、下記条件を満たす。

\sum_{i=1}^n\sum_{j=1}^n\alpha_iy_i = 0\\
0 \leqq \alpha_i \leqq C

$\alpha$の制約は下記。

C - \alpha_i - \mu_i = 0\\
C - \alpha_i = \mu_i \geq 0\\
C \geq \alpha_i \geq 0

$\alpha$ だけの最適化問題になってます。

##主問題と双対問題のまとめ
主問題は、主変数{w,b,$\xi$)に対する最適化問題。

双対問題は、双対変数{$\alpha, \mu$)に対する最適化問題。

最適化問題の最適解を右肩に*をつけると、それぞれの最適値は下記になる。

###主問題

\underset{\alpha,\mu}{max}L(w^*,b^*,\xi^*,\alpha,\mu)

###双対問題

\underset{w,b,\xi}{min}L(w,b,\xi,\alpha^*,\mu^*)

主問題と双対問題の間で下記不等式が成り立つ。

\underset{w,b,\xi}{min}L(w,b,\xi,\alpha^*,\mu^*)
\leq
\underset{\alpha,\mu}{max}L(w^*,b^*,\xi^*,\alpha,\mu)

この関係性を弱相対性と呼ぶ。
弱相対性は、あらゆる最適化問題で成立する。

そして、SV分類の場合には、これよりさらに強い強双対性(strong duality)が成り立つ。

\underset{w,b,\xi}{min}L(w,b,\xi,\alpha^*,\mu^*)
=
\underset{\alpha,\mu}{max}L(w^*,b^*,\xi^*,\alpha,\mu)

※強双対性は、「鞍点定理」とも呼ばれる。

##カーネルトリック
特徴ベクトルを非線形変換して、その空間での線形分類を行う。
これによって、線形な決定関数では、うまく分離できないケースに対して解くことができる。

何をするかというと、入力データを高次元(特徴空間)に拡張する。
すると、線形分離が可能になる場合がある。

高次元に拡張 -> 2次元を3次元に変換する。

変換の際、カーネル関数を使うので、カーネルトリック(かな？)。

###カーネル関数
カーネル関数として使用する代表的な関数は下記がある。

正規化線形カーネル

K(x, x')= \frac{x^Tx'}{||x|| ||x'||}\\
定義を下記とすると\\
k(x,x') = \phi(x)^T\phi(x')\\
特徴ベクトル \phi(x) は、\frac{x}{||x||} になる。

多項式カーネル

K(x_i, x_j)=[x_i^Tx_j + c]^d

ガウスカーネル (RBFカーネル)

K(x_i, x_j)=exp(-\gamma || x_i-x_j||^2)

シグモイドカーネル

K(x_i, x_j)=\tanh(bx_i^Tx_j + c)

※c, d, $\gamma$ はハイパーパラメータ