誤分類を許容しながらマージンの最大化を行うアルゴリズム

ソフトマージン

SVM は分類問題を解く機械学習手法の一つである。SVM では、データを分類するための超平面を求めて、その超平面を用いてデータの分類を行なっている。その超平面を計算する方法としてハードマージン法とソフトマージン法がある。ハードマージン法は、データが空間上できれいにクラスごとに分離している場合だけに適用できる。これに対して、ソフトマージン法は、データがきれいに分離していなくても適用でき、その適用範囲は広い。ソフトマージン法では、教師データが間違って分類された場合に、ペナルティを与えることで誤分類に対応している。

ハードマージン法の定式化

マージン最大化

ソフトマージン法は、ハードマージン法と同様に定式化することができる。すなわち、マージンを最大化することは、次式の右辺を最大化する問題に帰着できる。

\[ \frac{\mathbf{w}^{t}(\mathbf{x}_{positive} - \mathbf{x}_{negative})}{||\mathbf{w}||} = \frac{2}{||\mathbf{w}||} \]

制約条件

2/||w|| の最大化は、制約条件のもとで行わなければならない。ハードマージン法では、2 つのサポート超平面の間にサンプルが存在しないことを利用して、制約条件を次のようなものとしている。

\[ y^{(i)}( w_{0} + \mathbf{w}^{t}\mathbf{x}^{(i)}) \ge 1 \]

これに対して、ソフトマージン法では、あるクラスに属するサンプルが、サポート超平面を超えて他のクラスの近くに配置されていることも許している。ただし、この場合は、ペナルティを課す。例えば、下図のように、オレンジ色の点(サンプル 1)が、水色の点のクラスタの中に配置されている。このとき、サンプル 1 が、サポート超平面から誤分類された位置までの距離を ξ1/||w|| とすると、距離 ξ1/||w|| をそのままペナルティとして課すことができる。ただし、ペナルティを課すのは、サポートの超平面の外側にあるサンプルのみである必要がある。そのため、サンプル i がサポート超平面の内側にあるとき、ペナルティとならないように ξi = 0 とする必要がある。

ソフトマージン法によりSVMの超平面を推定する方法

サンプル i が誤分類でなければ ξi = 0 であり、サポート超平面と分類超平面の間であれば、0 < ξi/||w|| < 1 であり、(超平面を超えて)誤分類であれば ξi/||w|| > 1 である。従って、「誤分類の程度」をある定数 K 以下に抑えたとき、次のことが成り立つ。

\[ \sum_{i=1}^{n}\frac{\xi_{i}}{||\mathbf{w}||} \le K \]

このとき、誤分類をどのぐらいまで許容するのかを指標 K を与えると、これを制約条件として使えるようになる。

ソフトマージン法の定式化

以上のことから、SVM のソフトマージン法では、次のように定式化できる。

\[ \arg \max \left\{ \frac{2}{||\mathbf{w}||} \right\} \quad \text{subject to} \quad \sum_{i=1}^{n}\xi_{i} \le ||\mathbf{w}|| K \quad \xi_{i} \ge 0 \] \[ \quad (i = 1, 2, 3,\cdots) \]

これをラグランジュの未定乗数法の式で書き直すと、次のようになる。

\[ \arg \max \left\{ \frac{2}{||\mathbf{w}||} \right\} + C\sum_{i=1}^{n}\xi_{i} \quad \xi_{i} \ge 0 \]

C は定数で、誤分類を許容する指標 K と同じ役割を持つ。ソフトマージン法を利用するにあたり、C をあらかじめ与えておく必要があるので、C はハイパーパラメーターと呼ばれている。実際に、SVM を使って予測モデルを作成する上で、C は交差検証で最適な値に決められる。また、このハイパーパラメーター C にちなんで、ソフトマージン法は C-SVM などと呼ばれたりする。