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

2021年10月15日

宅配便会社Aでは、ある配送センターから1時間以内で配送できる範囲を調べるために、15か所の配送先でテストしました。

下記がその結果です。

 

例えば、最初の配送先は東に16km、南に21.1km配送センターから離れていて1時間以内に配達不可、最後の配送先は東に13km、南に2.3km配送センターから離れていて1時間以内に配達できたことを示しています。

グラフにすると次のようになります。

 

ここで、新しい配送先が出てきた時の配送可否の判断をシステム化してみましょう。

このように新しく得られるデータを、その特徴に従って2つのグループに分けるのはサポートベクターマシンの得意とするところです。

しかし、今回は前回と違って直線できれいに切り分けることができません。

下図に示すような曲線で切り分けるしかありません。

 

このように直線で切り分けられない問題を「非線形問題」といいます。

こんなトリッキーな切り分けができるのでしょうか?

 

簡単にできるのです!

 

カーネルトリックという名のトリックを使えば。

このトリックは良くできたトリックですが、具体例で解説した記事が少ないようですので、皆が理解できるExcelでその種明かしをしていきます。

 

次元を増やせば直線で分けられる

まずは、話しを簡単にするために1次元で考えてみましょう。

ある新薬について、摂取量による効き目を調べるテストをしたところ、次のようなデータが得られました。

 

薬は過剰摂取でも過少摂取でもダメで、丁度良い量を飲んだ時だけ効き目があったというデータです。

でも、このままでは2グループに分けることはできませんね。

そこで、次元をもう一つ上げて、2次元にしてみましょう。

どうするのかというと、摂取量の二乗を計算して縦軸に加えるのです。

つまりこういうことです。

 

するとほら、青の点線のように直線で分けられますね。

このように次元を増やせば、直線で分けられるようになる可能性があります。

この例では1次元だけ増やしましたが、更に多くの次元にまで増やすことにより、もっと複雑な問題でも直線で切り分けられるようになることが知られています。

 

ここで配送センターの例に戻ります。

この例では平面にプロットできたので、2次元のデータです。

東西方向の距離で1次元、南北方向の距離でもう1次元です。

 

これでは直線で分けれませんが、このシートを真ん中で摘まんで引っ張り上げれば、ほら、直線で分けられますね。

 

次元を上げれば直線で分けられるとは、このようなイメージです。

更に、この引っ張り上げた状態で切り分ける直線を引けば、シートを元の状態に戻したら青色部分を囲むような曲線になることもイメージできると思います。

つまり、直線で切り分けられる状態になるまで次元を上げて直線を引けば、元の次元に戻した時にはうまく切り分けるクネクネした曲線が出来上がってくるのです。

 

では、具体的にどのように次元を上げるのかを見ていきましょう。

配送センターの例では、15個あるうちの1つ目のデータは(16, -21.1)です。

これを(x1, y1)=(16, -21.1)というようにx1とy1を定義します。

よくある次元の増やし方は、こんな感じです。

(x12, y12, √2x1y1)=(256, 445.2, -477.4)

 

これで、3次元まで増えたことになります。

 

ここで、サポートベクターマシンのアルゴリズムをもう一度おさらいしてみましょう。

 

λ1t1+λ2t2+ ・・・ +λntn=0の条件下で、

L = (λ1+λ2+ ・・・ +λn ) – ½ (λ1λ1t1t1(x1x1+y1y1) + λ1λ2t1t2(x1x2+y1y2) + ・・・ + λnλntntn(xnxn+ynyn))

最大値を求める。

 

でした。

>> サポートベクターマシンを理解するためにExcelに実装して具体例を解いてみた

 

Lの中には(x1x1+y1y1)(x1x2+y1y2)等の項が含まれていますね。

このxiやyiは教師データです。

配送センターの例だと、(x1, y1)=(16, -21.1)が1つ目の教師データです。

今回はこれが15個ありますので、xiとyiの組が15個あります。

これらすべての組み合わせについて(xixj+yiyj)を計算しますので、225個の項がLの中に現われます。

 

