python機械学習プログラミング(サポートベクターマシン)



スポンサーリンク

 

Python機械学習プログラミング 達人データサイエンティストによる理論と実践 (impress top gear)」で勉強開始したので、3章のサポートベクターマシンについて書いてみます。

   

ついでに、本書2章のパーセプトロンとか、確率的勾配降下法については以前にまとめたので、今回は飛ばします。

 

 

サポートベクターマシンとは?

2クラス分類において高性能を叩き出す分類器を作成する。汎化能力を上げる方法としてマージン最大化が行われる。マージン最大化のために、二次計画法、特にラグランジュの未定乗数法カルーシュ・クーンタッカー条件(KKT条件)が用いられる。

 

非線形分類では、リプレゼンター定理を用いカーネル化を行い特徴空間に写像する。

 

サポートベクターマシンについて本気で根本から理解しようとするとこれらの専門用語を掘り下げないといけません。

 

しかし、scikit-learnのライブラリに用意されているので理論的背景を理解しなくてもSVMを用いて実装はできるわけです。

 

でもブラックボックス状態で使うのは嫌なので、どこまで理解できるかわかりませんが、このたび本気で理解してみることに。

 

ついでに本書によると以下のマイクロソフトの公式チュートリアル(論文?)がおすすめらしいです。英文なのでしんどいですが。

日本語では以下がおすすめ。

 

 

図で説明

文章だけではわかり辛いと思うので図での説明。最大化

 

 

サポートベクトルマシンによる最大マージン分類

 

重みベクトル\(\vec{w}\)、サンプルの位置\(\vec{x}\)を用いると、

\begin{eqnarray}
&w_{0}& + \vec{w^{T}} \vec{x_{pos}} = 1 \\
&w_{0}& + \vec{w^{T}} \vec{x_{neg}} = -1 \\
\end{eqnarray}

2式を引き算すると
\begin{eqnarray}
\vec{w^{T}} (\vec{x_{pos}} – \vec{x_{neg}}) = 2  (1)\\
\end{eqnarray}

ベクトルの長さを定義して上の式を標準化する。ベクトルの長さは以下のように定義できる。

\begin{eqnarray}
\|w\| = \sqrt{\sum^{m}_{j=1}w_{j}^{2}}      (2)
\end{eqnarray}

式1,2より
\begin{eqnarray}
\frac{\sqrt{\sum^{m}_{j=1}w_{j}^{2}} }{\|w\|} = \frac{2}{\|w\|}
\end{eqnarray}
この式の左辺は、正の超平面と負の超平面の距離である、要するに最大化するマージンである。

サンプルが正しく分類されているという制約のもとでSVMの目的関数の最大化する問題は、マージン\(\frac{2}{\|w\|}\)を最大化する問題に帰着できる。
実際には、\(\frac{2}{\|w\|}\)を最大化するのではなく、\(\frac{1}{2}\|w\|^2 \)を最小化する方が簡単である。最小化する際には、二次計画法(ラグランジュの未定乗数法)により解ける。

 

スラック変数を使った非線形分離可能なケースへの対処

 

スラック変数\(\eta\)を用いることで非線形分類のために線形規約を緩和することができる。直感的に説明するならば、適切なコストペナルティを科した上で誤分類が存在する状態のまま最適化問題を収束させることが可能になった。

正値のスラック変数は線形規約の式にそのまま追加される。
\begin{eqnarray}
\vec{w^{T}} \vec{x^{(i)}} \geq = 1 – \xi^{i} (y^{i}= 1) \\
\vec{w^{T}} \vec{x^{(i)}} < -1 + \xi^{i} (y^{i}= -1) \\
\end{eqnarray}

 

したがって、最小化すべき新しい対象(先の制約の対象)は以下のようになる。
\begin{eqnarray}
\frac{1}{2}\|w\|^{2} + C \sum_{i}\xi^{(i)}
\end{eqnarray}

 

あとは、変数cを使って誤分類のペナルティを制御すれば良い。Cの値が大きいと誤分類のペナルティが大きく、小さければペナルティは小さく誤分類に対して寛容ということになる。これによりマージンの幅が制御できるので、以下の図に示すようにバイアスとバライアンスのトレードオフを調整できる。

 

確認のためパーセプトロンのアルゴリズム、ロジスティック回帰、SVMを用いて実際にIrisのデータセットを分類し、可視化してみる。

 

 

パーセプトロンによる分類
ロジスティック回帰モデルによる分類

 

 

 

 

 

 

サポートベクターマシンによる分類


スポンサーリンク

 

カーネルSVMを使った非線形問題の求解

SVMが人気の理由の一つに非線形問題をカーネル化するのが容易であることが挙げられます。例えば以下のようにnumpyのlogical_xor関数を使って200個のサンプルを用意し、2つのクラスラベルがつけられているとする。

 

これを線形SVMを用いた場合、サンプルをうまく分割できない(適切な超平面見つからない)のは明らかです。

そうした線形分離できないようなものを射影関数を用いて、高次元空間へと射影し線形分離できるようにします。以下の式で表現できる射影を使ってクラスを分離します。
\begin{eqnarray}
\phi(x_1,x_2) = (z_1,z_2,z_3) = (x_1,x_2,x_1^2 + x_2^2)
\end{eqnarray}

これによりグラフに示されている二つのクラスを線形超空間を使って分離できるようになります。それを元に特徴空間へ再度射影することで非線形の決定境界が得られます。

以下は、非線形分離するまでの過程を視覚的に表現したものです。

 

 

記事が役に立ったらシェア!

投稿者:

中村 俊

中村 俊

1993/09/04生まれ。機械系大学院を休学し、ベンチャーでインターンしている最中。直近では、デカルトの「方法序説」に感銘を受けた。 趣味:読書、web開発の勉強、異分野の論文読んだり、記事書いたり。 最終的には経営者か研究者になりたい。

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です

CAPTCHA