next up previous
次へ: カーネルトリック 上へ: カーネル学習法 戻る: サポートベクターマシン

ソフトマージン

図 3: ソフトマージン(◯がクラス1のサンプルで、 □がクラス-1のサンプルを示す。●と■はサポートベクターを示す。)
\begin{figure}\begin{center}
\psfig{file=soft-margin.eps,width=65mm} \end{center}\end{figure}

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

ソフトマージン法では、マージン $\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}$と表す とすると、その和

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

はなるべく小さいことが望ましい。これらの条件から最適な識別面を求める問題 は、制約条件
\begin{displaymath}
\xi_i \ge 0, \ \ \ t_i (\mbox{\boldmath$w$}^T \mbox{\boldmath$x$}_i - h) \ge 1 - \xi_i, \ \ \ (i=1,\ldots,N)
\end{displaymath} (15)

の下で、目的関数
\begin{displaymath}
L(\mbox{\boldmath$w$},\mbox{\boldmath$\xi$}) = \frac{1}{2} ...
...ert\mbox{\boldmath$w$}\vert\vert^2 + \gamma \sum_{i=1}^N \xi_i
\end{displaymath} (16)

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

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

$\displaystyle L(\mbox{\boldmath$w$},h,\mbox{\boldmath$\alpha$},\mbox{\boldmath$\nu$})$ $\textstyle =$ $\displaystyle \frac{1}{2} \vert\vert\mbox{\boldmath$w$}\vert\vert^2 + \gamma \sum_{i=1}^N \xi_i$  
    $\displaystyle - \sum_{i=1}^{N} \alpha_i \{t_i (\mbox{\boldmath$w$}^T \mbox{\boldmath$x$}_i - h) - (1 - \xi_i) \}$  
    $\displaystyle - \sum_{i=1}^N \nu_i \xi_i$ (17)

と書き換える。パラメータ $\mbox{\boldmath$w$}$$h$$\nu_i$ に関する偏微分を$0$とする 停留点では、
$\displaystyle \mbox{\boldmath$w$}$ $\textstyle =$ $\displaystyle \sum_{i=1}^N \alpha_i t_i \mbox{\boldmath$x$}_i$ (18)
$\displaystyle 0$ $\textstyle =$ $\displaystyle \sum_{i=1}^{N} \alpha_i t_i$ (19)
$\displaystyle \alpha_i$ $\textstyle =$ $\displaystyle \gamma - \nu_i$ (20)

という関係が成り立つ。これらを目的関数の式に代入すると、制約条件
$\displaystyle \sum_{i=1}^{N} \alpha_i t_i$ $\textstyle =$ $\displaystyle 0$ (21)
$\displaystyle 0$ $\textstyle \le$ $\displaystyle \alpha_i \le \gamma, \ \ \ i=1,\ldots,N$ (22)

の下で、目的関数
\begin{displaymath}
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
\end{displaymath} (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の内側に存在することになる。


next up previous
次へ: カーネルトリック 上へ: カーネル学習法 戻る: サポートベクターマシン
平成14年7月18日