SVM（サポートベクターマシン）の解説＆構築に挑戦！ - 俺人〜OREGIN〜俺、バカだから人工知能に代わりに頑張ってもらうまでのお話

前回、次は「自然言語」と予告いたしましたが、これまでscikit-learnのライブラリを使っていたSVM（サポートベクターマシン）について、自分なりの理解で解説と、ライブラリを使わない実装に挑戦していきたいと思います！

scikit-learn を使ったSVMについては、以下の過去記事をご参照ください。

oregin-ai.hatenablog.com

今回のお品書きは以下の通りです。

SVM（サポートベクターマシン）の解説

SVM（サポートベクターマシン）の解説

1.SVM（サポートベクターマシン）とは何か。

SVM（サポートベクターマシン）とは、教師あり学習のモデルの一つです。

回帰にも、分類にも使うことができます。（今回は、分類で解説いたします。）

SVMの考え方は、２値分類の場合、以下の基準を満たす境界線（多次元の場合は境界となる超平面）を表す重みwと閾値ｂを見つけるということになります。

クラスAに所属するすべてのXAは、境界線より上（w.T*XA - b > 0）となり、クラスBに所属するすべてのXBは、境界線より下（w*XB - b < 0）となる。
境界線　w.T*X - b = 0 から直近のデータの距離（マージン）が最大になる。

図で表すと以下の通りとなります。

f:id:kanriyou_h004:20200531094535p:plain — 図1.SVM（サポートベクターマシン）概要図

この境界線を使って、新たなデータについて、境界線より上（w*X-b>0）の場合はクラスA、境界線より下（w*X-b<0）の場合は、クラスBと分類できるようになります。

2.分類するデータを作成する。

まずは、SVMで分類するためのデータを作成します。

今回は、２つの特徴量をもつ、３０個のランダムデータを作成します。

また、正解データとしては、特徴量１より特徴量２が大きければ「1」、小さければ「-1」としました。

import numpy
numpy.random.seed(614)
N = 30 # データの個数
d = 2 # 特徴量の数（次元数）
# 30個x2次元の訓練データを作成する
X = numpy.random.randn(N, d)
# 30個の正解データを作成する
#（特徴量１より特徴量２が大きい場合 1,小さい場合 -1）
T = numpy.array([1 if feature1 < feature2 else - 1 for feature1, feature2 in X])

作成したデータをプロットすると以下の通りです。

from matplotlib import pyplot

pyplot.figure(figsize = (6, 6))
pyplot.xlim(-3, 3)
pyplot.ylim(-3, 3)
pyplot.plot(X[T == 1,0], X[T == 1,1], 'ro')
pyplot.plot(X[T == -1,0], X[T == -1,1], 'bo')

f:id:kanriyou_h004:20200531190526p:plain — 図2.分類するデータ

3.クラスA、クラスBについて考えてみる。

SVMの考え方の１点目の、クラスA、クラスBに関する基準につき、もう少し掘り下げて考えてみます。

各クラスのラベルデータ（正解データ）は以下の通りです。

f:id:kanriyou_h004:20200531121349p:plain — 式1.ラベルデータ（正解データ）

また、クラスAのデータが境界線より上、クラスBが境界線より下となるので、重みwと閾値bは以下の条件を満たす必要があります。

f:id:kanriyou_h004:20200531122409p:plain — 式2.境界線の制約条件

クラスAのときは式１、式２ともに正、クラスBのときは式１、式２ともに負なので、SVMが満たすべき基準の１つ目は、以下を満たすことであると定義できます。

f:id:kanriyou_h004:20200531122647p:plain — 式3.SVMで満たすべき基準１

3.マージンの最大化について考えてみる。

次に、SVMの二つ目の基準について考えてみます。

ある点ｘ[i]から直線（w*x-b）までの距離ｄは、以下の式で表されます。（この式の導入については省略します。）

f:id:kanriyou_h004:20200531123013p:plain — 式4.ある点X[i]から境界線への距離

ここで、分子に着目してみると、前述の式３のカッコ内の絶対値となっています。

式３では、T[i]を掛けることで常に正の数に変換していて、絶対値をとることと同義になっています。

よって、式４は以下に変換することができます。

f:id:kanriyou_h004:20200531123845p:plain — 式5．ある点X[i]から境界線への距離（式３を適用）

マージンMは、境界線から最も近いX[i]になるので、すべてのX[i]からの距離（式5のd）は、必ずM以上となり、以下の式が成り立ちます。

f:id:kanriyou_h004:20200531124740p:plain — 式6.すべてのX[i]までの距離は、マージンMより大きい

これで、Mの上限を抑え込むことができました。

マージンMは、分子が最小になるときの値となるので、①Mが最大となるのは、分母の||w||が最小値をとるときになります。

||w||は正の値なので、||w||が最小値となるときは、➁||w||の二乗も最小値となります。二乗にすることで、凸型の関数に変換できます。

f:id:kanriyou_h004:20200531151434p:plain — 図3.最小値を見つけやすく変形

①、➁より、Mを最大にするということは、以下の通り||w||の２乗を最小とすることと等価となります。（定数をかけても最小となるwは変わらないので、今後の処理で必要となる微分を考慮して、2分の１をかけています。）

f:id:kanriyou_h004:20200531152346p:plain — 式7.Mの最大値を求めることは||w||の２乗の最小値を求めることと等価

式6の両辺をMで割ると以下の式になります。

f:id:kanriyou_h004:20200531141854p:plain — 式8.両辺をマージンで割る

単純化するために、w,bを、それぞれ以下で置き換えます。

f:id:kanriyou_h004:20200531142055p:plain — 式9.w,bの置き換え

置き換えた結果が以下の式です。

これが、Mを最大にするw,bの制約条件になります。

