数学的に考えてみる(ハードマージンSVM)

HOME>>メモ>>アルゴリズム>>SVM>>数学的に考えてみる(ハードマージンSVM)
もっと数学的な説明が欲しい方のために、少しまとめてみました。

仕組み

簡単な仕組みはハードマージンSVMを参照してください。 JavaScript+SVGで実装した例があります。

問題の定式化

データ$\bm x_i$が$y_i=-1$と$y_i=+1$のどちらかのクラスに分類されているものとします。 この分類が線形分離可能で、 \[\bm w\cdot\bm x + b = 0\] で表される超平面で完全に分類できるものと仮定します。 ここで$\bm w$は重みベクトル、$b$はバイアスパラメータです。

超平面の方程式は両辺を定数倍しても変わらないので、一つに決めることができません。 そこで、二つの超平面 \[\bm w\cdot\bm x + b = +1\] \[\bm w\cdot\bm x + b = -1\] の間(下図の点線の間)にはデータが存在しないという条件をつけることにします。 この条件は$y_i$を使って次のように表すことができます。 \[y_i(\bm w\cdot\bm x_i + b) \le 1\]

マージン最大化

このような条件下ではマージンは$2/||\bm w||$とかけます。 マージン最大化問題は、これを最大化するパラメータを求める問題と考えることができます。

ただし、これを直接最大化するは難しいので、次のように書き換えておきます。

\[y_i(\bm w\cdot\bm x_i + b) \le 1\] の条件下で \[\frac{1}{2}||\bm w||^2\] を最小化する。

双対問題への置き換え

上の最小化問題は、条件式がありそのまま扱うのは面倒です。 そこで、ラグランジュの未定乗数を導入し、 \[L(\bm w, b, \bm \alpha)=\frac{1}{2}||\bm w||^2+\sum_{i=1}^{n}\alpha_i \left\{1-y_i(\bm w\cdot\bm x_i + b)\right\}\] の最小化と置き換えます。 このとき、不等式制約条件を持つ関数最適化問題の一種なのでKKT条件から次の条件を満たす必要があります。 \[\frac{\partial}{\partial \bm w}L(\bm w, b, \bm \alpha)=0, \frac{\partial}{\partial b}L(\bm w, b, \bm \alpha)=0\] \[\alpha_i \ge 0\] これから \[\bm w = \sum_{i=1}^{n}\alpha_i y_i\bm x_i\] \[\frac{\partial}{\partial b}L(\bm w, b, \bm \alpha)=\sum_{i=1}^{n}\alpha_i y_i=0\] が得られます。するとラグランジュ関数を次のように書き換えることができます。 \begin{eqnarray*} L(\bm w, b, \bm \alpha)&=&\frac{1}{2}||\bm w||^2+\sum_{i=1}^{n}\alpha_i - \bm w\cdot\sum_{i=1}^{n}\alpha_i y_i\bm x_i - b\sum_{i=1}^{n}\alpha_i y_i \\ &=&\sum_{i=1}^{n}\alpha_i - \frac{1}{2}||\bm w||^2 \\ &=&\sum_{i=1}^{n}\alpha_i - \frac{1}{2}\sum_{i,j}\alpha_i\alpha_j y_i y_j \bm x_i \bm x_j \end{eqnarray*}

以上のことをまとめると、 \[\alpha_i \ge 0\] \[\frac{\partial}{\partial b}L(\bm w, b, \bm \alpha)=\sum_{i=1}^{n}\alpha_i y_i=0\] の条件下で、 \[L(\bm w, b, \bm \alpha)=\sum_{i=1}^{n}\alpha_i - \frac{1}{2}\sum_{i,j}\alpha_i\alpha_j y_i y_j \bm x_i \bm x_j \] を最小化する$\alpha_i$を求める問題に帰着できました。 この問題は二次計画問題と呼ばれる問題で、局所解が最適解になることが保証されており、効率的に解くアルゴリズムがいくつか知られています。

このとき \[\bm w = \sum_{i=1}^{n}\alpha_i y_i\bm x_i\] で重みを求めることができます。 さらに、bの値はKKT条件の相補条件から、$\alpha_i$が0で無いベクトル(サポートベクトル)から $b=y_i-\bm{w}\cdot\bm{x}_i$ となります。

