【カーネルトリック】非線形のサポートベクターマシンをExcelに実装してみた。Excel【カーネルトリック】非線形のサポートベクターマシンをExcelに実装してみた。判別できているか確認する◆仕事や勉強の息抜きに。カーネルトリックで非線形のサポートベクターマシンが解ける!宅配便会社Aでは、ある配送センターから1時間以内で配送できる範囲を調べるために、15か所の配送先でテストしました。最初の配送先は東に16km、南に21.1km配送センターから離れていて1時間以内に配達不可、最後の配送先は東に13km、南に2.3km配送センターから離れていて1時間以内に配達できたことを示しています。グラフにすると次のようになります。ここで、新しい配送先が出てきた時の配送可否の判断をシステム化してみましょう。このように新しく得られるデータを、その特徴に従って2つのグループに分けるのはサポートベクターマシンの得意とするところです。今回は前回と違って直線できれいに切り分けることができません。下図に示すような曲線で切り分けるしかありません。このように直線で切り分けられない問題を「非線形問題」といいます。こんなトリッキーな切り分けができるのでしょうか?簡単にできるのです!カーネルトリックという名のトリックを使えば。このトリックは良くできたトリックですが、具体例で解説した記事が少ないようですので、皆が理解できるExcelでその種明かしをしていきます。非線形でも次元を増やせば直線で分けられる次元を増やすことはビニールを摘まみ上げることと同じまずは、話しを簡単にするために1次元で考えてみましょう。ある新薬について、摂取量による効き目を調べるテストをしたところ、次のようなデータが得られました。薬は過剰摂取でも過少摂取でもダメで、丁度良い量を飲んだ時だけ効き目があったというデータです。このままでは2グループに分けることはできませんね。そこで、次元をもう一つ上げて、2次元にしてみましょう。するのかというと、摂取量の二乗を計算して縦軸に加えるのです。するとほら、青の点線のように直線で分けられますね。このように次元を増やせば、直線で分けられるようになる可能性があります。この例では1次元だけ増やしましたが、更に多くの次元にまで増やすことにより、もっと複雑な問題でも直線で切り分けられるようになることが知られています。ここで配送センターの例に戻ります。この例では平面にプロットできたので、2次元のデータです。東西方向の距離で1次元、南北方向の距離でもう1次元です。これでは直線で分けれませんが、このシートを真ん中で摘まんで引っ張り上げれば、ほら、直線で分けられますね。次元を上げれば直線で分けられるとは、このようなイメージです。この引っ張り上げた状態で切り分ける直線を引けば、シートを元の状態に戻したら青色部分を囲むような曲線になることもイメージできると思います。直線で切り分けられる状態になるまで次元を上げて直線を引けば、元の次元に戻した時にはうまく切り分けるクネクネした曲線が出来上がってくるのです。二次元を三次元に上げる方法では、具体的にどのように次元を上げるのかを見ていきましょう。-21.1)というようにx1とy1を定義します。ある次元の増やし方は、こんな感じです。-477.4)これで、3次元まで増えたことになります。ここで、サポートベクターマシンのアルゴリズムをもう一度おさらいしてみましょう。λnλntntn(xnxn+ynyn))の最大値を求める。サポートベクターマシンを理解するためにExcelに実装して具体例を解いてみたLの中には(x1x1+y1y1)や(x1x2+y1y2)等の項が含まれていますね。このxiやyiは教師データです。-21.1)が1つ目の教師データです。今回はこれが15個ありますので、xiとyiの組が15個あります。これらすべての組み合わせについて(xixj+yiyj)を計算しますので、225個の項がLの中に現われます。√2xiyi)になると、Lの計算式は次のようになります。yi)を数字の組と見るのではなく、1つのベクトルxiとして見ます。(xi))のように表します。するとこれもベクトルになりますので、全体をΦ(xi)と表します。Φ(xn)))のように簡潔に表すことができます。今後は、この最後の式をLの式として使います。この式を使えば、線形にも非線形にも対応できるからです。xiとすれば良いだけです。Φ(xj)のように定義します。xj)はカーネル関数と呼ばれています。xj)はただの数字(スカラー)ということです。このようにわざわざ新しい関数を持ち出すのかというと、この後の計算でΦ(xi)が単独で出てくることはないためです。Φ(xj)のように必ずセットで出てきます。Φ(xj)はただの数字(スカラー)なので、後の計算も簡単になります。ここで思い出して下さい。Φ(xi)は低次元のベクトルを高次元のベクトルに変換する関数でしたね。√2x1y1)に変換する関数です。x1y1)と書くことができます。x2)を求めてみましょう。Φ(x2)の値は、変換する前のx1Tx2の値の2乗になりました。この事実は大変重要です。√2xiyi)の3次元データに変換したと見なして最適化計算ができるからです。別に非線形変換なんてしてなくてもいいんです。w0)を求めることができるのです。この直線は摘まんだ状態で引いた直線ですので、シートを元に戻すとクネクネ曲がった曲線になります。これこそが求める曲線になるのですが、ここでカーネル関数が効いてきます。w0が配送可否を判断する式になります。プラスなら配送可、マイナスなら配送不可の判断となります。x=(x,y)の二次関数になっています。非線形になっているのです。これがトリックと呼ばれる所以です。カーネルトリックをExcelに実装するカーネル関数の箇所を変更するだけ前回は線形のサポートベクターマシンでしたが、教師データは同じく15個でしたので、同じExcelシートを使いまわします。Φ(xn)))の式の中の青字の部分だけです。λnλntntn(xnTxn))でしたので、xiTxjを(xiTxj)2に変更するだけです。(xiTxj)2だからです。計算する箇所だけを下記のように変えます。後は、前回と同じようにLを目的関数、λ1からλ15を操作変数としてソルバーを実行します。すると、次のようにλ1からλ15が最適化されます。クリックすると拡大しますパラメータから一次式の係数を求める次にw1とw2を求めますが、これは前回と同じ式で計算できます。yi)を次式に代入してw0を求めます。16.9)を上式に代入します。従って、次のように大変長ったらしい式で計算します。どんな値になるか確かめてみます。下図のように、f(x)がプラスかマイナスかにより、配達可能か不可かを正確に判断できるようになりました。f(x)をグラフに描いてみると、次のようになります。青色の円で示しているのがf(x)の値がプラスになる地点、つまり配送可能地域です。いい具合に判別できていることが分かります。今後、新しいデータが追加されるごとにパラメータが自動更新されるようにすれば、精度はどんどん向上していくことになります。このように非線形の難しい区分けでも、サポートベクターマシンは線形とほぼ同じ手間と手順で計算することができます。それを可能にするのがカーネルトリックなのです。ロジギークよろしければシェアお願いしますTwitterFacebookLinkedInB!HatenaLINELINEガウスカーネルを使ったサポートベクターマシンで配送可能エリアを区分けするNextサポートベクターマシンをExcelに実装して2クラス分類問題を解いてみた。棄却サンプリング法とは?アルゴリズムをExcelに実装して試してみた。...【強化学習】モンテカルロ法をExcelに実装して迷路問題を解いてみた。...重点サンプリングによるモンテカルロ積分をExcelで試して効果を見てみた。...◆キーワードで探すイチローの安打数がポアソン分布にならず正規分布になる理由を考察してみた【マルコフ連鎖】標準体重の人が太りすぎになるまで平均何年かかる?待ち行列理論を応用して10分カットが儲かる仕組みを解明してみた。計算グラフモンテカルロ積分クラスタリングカーネルトリックPythonSimPy(離散事象シミュレーション)inventorize(在庫シミュレーション)SARIMAX(時系列解析)investpy(財務データ取得)PyPDF2(PDF操作)仕事や勉強の合間の息抜きに管理人ロジギークロジスティクス業界で6か国に勤務。