元のデータが(xi, yi)でこの計算式ですので、3次元のデータ(xi2, yi2, √2xiyi)になると、Lの計算式は次のようになります。

L = (λ1+λ2+ ・・・ +λn ) – ½ (λ1λ1t1t1(x12x12+y12y12+2x1y1x1y1)  + λ1λ2t1t2(x12x22+y12y22+2x1y1x2y2)  + ・・・ + λnλntntn(xn2xn2+yn2yn2+2xnynxnyn))

 

このようにとても長い式になって目がチカチカしてきますので、(xi, yi)を数字の組と見るのではなく、1つのベクトルxiとして見ます。

(この記事ではただの数字とベクトルを区別するために、ベクトルはxiの色でかつ太字で表します)

 

そして(xi2, yi2, √2xiyi)は(Φ1(xi), Φ2 (xi), Φ3 (xi))のように表します。

するとこれもベクトルになりますので、全体をΦ(xi)と表します。

このようにすると、

L = (λ1+λ2+ ・・・ +λn ) – ½ (λ1λ1t1t1(x1x1+y1y1) + λ1λ2t1t2(x1x2+y1y2) + ・・・ + λnλntntn(xnxn+ynyn))

L = (λ1+λ2+ ・・・ +λn ) – ½ (λ1λ1t1t1(x1Tx1) + λ1λ2t1t2(x1Tx2) + ・・・ + λnλntntn(xnTxn))

L = (λ1+λ2+ ・・・ +λn ) – ½ (λ1λ1t1t1(x12x12+y12y12+2x1y1x1y1)  + λ1λ2t1t2(x12x22+y12y22+2x1y1x2y2)  + ・・・ + λnλntntn(xn2xn2+yn2yn2+2xnynxnyn))

L = (λ1+λ2+ ・・・ +λn ) – ½ (λ1λ1t1t1(Φ(x1)T Φ(x1)) + λ1λ2t1t2(Φ(x1)T Φ(x2)) + ・・・ + λnλntntn(Φ(xn)T Φ(xn)))

のように簡潔に表すことができます。

今後は、この最後の式をLの式として使います。

この式を使えば、線形にも非線形にも対応できるからです。

線形で良い場合には、Φ(xi) = xiとすれば良いだけです。

 

ここで、新しい関数K(xi, xj)をK(xi, xj) = Φ(xi)T Φ(xj)のように定義します。

K(xi, xj)はカーネル関数と呼ばれています。

ここで注意すべきことは、K(xi, xj)はただの数字(スカラー)ということです。

 

なぜこのようにわざわざ新しい関数を持ち出すのかというと、この後の計算でΦ(xi)が単独で出てくることはないためです。

Φ(xi)T Φ(xj)のように必ずセットで出てきます。

しかも、先ほども述べたように、K(xi, xj) = Φ(xi)T Φ(xj)はただの数字(スカラー)なので、後の計算も簡単になります。

 

さて、ここで思い出して下さい。

Φ(xi)は低次元のベクトルを高次元のベクトルに変換する関数でしたね。

例えば、2次元の(x1, y1)を3次元の(x12, y12, √2x1y1)に変換する関数です。

ですので

Φ(x1) = Φ(x1, y1) = (x12, y12,√2 x1y1)

と書くことができます。

もう一つ

Φ(x2) = Φ(x2, y2) = (x22, y22, √2x2y2)

がある時、K(x1, x2)を求めてみましょう。

 

K(x1, x2) = Φ(x1)T Φ(x2)

= Φ(x1, y1) Φ(x2, y2)

= (x12, y12, √2x1y1)T(x22, y22, √2x2y2)

= x12 x22 + y12 y22 + 2x1y1 x2y2

= (x1 x2 + y1 y2)2

= ((x1 , y1)T(x2 , y2))2

= (x1Tx2)2

 

なんと3次元に変換した後のΦ(x1)T Φ(x2)の値は、変換する前のx1Tx2の値の2乗になりました。

 

この事実は大変重要です。

 

