マージン最大化と SVM

線形分離の場合，サンプルを分離する超平面は一般に無限にたくさんある． 次元を上げれば上げるほどその自由度は高くなる． パーセプトロンはそのなかのどれかに収束することしか保証してくれない． サポートベクタマシン (SVM) では，そのような超平面のうち 一番近いサンプル点までの距離(これをマージンという)が最も大きいものを選ぶ．

とりあえずカーネルのことは忘れて，特徴空間のサンプルを超平面で分けること を考えよう． 識別超平面 $\mbox{\boldmath$w$}\cdot\mbox{\boldmath$\phi$}(\mbox{\boldmath$x$})=0$ は $\mbox{\boldmath$w$}$ に任 意の正定数を掛けても不変なので，正のサンプルに対して $\mbox{\boldmath$w$}\cdot\mbox{\boldmath$\phi$}(\mbox{\boldmath$x$})\ge1$，負のサンプルに対しては $\mbox{\boldmath$w$}\cdot\mbox{\boldmath$\phi$}(\mbox{\boldmath$x$})\le-1$ を満たすようにできる． 少なくとも一つがこの等式を満たしているとすると，マージンが $1/\Vert\mbox{\boldmath$w$}\Vert$ であることは容易にわかる． 従って，解くべき問題は以下の制約付き最適問題に帰着される．

$$\begin{eqnarray*} \mathop{\mbox{minimize }}_{\mbox{\boldmath$w$}} && \Vert\mbox... ...dmath$w$}\cdot\mbox{\boldmath$\phi$}(\mbox{\boldmath$x$}_i)\ge 1 \end{eqnarray*}$$

このままでは高次元での内積が入っているので，Lagrange の未定係数を導入し， $\mbox{\boldmath$w$}$ で微分して得られる式を代入すると，Wolfe-dual と呼ばれる双対問題

$$\mathop{\mbox{maximize }}_{\mbox{\boldmath$\alpha$}} \sum_{i=1}^n \alpha_i -{1\over2}\sum_{i,j} \alpha_i\alpha_j y_i y_j k(\mbox{\boldmath$x$}_i,\mbox{\boldmath$x$}_j).$$ (3)

$$\mbox{subject to} \alpha_i \ge 0$$

が得られる． ただし $\mbox{\boldmath$\phi$}$ 同士の内積はカーネルで置き換えた．

この解を用いて，重み係数 $\mbox{\boldmath$w$}$ は $\sum_{i=1}^n \alpha_i y_i \mbox{\boldmath$\phi$}(\mbox{\boldmath$x$}_i)$ と書くことができ，入出力関数に入れると

$$y = \mbox{sgn}[\sum_i\alpha_i y_i k(\mbox{\boldmath$x$}_i,\mbox{\boldmath$x$})]$$ (4)

となり，サンプル点でのカーネル関数の形で書けることがわかる． こうして導かれた識別器を(ハードマージン)SVMと呼ぶ．

さて，最適化問題の形を見ると，線形制約のもとでの最適化であり， 最適化関数 $\Vert\mbox{\boldmath$w$}\Vert^2$ は凸な 2 次関数である． このような問題は 凸 2 次計画問題と呼ばれる． 凸 2 次計画問題であることによって，SVM のもつ 以下のような特長が示される．

• 大域的最適解を一つだけ持つ． これは多くの複雑な学習モデルが 局所最適解を持つのに対して優位性がある．
• Karush-Kuhn-Tucker 条件により，$\alpha_i\ne0$ となるサンプルは制約の 不等式を等号で満たすことがわかる． つまり，入出力関数は 超平面に最も近いサンプルだけに依存した関数となる． 多くの場合これは サンプル数よりもずっと少ないので，識別を行う際には計算量 の大きな節約となる． $\alpha_i\ne0$ でないサンプルを超平面の支持関数 という意味でサポートベクタと呼ぶ． この基底関数のスパースネスは他のカーネルベースの方法にはない SVM の大きな特長である．
• 凸 2 次計画問題は数理計画法の基本的なパッケージに含まれていて 比較的高速に解くことができる．