ハードマージンSupport Vector Machine - danglingfarpointer's memoization

ハードマージンSVM(Support Vector Machine)の勉強のまとめ。以下の資料に基づく。

資料: http://cs229.stanford.edu/notes/cs229-notes3.pdf

1. はじめに

正例と負例を分割する識別平面を求める際、識別平面のマージン、つまり識別平面の両サイドで訓練データが存在しない領域が、なるべく大きくなるようにしたい。

SVMを使うと、訓練データが線形識別可能な場合、マージンを最大化する識別平面を求めることが出来る。

2. 記法

$x$を特徴ベクトル、$y$を特徴ベクトルが正例か負例かを表すラベルとする。正例の場合は$y=+1$, 負例の場合は$y=-1$.

重みベクトル$w$としきい値$b$をつかって、識別平面を$w^Tx+b = 0$と定義する。$w^Tx+b$の正負により正例か負例かを判定することになるので、識別器$h_{w, b}$は以下のように定義される。 $$ h_{w,b}(x) = \begin{cases} +1 & & (if\ w^Tx+b \geq 0)\\ -1 & & (otherwise) \end{cases} $$

訓練データとして与える特徴ベクトルを$x^{(i)}$, そのラベルを$y^{(i)}$とする。

識別平面が訓練データを正しく識別することは、全ての$i$について $y^{(i)}(w^Tx^{(i)}+b)\geq 0$が成り立つことと同値である。

3. マージンの定義

訓練データと識別平面が与えられた時の"マージン"を定義する。

まずは訓練データ$x^{(i)}$と識別平面$w^Tx+b = 0$の距離$\gamma^{(i)}$について考えてみる。

訓練データ$x^{(i)}$が正例($y^{(i)}=+1$)である場合、識別平面の垂直ベクトルは$w/\|w\|$であり、かつ正例の空間を向いていることから、 $x^{(i)}$から識別平面に垂線を下ろした時の交点は、$x^{(i)}-\gamma^{(i)}\cdot w/\|w\|$となる。交点は識別平面上であることから、以下が成り立つ。 $$ w^T(x^{(i)}-\gamma^{(i)}\cdot w/\|w\|) - b = 0 $$ 従って、$\gamma^{(i)}$は以下のようになる。 $$ \gamma^{(i)} = \frac{w^Tx^{(i)}+b}{\|w\|} $$

一方で、訓練データが$x^{(i)}$が負例である場合は、 $$ \gamma^{(i)} = -\frac{w^Tx^{(i)}+b}{\|w\|} $$ となる。従って、識別平面が訓練データを正しく識別する場合は、正例・負例を問わず、$\gamma^{(i)}$は以下のように書ける。 $$ \gamma^{(i)} = y^{(i)}\cdot\frac{w^Tx^{(i)}+b}{\|w\|} $$

ここで、"マージン"を$\gamma^{(i)}$の中で最小のもの、つまり$\min_i \gamma^{(i)}$と定義する。

4. マージンの最大化

マージンを最大化する$w$と$b$, つまり、 $$ \begin{eqnarray} \max_{w, b}\min_i \gamma^{(i)} &=& \max_{w, b}\min_i y^{(i)}\cdot\frac{w^Tx^{(i)}+b}{\|w\|}\\ &=& \max_{w, b}\left(\frac{1}{\|w\|}\min_i y^{(i)}(w^Tx^{(i)}+b)\right) \end{eqnarray} $$ を与える$w$と$b$を求めていきたい。

ここで、$w$と$b$に任意の正の定数をかけても、識別平面の意味は変わらない。つまり、$\min_i y^{(i)}(w^Tx^{(i)}+b)=1$という条件を設けても構わない。すると、 $$ \begin{eqnarray} & &\max_{w, b}\frac{1}{\|w\|} \\ & & s.t.\ \ \forall i.\ y^{(i)}(w^Tx^{(i)}+b) \geq 1 \end{eqnarray} $$ という問題を解けばよいことになる。計算を解きやすくするために、以下の同値の問題に変換する。 $$ \begin{eqnarray} & &\min_{w, b}\frac{1}{2}\|w\|^2 \\ & &s.t.\ \ 1 - y^{(i)}(w^Tx^{(i)}+b) \leq 0\ \ (\forall i) \end{eqnarray} $$ この最適化問題の解となる$w, b$を求めていく。

ところで、$\min_i y^{(i)}(w^Tx^{(i)}+b)=1$を与える$x^{(i)}$,つまり識別平面に最も近い訓練データをサポートベクターと呼び、このアルゴリズム名の由来となっている。

5. 双対問題への変換

上記の最適化問題をそのまま二次計画問題として解くこともできるが、より効率的に解くために、ラグランジュの双対性を用いる。制約条件を$g_i(w, b)=1 - y^{(i)}(w^Tx^{(i)}+b)$ と置いた上で、ラグランジュ乗数$a_i\ (\geq 0)$を用いてラグランジュ関数に変換する。 $$ L(w, b, a)=\frac{1}{2}\|w\|^2 + \sum_i a_i g_i(w, b) $$ すると、元々解こうとしていた最適化問題（primal; 主問題）は、 $$ \begin{eqnarray} & & \min_{w, b}\max_{a; a_i\geq 0}L(w, b, a)\\ & & s.t.\ \ g_i(w, b) \leq 0\ \ (\forall i) \end{eqnarray} $$ と書ける（$g_i(w, b) = 1 - y^{(i)}(w^Tx^{(i)}+b) \leq 0\ \ (\forall i)$の条件で $\max_{a; a_i\geq 0}L(w, b, a)=\frac{1}{2}\|w\|^2$であるから）.

