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

倉庫の中の従業員が熱射病になり易い条件を調べるために、次のようなデータを採りました。

 

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

 

この点線は管理人が勘で引いた境目ですが、サポートベクターマシンではどんな直線を出すのか試してみましょう。

ちなみにこの例は、単純パーセプトロンのアルゴリズムを試した時に使ったものと同じです。

>> 【スーパーわかりやすく!】Excelで単純パーセプトロンの具体例を試してみる

 

数値計算し易い双対問題に変換する

前回の記事で、サポートベクターマシンのアルゴリズムは次のような「制約条件付きの最小化問題」に帰着できることを解説しました。

 

制約条件gi (w0, w1, w2)=ti (w1x+w2y+w0)-1≧0の下で、関数f(w1, w2)=w12+w22の最小値を求めたい場合、まず

L(w0, w1, w2,λ) = f(w1, w2) – λi gi (w0, w1, w2)

というw0、w1、w2、λiの関数Lを作り、

∂L/∂ w0 = 0

∂L/∂ w1 = 0

∂L/∂ w2 = 0

∂L/λi = 0

の偏微分方程式を解けば、f(w1, w2)を最小にするw1とw2が求まる。

更にグループ1の際の点の座標を

w1x+w2y+w0=1

に代入することにより、w0も求まる。

>> サポートベクターマシンの原理からラグランジュの未定乗数法適用までをわかりやすく

 

ここで更に一工夫加えます。

f(w1, w2)=w12+w22は二次関数ですので、L/∂ w1 = 0L/∂ w2 = 0を計算するにはf(w1, w2)=1/2(w12+w22)としておいた方が便利です。

こうすることによって微分をするとf/∂w1=w1とか、f/∂w2=w2というように簡単になるからです。

f(w1, w2)=w12+w22を最小化するのも、f(w1, w2)=1/2(w12+w22)を最小化するのも結果は同じですので、以降はf(w1, w2)=1/2(w12+w22)とします。

 

これから先のラグランジュの未定乗数法の式を更に簡単にしていきます。

最初の3つの偏微分方程式を解くと、次のようになります。

∂L/∂ w0 = λ1t1+λ2t2+ ・・・ +λntn=0

∂L/∂ w1 = w1λ1t1x1λ2t2x2・・・ –λntnxn=0

∂L/∂ w2 = w2λ1t1y1λ2t2y2・・・ –λntnyn=0

 

これらを最初の式

L(w0, w1, w2,λ) = f(w1, w2) – λi gi (w0, w1, w2)

に代入して式変形すると、

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

w0とw1とw2が消えて、変数λiだけの式になります。

この式は1/2(w12+w22)の最小値を求める式ですので、

L≦1/2(w12+w22)

の関係にあります。

ここで、もしλiを動かしてLの最大値を求めることができれば、そのLの値が1/2(w12+w22)の最小値になります。

つまり、1/2(w12+w22)最小値を求める問題が、

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

最大値を求める問題に変換されました。

(この式にはL/∂ w0 = λ1t1+λ2t2+ ・・・ +λntn=0の条件が入っていないので、これが制約条件として付きます)

このように元の問題と同等の関係にある問題のことを双対問題といいます。

双対問題の方が解きやすい場合があり、そのような時には双対問題に変換して解きます。

 

これでサポートベクターマシンの問題が、コンピュータで数値計算し易い双対問題に変換できました。

 

Excelで解いてみる

長い道のりでしたが、サポートベクターマシンのアルゴリズムは以下の問題まで簡略化されました。

 

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

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

最大値を求める。

 

nは今あるデータサンプル数です。

教師データの数とも言えます。

Lの式は複雑そうに見えますが、よく見るときれいな規則性があります。

教師データから2つずつピックアップした組み合わせの掛け算です。

今回の場合は15個の教師データがありますので、λ、t、x、yのそれぞれについて152=225通りの組み合わせがあります。

大変な数ですが、Excelでやるとそうでもありません。

 

以下のようにすれば、すべての組み合わせの掛け算が計算できます。

 

 

 

 

 

ここまで入力すれば、目的関数制約条件の式を次のように入力できます。

 

この問題は、λ1からλ15を変えながら目的関数Lの最大値を求める最適化問題です。

このような計算はExcelのソルバーが得意とするところです。

下記のようにソルバーに設定します。

 

この段階でλ1からλ15には初期値として2が入力されています。

「Solve(解決)」を押すと、λ1からλ15は次のように最適化されます。

 

λ1とλ9とλ11だけゼロ以外の値になりました。

これは15個の教師データの中で、サポートベクターマシンが直線の式を決めるのに寄与したデータがこの3個だったということを意味しています。

これら3個のデータの中間を通るような直線の式を作ったということです。

 

従って、これら3点では

w1x+w2y+w0=1

または

w1x+w2y+w0=-1

の式が成り立ちます。

またw1とw2

∂L/∂ w1 = w1λ1t1x1λ2t2x2・・・ –λntnxn=0

∂L/∂ w2 = w2λ1t1y1λ2t2y2・・・ –λntnyn=0

の式から求められますので、w1とw2とw0は次のように求まります。

 

これで2つのグループを分ける直線の式が求まりました。

0.84x + 0.18y – 33.74 = 0

です。

グラフに描くとこのようになります。

 

確かに2つのグループをきれに分ける直線を求めることができました。

このように、サポートベクターマシンのアルゴリズムをExcelに実装することは難しくありません。

しかし、このアルゴリズムを導くためにラグランジュの未定乗数法双対問題を使っていて、理解するのに結構骨が折れます。

 

>> ラグランジュの未定乗数法は関数を立体的に解釈すれば意味を理解できる

>> サポートベクターマシンの原理からラグランジュの未定乗数法適用までをわかりやすく

を含め、3回に渡りサポートベクターマシンの原理について勉強してきましたが、

原理が分からずにアルゴリズムを使うのは気持ち悪い

という管理人のような人に、少しでも理解の足しになれば嬉しいです。