サポートベクターマシーンを基礎から読んでみた - 時代に翻弄されるエンジニアのブログ

こんにちは，今日もコロナ社から出版されている自然言語シリーズの自然言語のための機械学習入門をよんだので，それについて書いていこうと思います．

はじめに

サポートベクターマシン（SVM）は一時期すごくはやっていましたね．今はニューラルネットワークが話題ではありますが，原理的な解析ができることからSVMを使う人も多いそうです．

SVMは二値分類を行います．たとえば，身長体重から女性か男性かみたいな問題です．それを応用して複数分類や回帰問題に発展させていることも多いようです．

SVMが良く使われる理由は全体的に良い分類を行ってくれるからだそうです．といってもよくわからないと思います．ニューラルネットワークなどは与えられた値からその値を分類するように頑張るのですが，SVMは与えられた値以外にも対応する性質を持った分類を行ってくれます．その秘密は二つのクラスがあった場合に「どちらのクラスからもなるべく遠い位置でわける」というマージン最大化という仕組みを導入しているからです．今回は，そのマージン最大化について説明して，SVMを実際に解いていこうと思います．

分類の方法

いま，あるデータxに対して正解となるクラスy(+1 or -1)が与えられているとき，それらデータをクラスで分ける平面をwと仮定して，平面で分離する式を以下のように定義します．

${ f(x) = w \cdot x - b ≧ 0 }$

つまり，fはxが入力されたときに0以上ならクラス(+1)に未満ならクラス(-1)に属するということです．マージン最大化とはこの平面と各クラスの最も近いデータとの距離の最大化のことを言います．

マージン最大化

データを分離する平面に最も近いデータを ${x_+}$ として，データから平面に垂線を伸ばした時の交点を ${x_*}$ とする．ここで， ${x_*}$ は平面上にあるため， ${w \cdot x_* = b}$ となります．

パラメータbを調節することで平面を移動させることができます．よって ${ w \cdot x_+ -b = 1 }$ となるような平面を仮定すると，

${ w \cdot ( x_+ - x_* ) = w \cdot x_+ - w \cdot x_* = (b + 1) - b = 1 }$

と，することができ， ${w}$ と ${x_+ - x_*}$ が同じ方向を向いていることから，

${ w \cdot ( x_+ - x_* ) = |w||x_+ - x_*| = 1 \\ |x_+ - x_*| = \frac{1}{|w|} }$

となります．つまり，マージン ${|x_+ - x_*|}$ の距離は ${\frac{1}{|w|}}$ となり，これの最大化がSVMの解く問題になるということです．

厳密制約でのSVM

厳密制約というのはデータが過不足なくクラスに分けられている状態でのSVMの学習ということです．実際は外れ値や選択する特徴の表現不足で厳密なデータを用意するのは難しいですが，実践への導入として解説したいと思います．

先ほど，解くべき問題は ${\frac{1}{|w|}}$ の最大化といいましたが，これは扱いにくいので， ${|w|}$ の最小化として，さらに，絶対値は扱いにくいので ${w^2}$ の最小化とします．解くべき問題は変わっていません．

先ほど仮定した ${ w \cdot x_+ -b = 1 }$ を満たすために，クラス(y=+1)のときは ${f(x)≧1}$ であり，クラス(y=-1)のときは ${f(x)≦-1}$ を満たす必要があるとすると，二つの条件は以下のようにまとめることができる．

${ y^{(i)}(w \cdot x^{(i)} - b) ≧ 1 }$

よって，以下の最適化問題を解くことになる．

${ min. \frac{1}{2}w^2 \\ s.t. y(w \cdot x -b) -1 ≧ 0; \forall i }$

この不等式制約付き最適化問題は凸問題であるので，ラグランジュ方程式を用いてデータ数分だけラグランジュ乗数 ${α_i}$ を導入すると，ラグランジュ関数は以下のようになります．

${ L(w,b,α) = \frac{1}{2}w^2 - \displaystyle \sum_i α_i(y^{(i)}(w \cdot x^{(i)}-b)-1) }$

これをそれぞれのパラメータで偏微分して0とおくと

${ \frac{\partial L}{\partial w} = w - \displaystyle \sum_i α_i y^{(i)} x^{(i)} = 0\\ w = \displaystyle \sum_i α_i y^{(i)} x^{(i)} \\ \\ \frac{\partial L}{\partial b} = \displaystyle \sum_i α_i y^{(i)} = 0 }$

これを，ラグランジュ関数に入れると以下のようにαのみの関数となり，変形することができる．

${ \begin{align} L(w,b,α) &= \frac{1}{2}\sum_{i,j} α_i α_j y^{(i)} y^{(j)} x^{(i)} \cdot x^{(j)} - \displaystyle \sum_i α_i(y^{(i)}(\displaystyle \sum_j α_j y^{(j)} x^{(j)} \cdot x^{(i)}-b)) + \displaystyle \sum_i α_i \\ &= -\frac{1}{2}\sum_{i,j} α_i α_j y^{(i)} y^{(j)} x^{(i)} \cdot x^{(j)} + b \displaystyle \sum_i α_i y^{(i)} + \displaystyle \sum_i α_i \\ \end{align} }$

これでもともパラメータがなくなったので，あととはラグランジュ関数を最大にするαをもとめることで，はじめにもとめた，分類関数f(x)を求めることができます．しかしこの問題は二次計画問題となり解析的に解くことが難しくなっています．なので逐次的に解くなど工夫する必要があります．

おわりに

SVMで一番難しい，というかわかりづらい概念は ${ w \cdot x_+ -b = 1 }$ となるような平面を仮定するところだと思います．これは，平面を平行移動して距離関数が1となるような制約が必要という意味になります．そのため，ラグランジュ関数の制限の項で用いられています．距離は絶対値であるので+方向-方向でも同様に1にするためにラベルを+1,-1とすることが大事であるといえます．今回は厳密回を求めましたが，通常はそのような式は使えません．また，今回は線形分離を行いましたが，カーネルトリックを利用した非線形分離にも拡張することができます．今後そのような例も解説していこうと思います．