L = (λ1+λ2+ ・・・ +λn ) – ½ (λ1λ1t1t1(Φ(x1)T Φ(x1)) + λ1λ2t1t2(Φ(x1)T Φ(x2)) + ・・・ + λnλntntn(Φ(xn)T Φ(xn)))

の式で

Φ(x1)T Φ(x2) = (x1Tx2)2

としておけば、(xi , yi)の2次元データを (xi2, yi2, √2xiyi)の3次元データに変換したと見なして最適化計算ができるからです。

別に非線形変換なんてしてなくてもいいんです。

 

どういうことかというと、x1Tx2を (x1Tx2)2に置き換えるだけで、ビニルシートを指で摘まんだ状態で切り分ける直線のパラメータ(w1, w2, w0)を求めることができるのです。

この直線は摘まんだ状態で引いた直線ですので、シートを元に戻すとクネクネ曲がった曲線になります。

これこそが求める曲線になるのですが、ここでカーネル関数が効いてきます。

 

カーネル関数の定義より、

K(x1, x2) = Φ(x1)T Φ(x2) = (x1Tx2)2

です。

 

一方、最適化問題を解くとパラメータλiが求まるので、そのλiを使って

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

配送可否を判断する式になります。

配送可否を知りたい地点のx=(x,y)を代入して、f(x) がプラスなら配送可マイナスなら配送不可の判断となります。

 

この式の中のK(x, xi)は(xTxi)2としていますので、f(x) はx=(x,y)の二次関数になっています。

つまり、線形問題を解く時と同じように最適化問題を解いてλiを求めましたが、最終的にできる判別式f(x) はちゃんと非線形になっているのです。

これがトリックと呼ばれる所以です。

 

Excelに実装する

前回は線形のサポートベクターマシンでしたが、教師データは同じく15個でしたので、同じExcelシートを使いまわします。

>> サポートベクターマシンを理解するためにExcelに実装して具体例を解いてみた

 

変更箇所は

L = (λ1+λ2+ ・・・ +λn ) – ½ (λ1λ1t1t1(Φ(x1)T Φ(x1)) + λ1λ2t1t2(Φ(x1)T Φ(x2)) + ・・・ + λnλntntn(Φ(xn)T Φ(xn)))

の式の中の青字の部分だけです。

前回は

L = (λ1+λ2+ ・・・ +λn ) – ½ (λ1λ1t1t1(x1Tx1) + λ1λ2t1t2(x1Tx2) + ・・・ + λnλntntn(xnTxn))

でしたので、xiTxjを(xiTxj)2に変更するだけです。

なぜなら、Φ(xi)T Φ(xj) = (xiTxj)2だからです。

従って、λiλjtitj(xiTxj) を計算する箇所だけを下記のように変えます。

 

後は、前回と同じようにLを目的関数、λ1からλ15を操作変数としてソルバーを実行します。

すると、次のようにλ1からλ15最適化されます。

 

次にw1w2を求めますが、これは前回と同じ式で計算できます。

問題はw0で、f(x) = ΣλitiK(x, xi) + w0の式においてf(x)が一番大きな値を取る教師データ(xi, yi)を次式に代入してw0を求めます。

-1 = ΣλitiK(x, xi) + w0

 

今回は7番目のデータ(15, 16.9)がそれに相当しますので、xとして(15, 16.9)を上式に代入します。

従って、次のように大変長ったらしい式で計算します。

 

これで、すべてのパラメータが求まりましたので、f(x) = ΣλitiK(x, xi) + w0の式に教師データの各データを入力して、f(x) がどんな値になるか確かめてみます。

下図のように、f(x)がプラスかマイナスかにより、配達可能か不可かを正確に判断できるようになりました。

 

f(x)をグラフに描いてみると、次のようになります。

 

 

青色の円で示しているのがf(x)の値がプラスになる地点、つまり配送可能地域です。

いい具合に判別できていることが分かります。

 

今後、新しいデータが追加されるごとにパラメータが自動更新されるようにすれば、精度はどんどん向上していくことになります。

このように非線形の難しい区分けでも、サポートベクターマシンは線形とほぼ同じ手間と手順で計算することができます。

そしてそれを可能にするのがカーネルトリックなのです。