はじめに

スタンフォード大学 Andrew Ng氏による機械学習の講義動画を各週社内メンバーで持ち回りで受講し、学んだことを発表、Qiitaで共有しています。
その第七回が今回の記事です。

社内輪講をやるにあたっての記事です。
【機械学習】社内輪講はじめました

第六回の講義が以下の記事
【機械学習】社内輪講 Week6 〜モデルの評価と改善〜

本講義の導入

これまでの講義の中で、ロジスティック回帰やニューラルネットワークなど、様々なアルゴリズムを学んできましたが、
複雑な非線形のものを分類するアルゴリズムとして、もう一つ、紹介します。
それが、サポートベクターマシン。
アルゴリズムが明確で、優れた認識性能を発揮するので、様々なところで活用されており、人気のアルゴリズムの一つです。

そもそもサポートベクターって？

データを分類し、他のクラスに一番近いデータをサポートベクトルと言います。
下記のような○と✖︎のデータがあったとすると、それぞれに一番近いデータ(赤丸)をサポートベクターとなります。

このサポートベクター間のマージンを最大化するのが、サポートベクターマシンです。

まずは目的関数から

ロジスティック回帰の時はコスト関数を下記のように表しておりました。
(忘れたかたはこちら)

J(\theta) = -ylog(\frac{1}{1+e^{-z}})-(1-y)log(1-\frac{1}{1+e^{-z}})

z = \theta^{T}x

上記を最小化するために、

$y=1$のとき、$z>0$
$y=0$のとき、$z<0$
となる$\theta$を学習させてました。

今回のサポートベクターマシンでは、ややこしいことはやめて、

$y=1$の時、$z$が1以上の時はコストが0、$z$が1以下の時は線形に増加
$y=0$の時、$z$が-1以下の時はコストが0、$z$が-1以上の時は線形に増加

とし、それぞれのコスト関数を

$y=1$の時、$cost_1(z)$
$y=0$の時、$cost_0(z)$

とします。

その時、サポートベクターマシンの目的関数をロジスティック回帰の時のように当てはめると、下記のように記述できます。

\frac{1}{m}[\sum_{i=1}^my^{(i)}cost_1(\theta^Tx^{(i)})+(1-y)^{(i)}cost_1(\theta^Tx^{(i)})]+\frac{\lambda}{2m}\sum_{j=1}^n\theta_j^2

また、サポートベクターマシン用に、新しいパラメタ$C(C=\frac{m}{\lambda})$を設定すると、

C[\sum_{i=1}^my^{(i)}cost_1(\theta^Tx^{(i)})+(1-y)^{(i)}cost_1(\theta^Tx^{(i)})]+\sum_{j=1}^n\theta_j^2

となります。
$C$がとても大きな値だとすると、、、
この目的関数を最小化しないといけないので、下記を最小化させたい。

\sum_{i=1}^my^{(i)}cost_1(\theta^Tx^{(i)})+(1-y)^{(i)}cost_1(\theta^Tx^{(i)})

先ほどの、
$y=1$の時、$z$が1以上の時は$cost_1=0$
$y=0$の時、$z$が-1以下の時は$cost_0=0$
$z=\theta^Tx^{(i)}$
から考えると、
$y^{(i)}=1$の時、$\theta^Tx^{(i)}\geq1$
$y^{(i)}=0$の時、$\theta^Tx^{(i)}\leq-1$

その時の目的関数は以下となります。

\sum_{j=1}^n\theta_j^2

すごいシンプルになりました。

決定境界の考え方

サポートベクターマシンがどのようにマージンを決定しているのかを考えていきます。

下記の図のようにベクトル$x$をベクトル$\theta$上に射影したものの長さを$p^{(i)}$とすると、

$\theta^Tx^{(i)}$はベクトルの内積を計算してますので、

\theta^Tx^{(i)}=p^{i}・\|\theta\|

となります。

さてここで、◯と×のような2種類のデータがあった時に、下記のように適当に2つを分類するような直線を引きます。

なんとなく、悪そう。

直線の垂線ベクトルを$\theta$、一番近い◯データを$x^{(i)}$とすると下記のようになります。

ここで思い出していただきたいのが、

\theta^Tx^{(i)}\leq-1

\theta^Tx^{(i)}=p^{i}・\|\theta\|

この2つの式。
$\theta^Tx^{(i)}$を-1より小さい値にするためには、$|\theta|$は固定なので、$p^{i}$をできる限り長くなるような直線を引かなければならない。
こうして求められた直線が決定境界となります。

カーネルについて

これまで、サポートベクターマシンで扱ってきたのが、線形分類のみでしたが、サポートベクターマシンでも非線形分類にも対応することができます。
それを可能にするのが、カーネルを用いた手法になります。
カーネルは重づけを行い、非線形の問題を線形に置き換えて考えようという手法です。

例えば下記のような非線形分類をサポートベクターマシンで行う時に、カーネルを使用します。(グラフが汚くてすみません。。。)

そこで、入力値$x^{(i)}$を用いて新たな関数$f$を定義してきます。

まずは下記のように任意の3つのランドマーク$l^{(1)},l^{(2)},l^{(3)}$を設定したとします。

この時、入力$x^{(i)}$とランドマークの近似値を$f_{(i)}$を下記のように表します。

f_i=similarity(x, l^{(i)})=exp(-\frac{\|x-l^{(i)}\|}{2\sigma})

$|x-l^{(i)}|$はランドマークと入力とのユークリッド距離を表しており、
$x$が$l^{(i)}$から近ければ、$f_i\approx1$
$x$が$l^{(i)}$から遠ければ、$f_i\approx0$となります。

$\sigma$はどこまでの距離を許容するかのパラメータとなります。
$\sigma$が大きいと、ランドマークから離れるに連れて、$f_i$が緩やかに1から0になり、
$\sigma$が小さいと、ランドマークから離れるに連れて、$f_i$がすぐに1から0になります。

先ほどの3つのランドマーク$l^{(1)},l^{(2)},l^{(3)}$を設定した際は

y=1　if　\theta_0+\theta_1f_1+\theta_2f_2+\theta_3f_3\geq0

y=0　if　\theta_0+\theta_1f_1+\theta_2f_2+\theta_3f_3<0

と定義し、予測を行います。
こうすることで、サポートベクターマシンにおいても、非線形分類を解くことができます。

ロジスティック回帰とサポートベクターマシンの使い分け

では、どの様にロジスティック回帰とサポートベクターマシンを使い分ければ良いのかをご紹介いたします。
大きく分けて下記の通り3つあります。

特徴量の数が、サンプル数より多い場合は、ロジスティック回帰か、カーネルを使用しないサポートベクターマシン
特徴量の数が、1000以下程度で、サンプル数が10,000程度とそこそこの場合は、カーネルを使用したサポートベクターマシン
特徴量の数が、1000以下程度で、サンプル数が50,000以上と多い場合は、ロジスティック回帰か、カーネルを使用しないサポートベクターマシン

この3つをベースに、使い分けると、より効果的に活用できます。

以上、今回はサポートベクターマシンについての説明でした。

次回はWeek8 〜教師なし学習: 特に固有値問題〜について学んでいきます。