サポートベクターマシンとは［最適化問題の解法］
はじめに最適化問題の解法について一般論を述べた後、それをサポートベクターマシンで現れる最適化問題に適用していきます。
最適化問題とは、「ある制約の下で、関数の最小値や最大値を発見すること」で、次のように定式化できます。
なお、目的関数が2次関数で、不等式制約、等式制約は線形関数の最適化問題は2次計画問題(quadratic programming)と呼ばれます。全ての式が線形のときは線形計画問題(linear programming)と呼ばれます。
サポートベクターマシンの目的関数$\frac{||w||^2}{2}$は２次関数、制約条件は線形ですので、サポートベクターマシンの最適化問題は２次計画問題となります。
サポートベクターマシンの最適化問題には等式制約は現れないのですが、ここでは等式制約も含めた最適化問題の一般的な解法であるラグランジュ未定乗数法について述べます。
まず、前述の最適化問題に出てくる目的関数、等式制約、不等式制約を融合した関数$L$（ラグランジュ関数またはラグランジアンと呼ばれます）を定義します。$$
L(z, \alpha, \beta)=f(z)+\sum_{i=1}^{k}\alpha_ig_i(z)+\sum_{i=1}^{m}\beta_ih_i(z)
$$
ここで、
$$
\begin{align}
\alpha&=(\alpha_1,\ldots, \alpha_k)^T, \alpha_i\geqq 0, i=1,\ldots,k\\
\beta&=(\beta_1,\ldots, \beta_k)^T, \beta_i \geqq 0, i=1,\ldots,m
\end{align}
$$
です。この実数ベクトル$\alpha, \beta$はラグランジュ乗数と呼ばれます。
このとき、（制約付き）最適化問題の解は、次のクーン・タッカー(Kuhn-Tucker)の定理を利用して求めることができます。
クーン・タッカー(Kuhn-Tucker)の定理
最適化問題の解が存在する必要十分条件は、その解$x$において次の５つの条件が成り立つような$\alpha, \beta$が存在することです。
$$
\begin{align}
\frac{\partial L(z, \alpha, \beta)}{\partial z}&=0,\\
\frac{\partial L(z, \alpha, \beta)}{\partial \beta}&=0,\\
\alpha_ig_i(z)&=0, i=1,\ldots,k,\\
g_i(z)&\leqq 0, i=1,\ldots,k,\\
\alpha_i&\geqq 0, i=1,\ldots,k,
\end{align}
$$
なお、上の3番目の等式$\alpha_ig_i(z)=0, i=1,\ldots,k$はカルーシュ・クーン・タッカー(Karush-Kuhn-Tucker)の（相補性）条件（KKT条件と略します）として知られています。これから述べるようにKKT条件はサポートベクターマシンの定式化で重要な役割を果たします。
最適化問題を実際に解く前にKKT条件について検討しておきます。
KKT条件から、$\alpha_i$と$g_i(z)$の積は０になるので、次の2つの場合のどちらかが成り立っていることがわかります。
- $g_i(z)< 0$のときは$\alpha_i=0$
- $g_i(z)= 0$のときは$\alpha_i<0$
サポートベクターマシンの不等式制約
$$y(w^Tx+b)\geqq 1$$
にこのKKT条件を適用しましょう。
$z \leftarrow (w, b)$、$g_i(w, b)=1-y_i(w^Tx_i+b)\leqq 0$なのでKKT条件から
- $1-y_i(w^Tx_i+b)< 0$のときは$\alpha_i=0$
- $1-y_i(w^Tx_i+b)= 0$のときは$\alpha_i<0$
のどちらかが成り立ちます。すなわち、
- $y_i(w^Tx_i+b)> 1$のときは$\alpha_i=0$
- $y_i(w^Tx_i+b)= 1$のときは$\alpha_i<0$
となります。
まず、この2番めのケースに注目すると、この式ははまさしく$x_i$が支持超平面（$y(w^Tx+b)=1$）にちょうど乗っている、すなわち$x_i$がサポートベクターである場合に相当します。したがって、$x_i$がサポートベクターであるときは、対応するラグランジュ乗数$\alpha_i<0$となります。
つぎに、1番目のケースを見ます。$x_i$が支持超平面の正例側または負例側のどちらかに存在する、すなわち$x_i$はサポートベクターではないときは、ラグランジュ乗数$\alpha_i=0$となることを意味しています。
以上をまとめると、最適化問題の解のうち、$\alpha_i<0$に対応するデータ$x_i$はサポートベクターとなります。
さらに、サポートベクターではないデータ$x_i$では$\alpha_i=0$となることを利用すれば分類超平面の$w$の計算回数を削減できます（後述）。
それではクーン・タッカー(Kuhn-Tucker)の定理を使って最適化問題を実際に解いていきます。
まずサポートベクターマシンの最適化問題に対するラグランジュ関数$L(w, b, \alpha, \beta)$を求めます。
$$
\begin{align}
f(w, b)&=\frac{||w||^2}{2},\\
g_i(w, b)&=1-y_i(w^Tx_i+b), i=1,\ldots,l,\\
h_i(w, b)&=0, i=1,\ldots,m
\end{align}
$$
とおけるので、このときラグランジュ関数は、
$$
\begin{align}
L(w, b, \alpha, \beta) &= f(w, b)+\sum_{i=1}^{l}\alpha_ig_i(w, b)+\sum_{i=1}^{m}\beta_ih_i(w, b)\\
&= \frac{||w||^2}{2}+\sum_{i=1}^{l}\alpha_i(1-y_i(w^Tx_i+b))
\end{align}
$$
となり、これを$w$、$b$、$\beta$で偏微分すると
$$
\begin{align}
\frac{\partial L(w, b, \alpha, \beta)}{\partial w}&=w-\sum_{i=1}^{l}\alpha_iy_ix_i\\
&=0,\\
\frac{\partial L(w, b, \alpha, \beta)}{\partial b}&=-\sum_{i=1}^{l}\alpha_iy_i\\
&=0\\
\frac{\partial L(w, b, \alpha, \beta)}{\partial \beta}&=0
\end{align}
$$
ここで$\partial ||w||^2/\partial w = \partial w^Tw/\partial w =2w$であることを使いました。
整理すると、
$$
\begin{align}
w&=\sum_{i=1}^{l}\alpha_iy_ix_i,\\
\sum_{i=1}^{l}\alpha_iy_i&=0
\end{align}
$$
となります。
しかしこれらの式だけでは$\alpha$を決めることができません。
そこでこれまでの最適化問題とは別の$\alpha$に関する最適化問題（双対問題）を導き、これを解くことにより$\alpha$を求めます。
$w=\sum_{i=1}^{l}\alpha_iy_ix_i$なので、これをラグランジュ関数$L(w, b, \alpha, \beta)$に代入した関数を
$$
L_D(\alpha, \beta)=L(\sum_{i=1}^{l}\alpha_iy_ix_i, b, \alpha, \beta)
$$
と定義します。
最適化問題（双対問題）
- 目的関数
$$L_D(\alpha, \beta)$$
を制約条件のもとで$\alpha$に関して最小化
- 制約条件
$$\alpha_i\geqq 0, i=1,\ldots,l\\
\sum_{i=1}^{l}\alpha_iy_i=0$$
この最適化問題は主問題に対する双対問題と呼ばれます。なお、制約条件に$\beta$は現れないことに注意してください。
ラグランジュ関数$L_D(b, \alpha, \beta)$を具体的に計算しましょう。
$$
\begin{align}
L_D(\alpha, \beta)&=L(\sum_{i=1}^{l}\alpha_iy_ix_i, b, \alpha, \beta)\\
&=\frac{||w||^2}{2}+\sum_{i=1}^{l}\alpha_i(1-y_i(w^Tx_i+b))\\
&=\frac{w^Tw}{2}+\sum_{i=1}^{l}\alpha_i(1-y_i(w^Tx_i+b))\\
&=\frac{(\sum_{i=1}^{l}\alpha_iy_ix_i)^T(\sum_{i=1}^{l}\alpha_iy_ix_i)}{2}+\sum_{i=1}^{l}\alpha_i\{1-y_i((\sum_{i=1}^{l}\alpha_iy_ix_i)^Tx_i+b)\} \\
&=\frac{1}{2}\sum_{i,j=1}^{l}\alpha_i\alpha_jy_iy_jx_i^Tx_j+\sum_{i=1}^{l}\alpha_i-\sum_{i=1}^{l}\alpha_iy_i(\sum_{i=1}^{l}\alpha_iy_ix_i)^Tx_i-b(\sum_{i=1}^{k}\alpha_iy_i)\\
&=\frac{1}{2}\sum_{i,j=1}^{l}\alpha_i\alpha_jy_iy_jx_i^Tx_j+\sum_{i=1}^{l}\alpha_i-\sum_{i,j=1}^{l}\alpha_i\alpha_jy_iy_jx_i^Tx_j (\because \sum_{i=1}^{l}\alpha_iy_i=0)\\
&=\sum_{i=1}^{l}\alpha_i-\frac{1}{2}\sum_{i,j=1}^{l}\alpha_i\alpha_jy_iy_jx_i^Tx_j
\end{align}
$$
したがって、双対問題の目的関数：
$$
\sum_{i=1}^{l}\alpha_i-\frac{1}{2}\sum_{i,j=1}^{l}\alpha_i\alpha_jy_iy_jx_i^Tx_j
$$
を制約条件：
$$\alpha_i\geqq 0, i=1,\ldots,l\\
\sum_{i=1}^{l}\alpha_iy_i=0$$
のもとで最小化することにより$\alpha$が求めれば良いことになります。
$\alpha$がわかれば、$w$も$w=\sum_{i=1}^{l}\alpha_iy_ix_i$から求まります。
この時点で分類超平面の式のパラメータ$w$は求まりましたが、まだ$b$がわかりません。
ここでサポートベクターが支持超平面（$y(w^Tx+b)=1$）に乗っているという事実を思い出せば、この式から$b$が直接計算できることが分かります。すなわち、$x_{+}, x_{-}$をそれぞれ正例、負例のサポートベクターとすれば、これを支持超平面の式に代入して
$$
\begin{align}
w^Tx_{+}+b&=1,\\
w^Tx_{-}+b&=-1
\end{align}
$$
が得られ、この２式を足し合わせて$b$に関して解くと、$b$を求める式
$$
b=-\frac{1}{2}w^T(x_{+}+x_{-})
$$
が得られます。
ところで以前、KKT条件からサポートベクターではないデータでは$\alpha_i=0$であることを見ました。サポートベクターとなるデータは訓練データ全体と比べると圧倒的に少ないので、これを利用して分類超平面の$w$の計算量を削減できます。
すなわち、サポートベクターの集合を$\mathcal{V}$で表現すると、$w$は次式で計算できます。
$$
\begin{align}
w&=\sum_{i=1}^{l}\alpha_iy_ix_i\\
&=\sum_{x_i \in \mathcal{V}}\alpha_iy_ix_i
\end{align}
$$
これで分類超平面を求める式が出揃いました。以上をまとめるとつぎのようになります。
ハードマージンサポートベクターマシン
線形分離可能な訓練データ
$$D = \{(x_1, y_1), \ldots, (x_l, y_l)\}, (x_i, y_i) \in \Re^n \times {-1, 1}$$
が与えられたとき、次の最適化問題を解き$\alpha$を求めます。
- 目的関数
$$
\sum_{i=1}^{l}\alpha_i-\frac{1}{2}\sum_{i,j=1}^{l}\alpha_i\alpha_jy_iy_jx_i^Tx_j
$$
を次の最適条件のもとで$\alpha$に関して最小化
- 制約条件
$$\alpha_i\geqq 0, i=1,\ldots,l$$
$$\sum_{i=1}^{l}\alpha_iy_i=0$$このとき決定関数$\hat{f}(x)$は
$$
\hat{f}(x) = \text{sgn}(w^T x + b)
$$
です。ここで、$w,b$は
$$
w=\sum_{\mathcal{V}}\alpha_iy_ix_i\\
b=-\frac{1}{2}w^T(x_{+}+x_{-})
$$
で与えられます（$x_{+}, x_{-}$はそれぞれ正例、負例のサポートベクター）。
これで、サポートベクターマシンの基礎が一応完成しましました。
とくに訓練データが線形分離可能な場合のアルゴリズムのことをハードマージンサポートベクターマシンと呼ぶことがあります。
残念ながら、ハードマージンサポートベクターマシンを現実の問題に適用しても高い分類性能が得られない可能性が高いと考えられます。なぜなら、現実の状況では正確なデータだけでなく測定誤差や人為的ミスなどによるデータも発生するので、当然訓練データにもそのようなデータが含まれています。したがって、訓練データが線形分離可能であることはあまり期待できないため、ハードマージンサポートベクターマシンの前提が満たされません。
また、支持超平面から離れたデータが誤差を含んでいてもこれらのデータが支持超平面の決定に影響を与えることはないので問題はありませんが、クラス境界近くにある誤差データは分類超平面の決定に直接的に影響するため精度高い分類性能は期待できなさそうです。
このように誤差を含むデータの影響を少なくし、サポートベクターマシン本来の高い分類性能を発揮できるように、サポートベクターマシンにスラック変数を導入します。これが次に説明するソフトマージンサポートベクターマシンです。
