"機械学習","信号解析","ディープラーニング"の勉強

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

"機械学習","信号解析","ディープラーニング"の勉強

"機械学習","信号解析","ディープラーニング"について、それぞれ勉強しながらブログにまとめていきます。テーマは気分によってバラバラかもしれません。

サポートベクターマシンを手計算して理解する

人工知能 人工知能-機械学習

 サポートベクターマシンの数式

サポートベクターマシンの最適化問題

サポートベクターマシンの考え方と、数式の導出は以下の記事で扱っています。

 

s0sem0y.hatenablog.com

 

今回は最適化問題が導出されたところから始めます。

データ\bf x_nとそれにそれに対するラベルt_nがあるときに、以下の最適化問題

 

\arg \min_{\bf w} \frac{1}{2}|{\bf w}|^2

 

s.t. t_n({\bf w^T}φ({\bf x_n})+w_0)-1 \geq 0

 

を解くことで、サポートベクターマシンの2クラス分類器

 

y={\bf w^T}φ({\bf x})+w_0

 

を得ることができます。新しい入力データ\bf xに対しては、上記の式で計算されるyが正であるか負であるかで分類を行うことができます。

 

ただしφ(・)は予め決めておいた非線形関数であり、線形分類ができなさそうな問題に対して、上手く分類できそうな非線形関数を選択せねばなりません。このような関数を明示的に扱うこと無く、全く同じ処理を行う方法があり、「カーネル法」と呼ばれています。

 

普通に線形分類をしたければφ({\bf x})={\bf x}としてしまえばいいです。

 

最適化問題の別の表現、双対問題

上記の最適化問題は制約不等式が少々めんどくさい形をしています。

ラグランジュの乗数法を用いることで、最適化問題を式変形して別の表現にしてしまうことができます。もともとの最適化問題を主問題、書き換えられた問題を双対問題と呼び、これらの解は1対1に対応するため、一方を解けば他方も解けたことになります。

 

双対問題の導出は以下の記事で行っています。

s0sem0y.hatenablog.com

この双対問題においては、非線形関数φ(・)を明示的に扱う必要はなくなっていることに注意してください(つまり非線形関数が多次元への複雑な写像だとしても、実際にそれを計算する必要がなくなる → 無限次元も扱える)。

 

双対問題は以下の最適化問題となっています。

 

 \arg \max_{\bf a} \left( \sum_{n=1}^{N}a_n-\frac{1}{2}\sum_{n=1}^{N}\sum_{m=1}^{N}a_na_mt_nt_mk({\bf x}_n, {\bf x}_m) \right)

 

s.t. a_n \geq 0 , \sum_{n=1}^N a_nt_n=0

 

目的関数が少々複雑に見えますが、単にデータ\bf xとラベルtの代入計算を行い、{\bf a} = (a_1,...,a_N)^T に関する関数にしてしまい、あとは最大化問題を解くだけです。高々二次関数なので、必ず解を得ることができます。

 

これにより\bf αが求まったならば、新しい入力データ\bf xに対して、サポートベクターマシンによる分類器は以下の数式による計算を行います。

 

y = \sum_{n=1}^N a_nt_nk({\bf x},{\bf x}_n)+w_0

 

この値が正であるか負であるかによって分類を行います。

ここで{\bf x}_nというのは訓練データです。サポートベクターマシンでは訓練データを分類の際にも覚えておかねばなりません。

ただし、学習を行う際には、分類平面の近くにあるきわどいデータのみを少数だけ選び出して訓練データとするため、実際には何千ものデータを保持する必要はありません(そもそもサポートベクターマシンは、分類が際どくなりそうなデータに対して、そのマージンを最大化することで汎化性能を高めるものでした)。

 

w_0を求める方法は単純で、そもそもサポートベクターマシンは正例の訓練データに対して、y=1となるように学習させ、負例に対してy=-1となるように学習させるものです。

従って、サポートベクターマシンによる分類器において正例データ{\bf x}^+を使って

 

1 = \sum_{n=1}^N a_nt_nk({\bf x}^+,{\bf x}_n)+w_0

 

という方程式を解けばw_0が求まります。

 

ここでk({\bf x},{\bf x}_n)というのは非線形関数を明示すれば

 

k({\bf x},{\bf x}_n)=φ({\bf x})^Tφ(\bf x)_n

 

という形でした。線形判別をしたければφ({\bf x})=\bf xとするので、

 

k({\bf x},{\bf x}_n)={\bf x}^T {\bf x}_n

 

となり、これは単なる標準内積です。カーネル法を用いたサポートベクターマシンは、内積に相当する計算k({\bf x},{\bf x}_n)を非線形にすることで、あたかも非線形変換を行ってから、内積を取っているかのように扱う手法だと言えます。

 

分類自体は既に上記の式でできてしまいますが、元々も主問題では\bf wを求めるのが目的でした。これを明示的に求めたい場合は

 

 {\bf w}=\sum_{n=1}^N a_nt_nφ(\bf x)_n

 

を計算すればいいです。

 

まとめ

