サポートベクターマシン(support vector machine:SVM)の基礎

線形識別器の代表格としてサポートベクターマシンを取り上げます。

機械学習で一躍有名となった手法の1つで、ディープラーニングが流行る以前は「え、まだニューラルネットやっているの？時代はサポートベクターマシンでしょ」と言った雰囲気でした。今はなぜか逆転して「まだサポートベクターマシンやってるの？」と言う人が実際にいるのですが（笑）、ディープラーニングの設計・学習の手間などを考えるとサポートベクターマシンはまだまだ捨てたものではありません。転移学習などでも応用が効きますしね。

SVMはマージン最大化という考えで、高い汎化性能を持つことが知られています。今回は、SVMがどのような考えでデータを識別するように学習を行うのかを説明していきたいと思います。今回は線形識別器として取り上げますが、当然基底関数を変える、カーネル法を用いることで非線形への拡張ができますから、その点についても触れていきたいと思います。

線形識別器の基本
- マージン最大化
SVM
発展的な話題
更に理解を定着させるために

線形識別器の基本

まずは、線形識別器というものが如何なるものかをおさらいします。

以下の記事を読んでみてください。短いのですぐ終わるはずです。

www.hellocybernetics.tech

キーポイントだけ述べると、2つのクラスの2次元データ $x_n$ が複数あるとして平面上に

$y=wx+w_0$

という直線を引くことで、その直線を境界線にしたいというのが線形識別器です。願わくばその境界線は、2つのクラスをピシッと分けるような境界線になっていてほしいわけですが、そのような境界線を決めているのは $w,w_0$ にほかなりません。こいつらをどうやって決めるのか？その方法の1つにマージン最大化なる考え方があります。

マージン最大化

マージンとは、引いた境界線と、データの最短距離のことを言います。

つまり今から引く境界線は、2つのクラスのデータからそれぞれなるべく離れている場所に引きますというのがマージン最大化の考え方です。以下の画像を見比べてください。

f:id:s0sem0y:20160808042726p:plain

左の絵と右の絵、どちらも直線が赤と青をしっかり分類できていますね。しかし、どちらの線の方がより良さそうか？と聞かれたら右だと感じることでしょう。

それは、直線に最も近いそれぞれのデータ点と直線との距離が、右の絵の方が遠いからです。この距離がマージンであって、これを最大化するように引くというのがSVMの考え方です。

今後新しいデータ（黒丸）が入手できたとして、それが下の画像のような場所に来た場合はどちらだと判別すべきでしょうか？左の境界線によれば、新しいデータは赤の仲間であると判断し、こ右の境界線によれば青の仲間であると判断すべきです。さすがに参考の画像からは一概には言えません（元々境界線を引いたときの訓練データが少なすぎるためです）。しかし、訓練データが多くなり、それぞれのクラスがどのへんに固まってくるかが分かってくると、マージン最大化により得られた境界線の方が信用できそうだというのは直感に合っているでしょう。

f:id:s0sem0y:20160808043146p:plain

SVM

以後は、多次元データ $x$ はベクトルで、 $w$ も同じく多次元ベクトルとします。また、これから扱うデータは、いつでも上記の画像のように、線形識別が可能であるような配置になっているとします（線形識別できない場合は非線形な境界を考えれば良く、それは後で拡張します。また、集めたデータに対して少し間違っていても、それっぽく引くというのも大事で、それも後で説明します）。そのような状況でも、上記の通り、境界線の引き方は無数に考えられるので、マージン最大化という考えで境界を引く方法を考えていきます。

SVMの線形識別

求めるべき境界は以下の式で表されますね。

$y(x)=w^Tx+w_0$

また適当なデータ点 $x_n$ について $y(x_n)$ が正となれば、そのデータ点の番号 $n$ について $t_n=1$ とラベルを振り、逆に $y(x_n)$ が負であれば、 $t_n=-1$ とラベルを割り振ることにしましょう。もちろん境界上の点 $x_n$ については $y(x_n)=0$ となってしまいますが、我々は今マージン最大化で、データ点から境界がなるべく離れるように境界線を決めようとしているのでコレでいいのです（境界上に点が来るとマージン0です！）。

すると、必ず $t_ny(x_n)$ は正となることに注意してください。

上記の境界と、あるデータ点 $x_n$ との距離 $|r|$ は

$|r|=\frac{|y(x_n)|}{|w|}$

で求まります。(線形識別モデルの基本 - HELLO CYBERNETICS)

必ず $t_ny(x_n)$ は正であり、しかも $|t_n|=1$ であることに着目すれば

$|r|=\frac{|y(x_n)|}{|w|}=\frac{t_ny(x_n)}{|w|}=\frac{t_n(w^Tx+w_0)}{|w|}$

となります。これを最大化するようにすればいいわけですね。

ただし、今見ている境界と点の距離 $|r|$ というのは、データ点の中で境界に一番近いもののことを言っていますから、数式では以下のように表現します。

