機械学習初心者でも、サポートベクターマシン(SVM)のハードマージン最大化について理解しなければならない日がいつか来る。なので初心者代表の私が、SVMハードマージン最大化について初心者なりに分かりにくいところなどを含め解釈したものをまとめてみました。
加筆修正のコメント等あれば、遠慮なく教えてください。
1. なぜ人はSVMマージン最大化を学ぶのか
それはズバリ、機械学習を勉強している人には必須とも言えるサポートベクターマシン(SVM)の基本原理となっているからです。SVMの理解のためにはSVMマージン最大化の深い理解が必要不可欠です。
SVMはこのマージン最大化において、ハードマージンという概念を基にしたソフトマージンというものを採用しています。なので今回は、まず基盤となっているハードマージンについて説明した後にソフトマージンの説明をしようと思います。(ソフトマージンは別記事)
2. ハードマージン最大化
大前提として、単純パーセプトロン,SVMはともに２クラス分類のための学習機械です。
しかし単純パーセプトロンについて説明した初心者の初心者による初心者のための単純パーセプトロンでは、分類アルゴリズムについては説明しているものの、その識別境界(decision boundary)をどう引くのかについての説明はしていませんでした。
なぜなら、単純パーセプトロンの目的はあくまで２クラスに完璧に線形分離するための重みを決定することであり、分離さえできていればその境界は何でも良いからです。つまり単純パーセプトロンでは、下図の青,緑,オレンジで描かれた識別境界はいずれも条件を満たしており、アルゴリズムから導かれる可能性があります。
これでは、たとえ教師データは２クラスに完璧に分類できていたとしても、未知データを最適に分類できるかと言われればその信憑性に欠けてしまいます。これが、単純パーセプトロンに不足している汎化能力というものです。
そこでSVMでは、単純パーセプトロンのアルゴリズムにある条件を加えることによって、その観点からは最適だと言える識別境界の決定を可能にしました。その条件というのが、ハードマージン最大化です。
2.1. ハードマージン
SVMにおけるハードマージン最大化というからには、ハードマージンと呼ばれる関数が極大値となるように重みベクトルを決定するのだろうなというのは予想がつくと思います。ハードマージンはマージンとも呼ばれますが、ではこのマージンとは一体何を指すのでしょうか。
マージンは、２クラス学習データの中で最も他クラスと近い位置にいるもの(これをサポートベクトルと呼ぶ)と識別境界f(x)=0との間のユークリッド距離のことです。ハードマージン最大化では、このマージンdを最大化するような識別境界を求めます。
🔥初心者ゾーン突入🔥
しかしここで、初心者の僕は疑問に思ってしまいました。マージンは定義上クラスと識別境界の距離のこととなっているが、クラスは２つある。これはつまり、マージンも２つ存在することになってしまうのではないかと。そして、例えば識別境界を平行移動させることでクラス１のマージンを大きくしようとしてしまうと、クラス２のマージンは小さくなってしまうのではないかと。
これについては、マージン最大化に対する考え方を再確認することで解決できました。クラス１,2それぞれのマージンをd1,d2としましょう。マージン最大化の観点では、d1,d2どちらも最大化させなければいけません。クラス１とクラス２のマージンの合計を定数Dとしたとき、d1+d2 = Dとなります(識別境界は平行移動させただけなので)。この制約条件の上でどちらのクラスにとっても最適となるようなd1,d2を求めようとすれば解は必然的にd1=d2=D/2となり、最適解としてのマージンはd1=d2=dとおけることが分かります。
ただ「どちらのクラスにとっても最適となるようなd1,d2」という表現に少し曖昧さがあります。感覚的に中点をとれば総合的にみて最適だというのは分かるのですが、その包括的効用を数式化することはできるのでしょうか。例えばd1+d2=Dの制約のもとでmax d1*d2を満たすd1,d2を決定する、というような。可能な場合、d1*d2という効用関数は適当なのでしょうか。ここがまだ少し曖昧ですが、クラス１,２に優劣がなく対称性があることを考えれば、この結果自体には納得できるでしょう。
🔥初心者ゾーン脱出🔥
この項をまとめると、ハードマージン最大化においては、サポートベクトルと識別境界のユークリッド距離が最も大きくなるような位置(２つのサポートベクトルの真ん中)に識別境界が設定されます。
2.2. ヘッセの公式
それではここから、識別境界を数理的にどのように決定するかについて話していきます。
これ以降は、多くを機械学習入門～ハードマージンSVM編～から引用しています。
識別境界の数理的探索におけるマージン最大化のためには、マージンがどのような関数で設定されるのかを把握しなければならず、その関数の設定にはヘッセの公式が用いられます。ヘッセの公式とは、平面上の点と直線の距離を表す公式です。(証明はこちらを参考に→点と直線の距離公式の３通りの証明)
そして上図のように、ヘッセの公式をSVMにおいて多次元に拡張することによってマージンの関数を設定することが出来ます。
このときの||w||はノルムと呼ばれるものであり、||w||=√(w1^2+w2^2+・・・)の簡易表現です。
2.3. ハードマージン最大化の定式化
多次元における点と識別境界の距離を数式化できたので、これに基づいてマージン最大化を満たすための最適化問題の定式化を行います。
ヘッセの公式より、学習データの総数がn個のときの学習データと識別境界の最小距離d(マージン)は下記で与えられます。ここで、min_i=1,...,nとはデータi=1～nの中で関数内の計算結果が最も小さい値をとるときの値を返す関数です。
ハードマージン最大化のもとでは、この最小距離dを最大化するwとθを求めたいので、これを式にすると下記のようになります。ここで、maxw,θとは取り得るwとθの中で関数内の計算結果が最も大きい値を返す関数です。
このとき、||w||はiに結果が依存しないのでmin関数の外に出すことができることから、
と表すことができます。
🔥初心者ゾーン突入🔥
私はここでこう思いました。
上記の式は
①識別境界との距離が最小(マージン)となるようなデータ点iを取った上で、
②その最小距離を最大化するためのw,θを決定する
というプロセスで解釈されやすいが、これは誤りだ。なぜなら、プロセス①の時点でマージンとなる点iの決定はw,θに依存しているので、w,θを決めることなく最小距離となるような点iは分からない。つまり、プロセス②を行うためには①が必要だが、①を行うためには②が必要という状態になっている。これでは堂々巡りになってしまいw,θを求めることが出来ない。
しかし、私のこの疑問はある前提を忘れていることによるものでした。
それは、サポートベクトルは、識別境界に最も近いものではなく、２クラス学習データの中で最も他クラスと近い位置にいるものを指すということです。
これなら納得です。サポートベクトルの決定は識別境界に依存しないので、識別境界が決定されなくてもサポートベクトルを決定することができます。
しかしさらに、初心者の私にはある新たな疑問が浮かび上がってきました。
もしサポートベクトルiが識別境界に最も近い点jと異なる点だった場合だったときであっても、サポートベクトルiをマージン最大化のための点として用いなければいけないのかと。
しかし、これはあり得ないことです。なぜなら、識別境界はサポートベクトルに依存して決められるものなので、サポートベクトルiが識別境界に最も近い点jとなるように識別境界が決定されるからです。
上記の議論はいずれも疑問に持つまでもないとるにたらないものものですが、もし混乱してしまった人のためにメモとして記しておきました。以上をまとめると、
この式は、
①サポートベクトルとなるような点(識別境界に依存しない)を各クラスから２点抽出し、
②その点と識別境界との距離が最大となるように識別境界が決定される
と解釈できます。
🔥初心者ゾーン脱出🔥
では式の解釈ができたところで本題に戻ります。
この節の目的は、マージン最大化を満たすための識別境界決定問題の定式化というものでした。
(すいません数式の入れ方が分からずjpegとして挟ませていただきました。)
以上より、ハードマージン最大化のための識別境界決定問題は以下のように定式化されることが分かりました。
2.4. ラグランジュの未定乗数法
2.5. KKT条件
2.6. ハードマージンによる識別境界の決定
それでは定式化ができたのでいざ数学的に解いてみようとなるはずなのですが、これ以降に関してはまだ授業でふれられていないので割愛します。
この部分については先程も述べました、機械学習入門～ハードマージンSVM編～に丁寧にまとめられているので、そちらをご参照ください。
2.7. 私見：識別境界の性質(メモ)
＜命題＞
マージンが最大となるように識別境界を設定する時、必ず２つのサポートベクトルの中点を通る
＜証明＞
この証明をステップで説明すると以下のようになります。
①２クラスにとってのマージン最大化なので、マージンは等しくなる(赤線の長さ)
②しかし、２クラス両方にとって赤線よりも青点線と緑線の交点である点Oまでの距離の方が長いので(三平方の定理より)、点Oを通る識別境界がマージン最大化を満たす。
このとき、点Oは中点である。
③点Oを通りサポートベクトル同士を結んだ直線に垂直になるように識別境界が決定される
