verum ipsum factum

sudillap's blog

サポートベクターマシンとは[ハードマージンサポートベクターマシン]

まずはじめに訓練データが線形分離可能な場合について定式化します。この場合のサポートベクターマシンをハードマージンサポートベクターマシンと呼びます。
線形分離できないデータへの拡張(ソフトマージンサポートベクターマシン)については次の記事で説明します。

準備

まず初めに記号を定義しておきます。

訓練データのサイズ(個数):$l$
訓練データの次元:$n$
とすると、属性データの集合$X$とそれに対応するクラスの集合$Y$をそれぞれ次のように表記します。
$$
\begin{align}
X &= \{x_1, x_2, \ldots, x_l\}, x_i \in \Re^n\\
Y &= \{y_1, y_2, \ldots, y_l\}, y_i \in \{-1, 1\}
\end{align}
$$
$X$の各要素$x_i$が1個の訓練データに相当し、それぞれ$n$次元ベクトルであることに注意してください。
またデータ$x_i$のクラスは$y_i$となります。後の定式化が楽になるようにクラスの値は1(正例)または-1(負例)である仮定します。
たとえば、スパム判定問題の場合には、メール$x_i$がスパムであるときそのクラス$y_i$は1,スパムでないときは-1となります。
このとき訓練データの集合$D$は
$$
\begin{align}
D &= \{(x_1, y_1), \ldots, (x_l, y_l)\}, (x_i, y_i) \in \Re^n \times \{-1, 1\}\\
&= X \times Y
\end{align}
$$
と表現できます。

分類超平面と決定関数

さらに両クラスのデータを2つに綺麗に分類(分割)する超平面(分類超平面と呼びます)の方程式を
$$
w^Tx+b=0
$$
と表記します。ここで$w \in \Re^n$は超平面から直角に正例データのある方向に向かうベクトル(法線ベクトル)、$b \in \Re$は切片に相当します。また、$w^Tx$は$w$と$x$の内積、$x^T$の$T$は転置記号です。
念の為に書いておきますと、この式の$x$は単に$\Re^n$空間の変数を表しているだけです。訓練データの$x_i$ではありません。

この分類超平面の一方に正例データ、反対側に負例データがありますので、分類超平面の式を求めさえすれば、$x$に未知のデータを代入した結果をもとにこのデータを正例または負例に分類することができます。

すなわち、サポートベクターマシンで分類超平面の式の$w$と$b$が求まれば、未知データ$x$の属するクラス$y$は次の式(決定関数、識別関数と呼ばれます)で求めることができます。
$$
\begin{align}
y &=
\begin{cases}
1, & \text{if } w^T x +b \geqq 0 \\
-1, & \text{if } w^T x +b < 0
\end{cases}\\
&= \text{sgn}(w^T x + b)
\end{align}
$$
ここで$\text{sgn}(x)$は符号関数で次で定義されます。
$$
\text{sgn}(x) =
\begin{cases}
1, & \text{if } x \geqq 0 \\
-1, & \text{if } x < 0
\end{cases}
$$

このように未知のデータでも精度良く分類できる分類超平面(式の$w$と$b$)を求めることがサポートベクターマシンアルゴリズムの目的となります。

これからサポートベクターマシンを構成していくわけですが、その前に用語を定義します。

支持超平面
分類超平面から最短距離にある正例または負例のデータを通り、かつ、分類超平面と平行な超平面のこと。下図の点線が支持超平面となります。
マージン
分類超平面を挟む2枚の支持超平面の間の距離のこと(下図参照)。
サポートベクター
支持超平面の上にちょうど乗っているデータのこと(下図参照)。

f:id:sudillap:20130405012035p:plain

さて、SVMでは分類超平面を求めるわけですが、いまのままでは分類超平面が一つに決まりません。実際、正例と負例を分ける超平面は無数に存在します。たとえば、上の図にあるように緑の実線で表された超平面も、黒の実線の超平面も共に分類超平面の候補となります。

このままでは困るので、サポートベクターマシンでは、分類性能の高い分類超平面を一意に決めるために、超平面に次の条件を課します。

  • 分類超平面は正例と負例のちょうど真ん中に位置する
  • マージンを最大にする

したがってこれらの条件を満たす分類超平面を求めることになるわけですが、上図を見ればわかるように、実際は少数のサポートベクターの情報さえあれば分類超平面を決定できます。それ以外の大部分の訓練データは分類超平面の決定に影響しないということになります。

分類超平面の導出

支持超平面は分類超平面($w^Tx+b=0$)に平行なので、正例側および負例側の支持超平面は、それぞれ次のように表現できます($k>0$)。
$$
\begin{align}
w^Tx+b &= k\\
w^Tx+b &= -k
\end{align}
$$

直線(平面)の方程式を定数倍しても、元の直線(平面)と同じなので、支持超平面の式($w^Tx+b=\pm k$)を$1/k$倍して
$$\frac{1}{k}w^Tx+\frac{1}{k}b=\pm 1$$
とできます。$1/k$があると式変形が煩雑になるため、
$$\frac{1}{k}w \rightarrow w, \frac{1}{k}b \rightarrow b$$
と書き直すことにより、最終的に支持超平面は
$$w^Tx+b=\pm 1$$
と表現できます。同様に分類超平面はつぎの式になります。
$$w^Tx+b=0$$

では、分類超平面の$w$と$b$を具体的に求めましょう。

まずは、上述した分類超平面の条件である、マージンの最大化、を検討します。

f:id:sudillap:20130405012042p:plain

