ソフトマージン

図 3: ソフトマージン(◯がクラス1のサンプルで、 □がクラス-1のサンプルを示す。●と■はサポートベクターを示す。)

上述のサポートベクターマシンは、訓練サンプルが線形分離可能な場合につい ての議論であるが、パターン認識の実問題で線形分離可能な場合は稀である。し たがって、実際的な課題にサポートベクターマシンを使うには、さらなる工夫が 必要である。まず考えられるのは、多少の識別誤りは許すように制約を緩める方 法である。これは、「ソフトマージン」と呼ばれている。

ソフトマージン法では、マージン $\frac{1}{\vert\vert\mbox{\boldmath$w$}\vert\vert}$を最大としながら、図 3に示すように、幾つかのサンプルが超平面H1あるいはH2を越 えて反対側に入ってしまうことを許す。反対側にどれくらい入り込んだかの距離 を、パラメータ$\xi_i (\ge 0)$を用いて、 $\frac{\xi_i}{\vert\vert\mbox{\boldmath$w$}\vert\vert}$と表す とすると、その和

$$\sum_{i=1}^N \frac{\xi_i}{\vert\vert\mbox{\boldmath$w$}\vert\vert}$$ (14)

はなるべく小さいことが望ましい。これらの条件から最適な識別面を求める問題 は、制約条件

$$\xi_i \ge 0, \ \ \ t_i (\mbox{\boldmath$w$}^T \mbox{\boldmath$x$}_i - h) \ge 1 - \xi_i, \ \ \ (i=1,\ldots,N)$$ (15)

の下で、目的関数

$$L(\mbox{\boldmath$w$},\mbox{\boldmath$\xi$}) = \frac{1}{2} ... ...ert\mbox{\boldmath$w$}\vert\vert^2 + \gamma \sum_{i=1}^N \xi_i$$ (16)

を最小とするパラメータを求める問題に帰着される。ここで、あらたに導入した パラメータ$\gamma$は、第１項のマージンの大きさと第2項のはみ出しの程度と のバランスを決める定数である。

この最適化問題の解法は、基本的には線形分離可能な場合と同様にふたつの制約 条件に対して、Lagrange乗数$\alpha_i$、および、$\nu_i$を導入し、目的関数 を

$$L(\mbox{\boldmath$w$},h,\mbox{\boldmath$\alpha$},\mbox{\boldmath$\nu$}) = \frac{1}{2} \vert\vert\mbox{\boldmath$w$}\vert\vert^2 + \gamma \sum_{i=1}^N \xi_i$$

$$- \sum_{i=1}^{N} \alpha_i \{t_i (\mbox{\boldmath$w$}^T \mbox{\boldmath$x$}_i - h) - (1 - \xi_i) \}$$

$$- \sum_{i=1}^N \nu_i \xi_i$$ (17)

と書き換える。パラメータ $\mbox{\boldmath$w$}$、$h$、$\nu_i$ に関する偏微分を$0$とする 停留点では、

$$\mbox{\boldmath$w$} = \sum_{i=1}^N \alpha_i t_i \mbox{\boldmath$x$}_i$$ (18)

$$0 = \sum_{i=1}^{N} \alpha_i t_i$$ (19)

$$\alpha_i = \gamma - \nu_i$$ (20)

という関係が成り立つ。これらを目的関数の式に代入すると、制約条件

$$\sum_{i=1}^{N} \alpha_i t_i = 0$$ (21)

$$0 \le \alpha_i \le \gamma, \ \ \ i=1,\ldots,N$$ (22)

の下で、目的関数

$$L_{D}(\mbox{\boldmath$\alpha$}) = \sum_{i=1}^{N} \alpha_i -... ...\alpha_j t_i t_j \mbox{\boldmath$x$}_i^T \mbox{\boldmath$x$}_j$$ (23)

を最大とする双対問題が得られる。線形分離可能な場合には、最適解 $\alpha^{*}_i$の値により、平面H1およびH2上の訓練サンプル(サポートベクター) とそれ以外のサンプルに分類されたが、ソフトマージンの場合には、さらに、H1 およびH2をはさんで反対側にはみ出すサンプルが存在する。それらは、同様に、 最適解$\alpha^{*}_i$の値により区別することができる。具体的には、 $\alpha^{*}_i = 0$なら、平面H1あるいはH2の外側に存在し、学習された識別器に よって正しく識別される。また、 $0 < \alpha^{*}_i < \gamma$の場合には、対 応するサンプルは、ちょうど平面H1あるいはH2の上に存在するサポートベクター となり、これも正しく識別される。 $\alpha^{*}_i = \gamma$ の場合には、対応 するサンプルはサポートベクターとなるが、$\xi_i \neq 0$となり、平面H1 あ るいはH2の内側に存在することになる。