これの双対問題(dual)は、minとmaxを入れ替えたもの、つまり $\max_{a; a_i\geq 0}\min_{w, b}L(w, b, a)$と定義される。主問題と双対問題の間では以下の関係が成り立つ（弱双対定理）。 $$ \max_{a; a_i\geq 0}\min_{w, b}L(w, b, a) \leq \min_{w, b}\max_{a; a_i\geq 0}L(w, b, a) $$ さらに、

目的関数（$\frac{1}{2}\|w\|^2$）が凸であり、
かつ各制約関数$g_i$がアフィン関数であり、
かつ$g_i$が実行可能である（$g_i(w, b)\leq 0\ \ (\forall i$を満たす$w, b$が存在する; the weak Slater's condition）

場合、上記の式で等号が成り立つ（強双対定理）。実際にこれらの条件を満たすので、主問題の代わりに双対問題を解けば、主問題の最適解が見つかったことになる。

6. 双対問題の最適解

そこで、双対問題$\max_{a; a_i\geq 0}\min_{w, b}L(w, b, a)$を解いていく。まずは、$L(w, b, a)$を$w$と$b$に関して最小化する。 $\nabla_w L(w, b, a)=0$という条件から、 $$ w=\sum_i a_iy^{(i)}x^{(i)} $$ が導かれる。これを$L(w, b, a)$に代入すると以下の式が得られる。 $$ L(w, b, a)=\sum_i a_i - \frac{1}{2}\sum_{i, j}y^{(i)}y^{(j)}a_ia_j(x^{(i)})^Tx^{(j)} - b\sum_i a_iy^{(i)} $$

さらに$\frac{\partial}{\partial b}=0$という条件から $$ \sum_ia_iy^{(i)}=0 $$ が導かれる。そのため、上記$L(w, b, a)$の最後の項は$0$となる。以上から、$L(w, b, a)$を$w$と$b$に関して最小化した結果は、 $$ L(w, b, a)=\sum_i a_i - \frac{1}{2}\sum_{i, j}y^{(i)}y^{(j)}a_ia_j(x^{(i)})^Tx^{(j)} $$ となる。

次のステップは、上記を$a$について最大化する。 $$ \begin{eqnarray} & & \max_a & & \sum_i a_i - \frac{1}{2}\sum_{i, j}y^{(i)}y^{(j)}a_ia_j(x^{(i)})^Tx^{(j)}\\ & & s.t. & & a_i \leq 0\ \ (\forall i)\\ & & & & \sum_i a_i y^{(i)} = 0 \end{eqnarray} $$ この双対問題はSMO(Sequential Minimall Optimization)というアルゴリズムで解ける。基本的には、ベクトル$a$の中から2変数を選択し、$\sum_i a_i y^{(i)} = 0$ を満たすように動かすことで最適解に近づいていく、というもののようだ。

SMOにより最適な$a$（$a^\ast$とする）が見つかったとすると、 $w=\sum_i a_iy^{(i)}x^{(i)}$という条件から、最適な$w$が以下のように求まる。 $$ w^\ast=\sum_i a_i^\ast y^{(i)}x^{(i)} $$

$b$については以下のように求まる。主問題での制約条件 $1 - y^{(i)}(w^Tx^{(i)}+b) \leq 0\ \ (\forall i)$から、$b$は $$ 1-w^{\ast T} x_{I^+}\leq b \leq -1-w^{\ast T}x_{I^-} $$ を満たさねければならない。ここで、$x_{I^+}=\arg\!\min_{x_i} \{w^{\ast T} x_i \mid y_i = +1\}$, $x_{I^-}=\arg\!\max_{x_i} \{w^{\ast T} x_i \mid y_i = -1\}$である。そこで、上記の右辺と左辺の中間をとるのが最適なので、 $$ b^\ast = - \frac{1}{2}(w^{\ast T} x_{I^+} + w^{\ast T}x_{I^-}) $$ となる。

以上より、識別平面が求まった。 $$ \begin{eqnarray} w^{\ast T}x + b^\ast &=& (\sum_i a_i^\ast y^{(i)}x^{(i)})^T x + b^\ast \\ &=& \sum_i a_i^\ast y^{(i)}\langle x^{(i)}, x\rangle - \frac{1}{2}(w^{\ast T} x_{I^+} + w^{\ast T}x_{I^-}) \end{eqnarray} $$

7. KKT条件

強双対条件が成り立つ場合、最適解$w^\ast, b^\ast, a^\ast$に関して、 KKT条件と呼ばれるいくつかの条件式が成り立つ。そのうちの1つが、KKT相補性条件と呼ばれる以下のものである。 $$ a_i^\ast g_i(w^\ast, b^\ast) = 0\ \ (\forall i)$$ この条件から、もし$g_i(w^\ast, b^\ast) < 0$, つまり $1 < y^{(i)}((w^\ast)^Tx^{(i)}+b^\ast)$ならば、$a_i^\ast = 0$という制約が導かれる。今、 $\min_i y^{(i)}(w^Tx^{(i)}+b)=1$という条件のもとで問題を解いていた。つまり、最も識別平面に近い訓練データ（サポートベクター）ではない場合、 $1 < y^{(i)}(w^Tx^{(i)}+b)$のはずなので、 $a_i^\ast = 0$となる。つまり、サポートベクター以外の大多数の訓練データについて$a_i^\ast = 0$となるので、求まった識別平面による判別は十分効率的である。