ガウスカーネルを使って無限次元に非線形変換!Excelでサポートベクターマシンを実験する

まずは前回のおさらいです。

下のようなデータがある時に、配送可能エリアと配送不可エリアを直線で分けることはできません。

 

そこで、x2y2xyという新たな特徴量を作り、3次元に非線形変換しました。

これによって下の写真のように直線で切り分けられるようになりました。

 

そして、その直線を元の2次元に復元すると、下図のように切り分ける曲線が出来上がるというものでした。

 

これをカーネルトリックと呼びました。

>> 【カーネルトリック】非線形のサポートベクターマシンをExcelに実装して理解する

 

ところが、もし次のようなデータだったらどうでしょうか?

 

実は前回のやり方では、このような分類曲線は作れません。

 

x2やy2やxyだけの特徴量では足りないのです。

このような曲線は2次関数では表現できないため、x3y4等のもっと高次の特徴量が必要なのです。

でも、どのくらい次数を高めれば良いのか事前に決めるのは難しいですね。

 

そこで役に立つのがガウスカーネルです。

ガウスカーネルは

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で実験してみましょう。

まずは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– x22)

ですから、

L = (λ1+λ2+ ・・・ +λn ) – ½ (λ1λ1t1t1exp(-β║ x1– x12)+ λ1λ2t1t2exp(-β║ x1– x22)+ ・・・ + λnλntntnexp(-β║ xn– xn2))

と書き換えられます。

 

ここで、║ x1– x2はベクトルx1とベクトルx2L2ノルムといい、次式で定義されます。

ベクトルx1の成分を(x1, y1)、ベクトルx2の成分を(x2, y2)とすると、

x1x2║= √(x1x2)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個のパラメータλが最適化されます。

 

この結果を使ってw1w2が求まり、更にそれを使ってw0を求めるやり方は前回と同じです。

求まったλiとw0を次式に代入して、1か-1かを判別する式が出来上がります。

f(x) = ΣλitiK(x, xi) + w0

 

そして、この式の結果と教師データを比べると次のようになります。

 

このように、ほぼ正確に判別できていることが分かります。

次に、教師データではないデータで試してみましょう。

原点に近いデータで試してみます。

判別結果はすべて1になるはずですが、なんと半分以上はマイナスに誤分類されました。

 

これは明らかに間違いです。

そこで、この判別式f(x)をグラフにしてみましょう。

f(x)を高さ方向にプロットすると、次のようになります。

 

なんと、ほとんどの地点ではf(x)はマイナスになっていて、教師データが1の地点でだけf(x)が1になっていて、教師データが-1の地点だけf(x)が-1になっています。

この判別式は、教師データと合うように局所的に調整しているだけだったのです。

これは過学習と呼ばれる現象です。

全体の傾向を学習するのではなく、一つひとつの教師データに過剰に合わせてしまったのです。

 

そこで、感度をもう少し下げてみましょう。

ガウスカーネルの感度は

K(x, x’) = exp(-βx-x’2)

の中のβで調整できます。

先ほどはβ=1でしたが、β=0.1に変えて試してみましょう。

結果はこうなりました。

 

まだ過学習しているようです。

もっと感度を下げてみましょう。

β=0.01にするとこうなります。

 

だいぶマシになりましたが、あと一息です。

もっと感度を下げてβ=0.001にしてみましょう。

すると、こうなります。

 

いい感じに学習されました。

真上から見ると、次のようになります。

 

黄色が1と分類された箇所で、配送可能地域ということです。

これは正に欲しかった下図のような分類曲線と一致します。

 

ガウスカーネルを使えば非線形の分類でも簡単にできますが、過学習を避けるために感度調整は必要であることが分かりました。