SVM(サポートベクターマシーン)についてまとめてみた

学生の頃から、いつかまとめようと思っていたSVM(サポートベクターマシーン)に関してまとめてみる。

SVM (サポートベクターマシーン)

サポートベクターマシーンとはそもそも何か？という話なんですが、
大きな枠でいうとデータ集合を分類する識別関数のことです。

関数なので、何かブラックボックスf(x)に入力を入れるとそれに対応する出力(-1 か 1)が出るわけです。

f({\bf x}) = {\rm sgn}(g({\rm x})) = -1\ {\rm or}\ 1\\
g({\rm x}) = {\bf w}^{\rm T}{\bf x} + b

※xは入力、wは結合荷重(入力にかかる重み)、bはバイアス項(接線)、sgnは符号関数
(中が正なら1, 負なら-1を返す関数のこと)

入力 x に対して 1 か -1を識別してあげる関数なので識別関数と考えれば問題ないかと。
そして、識別関数の出力がいい感じの出力になるようにwとbを求める問題に発展するわけです。
(例：文字認識なら、文字に対応したラベルなど)
ちなみにこのようなイメージ図になるわけです。

これだけだと線形二分器と呼ばれている単純パーセプトロンと何ら変わりないのです。

何が違うのかというと、サポートベクトルの概念を取り入れていることなんですね。
そもそも、上の図で何気なく識別平面(上図直線のこと)を引いてデータを二分割してますが、
本当にデータにとっていい識別平面ってなんだろう？という疑問が出てくるわけです

(こんな風にたくさん識別平面が引けるわけです。)
結論からいうと、データにとって良い識別線とは、未知のデータが入ったときに正しく分類される包容力のある線
なんです。かっこよく言うと汎化能力とか言っちゃったりします。

そこで出てくるのがサポートベクトルで、識別平面に最も近いデータがサポートベクトルになるわけです。
(枠で囲っている点2つが今回のサポートベクトルになる)
そうして決まったサポートベクトルと識別平面の距離(マージン)が最大になるwとbを求めることになります。

マージンの求め方

マージン、つまり識別平面との垂線の長さを求めるためには、三角比などを用いる必要があります。

ここで、g(x)=1となるような場合の範囲とg(x)=-1となるような範囲は以下のように決まります
(g(x)がy軸と考えればわかりやすいかと)

正:g({\rm x}) \leqq 1\\
負:g({\rm x}) \geqq -1

負の式に-1を両辺にかけて、正負の記号tを置いてあげると、二つの式は一緒くたにまとめれます。

tg({\rm x}) \leqq 1\\
\leftrightarrow t({\bf w}^{\rm T}{\bf x} + b) \leqq 1\\
t = (1, -1)

サポートベクトルの推薦の長さは上記の結果と識別平面との垂線の長さの知見から

\frac{1}{\|{\bf w}\|}

となり、正のデータのサポートベクトルと負のデータのサポートベクトルのマージンの差は、
2/|w|となるので、このマージン最大化問題は以下のように定式化できますね

t({\bf w}^{\rm T}{\bf x} + b) \leqq 1の制約で\\
{\bf w}の最小値、つまり\frac{2}{\|{\bf w}\|}の最大値を求める

wが小さくなればなるほど、上の下段式が大きくなっていきます。
また、wの評価関数を与えてあげるとこういう問題になります。

1/2{\bf w}^{\rm T}{\bf w}

この制約付き問題を解くために、ラグランジュの未定乗数をつけてあげて解きますが、
今回は体力的な事情で省略します(苦笑い)。

そうすると、双対問題に発展してくるのですが、そのあたりは
僕のおざなりな発表資料を見ていただくと、双対問題とは？？というのがわかるかと思います。

ざっくり説明すると、ラグランジュの未定乗数をつけると、解くべき問題(今回だとwとbを求める問題)が未定乗数に出てくる変数を求める問題(参項)に置き換わります。
解くべき問題を主問題、置き換えた後の問題を補問題と呼び、どちらを解いても(双対している)解がもとまるので双対問題と呼びます。

ソフトマージンとハードマージン

先ほどまでもとめていたマージン最大化はデータ集合自体が線形分離可能な場合のみ、使える技なのです。

上図のようなノイズが載ってまとまってないようなデータ集合の場合はいつまでたっても最適なwを求められない問題が生じてきます。マージンに対して厳密に分けようとするからハードマージンなんて言ったりします。
(※本当は別の意味で数式の解釈でハードマージンと呼ぶのですが直感的解釈でおｋ)

ハードがあるならソフトもある、ということでソフトマージンの考えが導入されます。

t({\bf w}^{\rm T}{\bf x} + b) \leqq 1 - \xiの制約で\\
1/2{\bf w}^{\rm T}{\bf w} + C\sum_{i=1}^{n}\xi_{n} の評価関数の最大化を行うwを求める

ここでCとξというパラメータが出てきました。

ξがどれだけ識別平面を緩和してあげるかというスラック変数
Cがどれだけ厳しくマージンを決めるかというパラメータになります。

この場合のSVMはパラメータCを用いるのでC-SVMなんて呼ばれたりします。

最終的にはハードマージンと同様の形の双対問題を解くことになり、めでたしめでたしです。

12/24のエキサイトアドベントカレンダーではpythonのscikit-learnを用いてC-SVMのパラメータ調節をまとめます。