AdventCalendar&Qiita初投稿です。
よろしくお願いします。
普段は深層学習をメインにやっているのですが、他の手法も学んでみようということで今回AdventCalendarの題材とさせていただきました。題材をSVMとしたのは、深層学習が台頭する以前にメジャーな識別器として使われていたこと、またニューラルネットワークと共に語られることが多いなどから、知っといて損はないかもなと思ったからです。
今回題材としたのは、データ点の実空間（写像等を適用する前の空間）に境界を設ける線形SVMのみです。
実際に使用するのであれば非線形の概念も抑えるべきなので、後々そちらの方にも触れてみようと思います。
SVMの基本的な事柄をまとめただけなので、既にありふれた内容だとは思いますがご容赦ください…
それと内容にあまり自信がないので、もし間違いなどありましたら指摘していただけると嬉しいです。
SVM
SVMとは
SVMというのは、乱暴に言ってしまえば「データ間の境界を決定する」学習器です。
例えば以下の様な二次元空間に幾つかのデータが存在し、それらのデータが２つのグループに属しているとします。
同じ色の点は、同じグループのデータであることを表しています。
ではこのグループ分けに従い、これらのデータ点を二つに分ける直線を引いてみます。
このように引いてもいいですし、
このように引いても分けられます。グループを二つに分ける直線のパターンはいくらでもあります。
もし直線を上手く引くことができたら、未知のデータが観測された場合でも、直線を基準にして未知データをグループ分け出来そうです。SVMは、そのような直線、もとい「境界」を学習によって決定します。SVMの学習については後の項で説明します。
線形SVMの数式表現
$\boldsymbol x$を$d$次元実数空間上のベクトル$(\boldsymbol x \in \mathrm{R}^d)$とし、以下の様な関数を定義します。
g(\boldsymbol{x})=
\begin{cases}
\ \ 1 \ \ \ & \ \ f(\boldsymbol{x}) \geq 0 \\
-1 \ \ & \ \ f(\boldsymbol{x}) < 0
\end{cases}
さらに、$f(x)$として以下の様な関数も考えます。
f(\boldsymbol{x}) = \boldsymbol{w^{\mathrm{T}}x}+b
一番目の定義は$f(\boldsymbol{x})$の正負によって$g(\boldsymbol{x})$の取る値が変わることを表し、二番目の定義は$f(\boldsymbol{x})$が傾き$\boldsymbol{w}$、切片$b$の超平面（二次元空間上なら直線）であることを表しています。実はこれらの定義は、先程の直線によるグループ分けを表現しています（簡単のため、諸々の定義を端折っています…）。$f(\boldsymbol{x})$が空間上の境界そのもの、$g(\boldsymbol{x})$が境界を基準にデータを二分する分類器にあたります。$\boldsymbol{x}$にはデータの特徴ベクトルが入ります。特徴ベクトルとはデータの特徴をベクトルで表現したものであり、今回の例ではデータ点の座標値が該当します。
再び、二次元空間上のデータ点を考えます。
もしデータ点が境界$f(\boldsymbol{x})$より上にある場合、$f(\boldsymbol{x})\geq0$より$g(\boldsymbol{x})=1$となり、下にある場合は$f(\boldsymbol{x})<0$より$g(\boldsymbol{x})=-1$となります。$g(\boldsymbol{x})$の出力値=データの所属グループと見れば、$g(\boldsymbol{x})$はデータ点を２つのグループに分ける関数とみなすことができます。
$f(\boldsymbol{x})$の傾き$\boldsymbol{w}$や切片$b$を変えれば、$f(\boldsymbol{x})$とデータ点との位置関係が変わり、それによって$g(\boldsymbol{x})$の出力結果を変えることができます。先程の直線を引くという操作は、$f(\boldsymbol{x})$の傾きや切片といったパラメタの決定と言い換えることができます。境界である$f(\boldsymbol{x})$のパラメタを観測データに合わせて調節してやることで、訓練データを正しく識別できる$g(\boldsymbol{x})$が完成します。この調節作業を訓練データを元に行うのがいわゆる「学習」となります。
マージンとその最適化
次に、最適な境界を決定する基準と、その基準を元した境界のパラメタ学習について説明します。
二次元空間の例では、すでにいくつかのデータ点が存在し、各々クラスラベルが与えられていました。SVMのような教師あり学習では、このような正解付きのデータを元に、未知のデータに対しても識別を行えるように学習を行います。この正解付きデータを訓練データと呼び、そのデータセットを訓練集合と呼びます。
訓練集合内のすべてのデータが正しいクラスに分類可能な状況を考えます（このような訓練集合を分離可能といいます）。訓練データのうち、i番目のデータの特徴ベクトルを$\boldsymbol{x_i}$、クラスラベルを$y_i$とすると、データの分類に成功している場合には$y_i$と$f(\boldsymbol{x_i})$の符号が一致するので
\begin{equation}
{y_i}f(\boldsymbol{x_i}) > 0
\end{equation}
となります。すべてのデータが正しく分類できるということは、任意の訓練データ$y_i(i∈[1...n])$に対して上記式が成り立つということになります。しかしそれを満たすような$f(\boldsymbol{x_i})$は複数存在しうるので、できればそのなかで最適な$f(\boldsymbol{x_i})$を選びたいところです。ここでいう「最適」とは、未知のデータを最も正しく分類しうるような状態のことを指します。となると、まず$f(\boldsymbol{x_i})$が「最適であるかどうか」の基準が必要になります。
そこでSVMでは、各クラスのデータ集合が直線とどの程度離れているかを分類の良さの基準としています。この距離をマージンと呼びます。
SVMではこのマージンが大きいほどよい境界であるとして、なるべくマージンが大きくなるように境界のパラメタを決定します。
特徴ベクトル$\boldsymbol{x_i}$と境界間の距離は、点と平面の距離の公式より
\frac{|\boldsymbol{w^{\mathrm{T}}x_i}+b|}{\|\boldsymbol{w}\|}
と表せます。
なおマージンの最大化は、境界に一番近い特徴ベクトルのマージンを最大化することで実現できるので、すべての特徴ベクトルに関して上記式を計算する必要はありません。このようなベクトルをサポートベクトルと呼びます。
ここで訓練集合が分離可能であることを思い出すと、すべての特徴ベクトルに関して ${y_i}f(\boldsymbol{x_i}) > 0$でなければなりません。この制約から、マージンの最大化は以下の様な最適化問題に置き換えられます。
\max _{\boldsymbol{w},b,M }{\frac{M}{\|\boldsymbol{w}\|} \ \ \ \ }\mbox{ s.t. } y_i(\boldsymbol{w^{\mathrm{T}}x_i}+b) \geq M \ \ \ (i \in \{1...n\}) \ , \ M>0
直感的には、境界との距離が最も近いデータ点に着目した時、その距離が最も大きくなるように$\boldsymbol{w}$や$b$、そして$M$を設定する問題と考えられます。
$\frac{M}{|\boldsymbol{w}|}$を最大化するためにMをできるだけ大きくしたいところですが、Mは$y_i(\boldsymbol{w^{\mathrm{T}}x}+b)$によって上から抑えられます。このことから、結果としてMの最大値は$y_i(\boldsymbol{w^{\mathrm{T}}x}+b)$の最小値となります。この最小値が、サポートベクトルと境界との距離になります。
なお最適化問題では、$\max _ {\boldsymbol{w},b,M} {\frac{M}{|\boldsymbol{w}|} }$のような最適化の目安となる関数を目的関数と呼びます。この目的関数を最大化あるいは最小化するパラメタを決定することが、最適化問題の目的です。
次に、サポートベクトルを$\boldsymbol{x_k}$とすると、目的関数の値は以下のようになります。d = \frac{M}{\|\boldsymbol{w}\|} =
\frac{y_k(\boldsymbol{w^{\mathrm{T}}x_k}+b)}{\|\boldsymbol{w}\|} =
\frac{|\boldsymbol{w^{\mathrm{T}}x_k}+b|}{\|\boldsymbol{w}\|}
目的関数の値が、先ほどの特徴ベクトルと境界間の距離の形になりました。さらに両辺を$M$で割り、$w \leftarrow \frac{w}{M} , b \leftarrow \frac{b}{M}$と置き換えると、データ点と境界との距離の最小値が$1$となるように正規化できます。
\max _{\boldsymbol{w},b }{\frac{1}{\|\boldsymbol{w}\|} \ \ \ \ }\mbox{ s.t. } y_i(\boldsymbol{w^{\mathrm{T}}x_i}+b) \geq 1 \ \ \ (i \in \{1...n\})
加えて、$\frac{1}{|\boldsymbol{w}|}$の最大化は逆数の$|\boldsymbol{w}|$の最小化と等価であること、$|\boldsymbol{w}|$の最小化は$|\boldsymbol{w}|^2$の最小化と等価であることから、上記最適化問題はさらに扱いやすい形に置き換えることができます。
\min _{\boldsymbol{w},b }{{\|\boldsymbol{w}\|}^2 \ \ \ \ }\mbox{ s.t. } y_i(\boldsymbol{w^{\mathrm{T}}x_i}+b) \geq 1 \ \ \ (i \in \{1...n\})
この目的関数が最小になるような$\boldsymbol{w}$を求めることで、各クラスを最も分離する境界$f(\boldsymbol{x}) = \boldsymbol{w^{T}x}+b$を求めることができます。この操作をマージン最大化とよび、訓練データが分離可能である仮定のもとにマージン最大化を行うSVMによる分類をハードマージンと呼びます。また目的関数より、サポートベクトルが境界の決定を左右することに、SVMの名前は由来しているそうです。なおパラメタの更新に関しては、
\boldsymbol{w}\leftarrow \boldsymbol{w}+\eta t^i \boldsymbol{x_i},
\ \ \ \
b\leftarrow b+\eta t^n\left(\max _{1\geq i\geq n}{\|\boldsymbol{x_i}\|}
\right)^2 \ \ \ \ if \ \ \ \ y_i(\boldsymbol{w^{\mathrm{T}}x_i}+b) < 1 \ \ \ (i \in \{1...n\})
のように行います。
ソフトマージン
先程は全ての訓練データが$f(\boldsymbol{x})$で分類可能であるという仮定のもと、分類を行っていました（ハードマージン）。しかし現実にはそのようなことは稀で、一部の訓練データにノイズが乗るなどして正しく分類できないことがほとんどです。
このようなデータセットを分類する場合、一般にソフトマージンと呼ばれる手法をSVM上で用います。
前項のハードマージンでは、以下のような目的関数と制約条件を設定していました。
\min _{\boldsymbol{w},b }{{\|\boldsymbol{w}\|}^2 \ \ \ \ }\mbox{ s.t. } y_i(\boldsymbol{w^{\mathrm{T}}x_i}+b) \geq 1 \ \ \ (i \in \{1...n\})
上記関数・制約はもともと、境界に一番近いデータ点（サポートベクトル）と境界との距離がなるべく大きくなる$\boldsymbol{w}$、$b$、$M$を決めるためのものでした。制約条件の右辺は、どんなに境界に近いデータ点であっても、全てのデータ点は境界とはユークリッド距離で$1$以上離れていなくてはならないことを示しています（これは$M$の正規化後の距離で、正規化前は少なくとも$M$離れていなくてはならない）。現実問題に対して、これでは少し厳しすぎます。
そこで、以下のように制約条件を緩和します。
y_i(\boldsymbol{w^{\mathrm{T}}x_i}+b) \geq 1-ξ_i \ \ \ (i \in \{1...n\}), \ \ \ ξ_i \geq 0
$ξ_i$は正の整数なので、制約条件の右辺が１以下となります。これはデータ点が境界に近づくことが許されることを表しています。また右辺は負の値にもなり得るので、データ点が境界の反対側に食い込むことすら許容します。この制約緩和をソフトマージンと呼びます。
図で表すと以下のようになります。
ただし、この緩和を過度に適用しすぎると誤分類が多発してしまいます。ある程度の外れ値も許容しつつ、データ点全体に対してはできるだけ正しく境界を設定したいところです。
データ点$\boldsymbol x_i $が誤分類されたとき、$y_i(\boldsymbol w^{\mathrm{T}} x_i +b)<0$となるので、この時制約条件をクリアするには$ξ _i>1$である必要があります。誤分類されたデータがK個の場合、少なくともK個の$ξ _i$は$>1$となるので、全ての$ξ _i$を足し合わせると
\sum_{i\in{1...n}}ξ_i>K
となります。
このことから、全ての$ξ_i$の総和を整数$K$以下にすれば、少なくとも誤分類は$K$個以下に抑えられることがわかります。
そこで、目的関数に変更を加えます。最終的に、制約緩和を適用した後の目的関数・制約条件は以下のようになります。
\min _{\boldsymbol{w},b,\boldsymbol{\xi} }\frac{1}{2}{{\|\boldsymbol{w}\|}^2+C\sum_{i\in{1...n}}ξ_i \ \ \ \ }
\mbox{ s.t. } y_i(\boldsymbol{w^{\mathrm{T}}x_i}+b) \geq 1-ξ_i \ \ \ (i \in \{1...n\}), \ \ \ ξ_i \geq 0
先程の$ \xi _i$の総和が目的関数に追加されました。これにより、$ \xi _i$の値が抑制され、過度な誤分類を防ぐことができます。なお$\boldsymbol \xi $は$ \xi _i$からなるベクトルを表しています。
$C$は正則化係数と呼ばれる正の定数で、この値を大きくすることで$ \xi _i $の増加に対しより強いペナルティを与えることができます。$C=\infty$とすることで、いずれかの$ \xi _i $が0より大きい値をとった時点で関数値が無限大に発散してしまうので、実質全ての$ \xi _i $は0となります。これは先のハードマージンに一致します（但しこのとき、データの訓練集合が分離可能でないと計算不能になってしまいます）。逆に$C$を小さくしていくと、$ \xi _i $の値が増えても目的関数の値はそれほど増加しないため、より誤分類が許容されやすくなります。
Cは定数であり、使用者が事前に決めておく必要があるので、交差検証法などで最適な$C$を設定します。
まとめ
今回は線形SVMの、それもハードマージンの部分だけを取り扱いました。ほんとはソフトマージン、双対問題、非線形SVMまでやるつもりだったのですが、全然間に合いませんでした…
（2016/12/10）ソフトマージンの項目追加+他一部修正を行いました。
（2016/12/10）非線形SVMと双対問題について、別記事でまとめました。