$\min_{n}\left( \frac{t_n(w^Tx_n+w_0)}{|w|} \right)$

すなわち、「境界線と距離が最も近いデータ点 $x_n$ についての、境界線との距離」が上記の式が指定しているものです。そしてこの距離が、 $w,w_0$ を調整することで最も大きくなるように線を引こうとしているので、求める式は

$arg \max_{w,w_0} \left( \frac{1}{|w|}min_n \left( t_n(w^Tx_n+w_0) \right) \right)$

を最大化すれば良いということになります。何かややっこしく見えますが、ともかく境界線から一番近くにある点 $x_{nearest}$ を決めて、その点と境界線との距離を最大化するような、 $w,w_0$ を求めるということです。

より一般的には

非線形な基底関数 $z=φ(x)$ を準備することで

$y=w^Tφ(x)+w_0=w^Tz+w_0$

を境界線とします。これは、データ点 $x$ を非線形変換した先の空間で線形識別を行うという発想になります。

図でイメージを示すと、以下のように、左図( $x$ の空間)では線形識別できなくとも、右図( $z$ の空間)では線形識別（平面による識別）ができるようになる（のではないか？）という発想です。そのような上手い $φ(x)$ はすぐに見つかるものではありません。ましてや、もっと高次元データの場合は可視化自体ができないため、非常に困難な問題になります。それでもこの発想によって、解決できる問題の幅が広がるのは間違いないでしょう。

f:id:s0sem0y:20160808053356p:plain

識別を行うために、どのように $w,w_0$ を決定するのかというと、議論は全く同じで

$arg \max_{w,w_0} \left( \frac{1}{|w|}min_n \left( t_n(w^Tφ(x_n)+w_0) \right) \right)$

を求めるということになります。通常の線形識別では $φ(x)=x$ と何も変換をしなかったと見なせば話が通じるので、通常教科書は $φ(x)$ の方で議論をしているでしょう。

問題の変形

しかし上記で得られた最適化問題を解くのは一般に非常に困難です。

そこで問題を少し変形していきましょう。

今求めようとしている $w,w_0$ についてですが、これらをそれぞれ $k$ 倍してみましょう。

そうしたとしてもデータ点との距離 $|r|$ については

$|r|=\frac{t_n(kw^Tφ(x_n)+kw_0)}{|kw|}=\frac{t_n(w^Tφ(x_n)+w_0)}{|w|}$

と約分で落ちてしまうので影響はありません。すなわち $w,w_0$ を適当に定数倍しても最適化問題に影響はなく、変更が自由にできます。そうであるならば境界に最も近い点 $x_n$ について

$t_n(w^Tφ(x_n)+w_0)=1$

となるように定数倍された $w$ で議論をしても問題がないはずです。

そうすると、境界に最も近い点が上記の値になっているのですから、それ以外の点も含めた全ての点について

$t_n(w^Tφ(x_n)+w_0)\geq 1$

となっています。当然、最も近い点のみが等式を満たしています。また、2クラスあるため、マージン最大化を行ったときには、それぞれのクラスに1つずつ等式を満たす点があるはずです（それぞれのクラスに1つずつ無いならば、境界線はどちらかに偏っていることになってしまう）。

このように定数倍を介したことで、最も近い点についてのマージン最大化問題は

$arg \max_{w,w_0} \left( \frac{1}{|w|}min_n \left( t_n(w^Tφ(x_n)+w_0) \right) \right)=arg \max_{w,w_0} \frac{1}{|w|}$

となります。しかもコレは結局

$arg \min_{w,w_0} \frac{1}{2}|w|^2$

に置き換えられます(係数は本質的には意味ありませんが、二乗の項には $\frac{1}{2}$ を付けておけば微分したときに楽だというだけです)。

つまり制約条件として

$t_n(w^Tφ(x_n)+w_0)\geq 1$

のもとで

$arg \min_{w,w_0} \frac{1}{2}|w|^2$

を求めるということになります。

これは最適化の手法である二次計画法によって解を導くことができます。

発展的な話題

これを更に不等式制約のラグランジュ定数法を用いて別の表現（双対表現）に変えることができます。その際にも二次計画法の問題に帰着されます。どちらの表現の方が処理が楽かは基底関数 $φ(x)$ の形によって決まってきます。 $φ$ が無限次元への変換になっている場合は、双対表現では $φ(x)$ を単独で扱うことがなくなり $φ(x_n)^Tφ(x_m)$ という内積の値でしか現れず、無限次元だろうが結局スカラー値のみしか評価しないため、非常に処理が楽になります。このスカラー値をカーネル関数 $k(x,x')$ と言います。どのような基底関数が識別に有利かは定かではない中で、様々な $φ(x)$ を直接扱うよりは、スカラー値であるカーネル関数 $k(x,x')$ を扱ったほうが楽そうなのは言うまでもありません。サポートベクターマシンが繁栄したのは、このような問題の様々な表現変更によって、数学的に扱いやすく整備されていったためです。通常この方法をカーネル法と言います。