数学的に考えてみる(ソフトマージンSVM)

HOME>>メモ>>アルゴリズム>>SVM>>数学的に考えてみる(ソフトマージンSVM)
もっと数学的な説明が欲しい方のために、少しまとめてみました。

問題の定式化

ハードマージンSVMではマージンの中にデータが入ることを許さず、次の条件を満たす必要がありました。 \[y_i(\bm w\cdot\bm x_i + b) \le 1\] この条件では、データが線形分離不可能な場合に解が求まらない場合があります。 そこで、この条件を次のように緩和します。 \[y_i(\bm w\cdot\bm x_i + b) \le 1 - \zeta_i\] $\zeta_i$はスラック変数と呼ばれるもので、先ほどの条件をどの程度違反しているかを表します。 データがマージンの中に入ってしまったときは$0>\zeta_i\ge 1$、 誤って分類してしまったときは$\zeta_i<1$となります。

ハードマージンSVMの目的関数にスラック変数をペナルティとして加えます。 \[\frac{1}{2}||\bm w||^2 + C\sum_{i=1}^{n}\zeta_i\] $C$はどの程度誤りを許すかを表します。 $C$が大きいほど誤りに対して厳しく、ハードマージンSVMに近づきます。

双対問題への置き換え

ハードマージンSVMと同様に双対問題へ置き換えます。 ラグランジュの未定乗数$\alpha_i, \beta_i$を導入し、 \[L=\frac{1}{2}||\bm w||^2+C\sum_{i=1}^{n}\zeta_i+\sum_{i=1}^{n}\alpha_i \left\{1-\zeta_i-y_i(\bm w\cdot\bm x_i + b)\right\}+\sum_{i=1}^{n}\beta_i(-\zeta_i)\] の最小化と置き換えます。 KKT条件から次の条件を満たす必要があります。 \[\frac{\partial L}{\partial \bm w}=0, \frac{\partial L}{\partial b}=0, \frac{\partial L}{\partial \zeta_i}=0\] \[\alpha_i \ge 0, \beta_i \ge 0\] これから \[\bm w = \sum_{i=1}^{n}\alpha_i y_i\bm x_i\] \[\frac{\partial}{\partial b}L(\bm w, b, \bm \alpha)=\sum_{i=1}^{n}\alpha_i y_i=0\] \[\alpha_i+\beta_i=C\] が得られます。すると$\zeta_i$に関する項が打ち消し合って、結局ハードマージンSVMと同じ式が得られます。 \[L=\sum_{i=1}^{n}\alpha_i - \frac{1}{2}\sum_{i,j}\alpha_i\alpha_j y_i y_j \bm x_i \bm x_j\] ただし、$\beta_i \ge 0$と\[\alpha_i+\beta_i=C\]から、$0 \le \alpha_i \le C$という条件がつきます。 制約条件が違うだけなので、クリッピングの条件を変えるだけでハードマージンSVMと同じように解けます。

最後にサポートベクトルから$b$の値を求めるわけですが、このベクトルの選び方が少し違います。 $\alpha_i=C$のとき$\zeta_i<0$となるため、\[y_i(\bm w\cdot\bm x_i + b) \le 1\]を満たしません。 このようなベクトルからは$b$を直接求めることができないので、 $0<\alpha_i<C$となるようなベクトルを選ぶ必要があります。