サポートベクターマシンを実際に試してみる
2次計画法のスクリプトが出来たので、サポートベクターマシンに実装してみます。
サポートベクターマシンにおける最小化すべき目的関数は、
制約条件は、
になります。重みが設計変数になります。
これらを行列形式で表します。(トレーニングサンプル数は、特徴量の個数はとします。)
重みは、しきい値も含め以下のようにベクトルで表します。
特徴行列は、しきい値を考慮し一番左の列に1を入れておきます。
また、教師データが対角項に並んだ行列を以下のように作ってやります。
これら(3)〜(5)式を使って目的関数と制約条件を行列表記すると、
になります。
(6)式のは単位行列と置きたいところですが、設計変数である重み行列がしきい値を含んでいます。目的関数であるマージンにはしきい値項は含まれないので少し工夫する必要があります。
(8)式のは、(6)式において丁度しきい値にかかる係数になります。しきい値項はマージンに含めないのでとしたいですが、2次計画法での逆行列を求める必要があるため、と置いてしまうと逆行列が計算できなくなってしまいます。
実際コード上で計算するときは、のようにものすごく小さな値を入れてやり、形式的にの逆行列を計算できるようにしておきます。
(6)、(7)式を2次計画法の行列に当てはめていきましょう。
は、の0ベクトル、
は、の-1ベクトルです。
以下が、2次計画法を実装したサポートベクターマシンのスクリプトです。
確認のため、scikit-learnのサポートベクターマシンでも同じ学習を実施して、同じ結果になるかを試してみます。
main関数中で以下4つの結果を出力するようにしています。
- オリジナルデータの学習結果(自作スクリプト版)
- オリジナルデータの学習結果(scikit-learn版)
- 1回目の結果のサポートベクトルをトレーニングサンプルから間引いた結果(自作スクリプト版)
- 1回目の結果のサポートベクトルをトレーニングサンプルから間引いた結果(scikit-learn版)
オリジナルデータの学習結果(自作スクリプト版)
サポートベクトルを〇で囲むようにしました。決定境界は黒で線を引いています。
+1側のサポートラインは青で、-1側のサポートラインは赤で書いています。
以下マージンとサポートベクトルの出力です。
■オリジナルデータ 4回目のイタレーションで最適解が見つかりました。 ・最適解w: [-4.45454545454541, -1.0576653637396341e-14, 1.8181818181818208] ・目的関数f(w)=1/2|w|^2の最小値: 1.65289256298 ・KKT条件1(∇f+λ∇g=0): True [1.3489388351862165e-15, -3.594543613827458e-15, 4.6629367034256575e-15] ・KKT条件2(g<=0): True [-0.909090909090915, ..., -1.9999999999999947] ・KKT条件3(λ>=0): True [0.0, ..., 0.0] ・KKT条件4(λg=0): True [0.0, ..., 0.0] ・マージン: 0.549999999835 ・サポートベクトル: [[5.1, 3.0], [4.8, 1.9], [5.1, 1.9]]
オリジナルデータの学習結果(scikit-learn版)
以下マージンとサポートベクトルの出力です。
■オリジナルデータ(sikit-learnで実施) ・マージン: 0.550096906883 ・サポートベクトル: [[4.8, 1.9], [5.1, 1.9], [5.1, 3.0]]
マージンもサポートベクトルも自作スクリプトの結果と一致しました。
ちなみにscikit-learnのSVMインスタンスでは、clf.support_vectors_
でサポートベクトル、clf.intercept_
でしきい値、clf.coef_
で重みベクトルが取得できます。
1回目の結果のサポートベクトルをトレーニングサンプルから間引いた結果(自作スクリプト版)
マージンとサポートベクトルの出力
■サポートベクターを間引いてみる 3回目のイタレーションで最適解が見つかりました。 ・最適解w: [-3.1827411080708097, -0.10152284429752614, 1.421319796835891] ・目的関数f(w)=1/2|w|^2の最小値: 1.0152284269 ・KKT条件1(∇f+λ∇g=0): True [-2.5908884946087534e-16, 8.326672684688674e-17, -4.440892098500626e-16] ・KKT条件2(g<=0): True [-0.7106598984179453, ..., -1.065989846460444] ・KKT条件3(λ>=0): True [0.0, ..., 0.0] ・KKT条件4(λg=0): True [0.0, ..., 0.0] ・マージン: 0.701783442206 ・サポートベクトル: [[5.0, 3.3], [5.1, 1.9]]
1回目の結果のサポートベクトルをトレーニングサンプルから間引いた結果(scikit-learn版)
マージンとサポートベクトルの出力
■サポートベクターを間引いてみる(sikit-learnで実施) ・マージン: 0.701783160732 ・サポートベクトル: [[5.1, 1.9], [5.0, 3.3]]
みごとに一致していますね。うれしいですね。