サポートベクトルマシーン

導入

これまで、分類問題として線形ロジスティック回帰モデルに取り組んできたが、ここではサポートベクトルマシーン（Support Vector Machine; SVM）について説明する。SVMは、線形分類モデルの一つであり、特にマージン最大化の観点から分類境界を定める方法である。

ここで考えるのは、二値分類問題であり、入力データ に対してクラスラベル を予測するモデルを構築することである。

線形モデル

線形分類モデルでは、分類境界を線形関数で表現する。まず、以下のような関数 を考える。

ここで、 は重みベクトル、 はバイアス項である。分類は、 の符号に基づいて行われ、具体的には以下のように定義される。

ここで、 は予測されたクラスラベルである。標準内積と以下のように定義されたスカラー値の符号を取り出す関数

を用いると、分類関数 は以下のように表現できる。

の内積空間を分類境界 で分割するという問題に帰着される。この境界は超平面（hyperplane）と呼ばれ、 は超平面の法線ベクトルを表す。なぜなら超平面上の2つの異なるベクトルを 、 とすると、

が成り立ち、 と超平面上の任意のベクトル が直交することが分かるからである。

マージン最大化

SVMの基本的な考え方は、分類境界から最も近いデータ点までの距離（マージン）を最大化することである。既知のデータセット に対して、超平面 から各データ点 までの距離 を計算してみたい。ある点 から超平面に垂直に下ろした足の点を とすると、ある が存在して

である。 は超平面上の点であるから、超平面の方程式に代入すると、

となる。 から超平面までの距離 は から までの距離であり、

である。したがって、点 から超平面までの距離 は

である。さて、加えてこの距離に対し、超平面のどっち側にいるのかという情報を正負で加えると下の符号付き距離 が得られる。

この は超平面に対して正の側（ ）にある場合は正、負の側（ ）にある場合は負の値を取る。だが、今の目的は各データ点が超平面から離れることである。

一方で、絶対値を取ってしまうのは悪手である。なぜなら、絶対値を取ると距離の情報のみが残り、 なら正の側に、 なら負の側にあることを保証できないからである。そこで、目的変数をかけてみることを考える。すると、各データ点 に対して

という量が定義できる。 について正解ラベル が ならば の増加は に対応し、 から正の方向に離れたがる。一方で が ならば、 の増加は の減少に対応し、 から負の方向に離れたがる。したがって、各データ点に対してこの量を最大化することは、各データ点が各々のラベルに応じた方向に超平面からできるだけ離れるようにすることと同値である。

SVMでは、この量 のうち、最小値となるものを最大化することを目的とする。最小値となるものに注目する。

この量 をマージン（margin）と呼ぶ。しかし、 は を定数倍しても変化しない。 とすれば

である。つまり、これを最小化する は無数に存在する。したがって、最適化問題としては適していない。そこで、

という制約を課すことにする。これにより、 のスケールが固定されることになる。すると、マージンは

となる。したがって、マージンを最大化することは を最小化することと同値である。以上より、SVMの最適化問題は以下のように定式化される。

ラグランジュ未定乗数法による解法

この最適化問題は制約付き最適化問題であるため、ラグランジュ未定乗数法を用いて解くことができる。ラグランジュ関数 を以下のように定義する。

ここで、 はラグランジュ未定乗数であり、各 である。まずラグランジュ関数を と で偏微分し、それらを0に等しく設定する。

これらの式をラグランジュ関数に代入すると、

ここで、 はラグランジュ関数における双対関数である。したがって、元の最適化問題は以下の双対問題に帰着される。

この双対問題は凸二次計画問題であり、様々な数値最適化手法を用いて解くことができる。例えば、逐次最小問題最適化法（Sequential Minimal Optimization; SMO）などがある。最適な が得られたら、対応する は以下のように計算される。

バイアス項 は、サポートベクトル（ となる事例 ）を用いて以下のように計算される。

ここで、 は任意のサポートベクトルのインデックスである。また、Karush-Kuhn-Tucker (KKT) 条件により、以下の関係が成り立つ。

後半二つは制約条件そのものとなっている。これらの条件により、サポートベクトルは分類境界に最も近いデータ点であることが保証される。