ともかく非線形だろうが線形だろうが解かなければいけない最適化問題は

 

 \arg \max_{\bf a} \left( \sum_{n=1}^{N}a_n-\frac{1}{2}\sum_{n=1}^{N}\sum_{m=1}^{N}a_na_mt_nt_mk({\bf x}_n, {\bf x}_m) \right)

 

s.t. a_n \geq 0 , \sum_{n=1}^N a_nt_n=0

 

で表されており、線形にしたいのか非線形にしたいのか、どんな非線形にしたいのかをk(・,・)を調整して決めるということになります。

訓練データを上記の最適化問題へ代入し、制約条件を考慮してa

 

その後

 

1 = \sum_{n=1}^N a_nt_nk({\bf x}^+,{\bf x}_n)+w_0

 

を計算してw_0を求めて分類器を完全に獲得します。

新規のデータ\bf xに対しては

 

y = \sum_{n=1}^N a_nt_nk({\bf x},{\bf x}_n)+w_0

 

の正負をみて分類することになります。

 

 

手計算してみる

問題設定

訓練データ\{ {\bf x}_n, t_n \}

 

\{ {\bf x}_1, t_1 \} =\{ (-1,-1),-1 \}

 

\{ {\bf x}_2, t_2 \} =\{ (1,1),1 \}

 

の2つにします。図示するとデータは以下のような感じです。

f:id:s0sem0y:20170124190018p:plain

赤い点が\{ {\bf x}_1, t_1 \} =\{ (-1,-1),-1 \}

青い点が\{ {\bf x}_2, t_2 \} =\{ (1,1),1 \}

これに対するサポートベクターマシンを構築しましょう。

目視で分かるというのは素晴らしいことです。

 

マージン最大化という観点からすれば、この問題に対する分類境界は、(線形ならば)原点を通る傾き-1の直線になるでしょう。もしもマージン最大化という観点を理解していなければ、他にも無数に分け方は存在します。

 

f:id:s0sem0y:20170124190401p:plain

マージン最大化による分類境界 

 

f:id:s0sem0y:20170124190440p:plain

適当な分類境界

パーセプトロンならば、収束時にこのような境界にもなりうる

 

 

他にも点が増えてきたであろうときにもマージン最大化での分類境界はおそらく上手く働きそうですね。実際には大量のデータの中から、分類が際どい点をそれぞれ数点選んでおいても良いのですが、今回は手計算で理解を深めるため、たったの2点でやります。

 

問題を解く

今回は簡単のため、線形分類を考えます。

すなわちk({\bf x}_i,{\bf x}_j)={\bf x}_i^T{\bf x}_jとするということです。(非線形でやりたかったら適当にカーネルを調べてやってみてください。この部分の計算が変わるだけです。)

 

さて訓練データは以下でした。解いていきましょう。

 

\{ {\bf x}_1, t_1 \} =\{ (-1,-1),-1 \}

 

\{ {\bf x}_2, t_2 \} =\{ (1,1),1 \}

 

 

最適化問題へ値を代入

最適化問題は以下でした。

 

 \arg \max_{\bf a} \left( \sum_{n=1}^{N}a_n-\frac{1}{2}\sum_{n=1}^{N}\sum_{m=1}^{N}a_na_mt_nt_mk({\bf x}_n, {\bf x}_m) \right)

 

s.t. a_n \geq 0 , \sum_{n=1}^N a_nt_n=0

 

まず訓練データを目的関数(最大化問題の中身)へ代入します。

 

\sum_{n=1}^{N}a_n-\frac{1}{2}\sum_{n=1}^{N}\sum_{m=1}^{N}a_na_mt_nt_mk({\bf x}_n, {\bf x}_m)

 

 = \sum_{n=1}^{2}a_n-\frac{1}{2}\sum_{n=1}^{2}\sum_{m=1}^{2}a_na_mt_nt_mk({\bf x}_n, {\bf x}_m)

 

 =a_1 + a_2 - \frac{1}{2} (a_1a_1t_1t_1{\bf x_1}^T{\bf x_1}+a_1a_2t_1t_2{\bf x_1}^T{\bf x_2}+a_2a_1t_2t_1{\bf x_2}^T{\bf x_1}+a_2a_2t_2t_2{\bf x_2}^T{\bf x_2})

 

この式へ

 

\{ {\bf x}_1, t_1 \} =\{ (-1,-1),-1 \}

 

\{ {\bf x}_2, t_2 \} =\{ (1,1),1 \}

 

を代入していき

 

=a_1+a_2 -\frac{1}{2}(2a_1^2+2a_1a_2+2a_2a_1+2a_2^2) 

 

=a_1+a_2 -a_1^2-2a_1a_2-a_2^2

 

と目的関数が得られました。(目的関数を以後L(a_1,a_2)と書きます)

次にa_1,a_2をいろいろ調整して値を最小にします。

 

制約条件\sum t_na_n=0を考慮

制約条件を使うと、

 

\sum t_na_n=0 ⇔ -a_1+a_2=0 ⇔ a_1=a_2

 