$x_p$、$x_q$をそれぞれ正例側、負例側のサポートベクターとすると、支持超平面間のマージン$m$はつぎのようになります(上図を参照)。
$$
\begin{align}
m &= ||x_p-x_q||\cos\theta \\
&=||x_p-x_q||\frac{w^T(x_p-x_q)}{||w|| ||x_p-x_q||} (\because a^Tb=||a|| ||b||\cos\theta)\\
&=\frac{w^Tx_p-w^Tx_q}{||w||}\\
&=\frac{(1-b)-(-1-b)}{||w||} (\because w^Tx_p+b=1, w^Tx_q+b=-1)\\
&=\frac{2}{||w||}
\end{align}
$$

マージン$m$の最大化は、
$$
\begin{align}
\max_{w, b}\frac{2}{||w||} &\Rightarrow \min_{w, b} 2||w||\\
&\Rightarrow \min_{w, b} 2||w||^2\\
&\Rightarrow \min_{w, b} \frac{||w||^2}{2}
\end{align}
$$
と表現出来ます。ここで、$\max_{w, b}, \min_{w, b}$はそれぞれ$w$と$b$に関する最大化、最小化を意味する記号です。また最小化(最大化)の対象となる式($||w||^2/2$)のことを目的関数と呼びます。

上の式変形についてそれぞれコメントします。

  • $1/||w||$を最大化するということは、$||w||$を最小化することと同じ
  • $||w||$を最小化するということは、その2乗$||w||^2$を最小化することと同じ
  • $||w||^2$を最小化することは、$||w||^2/2$を最小化することと同じ(後の式変形の都合上2で割っています)

以上より、マージンを最大化するには、目的関数$||w||^2/2$を最小化する$w$を求めれば良いことが分かりました。

この目的関数$||w||^2/2$の式だけをみると$w=0$とすれば最小化できますが、実際には後述する制約条件(正例・負例は分類超平面の片側のみに存在という条件)を考慮に入れて最小化しなければいけないため、$w=0$とすることはできません。

つぎに、もう一つの分類超平面の条件である、分類超平面は正例と負例のちょうど中間に位置、について考えます。後述しますが、この条件から導かれる関係式が上述の最小化問題の制約条件になります。

分類超平面は正例と負例のちょうど中間に位置することから、分類超平面の片側には正例データまたは負例データのみ存在します。これを数式で表現することを考えます(下の図を参照)。

f:id:sudillap:20130405012047p:plain

まず正例側にある支持超平面の場合から。

図の$x_A, c, z$はすべてベクトルなので、$x_A=c+z$が成り立ちます。この式と$w$の内積を計算すると
$$
\begin{align}
w^Tz&=w^Tx_A-w^Tc\\
&=w^Tx_A-(1-b) (\because w^Tc+b=1)
\end{align}
$$
正例データは支持超平面($w^Tc+b=1$)の左側にのみある、すなわち角度$\theta$は$-\frac{\pi}{2} \leqq \theta \leqq \frac{\pi}{2}$なので
$$
\begin{align}
w^Tz&=||w|| ||z||\cos\theta\\
&\geqq 0
\end{align}
$$
となります。これらの式から
$$
\begin{align}
w^Tx_A-(1-b)\geqq 0\\
\Downarrow\\
w^Tx_A+b\geqq 1
\end{align}
$$
が成り立ちます。


負例データの場合も同様の方法で求めます。$x_B=c+z$と$w$の内積を計算すると
$$
\begin{align}
w^Tz&=w^Tx_B-w^Tc\\
&=w^Tx_B-(-1-b) (\because w^Tc+b=-1)
\end{align}
$$
負例データは支持超平面($w^Tc+b=-1$)の右側にのみ存在、すなわち角度$\theta$は$\frac{\pi}{2} \leqq \theta \leqq \frac{3\pi}{2}$なので
$$
\begin{align}
w^Tz&=||w|| ||z||\cos\theta\\
& \leqq 0
\end{align}
$$
となります。これらの式から
$$
\begin{align}
w^Tx_B-(-1-b)\leqq 0\\
\Downarrow\\
w^Tx_B+b\leqq -1
\end{align}
$$
が成り立ちます。


以上をまとめておきます。

正例データのクラスは1($y=1$)、負例データのクラスは-1($y=-1$)であったことを思い出すと、あるデータ$x$のクラスは
$$
y =
\begin{cases}
1, & \text{if } w^T x +b \geqq 1 \\
-1, & \text{if } w^T x +b < -1
\end{cases}
$$
で求められます。

この式のままですと場合分けの必要があるため取り扱いが面倒なので一つの式で表現することを考えます。
正例データは$y=1$なので、上の正例の場合の式を$y$を用いて書き換えると
$$
w^Tx+b\geqq 1\\
\Downarrow \\
1(w^Tx+b)\geqq 1\\
\Downarrow\\
y(w^Tx+b)\geqq 1
$$
となります。同様に負例データのクラスは$y=-1$なので
$$
w^Tx+b\leqq -1\\
\Downarrow \\
-1(w^Tx+b)\geqq 1\\
\Downarrow \\
y(w^Tx+b)\geqq 1
$$
となります。これで正例・負例の場合をまとめて一つの式
$$
y(w^Tx+b)\geqq 1
$$
で表現できました。

これが前述した目的関数$||w||^2/2$を最小化する際の制約条件となります。

これで必要な関係式が揃いましたので、分類超平面を求める問題は次の最適化問題として定式化できます。

最大マージン分類器

線形分離可能な訓練データ
$$D = \{(x_1, y_1), \ldots, (x_l, y_l)\}, (x_i, y_i) \in \Re^n \times \{-1, 1\}$$
が与えられたとき、次の制約付き最適化問題を解き最大マージン分類超平面$w^Tx+b=0$を求めます。

目的関数(コスト関数)の最小化

$$\min_{w, b} \frac{||w||^2}{2}$$

制約条件

$$y(w^Tx+b)\geqq 1$$

これからこの最適化問題を解いていきます。