Processing math: 0%
スキップしてメイン コンテンツに移動

SVMの理論 part 1

Introduction  

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)をきれいに2クラスに分類するように決めます。

ここで\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||}
      と表されます。

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


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

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

      よって、今全てのデータは線形分離可能であることを仮定しているので、
      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_iw^T \phi(x) + b = 0を超えている場合、 \epsilon_i > 0 が成り立ちます。

      x_5x_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

        コメント

        このブログの人気の投稿

        カーネルK-means 理論編

        Introduction English ver 今日は、カーネルK-meansの理論について書きます。カーネルK-meansは通常のK-meansの欠点を補うことができます。通常のK-meansの欠点とカーネルK-meansの強みも説明します。もし、まだ御覧になられていなければ、通常の K-means 理論編 の記事を見ていただけるとよいのではないかと思います。 カーネルK-meansの実装編 も併せてご覧ください。 概要 K-meansの弱点 カーネルトリック カーネルK-means アルゴリズム K-meansの弱点 例えば、次のようなデータを用意します。 このデータはK-meansによってうまく分類することはできません。なぜなら通常のK-meansでは、データとプロトタイプのユークリッド距離に依存しているからです。そのため、このような円状に分布しているデータはうまく分類することができません。 プロトタイプとはそれぞれのクラスにあり、そのクラスを代表するようなもののことです。K-meansでは各クラスの平均ベクトルとなります。それゆえ、以下のような分類になってしまいます。 このようなデータではK-meansはうまくいきません。 K-meansで分類できるデータセットは次のように各クラスで固まっている必要があります。 カーネルK-meansはK-meansの弱点を補います。 カーネルトリック 初めに、カーネルトリックを説明します。 線形分離できないようなデータXを例えば次のように線形分離できるように\phi(x)に送る写像\phiを考えます。 カーネルは次のように定義されます。 K(x,y) = \phi(x)^T \phi(y) \phiを具体的に計算することは難しいですが、K(x,y)を計算することなら簡単です。 この手法をカーネルトリックと呼ばれます。 カーネルK means K-meansの目的関数を復習しておきます。 J = \sum_{n=1}^{N} \sum_{k=1}^{K} r_{nk} ||x_n-\mu_k||^2 ここで、 プロトタイプは\mu_i ~\forall k \in Kとしま...

        ダイクストラ法

        Introduction English ver 今日は、ダイクストラ法について書きます。ダイクストラ法とは最短距離を求めるアルゴリズムです。地図はグラフで表されます。もし、まだ this page を見ていない方は先にこちらをご覧ください。今回はこの記事を前提としています。このページでは、グラフの定義と、ヒープ構造について書いています。ダイクストラ法ではヒープ構造を使って、かなりの計算量を落とします。 この スライド はダイクストラ法を説明したスライドです。 Overview アルゴリズム 実装 アルゴリズム このアルゴリズムは スタート始点のノードを決める。そして、それをAと名付ける。 各ノードにd=\inftyを割り当てる。ただし、スタート地点はd=0 Aの隣接ノードのリストをadj_listと名付ける。  For adj in adj_list:  If d of adj > d of A + weight to adj -> d = A + weight to adj. グラフnetworkからAを取り除く グラフnetworkの中で最初のdを持っているノードをAとし、4に戻る。 となっています。 このアルゴリズムを図を用いて説明します。  このグラフを使って説明します。  初めに、スタート地点を決めます。そして、各ノードにd=\inftyを割り当てます。  Aから始まります。Aの隣接ノードであるBのdを更新します。もし、現在のBよりもAのdとA->Bへの重みを足したもののほうが小さいならdをその値に更新します。同じようにCnのdを更新します。 次にAを取り除きます。  次はBから始まります。Aと同じことをやります。 このダイクストラ法では今のような操作をグラフの全てのノードに×がつくまで続きます。 実装 このアルゴリズムではO(log(|V|^2))という計算量を持っています。最小のdを持つノードを探すのに時間がかかります。 しかし、ヒープ構造を使えばO((E+V)log(V))に減らせます。ヒープ構造で現時点での...

        Visualization of Variational method

        Introduction Today, I will implement visualization of Variational method. Variational method is used when we want to minimize functional. functional is function of function. Please look at  [1] , [2] , [3] , [5]  and  [6] . Overview formula  Implementation Visualization Formula I used following formula. F(x) = \sqrt{1+(\frac{du}{dx}(x))^2} l(u) = \int_{0}^{1} \sqrt{1+(\frac{du}{dx}(x))^2} dx l(u) is the length of the u(x).  I want to minimize l(u) subject to u(0)=a and u(1)=b. u minimizing I(u) is  u(x) = (b-a)x+a This u is line from (0,a) to (1,b). Because l(u) is the length of the u(x), We found out that u minimizing l(u) is line. Please look  [5]  to calculate of variational method. Implementation I implement visualization of variational method to check difference of optimize curve and other curve.  Let u_A is  u_A = (b-a)x+a + A sin(8t) A sin(8t) increase the di...