サポートベクトルマシンを理解する上ので基本的な知識
- 言語処理のための機械学習入門 (自然言語処理シリーズ)の4.3 サポートベクトルマシンを理解する上で重要な部分をまとめました。
前提
訓練データ
x^{(1)}, x^{(2)}, \cdots は訓練時に用いた事例
y^{(1)}, y^{(2)}, \cdots は上記のそれぞれの事例に対するクラスラベル(+1 または -1)
D = \{ ( x^{(1)}, y^{(1)} ), ( x^{(1)}, y^{(1)} ), \cdots, (x^{|D|}, y^{|D|}) \}
- 正クラス(+1)に属する事例は正例と呼ぶ
- 負クラス(-1)に属する事例は負例と呼ぶ
線形分類器
- SVMは線形二値分類器であり、クラス数が2つであるような問題に用いられ、関数は以下のように表す。
- 文献によっては-bのところが+bとなっているが証明の仕方に都合の良い形式をとると思われるので、気にしない
w: 2つのクラスを分離する平面の方向ベクトル。向きは正クラスの方向
b: wと分離平面の接点
f(x) = w\cdot x - b
- 正のクラスラベルは+1で条件は以下の通り
f(x) >= 0
- 負のクラスラベルは-1で条件は以下の通り
f(x) < 0
準備
正例x_+と分離平面を結ぶ垂線の足をx_*とする
0 = w\cdot x_* - b\\
w\cdot x_* = b
分離平面から平行かつ、分離平面から最短距離にある正例のデータを通る平面を考えた時に、
正例x_+を通る平面は以下の形で表すことができる
k > 0 \\
w\cdot x_+ - b = k \\
上記方程式を定数倍しても元の平面と同じなので
w / k \cdot x_+ - b / k = 1 \\
となり
w / k は w \\
b / k は b
と置き換えてもこれからの計算には影響しないので、以下のように置き換えが可能
w \cdot x_+ - b = 1 \\
w \cdot x_+ = b + 1 \\
マージン最大化
- SVMでは２つのクラスの分離平面が、それぞれのクラスをなるべく遠い位置で分けるようにする問題を取り扱う
平面間のマージンは|x_+ - x_*|となる
x_+とx_*は同じ方向を向いているので
w \cdot (x_+ - x_*) = |w| \cdot |x_+ - x_*|
先ほど求めた式を利用すると上記は
\begin{align}
w \cdot (x_+ - x_*) &= w \cdot x_+ - w \cdot x_* \\
&= (b + 1) - b \\
&= 1
\end{align}
上記2式を合わせると以下のようになり
|w||x_+ - w_*| = 1 \\
|x_+ - w_*| = 1 / |w|
2平面間のマージンは以下で表わされるが、
1 / |w|
絶対値では扱いにくいので
1 / w^2
となり上記を最大化する問題を解くことになるが、
分数も扱いにくいので
w^2
の最小化問題へと変換する
あとは本書の内容に沿って読み進めることができる