f:id:kanriyou_h004:20200531141801p:plain — 式10.Mを最大にするw,bの制約条件

4.解く問題の再整理

以上より再整理すると、以下の通りの問題を解くことに帰着しました。

【問題】以下の関数を最小化するwを求める。

f:id:kanriyou_h004:20200531154746p:plain — 式11.問題式

【条件】以下を制約条件とする。

f:id:kanriyou_h004:20200531154940p:plain — 式12.制約条件式

5.ラグランジュ未定乗数法について

4項で整理した問題を解くために、ラグランジュ未定定数法を使います。

今回は詳しく説明しませんが、4項で整理した問題のように、制約条件付きで最小値・最大値などの極値を求める問題を、単純な極値を求める問題に変換する方法になります。

具体的には、極値を求めたい目的関数f(x)を最小にする点をn個の不等式制約g(x)≧０のもとで、以下の通り求める。

f:id:kanriyou_h004:20200531162239p:plain — 式13.ラグランジュの未定乗数方

この時、以下を解くことで、最小値、最大値になる主変数を求めることができます。

f:id:kanriyou_h004:20200531170945p:plain — 式14.ラグランジュ未定乗数法で解く４つの式

6.ラグランジュ未定乗数法を適用する。

では、4項で整理した問題に、5項で確認したラグランジュ未定乗数法を適用します。

f:id:kanriyou_h004:20200531170033p:plain — 式15.ラグランジュ未定乗数法を適用

同様に主変数を求める式14の４つの式に当てはめます。

f:id:kanriyou_h004:20200531172144p:plain — 式16.主変数を求める式に当てはめる

式15を展開して、式16の①w,①bを代入します。

f:id:kanriyou_h004:20200531203455p:plain — 式17.最大化する関数

これにより、ラグランジュ未定乗数αと訓練データX[i]とラベルデータT[i]の線形和で、制約条件付きの最小値を求める問題から、L（α）を最大化するαiを求める単純な問題に落とし込むことができました。

7.解を求める。

なかなかに、ハードな内容でしたが、やっとこれでw,bの解を求める準備が整いました。

L（α）の最大となるαを求めるために、最急降下法を使います。

最急降下法は、その時点でのαiで偏微分した際の微分値によってL（α）が最小値に向かう方向にαiを更新していく手法です。

以下のように更新していきます。

f:id:kanriyou_h004:20200531192358p:plain — 式18.最急降下法でαを更新

式17をαiで偏微分した式を代入すると以下の通りとなります。

f:id:kanriyou_h004:20200531203721p:plain — 式19.αiの更新式

この式をpythonで実装すると以下の通りになります。

alpha = numpy.zeros(N) #αの初期値
eta_al = 0.0001 # αの更新率（η）
itr = 1000 #学習回数

# 学習回数分繰り返す
for _itr in range(itr):
# αiについてi=1からN（データ数３０個）まで繰り返す
for i in range(N):
# 式23のカッコ内の計算を実施
delta = 1 - (T[i] * X[i]).dot(alpha * T * X.T).sum()
# 式23のαi-nextの計算を実施　
alpha[i] += eta_al * delta

また、 f:id:kanriyou_h004:20200531184100p:plain をL（α）を最大化するα、Ts、Xsをそれぞれ、マージンMが最小となるラベルデータ、訓練データとすると、求めるw,bは式16の①wの変形、および式16の④から以下の通りで求められます。

f:id:kanriyou_h004:20200531183831p:plain — 式20.w,bを求める式

この式をpythonで実装すると以下の通りとなります。

#αiが正かどうかをindexに格納
index = alpha > 0
#式20からw,bを求める
w = (alpha * T).T.dot(X)
b = (T[index] - X[index].dot(w)).mean()

8.全体像

これまでの内容をpythonで実装すると以下のコードになります。

import numpy
from matplotlib import pyplot
numpy.random.seed(614)
N = 30 # データの個数
d = 2 # 特徴量の数（次元数）
# 30個x2次元の訓練データを作成する
X = numpy.random.randn(N, d)
# 30個の正解データを作成する
#（特徴量１より特徴量２が大きい場合 1,小さい場合 -1）
T = numpy.array([1 if feature1 < feature2 else - 1 for feature1, feature2 in X])

alpha = numpy.zeros(N) #αの初期値
eta_al = 0.0001 # αの更新率（η）
itr = 1000 #学習回数

# 学習回数分繰り返す
for _itr in range(itr):
# αiについてi=1からN（データ数３０個）まで繰り返す
for i in range(N):
# 式23のカッコ内の計算を実施
delta = 1 - (T[i] * X[i]).dot(alpha * T * X.T).sum()
# 式23のαi-nextの計算を実施　
alpha[i] += eta_al * delta

#αiが正かどうかをindexに格納
index = alpha > 0
#式20からw,bを求める
w = (alpha * T).T.dot(X)
b = (T[index] - X[index].dot(w)).mean()

#縦横6x6サイズに-3～3の範囲でグラフを描画
pyplot.figure(figsize = (6, 6))
pyplot.xlim(-3, 3)
pyplot.ylim(-3, 3)
#線を描画するためのサンプリング間隔を作成
seq = numpy.arange(-3, 3, 0.02)
#正解データの境界線を黄色の破線で表示
pyplot.plot(seq,seq,'y--')
#SVMで学習した境界線を黒の実線で表示
pyplot.plot(seq, -(w[0] * seq + b) / w[1], 'k-')
#正解ラベルが１のデータを赤点でプロット
pyplot.plot(X[T == 1,0], X[T == 1,1], 'ro')
#正解ラベルが-1のデータを青点でプロット
pyplot.plot(X[T == -1,0], X[T == -1,1], 'bo')
pyplot.show()