Introduction
SVMの理論編を書いていこうと思います。実装編は
線形SVMの実装
カーネルSVMの実装
をご覧ください。
このpart 1の記事ではSVMの目的関数の導出までを書いていきます。
概要
一般化線形モデル
SVMには一般化線形モデルが使われています。一般化線形モデルとは次のようなモデルのことです。
$$f(x) = w^T\phi(x) + b$$
bはバイアスと呼ばれています。
$$0 = w^T\phi(x) + b$$は超平面（n次元平面）を表します。この超平面は$\phi(x)$をきれいに２クラスに分類するように決めます。
ここで$\phi(x)$は平面で分類できないようなxを平面で分類できる特徴空間に送る写像です。
$\phi(x)$のイメージは以下の画像を見てください。
次に、SVMの目的を説明します。
SVMの説明
私たちの目的は決定関数と呼ばれるものを作ることです。
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ではマージンと呼ばれる値を使い、最適な境界線を決定します。
ハードマージン
マージンとは何なのでしょうか？
境界$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
線形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では以下のようなものです。
$$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ではマージンと呼ばれる値を使い、最適な境界線を決定します。
ハードマージン
マージンとは何なのでしょうか？
境界$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
コメント
コメントを投稿