概要
機械学習モデルの1つであるサポートベクトル・マシン(以下、SVM)について学習した
この章では以下の項目を学んだ
・SVMの基礎
・マージンの最適化問題
・不等式制約付き最適化問題
・不等式制約付き最適化問題を手計算(appendix)
SVMの基礎
・SVMとは2クラス分類モデルの代表的な1つである。回帰問題や教師なし問題への応用もされている
・SVMはマージンの最大化という考えがベースになっている
マージンの最大化とは？
2つのクラスK1とK2を考える。2つのデータ間に境界線を引くことで2つのクラスを分類することができる
この境界線と境界線の最短距離にあるデータを最大化するように境界線を引くことである。
境界線と境界線に最も距離が近いデータまでの距離をマージンという。
また、この境界線と最も距離が近いデータ(マージン上にあるデータ)のことをサポートベクトルという
また、境界線は以下の式で表すことができる。
上の式にあてはめて0未満であれば-1、0以上であれば+1として各クラスに割り当てる(正負によってクラス分けてを行う)
p次元データx = (x1,x2,・・・xp)Tと境界線までの距離は以下の式で表すことができる
よって、クラスを分ける境界線からサポートベクトルまでの距離であるマージンは以下の式で表すことができる
よってマージンの最大化は以下の式で表すことができる
式変形を繰り返すと以下のような式となり、制約条件下でw,bを最小化する最適化問題となる
上記の式のように線形分離可能を仮定したSV分類をハードマージンとよぶ
サポートベクトルを元に境界線を引くため、サポートベクトルより遠いデータが入力されても境界線には影響しない
しかし、全てのパターンにおいて線形分離が出来るわけではない
このようなデータに対してSVを適用できる世に制約条件を以下のようにしたものをソフトマージンという
ξはマージン内に入るデータや誤分類されたデータに対する誤差を許すスラック変数という
ソフトマージンの最適化問題は以下のように表すことができる
ペナルティであるCを大きくすると誤差を許さない。逆にいうと過学習を起こしてしまうリストがある
Cを小さくすると間違いを認めてるが、誤分類が多くなる
wとξは相反するパラメータであるため、両方のパラメータを調整しながら最小を図る
マージンの最適化問題
SVMのマージンの最大化は以下の最適化によって定式化される
これらの最適化問題をSV問題の主問題という
しかし、主問題を直接解くのではなく相対問題というべつの形で表現して最適化を図る
相対問題にすることによるメリット
①変数を減らせることがある
理由はわかったけど、どう解くのか？？
不等式制約付き最適化問題
この相対問題を解くためにラグランジュの未定乗数法を利用する。
ラグランジュの未定乗数法
目的関数f(x)を最小化する点をn個の不等式制約gi(x)<0,1,,,iの元で求める
目的関数と不等式制約を1つにした関数ラグランジュ関数は以下の式で定義される
ここでSVMの話にもどす
SVMの目的関数および不等式制約は以下の式である
この条件をラグランジュ関数に果てはめて計算すると以下のようになる
上記の式を写像すると以下のようになる
カーネルトリック
しかし、次元が大きいとΦ(x)TiΦ(x)jの計算は非常に難しい
そこでΦ(xi)TΦ(xj)の部分を以下のように置き換えることができる
このKをカーネル関数といい、2つのベクトル計算をすることなく内積を見積もることができる
以下、代表的なカーネル関数
不等式制約付き最適化問題を手計算(appendix)
以下は手計算にて不等式制約付き最適化問題を解く過程である
