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

f:id:s0sem0y:20170124195502p:plain

サポートベクターマシンの数式
手計算してみる
- 問題設定
- 問題を解く
終わりに

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

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

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

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}$ としてしまえばいいです。

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

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

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

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

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つにします。図示するとデータは以下のような感じです。

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

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

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

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

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

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

適当な分類境界

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

他にも点が増えてきたであろうときにもマージン最大化での分類境界はおそらく上手く働きそうですね。実際には大量のデータの中から、分類が際どい点をそれぞれ数点選んでおいても良いのですが、今回は手計算で理解を深めるため、たったの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}$ と求まり、もう１つの制約条件である $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)$

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

$\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$ が実際負の値を取るのかを確かめてみるということになります。

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

$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$ 正則化項だけが目的関数になっていたということになります。）

記事

HELLO CYBERNETICS

深層学習、機械学習、強化学習、信号処理、制御工学、量子計算などをテーマに扱っていきます

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

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

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

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

まとめ

手計算してみる

問題設定

問題を解く

最適化問題へ値を代入

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

$w_0$ を計算する

主問題の $\bf w$ を確認

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

終わりに

現実の問題：データ点

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

記事

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

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

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

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

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

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

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

まとめ

手計算してみる

問題設定

問題を解く

最適化問題へ値を代入

制約条件を考慮

を計算する

主問題のを確認

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

終わりに

現実の問題：データ点

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

記事

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

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

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

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

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

$w_0$ を計算する

主問題の $\bf w$ を確認