読者です 読者をやめる 読者になる 読者になる

Pythonと機械学習

Pythonも機械学習も初心者ですが、頑張ってこのブログで勉強してこうと思います。

サポートベクターマシンを実際に試してみる

機械学習

2次計画法のスクリプトが出来たので、サポートベクターマシンに実装してみます。

サポートベクターマシンにおける最小化すべき目的関数は、

{\displaystyle
f(\mathbf{w})=\frac{1}{2}||\mathbf{w}||^2  \tag{1}
}

制約条件は、

{\displaystyle
g_i(\mathbf{w}) = y_i \mathbf{x}_i\mathbf{w}+w_0 \geqq \mathbf{1}  \tag{2}
}

になります。重み{\mathbf{w}}が設計変数になります。

これらを行列形式で表します。(トレーニングサンプル数は{m}、特徴量の個数は{n}とします。)

重み{\mathbf{w}}は、しきい値{w_0}も含め以下のようにベクトルで表します。

 {
\displaystyle
\begin{eqnarray}
\mathbf{w}=\left[
\begin{array}{c}
w_{0} \\
w_{1} \\
w_{2} \\
\vdots \\
w_{n}
\end{array}
\right]
\end{eqnarray}
\tag{3}
}

特徴行列{\mathbf{X}}は、しきい値を考慮し一番左の列に1を入れておきます。

 {
\displaystyle
\begin{eqnarray}
\mathbf{X}=\left[
\begin{array}{ccccc}
1 & x_{11} & x_{12} & \cdots & x_{1n} \\
1 & x_{21} & x_{22} & \cdots & x_{2n} \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
1 & x_{m1} & x_{m2} & \cdots & x_{mn}
\end{array}
\right]
\end{eqnarray}
\tag{4}
}

また、教師データが対角項に並んだ行列{\mathbf{Y}}を以下のように作ってやります。

 {
\displaystyle
\begin{eqnarray}
\mathbf{Y}=\left[
\begin{array}{ccccc}
y_{1} & 0 & \cdots & 0 \\
0 & y_{2} & \cdots & 0 \\
\vdots & \vdots  & \ddots & \vdots \\
0 & 0 & \cdots & y_{m}
\end{array}
\right]
\end{eqnarray}
\tag{5}
}

これら(3)〜(5)式を使って目的関数と制約条件を行列表記すると、

{\displaystyle
f(\mathbf{w})=\frac{1}{2} \mathbf{w}^{T} \mathbf{E}^{\prime} \mathbf{w} \tag{6}
}

{\displaystyle
\mathbf{g}(\mathbf{w}) = - \mathbf{Y} \mathbf{X}\mathbf{w} + 1 \leq 0  \tag{7}
}

になります。

(6)式の{\mathbf{E}^{\prime}}単位行列と置きたいところですが、設計変数である重み行列{\mathbf{w}}しきい値{w_0}を含んでいます。目的関数であるマージンにはしきい値項は含まれないので少し工夫する必要があります。

 {
\displaystyle
\begin{eqnarray}
\mathbf{E}'=\left[
\begin{array}{ccccc}
\epsilon & 0 & \cdots & 0 \\
0 & 1 & \cdots & 0 \\
\vdots & \vdots  & \ddots & \vdots \\
0 & 0 & \cdots & 1
\end{array}
\right]
\end{eqnarray}
\tag{8}
}

(8)式の{\epsilon}は、(6)式において丁度しきい値{w_0}にかかる係数になります。しきい値項はマージンに含めないので{\epsilon=0}としたいですが、2次計画法で{\mathbf{E}^{\prime}}逆行列を求める必要があるため、{\epsilon=0}と置いてしまうと逆行列が計算できなくなってしまいます。

実際コード上で計算するときは、{\epsilon=10^{-10}}のようにものすごく小さな値を入れてやり、形式的に{\mathbf{E}^{\prime}}逆行列を計算できるようにしておきます。

(6)、(7)式を2次計画法の{\mathbf{Q},\mathbf{c},\mathbf{A},\mathbf{b}}行列に当てはめていきましょう。

{\displaystyle
\mathbf{Q}=\mathbf{E}^{\prime}  \tag{9}
}

{\displaystyle
\mathbf{A}=\mathbf{-YX}  \tag{10}
}

{\mathbf{c}}は、{(n+1) \times 1}の0ベクトル、

 {
\displaystyle
\begin{eqnarray}
\mathbf{c}=\left[
\begin{array}{c}
0 \\
\vdots \\
0
\end{array}
\right]
\end{eqnarray}
\tag{11}
}

{\mathbf{b}}は、{m \times 1}の-1ベクトルです。

 {
\displaystyle
\begin{eqnarray}
\mathbf{b}=\left[
\begin{array}{c}
-1 \\
\vdots \\
-1
\end{array}
\right]
\end{eqnarray}
\tag{12}
}

以下が、2次計画法を実装したサポートベクターマシンスクリプトです。

確認のため、scikit-learnのサポートベクターマシンでも同じ学習を実施して、同じ結果になるかを試してみます。

main関数中で以下4つの結果を出力するようにしています。

  • オリジナルデータの学習結果(自作スクリプト版)
  • オリジナルデータの学習結果(scikit-learn版)
  • 1回目の結果のサポートベクトルをトレーニングサンプルから間引いた結果(自作スクリプト版)
  • 1回目の結果のサポートベクトルをトレーニングサンプルから間引いた結果(scikit-learn版)
オリジナルデータの学習結果(自作スクリプト版)

サポートベクトルを〇で囲むようにしました。決定境界は黒で線を引いています。

+1側のサポートラインは青で、-1側のサポートラインは赤で書いています。

f:id:darden:20160906211312p:plain:w600

以下マージンとサポートベクトルの出力です。

■オリジナルデータ
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版)

f:id:darden:20160906211932p:plain:w600

以下マージンとサポートベクトルの出力です。

■オリジナルデータ(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回目の結果のサポートベクトルをトレーニングサンプルから間引いた結果(自作スクリプト版)

f:id:darden:20160906212327p:plain:w600

マージンとサポートベクトルの出力

■サポートベクターを間引いてみる
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版)

f:id:darden:20160906212645p:plain:w600

マージンとサポートベクトルの出力

■サポートベクターを間引いてみる(sikit-learnで実施)
・マージン: 0.701783160732
・サポートベクトル: [[5.1, 1.9], [5.0, 3.3]]

みごとに一致していますね。うれしいですね。