SVMの理論 part 1

Introduction  

English ver

SVMの理論編を書いていこうと思います。実装編は
線形SVMの実装
カーネルSVMの実装
をご覧ください。
このpart 1の記事ではSVMの目的関数の導出までを書いていきます。

概要

• 一般線形モデル
• SVMの説明
• ハードマージン
• ソフトマージン

一般化線形モデル 

SVMには一般化線形モデルが使われています。一般化線形モデルとは次のようなモデルのことです。
$$f(x) = w^T\phi(x) + b$$
bはバイアスと呼ばれています。

$$0 = w^T\phi(x) + b$$ は超平面（n次元平面）を表します。この超平面は$\phi(x)$をきれいに２クラスに分類するように決めます。

ここで$\phi(x)$は平面で分類できないようなxを平面で分類できる特徴空間に送る写像です。
$\phi(x)$のイメージは以下の画像を見てください。

左は線形分離不可能なデータ。右は$\phi(x)$によって特徴空間に移された線形分離可能なデータです。

よって$w^T \phi(x) + b$は特徴空間では平面となります。

次に、SVMの目的を説明します。

SVMの説明

SVMではラベルは1 or -1として扱います。$y \in \{1,-1\}$、Xをデータセットとします。
私たちの目的は決定関数と呼ばれるものを作ることです。
SVMでは以下のようなものです。
$$f(x_i) > 0 \implies y_i = 1$$
$$f(x_i) < 0 \implies y_i = -1$$

f(x)は $w^T \phi(x) + b$とし、パラメータwとbを最適化します。
しかし、最適化するにはあるよい基準が必要になります。SVMではマージンと呼ばれる値を使い、最適な境界線を決定します。

ハードマージン

SVMはマージンと呼ばれる値を用いて、クラスの境界は決定されます。
マージンとは何なのでしょうか？


境界$w^T \phi(x) +b = 0$から一番近いデータ$x_i$を持ってきます。マージンとは、境界と$x_i$との距離のことを言います。
次の画像は二次元でのデータに対して、マージンを可視化したものです。

この緑の線がマージンになります。SVMでは$w^T \phi(x) + b= 0$という境界は$w^T \phi(x) + b = 0$から最も近いデータのみに依存して決められます。このデータ点のことをサポートベクトルといいます。一般に二つ以上あります。

私たちはマージンを最大化させるようなw,bを求め、境界を求めます。これは境界線と互いのクラスのデータをできるだけ話したいからです。

データセットをXとします, $\forall x_i \in X$, xと境界$w^T \phi(x) + b = 0$の距離は
$$\frac{|w^T \phi(x_i) + b|}{||W||}$$
と表されます。

今、すべてのデータ点は線形分離可能とします。つまり、特徴空間において、ある平面で完全に２クラスを分けることができるということです。

この画像は線形分離可能なデータです。

これは線形分離可能ではないデータです。

よって、今全てのデータは線形分離可能であることを仮定しているので、
$$f(x_i) > 0 \implies y_i = 1$$
$$f(x_i) < 0 \implies y_i = -1$$
が必ず成立している必要があります。

よって、
$$\forall i \in N,~~~~~~~y_i(w^T \phi(x_i) + b) > 0$$
が成り立ちます。

そして、
$$\frac{|w^T \phi(x_i) + b|}{||W||} = \frac{y(w^T \phi(x_i) + b)}{||W||}$$
として、絶対値を外すことができます。

次に$i_0$を次のような値とします。

$$\forall i_0 \in \arg_{n \in N} \min_{x \in X} \frac{|w^T \phi(x_n) + b|}{||W||}$$ ,

そして、Mを
$$M = y_{i_0}(w^T \phi(x_{i_0}) + b)$$
と定義します。
ここで、$\forall i \in N,~y_i(w^T \phi(x_i) + b) > 0$なので、$M > 0$が常に成り立ちます。

Mは境界$w^T \phi(x) + b = 0$から最も近いデータまでの距離を表しています

