サポートベクターマシンをExcelに実装して２クラス分類問題を解いてみた。
サポートベクトルマシンで２クラス分類するような直線をExcelで計算する
倉庫の中の従業員が熱射病になり易い条件を調べるために、次のようなデータを採りました。
グラフにすると次のようになります。
この点線は２つのクラスに分類するために管理人が勘で引いた境目ですが、サポートベクターマシンではどんな直線を出すのか試してみましょう。
この計算を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 = 0や∂L/∂ 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)とします。
「最大化問題」の双対問題に変換する
これから先のラグランジュの未定乗数法の式を更に簡単にしていきます。
最初の３つの偏微分方程式を解くと、次のようになります。
∂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の式は複雑そうに見えますが、よく見るときれいな規則性があります。
教師データから２つずつピックアップした組み合わせの掛け算です。
今回の場合は15個の教師データがありますので、λ、t、x、yのそれぞれについて152＝225通りの組み合わせがあります。
大変な数ですが、Excelでやるとそうでもありません。
以下のようにすれば、すべての組み合わせの掛け算が計算できます。
目的関数と制約条件を計算する
ここまで入力すれば、目的関数と制約条件の式を次のように入力できます。
Excelソルバーで最適化する
この問題は、λ1からλ15を変えながら目的関数Lの最大値を求める最適化問題です。
このような計算はExcelのソルバーが得意とするところです。
下記のようにソルバーに設定します。
この段階でλ1からλ15には初期値として２が入力されています。
「Solve（解決）」を押すと、λ1からλ15は次のように最適化されます。
最適解を解釈して直線の式を求める
λ1とλ9とλ11だけゼロ以外の値になりました。
これは15個の教師データの中で、サポートベクターマシンが直線の式を決めるのに寄与したデータがこの３個だったということを意味しています。
これら３個のデータの中間を通るような直線の式を作ったということです。
従って、これら３点では
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は次のように求まります。
これで２クラスに分ける直線の式が求まりました。
0.84x + 0.18y – 33.74 = 0
です。
グラフに描くとこのようになります。
確かにきれいに２クラスに分類する直線を求めることができました。
このように、サポートベクターマシンのアルゴリズムをExcelに実装することは難しくありません。
しかし、このアルゴリズムを導くためにラグランジュの未定乗数法や双対問題を使っていて、理解するのに結構骨が折れます。
>> ラグランジュの未定乗数法は関数を立体的に解釈すれば意味を理解できる
>> サポートベクターマシンの原理からラグランジュの未定乗数法適用までをわかりやすく
を含め、３回に渡りサポートベクターマシンの原理について勉強してきましたが、
「原理が分からずにアルゴリズムを使うのは気持ち悪い」
という管理人のような人に、少しでも理解の足しになればと思います。