【初心者向け】2値分類SVM(サポートベクターマシン)の考え方と最適化問題

サポートベクターマシンとは

SVMは理系の方なら耳にすることも多いかもしれません。機械学習的な手法は文系にとってはあまり需要が無いので、文系の人は馴染みがないかもしれません。一つ説明する前に補足しておくと、SVMはよく機械学習の文脈で説明されますが、厳密に区別するのであればパターン認識という手法の一つであって、機械学習ではありません。でも最近ではパターン認識も機械学習も目的の点で似通っているので、あまり区別されなくなってきています。

機械学習のイメージを知りたい方は前記事で。
bananarian.hatenablog.com

で、SVMは結局何をするためのものなのかというと、要は事前に学習したデータを元に、新しいデータがどの分類にあてはまるか割り当てるという手法です。

具体例を挙げると、例えば

ある時期に届いたメール、300件について、適当な基準に基づいて迷惑メールか重要なメールかに分けるとします。最初はまあ手動で分けているわけですが、いつまでも手動で分けていても面倒くさいので、適当な基準があるわけだからその基準で分けてくれるよう機械に命令すればいいわけです。

しかし、もう少しよくよく考えてみるとこの適当な基準というのは結構難しくて、これから届く全てのメールに対して分類を失敗する確率が0になるような確定的な基準を考えるのは結構しんどい。というか多分ムリ。

そこで、各メールの特徴を学習させていって、そこそこの精度で分類できるような分類器を作るという方法に転換します。この分類器の一つがSVM(サポートベクターマシン)になります。

サポートベクターマシンによる分類のイメージ

その分類方法ですが、基本的には直線(or超平面)によって平面(or空間)を分割するという方法を取ります。図にするとこんな感じです。
f:id:bananarian:20180902173818p:plain

この黒い直線がSVMです。2グループに分けてます。

このようにうまく分類してくれる直線を引きたいというわけです。

SVMの数式

ちょっとベクトルで考えるとしんどいっすって人もいると思うので、とりあえず特徴量が１種類のケースで定式化してみます。
わかりやすくなるようメールの例で書いていきます。
今、メールを300通受け取りました。そしてそのメールに対して

$(y_i=-1)$ :i通目のメールが迷惑メールである
$(y_i=1)$ :i通目のメールが重要なメールである

という分類をしていき、メールの特徴として、「謎のURLが何個貼ってあるか」というような特徴 $X$ を考えます。
(よく、迷惑メールってURLいっぱい貼ってあったりしますよね？しないかな。その辺はわかんないけどあくまで例として)

そして、次のような分類を考えます。

$aX-h=0$

この式を分類器であると考えるとこの式の意味はしきい値である $h$ を $aX$ が超えるか超えないかを見る話だということがわかりますね。

この超えるか超えないかを迷惑メールか否かの意思決定に対応させたいので次のような関数を考えます。

$sgn(aX-h)$

この $sgn()$ とは、中身が0以上であれば1を0未満であれば-1をとる関数とします。
こうすることで、空間を二つの領域に分解することが出来ました。要は $sgn(aX-h)=1$ を取る領域と、 $sgn(aX-h)=-1$ を取る領域です。

さっきの図に書き加えると次の通り。
f:id:bananarian:20180902182226p:plain

ですが、直感的にわかるかもしれませんが、300個のデータをきれいに分類する直線は

・そもそも引けないかもしれない
・反対にたくさん引けるかもしれない

という２種類の可能性があります。

そういうわけで、とりあえず与えられたデータ及びこれから与えられるデータはこのように直線で分類することが可能であると仮定しましょう。

これを線形分離可能と呼びます。

しかし、まだこのままでは色々な直線が考えられます。

そこで次のような概念を考えます。

マージン

どっかの点とスレスレになるような直線ではなく、余裕をもった直線を引きたいというようなことを考えるとします。

つまり下のような直線を引くよりは
f:id:bananarian:20180902183530p:plain

このような直線を引く方が望ましいというわけです。
f:id:bananarian:20180902182226p:plain

そこで、直線を引いた時に、一番近い点との距離が最も遠くなるようにしたい

と言うことを考えるわけです。

まず、各点と直線の距離はこうなりますね。

$d(X_i,a,h)=\frac{|aX_i-h|}{||a||}$

ここでまず一番近いXとの距離を考えます。
$\min_{X_i}d(X_i,a,h)=\min_{X_i}\frac{|aX_i-h|}{||a||}$

その中で距離が最も遠くなるように $aとh$ を決めます。
$\max_{a,h}\min_{X_i}d(X_i,a,h)=\max_{a,h}\min_{X_i}\frac{|aX_i-h|}{||a||}$

これを最大マージンと呼びます。

最大マージンの計算方法

しかし、式では書けるけど、これどうやって解けばいいんだとなるので、もう少し工夫します。まず、

$aX=h$

ですが、これ、別に両辺定数倍しても関係式はおかしなことにはなりませんよね。
というわけで適当に定数倍を行うことで

全てのサンプルに対して
$y_i=1の時は(aX_i-h)≧1であり、y_i=-1の時は(aX_i-h)≦-1$ であるという条件を加えてみます。

そうすると $\min_{X_i}|aX_i-h|=1$ なので最大マージンは $\frac{1}{||a||}$ を最大化すればよいということになりますね。

しかし、このままではまだ考えにくいので、二乗して逆数を取ってやり、

$||a||^2$ を最小化する問題を考えよう

という話に変換します。

これなら二乗したものを最小化するという話に落ち着いたので、考えることが出来そうです。

というわけで、長くなりましたがまとめると次のような定式化となります。

制約　 $y_i=1の時は(aX_i-h)≧1であり、y_i=-1の時は(aX_i-h)≦-1$ 　の下で

$||a||^2$ を最小化したい。

で、後はどうするかというと不等式制約を持つ最大最小化問題なので、KKT条件を使ってやって、ちょっと計算しにくいので双対問題を考えてやり、強双対定理が成り立つことを適当に示した後で最適化問題を解いてやればよいということになります。

※よく、機械学習関連のブログでラグランジュ未定乗数法を使うといった記述が見られますが、不等式制約に関する問題にラグランジュ未定乗数法は使えません。KKT条件を活用します。

KKT条件に関する話はまた別の記事で。

補足

今回は最大マージンを考える方法でSVMを考えましたが、別の基準に従って考えることもできます。これについてもまた別の記事で書いていきたいと思います。