サポートベクターマシン

図 1: 線形しきい素子

　サポートベクターマシンは、ニューロンのモデルとして最も単純な線形しきい 素子を用いて、2クラスのパターン識別器を構成する手法である。訓練サンプル 集合から、「マージン最大化」という基準で線形しきい素子のパラメータを学習 する。線形しきい素子は、図1に示すようなニューロンを単 純化したモデルで、入力特徴ベクトルに対し、識別関数（線形識別関数）

$$y = \mbox{sign}(\mbox{\boldmath$w$}^T \mbox{\boldmath$x$}-h)$$ (1)

により2値の出力値を計算する。ここで、 $\mbox{\boldmath$w$}$はシナプス荷重に対応するパ ラメータであり、$h$はしきい値である。また、関数 $\mbox{sign}(u)$は、$u > 0$のとき$1$をとり、$u \le 0$のとき$-1$をとる符号関数である。このモデルは、 入力ベクトルとシナプス荷重の内積がしきい値を超えれば$1$を出力し、超えな ければ$-1$を出力する。これは、幾何学的には、識別平面により、入力特徴空間 を2 つに分けることに相当する。今、2つのクラスを$C_1$,$C_2$とし、各クラス のラベルを$1$と$-1$に数値化しておくとする。また、訓練サンプル集合として、 $N$個の特徴ベクトル $\mbox{\boldmath$x$}_1,\ldots,\mbox{\boldmath$x$}_N$ と、それぞれのサンプルに対 する正解のクラスラベル $t_1,\ldots,t_N$が与えられているとする。また、この 訓練サンプル集合は、線形分離可能であるとする。すなわち、線形しきい素子の パラメータをうまく調整することで、訓練サンプル集合を誤りなく分けることが できると仮定する。

図 2: 線形しきい素子の分離超平面とマージン(◯がクラス1のサンプルで、 □がクラス-1のサンプルを示す。●と■はサポートベクターを示す。)

訓練サンプル集合が線形分離可能であるとしても、一般には、 訓練サンプル集合を誤りなく分けるパラメータは一意には決まらない。サポート ベクターマシンでは、訓練サンプルをすれすれに通るのではなく、なるべく余裕 をもって分けるような識別平面が求められる。具体的には、最も近い訓練サンプ ルとの余裕をマージンと呼ばれる量で測り、マージンが最大となるような識別平 面を求める。もし、訓練サンプル集合が線形分離可能なら、

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

を満たすようなパラメータが存在する。これは、H1: $\mbox{\boldmath$w$}^T \mbox{\boldmath$x$} - h = 1$と H2: $\mbox{\boldmath$w$}^T \mbox{\boldmath$x$} - h = -1$の2枚の超平面で訓練サンプルが完全に分離されてお り、2枚の超平面の間にはサンプルがひとつも存在しないことを示している。こ のとき、識別平面とこれらの超平面との距離（マージンの大きさ）は、 $\frac{1}{\vert\vert\mbox{\boldmath$w$}\vert\vert}$となる。したがって、マージンを最大とするパラメータ $\mbox{\boldmath$w$}$と$h$を求める問題は、結局、制約条件

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

の下で、目的関数

$$L(\mbox{\boldmath$w$}) = \frac{1}{2} \vert\vert\mbox{\boldmath$w$}\vert\vert^2$$ (4)

を最小とするパラメータを求める問題と等価になる。この最適化問題は、数理計 画法の分野で２次計画問題として知られており、さまざまな数値計算法が提案さ れている。ここでは、双対問題に帰着して解く方法を紹介する。まず、Lagrange 乗数 $\alpha_i (\ge 0)$, $i=1,\ldots,N$を導入し、目的関数を

$$L(\mbox{\boldmath$w$},h,\mbox{\boldmath$\alpha$}) = \frac{1... ...\{t_i (\mbox{\boldmath$w$}^T \mbox{\boldmath$x$}_i - h) - 1 \}$$ (5)

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

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

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

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

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

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

の下で、目的関数

$$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$$ (10)

を最大とする双対問題が得られる。これは、Lagrange乗数 $\alpha_i (\ge 0)$, $i=1,\ldots,N$に関する最適化問題となる。その解で$\alpha^{*}_i$が$0$ でない、すなわち、 $\alpha^{*}_i > 0$となる訓練サンプル $\mbox{\boldmath$x$}_i$は、先の ２つの超平面 $\mbox{\boldmath$w$}^T \mbox{\boldmath$x$} - h = 1$か $\mbox{\boldmath$w$}^T \mbox{\boldmath$x$} - h = -1$のどち らかにのっている。このことから、$\alpha^{*}_i$が$0$でない訓練サンプル $\mbox{\boldmath$x$}_i$のことを「サポートベクター」と呼んでいる。これが、サポートベク ターマシンの名前の由来である。直感的に理解できるように、一般には、サポー トベクターは、もとの訓練サンプル数に比べてかなり少ない。つまり、沢山の訓 練サンプルの中から小数のサポートベクターを選び出し、それらのみを用いて 線形しきい素子のパラメータが決定されることになる。

実際、双対問題の最適解 $\alpha_i^{*} (i \ge 0)$、および停留点での条件式か ら、最適なパラメータ $\mbox{\boldmath$w$}^{*}$は、

$$\mbox{\boldmath$w$}^{*} = \sum_{i \in S} \alpha^{*}_i t_i \mbox{\boldmath$x$}_i$$ (11)

となる。ここで、$S$はサポートベクターに対応する添え字の集合である。また、 最適なしきい値$h^{*}$は、２つの超平面 $\mbox{\boldmath$w$}^T \mbox{\boldmath$x$} - h = 1$か $\mbox{\boldmath$w$}^T \mbox{\boldmath$x$} - h = -1$のどちらかにのっているという関係を利用して求め ることができる。すなわち、任意のサポートベクター $\mbox{\boldmath$x$}_s, s \in S$から

$$h^{*} = \mbox{\boldmath$w$}^{*T} \mbox{\boldmath$x$}_s - t_s$$ (12)

により求まる。

また、最適な識別関数を双対問題の最適解 $\alpha^{*}_i (i \ge 0)$を用いて表現 すると

$$y = \mbox{sign} (\mbox{\boldmath$w$}^{*T} \mbox{\boldmath$x$} - h^{*})$$

$$= \mbox{sign}(\sum_{i \in S} \alpha^{*}_i t_i \mbox{\boldmath$x$}_i^T \mbox{\boldmath$x$} - h^{*})$$ (13)

となる。 すなわち、 $\alpha^{*}_i = 0$となる多くの訓練サンプルを無視し、 $\alpha^{*}_i > 0$となる識別平面に近い少数の訓練サンプルのみを用いて識別関数 が構成される。ここで、重要な点は、「マージン最大化」という基準から自動的 に識別平面付近の少数の訓練サンプルのみが選択されたことであり、その結果と して、未学習データに対してもある程度良い識別性能が維持できていると解釈で きる。 すなわち、サポートベクターマシンは、マージン最大化という基準を用 いて、訓練サンプルを撰択することで、モデルの自由度を抑制するようなモデル 撰択が行われていると解釈できる。