統計検定準1級のためサポートベクトターマシンを学んでいる.
ここではその概要を記述する.
アイデア
フィッシャーの線形判別と同様に下の図1のような, 2つのデータを分ける超平面を考える.
２つのクラスを分ける超平面は無限個作ることができる. そこでサポートベクターマシンでは, マージンと呼ばれる距離を最大化するような超平面が選ばれる. マージンとは, 超平面から最も近くのデータとの距離である.
つまり, 図2のように最小距離を最大化しようとすると, 押し付けあってお互いのデータの中央に収束するイメージである.ここで, 超平面と最も近いデータ(パターン)のことをサポートベクターと呼ぶ.
ここからは, これをどのように数式にしていくかを考える.
定式化
$\boldsymbol{w}$を求める
ここでは図2のような超平面をどのように決定するのかを考える.
まず, 図3のように, クラス2のサポートベクトルを$\boldsymbol{\tilde{x}}$とし, $\boldsymbol{\tilde{x}}$ から超平面に垂直に下ろした足（最近傍点)を$\boldsymbol{x_0}$とする. この2点の距離は$\boldsymbol{\tilde{x}-x_0}$となる.
この時, 点$\boldsymbol{x_0}$は超平面上にあるため,
\begin{gather}
\boldsymbol{w^Tx_0+w_0=0} , \tag{1}
\end{gather}
が成り立つ.
加えて, 図4のように法線ベクトル$\boldsymbol{w}$と, それをそのノルムで割った単位ベクトルを定義する. 法線ベクトルは垂直な方向を表す.そのベクトルをノルムで割ると、大きさが1のベクトルになる. このベクトルは元の$\boldsymbol{w}$と同じ向きだが, 大きさが1に調整される.
この単位ベクトルと$\boldsymbol{\tilde{x}-x_0}$の関係から次の式が成り立つ.
\begin{gather}
\boldsymbol{\tilde{x}-x_0}=s\frac{\boldsymbol{w}}{|\boldsymbol{w}|}, \tag{2}
\end{gather}
ここで$s$が我々が求めたい距離となる. 言い換えると1を何倍したら$\boldsymbol{\tilde{x}-x_0}$になるか. なお, 法線ベクトルが逆であれば, sはマイナスになる.
(2)式に(1)式を入れると,
\begin{gather}
\boldsymbol{w^T(\tilde{x}}-s\frac{\boldsymbol{w}}{|\boldsymbol{w}|})+\boldsymbol{w_0}=0\\
\boldsymbol{w^T\tilde{x}+w_0}-s\frac{\boldsymbol{w^Tw}}{|\boldsymbol{w}|}=0\\
\boldsymbol{w^T\tilde{x}+w_0}-s\frac{|\boldsymbol{w}|^2}{|\boldsymbol{w}|}=0\\
\boldsymbol{w^T\tilde{x}+w_0}-s|\boldsymbol{w}|=0\\
s=\frac{|\boldsymbol{w^T\tilde{x}+w_0}|}{|\boldsymbol{w}|} \tag{3}
\end{gather}
途中, $\boldsymbol{w^Tw}$が$ \boldsymbol{w}$の内積である性質を利用した.
この$s$の最小値を見つけて, これを最大化する.
ここからは制約条件を考える.
学習データを$\boldsymbol{x}$で表し, それがクラス1に属していれば、クラスラベル$y_i$は1になり, クラス２に属している場合クラスラベルが-1になるとする. つまり,
\begin{gather}y_i=
\begin{cases}
1\quad \rm{if} \quad \it{x_i \in w_1} \\
-1\quad \rm{if} \quad \it{x_i \in w_2}
\end{cases}
\end{gather}
である. ここで重みの冗長性を防ぐために
\begin{gather}
\min_{i = 1,,,n}|\boldsymbol{w^Tx_i +w_0}|=1 \tag{4}
\end{gather}
を制約条件として考える.
これは, $\boldsymbol{w^Tx}+w_0=0$の超平面を$a$倍した, $a(\boldsymbol{w^Tx}+w_0)=0$も同じものを表す. $a$倍した超平面は無限にあるため1つに決まるような制約をつける.
式(3)において, $\tilde{x}$はここでは$x_i$であるため,超平面とパターンの最小距離は
\begin{gather}
\min_{i=1,,,,n}\frac{|\boldsymbol{w^Tx_i+w_0s}|}{|\boldsymbol{w}|}=\frac{1}{|w|}\tag{5}
\end{gather}
これを最大化する.
$\frac{1}{|w|}$を最大化するということは, $|w|$を最小化すると同義である.したがって次のように言い換えられる.
\begin{gather}
\frac{1}{2}|w|^2 \to \rm{minimize}\tag{6} \\
\rm{subject\quad to} \quad \it{y_i(w^Tx_i +w_0)}\rm{ \ge1 (i = 1,2,,,n)}
\end{gather}
ここで, $\frac{1}{2}$と, 2乗はのちに微分するときのためのものである.
また, 制約条件である$y_i(w^Tx_i+w_0)\ge1$はすべての学習データが正しく識別できていることを条件として示している (図5参照).
式(6)は, ラグランジュの未定乗数法を用いて解く.
\begin{gather}
L(w,w_0,\alpha) = \frac{1}{2}|\boldsymbol{w}|^2-\sum\alpha_i(y_i(w^Tx_i+w_0)-1) \tag{7}
\end{gather}
ここで, $\alpha$は, $\alpha_i\ge 0$を満たすラグランジュ乗数である.
この$L$を$w$と, $w_0$について次の式から最小化する.
\begin{gather}
\frac{\partial L}{\partial \boldsymbol{w}}=0, \quad \frac{\partial L}{\partial w_0}=0
\end{gather}
式(7)より,
\begin{gather}
L(\boldsymbol{w},w_0, \boldsymbol{\alpha})=\frac{1}{2}\boldsymbol{w^Tw}-\sum^{n}_{i = 1}(\alpha_iy_i\boldsymbol{w^Tx_i}+\alpha_iy_iw_0-\alpha_i)\tag{8}
\end{gather}
$\frac{\partial L}{\partial \boldsymbol{w}}=0\to $
\begin{gather}
-\sum^{n}_{i=1}\alpha_iy_i=0\to \sum^{n}_{i=1}\alpha_i y_i=0\tag{9}
\end{gather}
$\frac{\partial L}{\partial w_0}=0\to$
\begin{gather}
w-\sum^{n}_{i=1}\alpha_iy_ix_i=0 \to w=\sum^{n}_{i=1}\alpha_iy_ix_i\tag{10}
\end{gather}
式(9), 式(10)を式(8)に代入すると
\begin{align}
L&=\frac{1}{2}\sum^{n}_{i=1}\alpha_iy_ix_i^T\sum^{n}_{j=1}\alpha_jy_jx_j-\sum^{n}_{i=1}\alpha_iy_i\sum^{n}_{j=1}\alpha_jy_jx_j^Tx_i+\sum^{n}_{i=1}\alpha_i\\
&=\frac{1}{2}\sum^{n}_{i=1}\sum^{n}_{j=1}\alpha_i\alpha_jy_iy_jx_i^Tx_j-\sum^{n}_{i=1}\sum^{n}_{j=1}\alpha_i\alpha_jy_iy_jx_j^Tx_i+\sum^{n}_{i=1}\alpha_i\\
&=\sum^{n}_{i=1}\alpha_i-\frac{1}{2}\sum^{n}_{i=1}\sum^{n}_{j=1}\alpha_i\alpha_jy_iy_jx_i^Tx_j
\end{align}
したがって, 式(7)は次の問題と等価であることがわかる.
\begin{gather}
L=\sum^{n}_{i=1}\alpha_i-\frac{1}{2}\sum^{n}_{i=1}\sum^{n}_{j=1}\alpha_i\alpha_jy_iy_jx_i^Tx_j\to \rm{maximize}\\
\rm{subject}\quad to \quad \it{\alpha_i}\ge\rm{0(i=1,,,,n)}, \it{\sum^{n}_{i=1}\alpha_iy_i}=\rm{0}\tag{11}
\end{gather}
式(11)で新しく追加された制約条件は式(9)から得られる.
また, 式(11)は式(7)の双対問題である.式(7)が最小化問題であれば, 式(11)は最大化問題である.
ここで, 未知数が$\alpha$であり, $\alpha$について最大化する.
なぜ, 主問題である式(7)ではなく, 双対問題である式(11)を解くのかというと, 式(11)は二次計画問題になっているためである. つまり, $\alpha$の２次しかないため極大値につかまることなく, 最大値を求めることができる点がメリットとして大きいためである.(図6参照)
式(11)により$\alpha$が求まったら, 式(10)より$\boldsymbol{w}$を求めることができる.
$w_0$を求める
図7のように, 各クラスに最低１つのサポートベクトルがある.(でないと超平面を決められない.)
そのサポートベクトルを$x_{oA}$と$x_{oB}$と定義する.これらは, 超平面まで等距離であるため,$w_0$はサポートベクトルが通る切片, $w_{0A}$と$w_{0B}$の真ん中にある.
したがって,
\begin{gather}
w_0=\frac{w_{0A}+w_{0B}}{2}, \tag{12}
\end{gather}
また, $x_A$と$x_B$はそれぞれ,
\begin{gather}
w^Tx+w_{0A}=0,\\
w^Tx+w_{0B}=0,
\end{gather}が成り立つ.
これらを式(12)に代入すると,
\begin{align}
w_0&=\frac{-w^Tx_A-w^Tx_B}{2}\\
&=-\frac{1}{2}(w^Tx_A+w^Tx_B) \tag{13}
\end{align}
と求めることができる.
ソフトマージン
今までは,線形分離可能な問題に使える手法であった.
ここからは線形分離不可能な問題を考える.
例えば図８のような場合である.
図８は線形分離できていない. 言い換えると若干の間違いがある.
それを許すして線形識別関数を求める手法がソフトマージンと呼ばれる方法である.
\begin{gather}
\frac{1}{2}|w|^2+C\sum^{n}_{i=1}\zeta_i \to \min \tag{14}\\
s.t.\ y_i(w^Tx_i+w_0)\ge 1-\zeta_i, (i=1,2,,,n) \tag{15}\\
\zeta_i \ge 0(i=1,2,,,,n):\rm{slack \ variables}
\end{gather}
式(14)において, パラメータ$C$を調整することで, 制約条件を強めたり弱めたりすることができる.
そして, 式(15)の右辺が１よりも小さくなった場合、間違いが起こったことになる。
ここから式(14)をラグランジュの未定乗数法を用いて双対問題を解くと,
\begin{gather}
\sum^{n}_{i=1} \alpha_i-\frac{1}{2}\sum^{n}_{i=1}\sum^{n}_{j=1}\alpha_i \alpha_j y_i y_j x_i^tx_j \to \max \tag{16}\\
s.t. \ 0\le \alpha_i \le C(i=1,2,,,n), \sum^{n}_{i=1}\alpha_iy_i=0 \tag{17}
\end{gather}
ハードマージンの際と比較して変わった点は式(17)の制約条件の$C$の部分のみ.
ハードマージンの場合はラグランジュ乗数が0以上という制約でしたが, ソフトマージンの場合は, 上限が$C$になっている.
ソフトマージンにおいては, パラメータ$C$を変えて制約を調整する.
ソフトマージンがない場合は$0 \le \alpha_i \le \infty$と同じであるため, $C$を下げると制約が緩くなる.
非線形の場合
図8のように非線形特性が強い場合を考える.
この場合, ソフトマージンでどうにかなる話ではない.
このような場合は, 緑で囲ったクラス$w_2$を上にあげて３次元にすると、線形分離可能になる.
これは一般に言えることだが, 次元を上げると線形分離性が上がる.
高次元に写像するための関数を含んだ識別関数は次のように表せる.
\begin{gather}
f(\Phi(x))=\boldsymbol{w}^T\Phi(\boldsymbol{x})+w_0\tag{18}
\end{gather}
これは式(1)の$\boldsymbol{x}$が$\Phi(\boldsymbol{x})$になっているだけである.
式(10)より, $w=\sum^{n}_{i=1}\alpha_iy_ix_i$であるため, 式(18)は,
\begin{gather}
f(\Phi(x))=\sum \alpha_i y_i \Phi(x_i)^T\Phi(x_i)+w_0 \tag{19}
\end{gather}
式(19)の$\Phi(x_i)^T\Phi(x_i)$は内積である.
高次元の内積は計算量が大きくなる.これを一つにまとめた関数がカーネル関数であり, 次のように定義される.
\begin{gather}
K(\boldsymbol{x,x^{\prime}})=\Phi(\boldsymbol{x})^T\Phi(\boldsymbol{x}) \tag{20}
\end{gather}
この関数を使うと式(19)は,
\begin{gather}
f(\Phi(\boldsymbol{x}))=\sum^{n}_{i=1}\boldsymbol{\alpha_i}y_iK(\boldsymbol{x,x^{\prime}})+w_0 \tag{21}
\end{gather}
と表せる.
ここで$K$という関数は, $x$を高次元に写像する関数であるが, そんな便利な関数があるのかと最初は思ったが, 代表的な関数が二つ存在する. それが以下の二つである.
\begin{gather}
・多項式カーネル\\
K(\boldsymbol{x,x^{\prime}})=(x^Tx^{\prime}+1)^p\\
・ガウシアンカーネル\\
K(x,x^{\prime})=\exp(-\frac{|x-x^{\prime}|^2}{\sigma^2})
\end{gather}
(11)式の双対問題を参考に$\alpha$を求める.(11式はハードマージン)
しかし, $w=\sum \alpha_i y_i x_i$から$w_i$を求めることはできない.
これは, $x_i$を$\Phi(x_i)$として考えており, $\Phi$の求解を避けてきたためである.
そのため, $w_0$もわからない. しかし, $w_i$がわからなくても$\alpha_i$が分かれば問題ない.
それは高次元での識別関数である式(21)はわかるためである.($w_0$は拡張特徴重みベクトルを使って$w$に含められる)
我々が知りたいのは未知のパターン$x_i$が入ってきたときに、これが正なのか負になるのかさえ分かればいい。$w_i$がわからなくても, それはわかるため, 以下のようにクラス分類できる.
\begin{gather}
f(x)>0 \ \in w_1\\
f(x)<0 \ \in w_2
\end{gather}
今後可能な限り, ライブラリを使わずに, プログラムを使ってSVMを作っていきたい.
コメント