SMOアルゴリズム

考え方

この問題は一般的な二次計画問題として解くこともできますが、SVMに対して有効なアルゴリズムがいくつか提案されています。 代表的なものがSMO(Sequential Minimal Optimization)アルゴリズムです。

一度にすべての変数考えることは難しいので、いくつか適当な変数を選び、これらの変数に関する最適化問題を考えます。 他の変数は定数と考えます。 この部分問題を最適化をすることによって、元の問題も最適解へ近づくはずだ、と言うのがSMOの基本的な考え方です。

アルゴリズム

1つの変数をいじると、拘束条件を満たすために最低もう一つ変数を選んで変更しなければなりません。 そこで、適当な二変数\[\alpha_{i_1},\alpha_{i_2}\]を選んで、この二変数に対する最適化問題を考えます。

\[\alpha_{i_1} \rightarrow \alpha_{i_1} + \delta_{i_1},\alpha_{i_2} \rightarrow \alpha_{i_2} + \delta_{i_2}\]に置き換えるとします。 このとき、目的関数$L(\bm w, b, \bm \alpha)$から関係する項だけを抜き出したものを$O(\delta_{i_1}, \delta_{i_2})$とすると \begin{eqnarray*} O(\delta_{i_1}, \delta_{i_2}) &=& \delta_{i_1}+\delta_{i_2} -\delta_{i_1}y_{i_1}\sum_{i=1}^n\alpha_iy_i\bm{x}_{i_1}\bm{x}_i -\delta_{i_2}y_{i_2}\sum_{i=1}^n\alpha_iy_i\bm{x}_{i_2}\bm{x}_i\\ & & -\frac{1}{2}\delta_{i_1}^2\bm{x}_{i_1}\bm{x}_{i_1} -\delta_{i_1}\delta_{i_2}y_{i_1}y_{i_2}\bm{x}_{i_1}\bm{x}_{i_2} -\frac{1}{2}\delta_{i_2}^2\bm{x}_{i_2}\bm{x}_{i_2} \end{eqnarray*} となります。また、制約条件から \[\left\{ \begin{array}{rcl} \delta_{i_1}y_{i_1}+\delta_{i_2}y_{i_2}&=&0\\ \alpha_{i_1} + \delta_{i_1}&\ge&0\\ \alpha_{i_2} + \delta_{i_2}&\ge&0 \end{array} \right.\] です。

制約条件から、$\delta_{i_2}=-y_{i_1}y_{i_2}\delta_{i_1}$なので、 \begin{eqnarray*} O(\delta_{i_1}, \delta_{i_2}) &=& \left(y_{i_1}-y_{i_2}- \sum_{i=1}^n\alpha_iy_i\bm{x}_{i_1}\bm{x}_i+ \sum_{i=1}^n\alpha_iy_i\bm{x}_{i_2}\bm{x}_i\right)y_{i_1}\delta_{i_1}\\ & & -\frac{1}{2}\left(\bm{x}_{i_1}\bm{x}_{i_1}- 2\bm{x}_{i_1}\bm{x}_{i_2}+ \bm{x}_{i_2}\bm{x}_{i_2}\right)\delta_{i_1}^2 \end{eqnarray*} となります。$\partial O/\partial\delta_{i_1}=0$より \[ \delta_{i_1} = \frac{\displaystyle \left(\sum_{i=1}^n\alpha_iy_i\bm{x}_{i_2}\bm{x}_i-y_{i_2}\right)- \left(\sum_{i=1}^n\alpha_iy_i\bm{x}_{i_1}\bm{x}_i-y_{i_1}\right) }{ \bm{x}_{i_1}\bm{x}_{i_1}- 2\bm{x}_{i_1}\bm{x}_{i_2}+ \bm{x}_{i_2}\bm{x}_{i_2} }y_{i_1} \] と、更新式が得られます。ただし、制約条件を満たすように、クリッピングする必要があります。

２変数の選び方には、ランダムに選ぶ、KKT条件を満たさないものから順に選ぶなどの さまざまな手法が提案されています。 ハードマージンSVMでの実装はランダムに選択しています。