【カーネルトリック】非線形のサポートベクターマシンをExcelに実装してみた。
カーネルトリックで非線形のサポートベクターマシンが解ける！
宅配便会社Aでは、ある配送センターから1時間以内で配送できる範囲を調べるために、15か所の配送先でテストしました。
下記がその結果です。
例えば、最初の配送先は東に16km、南に21.1km配送センターから離れていて1時間以内に配達不可、最後の配送先は東に13km、南に2.3km配送センターから離れていて1時間以内に配達できたことを示しています。
グラフにすると次のようになります。
ここで、新しい配送先が出てきた時の配送可否の判断をシステム化してみましょう。
このように新しく得られるデータを、その特徴に従って2つのグループに分けるのはサポートベクターマシンの得意とするところです。
しかし、今回は前回と違って直線できれいに切り分けることができません。
下図に示すような曲線で切り分けるしかありません。
このように直線で切り分けられない問題を「非線形問題」といいます。
こんなトリッキーな切り分けができるのでしょうか？
簡単にできるのです！
カーネルトリックという名のトリックを使えば。
このトリックは良くできたトリックですが、具体例で解説した記事が少ないようですので、皆が理解できるExcelでその種明かしをしていきます。
非線形でも次元を増やせば直線で分けられる
次元を増やすことはビニールを摘まみ上げることと同じ
まずは、話しを簡単にするために１次元で考えてみましょう。
ある新薬について、摂取量による効き目を調べるテストをしたところ、次のようなデータが得られました。
薬は過剰摂取でも過少摂取でもダメで、丁度良い量を飲んだ時だけ効き目があったというデータです。
でも、このままでは２グループに分けることはできませんね。
そこで、次元をもう一つ上げて、２次元にしてみましょう。
どうするのかというと、摂取量の二乗を計算して縦軸に加えるのです。
つまりこういうことです。
するとほら、青の点線のように直線で分けられますね。
このように次元を増やせば、直線で分けられるようになる可能性があります。
この例では１次元だけ増やしましたが、更に多くの次元にまで増やすことにより、もっと複雑な問題でも直線で切り分けられるようになることが知られています。
ここで配送センターの例に戻ります。
この例では平面にプロットできたので、２次元のデータです。
東西方向の距離で１次元、南北方向の距離でもう１次元です。
これでは直線で分けれませんが、このシートを真ん中で摘まんで引っ張り上げれば、ほら、直線で分けられますね。
次元を上げれば直線で分けられるとは、このようなイメージです。
更に、この引っ張り上げた状態で切り分ける直線を引けば、シートを元の状態に戻したら青色部分を囲むような曲線になることもイメージできると思います。
つまり、直線で切り分けられる状態になるまで次元を上げて直線を引けば、元の次元に戻した時にはうまく切り分けるクネクネした曲線が出来上がってくるのです。
二次元を三次元に上げる方法
では、具体的にどのように次元を上げるのかを見ていきましょう。
配送センターの例では、15個あるうちの1つ目のデータは(16, -21.1)です。
これを(x1, y1)=(16, -21.1)というようにx1とy1を定義します。
よくある次元の増やし方は、こんな感じです。
(x12, y12, √2x1y1)=(256, 445.2, -477.4)
これで、３次元まで増えたことになります。
ここで、サポートベクターマシンのアルゴリズムをもう一度おさらいしてみましょう。
λ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)でこの計算式ですので、３次元のデータ(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)を数字の組と見るのではなく、１つのベクトル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)は低次元のベクトルを高次元のベクトルに変換する関数でしたね。
例えば、２次元の(x1, y1)を３次元の(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
なんと３次元に変換した後のΦ(x1)T Φ(x2)の値は、変換する前のx1Tx2の値の２乗になりました。
この事実は大変重要です。
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)の２次元データを (xi2, yi2, √2xiyi)の３次元データに変換したと見なして最適化計算ができるからです。
別に非線形変換なんてしてなくてもいいんです。
どういうことかというと、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が最適化されます。
パラメータから一次式の係数を求める
次にw1とw2を求めますが、これは前回と同じ式で計算できます。
問題は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)の値がプラスになる地点、つまり配送可能地域です。
いい具合に判別できていることが分かります。
今後、新しいデータが追加されるごとにパラメータが自動更新されるようにすれば、精度はどんどん向上していくことになります。
このように非線形の難しい区分けでも、サポートベクターマシンは線形とほぼ同じ手間と手順で計算することができます。
そしてそれを可能にするのがカーネルトリックなのです。
Udemyの関連講座
データ分析シリーズ① AI数学-文系でも理解できる!高校から始めるデータ分析、AIのための数学-
データ分析、機械学習に関わる数学に絞り、効率的に学習できるようカリキュラムを構成しました。文系でも理解できるよう丁寧な説明をしています。Pythonエンジニア育成推進協会認定スクールによる高品質な数学コースです。
数学アレルギーでも大丈夫／やさしく丁寧な解説／コード無し キーワード:基礎／数学／行列／線形代数／ベクトル／微分／データサイエンス／AI／機械学習／ディープラーニング／データドリブン／人工知能
【キカガク流】人工知能・機械学習 脱ブラックボックス講座 – 初級編 –
1000人以上が受講している（株）キカガクの『脱ブラックボックスセミナー』が遂に登場！機械学習の参考書を「閉じてしまった人」への再入門に最適な講座です。微分・線形代数といった数学の基礎からPythonでの実装まで短時間で習得しましょう。