という関係を満たす必要が出てきます。この制約を目的関数L(a_1,a_2)へ代入することで

 

L(a_1,a_2)=L(a_1)=2a_1-4a_1^2

 

が得られます。これをa_1について最大化すればよく、a_1で微分して0とおくと

 

L'(a_1)=2-8a_1=0  ⇔  a_1=\frac{1}{4}

 

と求まります。制約条件からa_2=a_1=\frac{1}{4}と求まり、もう1つの制約条件であるa_1,a_2 \geq 0も満たされているので問題ありません。

 

w_0を計算する

w_0を計算するためには正例のデータx^+=x_1=(1,1)の方を使って、y=1を出力するように学習させるため 

 

1 = \sum_{n=1}^N a_nt_nk({\bf x}^+,{\bf x}_n)+w_0

 ⇔

1 = \sum_{n=1}^2 a_nt_nk({\bf x}^+,{\bf x}_n)+w_0

 ⇔

1 = a_1t_1{\bf x}^{+T}{\bf x}_1+a_2t_2{\bf x}^{+T},{\bf x}_2+w_0

1 = \frac{1}{4}(-1)(-2)+\frac{1}{4}(1)(2)+w_0

1 = 1+w_0

w_0=0

 

と求まります。

 

主問題の\bf wを確認

 

ついでに主問題の\bf wを明示的に求めたい場合は

 

 {\bf w}=\sum_{n=1}^N a_nt_nφ(\bf x)_n

 

を使います。

 

{\bf w} = \frac{1}{4}(-1)(-1,-1)+\frac{1}{4}(1)(1,1)=\frac{1}{2}(1,1)

 

であり、このベクトルは境界直線に対する法線ベクトルとなっているので、図示すると具体的に境界が求まったことになります。

 

f:id:s0sem0y:20170124195502p:plain

\bf w=\frac{1}{2}(1,1)を法線ベクトルとし、切片w_0=0である直線が境界となる。

 

 

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

分類器は以下の形です。

 

y = \sum_{n=1}^N a_nt_nk({\bf x},{\bf x}_n)+w_0

 

ここで\bf xが新しい入力データで{\bf x}_nは訓練データです。

新しい入力データ\bf xが得られた場合には、新しいデータと既に求めたパラメータたちを代入してyの値を計算します。

いま{\bf x}=(-1,0)という新しいデータを使って分類を行ってみましょう。これは図から負例に分類されることが明らかに分かっていますから、yが実際負の値を取るのかを確かめてみるということになります。

 

f:id:s0sem0y:20170124195745p:plain

新しいデータ点を緑色でプロット。明らかに負例である。

 

 

a_1=a_2=\frac{1}{4}

 

w_0=0

 

そして訓練データ

 

\{ {\bf x}_1, t_1 \} =\{ (-1,-1),-1 \}

 

\{ {\bf x}_2, t_2 \} =\{ (1,1),1 \}

 

と入力データ

 

{\bf x}=(-1,0)

 

を代入します。

 

y = \sum_{n=1}^N a_nt_nk({\bf x},{\bf x}_n)+w_0

 

=\sum_{n=1}^2 a_nt_nk({\bf x},{\bf x}_n)

 

=\frac{1}{4}(-1)(-1,0)(-1,-1)^T+\frac{1}{4}(1)(-1,0)(1,1)^T

 

=-\frac{1}{4}-\frac{1}{4}=-\frac{1}{2}

 

と求まり、確かに負例であると分類しました。

 

 

 

終わりに

現実の問題:データ点

今回は訓練データが二点だけでした。従って制約条件を満たしながら最大化問題を解くことが簡単にできましたが、実際にデータ点が増えると手計算では無理になります。その場合は二次計画法という手法を使うことでシステマチックに解くことができます。

 

 

現実の問題:データが混ざっている

今回は二点を使って完全に分類できるデータを使いましたが、実際には負例と正例がわずかに重なっているようなデータを使う場合もあるでしょう。カーネル法を用いれば線形分離不可能な問題も分類できるため、混ざっているデータすらも無理やり分類できてしまいます。

しかしそれは単なる過学習に過ぎなく、実際には誤りを少し許しても良いから、妥当な境界を求めたいということになります。その場合は「ソフトマージン」という概念を用いて最適化問題を書き換えることになりますが、それほど難しくはありません。

 

また、目的関数を一般的な機械学習の手法から眺めた場合、ソフトマージンを使ったサポートベクターマシンは、損失関数をヒンジ損失に、正則化項をL2ノルムにしていると見ることもできます。そのような見方は、他のロジスティック回帰分析などとの違いを理解することに役立つでしょう。(サポートベクターマシンのマージン最大化という概念は、実はL2正則化項だけが目的関数になっていたということになります。)

 

 

記事

正則化についてMAP推定の立場から

s0sem0y.hatenablog.com

 

バイアスバリアンス分解による機械学習の性能評価

s0sem0y.hatenablog.com

 

サポートベクターマシンの基礎

s0sem0y.hatenablog.com

 

評価関数、目的関数からの機械学習

s0sem0y.hatenablog.com