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$ はハイパーパラメータ