サポートベクターマシンにラグランジュの未定乗数法を適用して制約条件付き最小化問題を解く
サポートベクターマシンは合理的な区分けを自動でしてくれる
サポートベクターマシン（Support Vector Machines：SVM）は、得られたデータをその特徴に従って２つのグループに分ける手法です。
例えば、管理人が雪見だいふくに特化したアイスクリーム屋を営んでいるとしましょう。
暑い日にはよく売れるため、気温を読み間違うと品切れを起こしてしまいます。
ですので、その日の気温と在庫数の２つの変数により、品切れになるかならないかを大体予測できます。
グラフに描いてみましょう。
この時点では２つのグループを分ける直線は①～③のようにいろいろあります。
これくらいのことなら、わざわざサポートベクターマシンのような難しい技を使わなくても勘でできますね。
ところが明日になって下記のようなデータが一つ増えると、どうでしょうか？
直線の候補はだいぶ絞り込まれます。
サポートベクターマシンは機械学習の中の１手法です。
機械学習ということは、わざわざ人間が張り付いていなくても、新しいデータが取れたら自動的に最もふさわしい直線に更新してくれます。
しかも、一番きれいに分ける直線を出してくれます。
きれいに分けるとは、下図のように、それぞれのグループの中の一番際（キワ）のデータの中間を通すような直線で分けることです。
このような直線を人間が勘で決めることは難しいですね。
サポートベクターマシンは、このように一番合理的に分ける直線を計算し、それをリアルタイムに自動更新できる点が魅力です。
ちなみに名前に「マシン」と付いていますが機械ではなく、ただのアルゴリズムです。
サポートベクターマシンは制約条件付き最小化問題に帰着する
それでは、どのような原理なのかを見ていきましょう。
簡単な例として、次のような4つの点を「１」と「－１」の2つのグループに分ける直線を計算します。
グラフにプロットすると、次のようになります。
サポートベクターマシンでは、2つのグループを分ける丁度中間に線を引きますが、これくらいの少ないデータなら、勘でも次のようにグループ分けする線を引くことができます。
黒色線が２つのグループを分ける中間線、赤色線はグループ-1の中の際の点を通る直線、青色線はグループ1の中の際の点を通る直線です。
グループ-1では2つの点が共に際（キワ）の点になっています。
そして、これら3本の直線の式を次のように定義します。
すると、赤色の2つの点では、
w1x+w2y+w0=-1
の式が成り立ちます。
また、青色の直線に乗っている青色の点では、
w1x+w2y+w0=1
の式が成り立ちます。
では、もう1つの青色の点ではどんな式が成り立つでしょうか？
青色の線よりも上にあるので、
w1x+w2y+w0≧1
の式が成り立ちますね。
つまり、各点の座標を
f(x,y) = w1x+w2y+w0
の式に代入してf(x,y)の値が1以上になればグループ1、-1以下になればグループ-1に分類できます。
このように大変便利な式になります。
次に教師データもこの式に加えます。
この場合の教師データとは、グループ1では「１」、グループ-1では「－１」です。
n個ある点の（今回の場合は４個）、それぞれの点の教師データをtnとすると、すべての点の座標は次の式を満たします。
tn (w1x+w2y+w0)≧1
（グループ-1の点ではw1x+w2y+w0の値が-1以下になり、tnは-1なので、掛けるとプラス1以上になる）
この式は重要で、また後で登場します。
次にそれぞれのグループの際の点から中間線への距離を計算します。
これは便利な公式が知られていて、点(x0,y0)から直線ax+by+c=0への距離は、
|ax0+by0+c|/√(a2+b2)
で計算できます。
この公式を使うと、際（キワ）の点から中間線への距離は次のように簡潔に表せます。
ここでサポートベクターマシンが中間線を決めるための基準を思い出しましょう。
それぞれのグループの中で際（キワ）の点からの距離が等しくなるように中間線を決めるのでした。
ということは、それぞれの際の点（普通は２点だが、この例のように３点以上の場合もある）から中間線への距離を目いっぱいに大きくするということです。
つまり、点から中間線への距離
1/√(w12+w22)
を最大化したいのです。
更に、平方根と分数が入っていて面倒臭いので、二乗して分母と分子をひっくり返しましょう。
すると、
w12+w22
を最小化する問題になります。
これでサポートベクターマシンのアルゴリズムがわかりました。
サポートベクターマシンは、
tn (w1x+w2y+w0)≧1
という制約条件の下で、
w12+w22
を最小化するようなw0、w1、w2を求めているのです。
制約条件付き最小化問題にラグランジュの未定乗数法を適用する
後は、この最小化問題をどのように解くかです。
一般に何の制約条件もなければ、偏微分を使って解くのが定石です。
しかし、制約条件がありますので、前回の記事で紹介したラグランジュの未定乗数法を使います。
>> ラグランジュの未定乗数法は関数を立体的に解釈すれば意味を理解できる
ラグランジュの未定乗数法とは、制約条件g(x,y)の下で、関数f(x,y)の最小値を求めたい場合、まず
L(x,y,λ) = f(x,y) – λg(x,y)
というx、y、λの関数Lを作り、
∂L/∂x = 0
∂L/∂y = 0
∂L/∂λ = 0
の3つの偏微分方程式を解けば、f(x,y)を最小にするxとyが求まるというものでした。
今回のサポートベクターマシンではw0、w1、w2を求めたいので、x､ｙではなくw0、w1、w2がパラメータになります。
また制約条件式はデータの数だけありますので、gi (w0, w1, w2)としてiは1～nとします。
するとλもn個あることになるので、λiとしてiは1～nとします。
従って、次のように言い換えることができます。
制約条件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も求まる。
次回はサポートベクターマシンのアルゴリズムをExcelに実装してみます。