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

2021年10月14日2024年5月18日

カーネルトリックで非線形のサポートベクターマシンが解ける！

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

下記がその結果です。

 

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

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

 

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

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

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

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

 

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

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

 

簡単にできるのです！

 

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

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

 

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

次元を増やすことはビニールを摘まみ上げることと同じ

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

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

 

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

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

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

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

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

 

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

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

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

 

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

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

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

 

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

 

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

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

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

 

二次元を三次元に上げる方法

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

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

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

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

(x₁², y₁², √2x₁y₁)=(256, 445.2, -477.4)

 

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

 

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

 

λ₁t₁+λ₂t₂+ ･･･ +λ_nt_n=0の条件下で、

L = (λ₁+λ₂+ ･･･ +λ_n ) – ½ (λ₁λ₁t₁t₁(x₁x₁+y₁y₁) + λ₁λ₂t₁t₂(x₁x₂+y₁y₂) + ･･･ + λ_nλ_nt_nt_n(x_nx_n+y_ny_n))

の最大値を求める。

 

でした。

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

 

Lの中には(x₁x₁+y₁y₁)や(x₁x₂+y₁y₂)等の項が含まれていますね。

このx_iやy_iは教師データです。

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

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

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

 

元のデータが(x_i, y_i)でこの計算式ですので、３次元のデータ(x_i², y_i², √2x_iy_i)になると、Lの計算式は次のようになります。

L = (λ₁+λ₂+ ･･･ +λ_n ) – ½ (λ₁λ₁t₁t₁(x₁²x₁²+y₁²y₁²+2x₁y₁x₁y₁)  + λ₁λ₂t₁t₂(x₁²x₂²+y₁²y₂²+2x₁y₁x₂y₂)  + ･･･ + λ_nλ_nt_nt_n(x_n²x_n²+y_n²y_n²+2x_ny_nx_ny_n))

 

ベクトルで式を表現すると簡単になる

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

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

 

そして(x_i², y_i², √2x_iy_i)は(Φ₁(x_i), Φ₂ (x_i), Φ₃ (x_i))のように表します。

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

このようにすると、

L = (λ₁+λ₂+ ･･･ +λ_n ) – ½ (λ₁λ₁t₁t₁(x₁x₁+y₁y₁) + λ₁λ₂t₁t₂(x₁x₂+y₁y₂) + ･･･ + λ_nλ_nt_nt_n(x_nx_n+y_ny_n))

は

L = (λ₁+λ₂+ ･･･ +λ_n ) – ½ (λ₁λ₁t₁t₁(x₁^Tx₁) + λ₁λ₂t₁t₂(x₁^Tx₂) + ･･･ + λ_nλ_nt_nt_n(x_n^Tx_n))

に

L = (λ₁+λ₂+ ･･･ +λ_n ) – ½ (λ₁λ₁t₁t₁(x₁²x₁²+y₁²y₁²+2x₁y₁x₁y₁)  + λ₁λ₂t₁t₂(x₁²x₂²+y₁²y₂²+2x₁y₁x₂y₂)  + ･･･ + λ_nλ_nt_nt_n(x_n²x_n²+y_n²y_n²+2x_ny_nx_ny_n))

は

L = (λ₁+λ₂+ ･･･ +λ_n ) – ½ (λ₁λ₁t₁t₁(Φ(x₁)^T Φ(x₁)) + λ₁λ₂t₁t₂(Φ(x₁)^T Φ(x₂)) + ･･･ + λ_nλ_nt_nt_n(Φ(x_n)^T Φ(x_n)))

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

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

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

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

 

カーネル関数とは？

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

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

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

 

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

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

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

 

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

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

例えば、２次元の(x₁, y₁)を３次元の(x₁², y₁², √2x₁y₁)に変換する関数です。

ですので

Φ(x₁) = Φ(x₁, y₁) = (x₁², y₁²,√2 x₁y₁)

と書くことができます。

もう一つ

Φ(x₂) = Φ(x₂, y₂) = (x₂², y₂², √2x₂y₂)

がある時、K(x₁, x₂)を求めてみましょう。

 

カーネル関数を使うと更に式が簡単になる

K(x₁, x₂) = Φ(x₁)^T Φ(x₂)

= Φ(x₁, y₁) Φ(x₂, y₂)

= (x₁², y₁², √2x₁y₁)^T(x₂², y₂², √2x₂y₂)

= x₁² x₂² + y₁² y₂² + 2x₁y₁ x₂y₂

= (x₁ x₂ + y₁ y₂)²

= ((x₁ , y₁)^T(x₂ , y₂))²

= (x₁^Tx₂)²

 

なんと３次元に変換した後のΦ(x₁)^T Φ(x₂)の値は、変換する前のx₁^Tx₂の値の２乗になりました。

 

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

 

L = (λ₁+λ₂+ ･･･ +λ_n ) – ½ (λ₁λ₁t₁t₁(Φ(x₁)^T Φ(x₁)) + λ₁λ₂t₁t₂(Φ(x₁)^T Φ(x₂)) + ･･･ + λ_nλ_nt_nt_n(Φ(x_n)^T Φ(x_n)))

の式で

Φ(x₁)^T Φ(x₂) = (x₁^Tx₂)²

としておけば、(x_i , y_i)の２次元データを (x_i², y_i², √2x_iy_i)の３次元データに変換したと見なして最適化計算ができるからです。

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

 

どういうことかというと、x₁^Tx₂を (x₁^Tx₂)²に置き換えるだけで、ビニルシートを指で摘まんだ状態で切り分ける直線のパラメータ（w₁, w₂, w₀）を求めることができるのです。

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

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

 

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

K(x₁, x₂) = Φ(x₁)^T Φ(x₂) = (x₁^Tx₂)²

です。

 

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

f(x) = Σλ_it_iK(x, x_i) + w₀

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

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

 

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

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

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

 

カーネルトリックをExcelに実装する

カーネル関数の箇所を変更するだけ

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

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

 

変更箇所は

L = (λ₁+λ₂+ ･･･ +λ_n ) – ½ (λ₁λ₁t₁t₁(Φ(x₁)^T Φ(x₁)) + λ₁λ₂t₁t₂(Φ(x₁)^T Φ(x₂)) + ･･･ + λ_nλ_nt_nt_n(Φ(x_n)^T Φ(x_n)))

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

前回は

L = (λ₁+λ₂+ ･･･ +λ_n ) – ½ (λ₁λ₁t₁t₁(x₁^Tx₁) + λ₁λ₂t₁t₂(x₁^Tx₂) + ･･･ + λ_nλ_nt_nt_n(x_n^Tx_n))

でしたので、x_i^Tx_jを(x_i^Tx_j)²に変更するだけです。

なぜなら、Φ(x_i)^T Φ(x_j) = (x_i^Tx_j)²だからです。

従って、λ_iλ_jt_it_j(x_i^Tx_j) を計算する箇所だけを下記のように変えます。

 

ソルバーで最適化計算

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

すると、次のようにλ₁からλ₁₅が最適化されます。

 

パラメータから一次式の係数を求める

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

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

-1 = Σλ_it_iK(x, x_i) + w₀

 

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

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

 

判別できているか確認する

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

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

 

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

 

 

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

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

 

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

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

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