よって目的関数は次のように表されます。

$$\max_{w,b,M} \frac{M}{||W||}$$ $$~~s.t~~ \forall i \in N ~, y_i(w^T \phi(x_i) + b) \geq M$$

$w^{\star}  = \frac{w}{M}, b^{\star}  = \frac{b}{M}$とし、目的関数を変数変換します。
$$\max_{w^{\star},b^{\star}} \frac{1}{||W^{\star}||}$$
$$~~s.t~~ \forall i \in N, y_i (w^{\star} \phi(x_i) + b^{\star}) \geq 1$$


$||W^{\star}|| > 0$なことから、
$$\max_{w^{\star},b^{\star}} \frac{1}{||W^{\star}||}$$
$$\iff \min_{w^{\star},b^{\star}}  ||W^{\star}||$$
$$\iff \min_{w^{\star},b^{\star}}  ||W^{\star}||^2$$
と書き換えることが可能です。

よってSVMの目的関数は
$$\min_{w,b}  ||W||^2$$
$$~~s.t~~ \forall i \in N, y_i (w^T \phi(x_i) + b) \geq 1$$
と書くことができます。

ただし、$W^{\star} = W, b^{\star} = b$と再び定義しなおしました。

ここまで、データが完全に超平面で分離できることを仮定していました。この手法はハードマージンと呼ばれています。

しかし、現実のデータは完全に線形分離できることは稀です。そこでハードマージンに代わり、ソフトマージンと呼ばれるものが開発されました。

ソフトマージン
$\epsilon_i \geq 0$ を新たに目的関数に導入することを考えます。

$\forall i \in N, y_i (w^T \phi(x_i) + b) \geq 1$という条件を緩和します。 条件を書き換えると以下のようになります。

$$\forall i \in N, y_i (w^T \phi(x_i) + b) \geq 1 - \epsilon_i$$

もし、$x_i$が$w^T \phi(x) + b = 0$を超えている場合、 $\epsilon_i > 0$ が成り立ちます。

$x_5$と$x_8$とx_9$は境界$w^T \phi(x) + b = 0$を超えています。 この黒い線の距離が\epsilon_i$の値になります。

目的関数を次のように書き替えます。
$$\min_{w,b}  \frac{1}{2}||W||^2 + C\sum_{i \in N} \epsilon_i$$
$$~~s.t~~ \forall i \in N, y_i (w^T \phi(x_i) + b) \geq 1 - \epsilon_i ,~~~~\epsilon \geq 0 , \forall i \in N$$

Cは正規化係数と呼ばれています。
このパラメータはハイパーパラメータであり、自分であらかじめ決めておく必要があります。Cは誤分類の抑制を調節する役割を担っています。Cが小さくなればなるほど、$\sum_{i \in N}\epsilon_i$が目的関数に与える影響は少なくなり、$\epsilon_i$は大きい値をとることができてしまします。よってたくさんの誤分類を許してしまうことになります。反対に、 Cが大きくなればなるほど、$\sum_{i \in N}\epsilon_i$が目的関数に与える影響は大きくなり、最小化をする上で$\epsilon_i$はあまり、大きい値をとれなくなります。
$C = \infty$とすると、これはハードマージンと同一視することができます。
Reference

https://www.amazon.co.jp/%E3%82%B5%E3%83%9D%E3%83%BC%E3%83%88%E3%83%99%E3%82%AF%E3%83%88%E3%83%AB%E3%83%9E%E3%82%B7%E3%83%B3-%E6%A9%9F%E6%A2%B0%E5%AD%A6%E7%BF%92%E3%83%97%E3%83%AD%E3%83%95%E3%82%A7%E3%83%83%E3%82%B7%E3%83%A7%E3%83%8A%E3%83%AB%E3%82%B7%E3%83%AA%E3%83%BC%E3%82%BA-%E7%AB%B9%E5%86%85-%E4%B8%80%E9%83%8E/dp/4061529064