ガウスカーネルを使ったサポートベクターマシンで配送可能エリアを区分けする
三次元のカーネルトリックでは解けないサポートベクターマシン分類問題もある
まずは前回のおさらいです。
下のようなデータがある時に、配送可能エリアと配送不可エリアを直線で分けることはできません。
そこで、x2やy2やxyという新たな特徴量を作り、３次元に非線形変換しました。
これによって下の写真のように直線で切り分けられるようになりました。
そして、その直線を元の２次元に復元すると、下図のように切り分ける曲線が出来上がるというものでした。
これをカーネルトリックと呼びました。
>> 【カーネルトリック】非線形のサポートベクターマシンをExcelに実装して理解する
ところが、もし次のようなデータだったらどうでしょうか？
実は前回のやり方では、このような分類曲線は作れません。
x2やy2やxyだけの特徴量では足りないのです。
このような曲線は２次関数では表現できないため、x3やy4等のもっと高次の特徴量が必要なのです。
でも、どのくらい次数を高めれば良いのか事前に決めるのは難しいですね。
ガウスカーネルで無限次元の分類ができる
そこで役に立つのがガウスカーネルです。
ガウスカーネルは
K(x, x’) = exp(-β║x-x’║2)
β>0
で定義されますが、exはマクローリン展開するとxについての無限次数の級数で表せるため、ガウスカーネルを使うと無限次数の特徴量を使っていることになるのです。
ちなみに、前回使ったカーネルは
K(x, x’) = (xTx’)2
でしたが、これは多項式カーネルと呼ばれ、一般的には次式で表現されます。
K(x, x’) = (xTx’+c)d
この式でc=0、d=2と置いた式が前回使ったカーネルというわけです。
多項式カーネルだと次数は有限になってしまい、何次の多項式カーネルにすれば良いのか試行錯誤が必要になりますが、ガウスカーネルだとその手間がなくなります。
ガウスカーネルをExcelに実装して試してみる
損失関数の式をL2ノルムを使って変更する
それではガウスカーネルを使って、先の分類曲線が作れるかどうかをExcelで実験してみましょう。
まずはExcelに入力するために、式を具体的に書き直します。
サポートベクターマシンは、次式の目的関数Lを最大化させるようなλiを求める問題に帰着しました。
λ1t1+λ2t2+ ･･･ +λntn=0の条件下で、
L = (λ1+λ2+ ･･･ +λn ) – ½ (λ1λ1t1t1(Φ(x1)T Φ(x1)) + λ1λ2t1t2(Φ(x1)T Φ(x2)) + ･･･ + λnλntntn(Φ(xn)T Φ(xn)))
今回の例では教師データが15個ありますので、n=15です。
また、
Φ(x1)T Φ(x2) = K(x1, x2) = exp(-β║ x1– x2║2)
ですから、
L = (λ1+λ2+ ･･･ +λn ) – ½ (λ1λ1t1t1exp(-β║ x1– x1║2)+ λ1λ2t1t2exp(-β║ x1– x2║2)+ ･･･ + λnλntntnexp(-β║ xn– xn║2))
と書き換えられます。
ここで、║ x1– x2║はベクトルx1とベクトルx2のL2ノルムといい、次式で定義されます。
ベクトルx1の成分を(x1, y1)、ベクトルx2の成分を(x2, y2)とすると、
║ x1– x2║= √(x1–x2)2
= √((x1-x2)2+(y1-y2)2)
従って、ベクトルの成分（スカラー）で目的関数Lを表現すると、次式のようになります。
L = (λ1+λ2+ ･･･ +λn ) – ½ (λ1λ1t1t1exp(-β((x1-x1)2+(y1-y1)2))+ λ1λ2t1t2exp(-β((x1-x2)2+(y1-y2)2))+ ･･･ + λnλntntnexp(-β((xn-xn)2+(yn-yn)2)))
前回は
L = (λ1+λ2+ ･･･ +λn ) – ½ (λ1λ1t1t1exp(-β(x1x1+y1y1)2)+ λ1λ2t1t2exp(-β(x1x2+y1y2)2)+ ･･･ + λnλntntnexp(-β(xnxn+ynyn)2))
でしたので、変更は簡単です。
ソルバーでλの最適解を求めて係数を計算する
βは1、λ1からλ15の初期値はすべて1としてソルバーを実行します。
すると、次のように15個のパラメータλが最適化されます。
この結果を使ってw1、w2が求まり、更にそれを使ってw0を求めるやり方は前回と同じです。
求まったλiとw0を次式に代入して、１か－１かを判別する式が出来上がります。
f(x) = ΣλitiK(x, xi) + w0
教師データは判別できたが過学習が発生
そして、この式の結果と教師データを比べると次のようになります。
このように、ほぼ正確に判別できていることが分かります。
次に、教師データではないデータで試してみましょう。
原点に近いデータで試してみます。
判別結果はすべて１になるはずですが、なんと半分以上はマイナスに誤分類されました。
これは明らかに間違いです。
そこで、この判別式f(x)をグラフにしてみましょう。
f(x)を高さ方向にプロットすると、次のようになります。
なんと、ほとんどの地点ではf(x)はマイナスになっていて、教師データが１の地点でだけf(x)が１になっていて、教師データが－１の地点だけf(x)が－１になっています。
この判別式は、教師データと合うように局所的に調整しているだけだったのです。
これは過学習と呼ばれる現象です。
全体の傾向を学習するのではなく、一つひとつの教師データに過剰に合わせてしまったのです。
ガウスカーネルは便利だが感度の調整は必要
そこで、感度をもう少し下げてみましょう。
ガウスカーネルの感度は
K(x, x’) = exp(-β║x-x’║2)
の中のβで調整できます。
先ほどはβ＝１でしたが、β＝０．１に変えて試してみましょう。
結果はこうなりました。
まだ過学習しているようです。
もっと感度を下げてみましょう。
β＝０．０１にするとこうなります。
だいぶマシになりましたが、あと一息です。
もっと感度を下げてβ＝０．００１にしてみましょう。
すると、こうなります。
いい感じに学習されました。
真上から見ると、次のようになります。
黄色が１と分類された箇所で、配送可能地域ということです。
これは正に欲しかった下図のような分類曲線と一致します。
ガウスカーネルを使えば非線形の分類でも簡単にできますが、過学習を避けるために感度調整は必要であることが分かりました。