注意

当記事は「はじめてのパターン認識」輪読会で担当した8章について備忘録です。
間違いや誤記があった場合は教えてくれると幸いです。

流れ

はじめてのパターン認識8章の以下三節について整理していく。
・ハードマージンSVM
・ソフトマージンSVM
・非線形特徴写像
→今回はハードマージンSVM

ハードマージンSVM　定義

式(7.2)で定義したクラス間マージンから導かれる、最大マージン$D_{max}$を実現する2クラス線形識別境界の学習法である

$$
\rho(\boldsymbol{w}) =\min_{x \in C_{1}}\frac{\boldsymbol{w}^{T}\boldsymbol{x}+b}{||\boldsymbol{w}||}-\max_{x \in C_{2}}\frac{\boldsymbol{w}^{T}\boldsymbol{x}+b}{||\boldsymbol{w}||} \tag{7.2}
$$
(バイアス項は省かない形で表す)

ここで$\boldsymbol{x_{i}} \in R^{d}$は学習データ、$t_{i}=(-1,1)$は教師データ、$\boldsymbol{w},b$は係数ベクトルとバイアスである。
→線形分離可能な分類問題に対する2クラス分類手法であり、その線形識別関数は最適化によって求まる。

マージンのイメージ

線形識別境界$(\boldsymbol{w}^{T}\boldsymbol{x}+b=0)$が引けると仮定したとき、その線形識別境界からの距離が最短となるデータ点とそのクラスのサポートベクトル(SV)という。
上記画像の場合、〇クラスのSVは赤い〇、△クラスのSVは青い△である。そして、それぞれのSVまでの距離をマージンと呼び、$D_{i}$で表す。

→引きたいのは誤分類は無い、クラスのマージンを最大にする線。
→線形識別境界の条件は①誤分類なく、かつ②線形識別境界とSVの距離が最大。

条件①誤分類なし

i番目のデータと線形識別境界の距離を$d_{i}$、マージンを$D$とすると、
点と線の距離なので
$$
d_{i}=\frac{||\boldsymbol{w}^{T}\boldsymbol{x_{i}}+b||}{||\boldsymbol{w}||} \geq D \Rightarrow ||\boldsymbol{w}^{T}\boldsymbol{x_{i}}+b|| \geq D||\boldsymbol{w}||=\kappa \\
\hspace{9.3cm}\Rightarrow ||\boldsymbol{w}^{T}\boldsymbol{x_{i}}+b|| \geq D||\boldsymbol{w}||=1 \quad (\because \boldsymbol{w}=\frac{\boldsymbol{w}}{\kappa},b=\frac{b}{\kappa}) \\
\hspace{7.5cm}\Rightarrow \begin{cases}
||\boldsymbol{w}^{T}\boldsymbol{x_{i}}+b|| \geq 1 \qquad(\boldsymbol{w}^{T}\boldsymbol{x_{i}}+b \geq 0) \\
||\boldsymbol{w}^{T}\boldsymbol{x_{i}}+b|| \leq -1 \quad(\boldsymbol{w}^{T}\boldsymbol{x_{i}}+b \leq 0)
\end{cases}
$$
これより予測の符号がクラス別に求まった。これにそれぞれの正解ラベル（教師テータ$t_{i}$）を乗算すると、誤分類していないときは符号が正になり、またその大きさは1より大きいことが分かる。
よって、マージンについて調べると、誤分類無しの条件は次の式になる。
$$
t_{i}(\boldsymbol{w}^{T}\boldsymbol{x_{i}}+b) \geq 1
$$

条件②線形識別境界とSVの距離が最大

前節の距離の式より、クラス間マージンは
$$
\rho(\boldsymbol{w})=\min_{x \in C_{i}}d_{i}-\max_{x \in C_{2}}d_{i}
=\frac{||\boldsymbol{w}^{T}\boldsymbol{x_{SV1}}+b||}{||\boldsymbol{w}||}-\frac{||\boldsymbol{w}^{T}\boldsymbol{x_{SV2}}+b||}{||\boldsymbol{w}||}
\\
\hspace{-10mm}=\frac{2}{||\boldsymbol{w}||}
$$
二段目の等式はSVまでの距離を条件①で正規化したことによる変換を適用したためである。
ここで上記式を最大化するという問題を移し変えてみる。
$$
\max_{\boldsymbol{w},b}\rho(\boldsymbol{w},b) \Rightarrow \max_{\boldsymbol{w}}\frac{2}{||\boldsymbol{w}||}
\\
\hspace{6cm}\Rightarrow \max_{\boldsymbol{w}}\frac{1}{||\boldsymbol{w}||} \quad(\because \mbox{係数の影響は小さい})
\\
\hspace{6cm}\Rightarrow \min_{\boldsymbol{w}}||\boldsymbol{w}|| \quad(\because \mbox{最大化→負の最小化})
\\
\hspace{9.5cm}\Rightarrow \min_{\boldsymbol{w}}\frac{1}{2}||\boldsymbol{w}||^{2} \quad(\because \mbox{内積計算をしたい、また微分計算を楽にするため})
\\
\hspace{2.7cm}\Rightarrow \min_{\boldsymbol{w}}\frac{1}{2}\boldsymbol{w}^{T}\boldsymbol{w}
$$

考えるべき最適化問題（主問題）

$$
\min \qquad f(\boldsymbol{w})=\frac{1}{2}\boldsymbol{w}^{T}\boldsymbol{w}\\
\mbox{subject to} \qquad g_{i}(\boldsymbol{w},b)=t_{i}(\boldsymbol{w}^{T}\boldsymbol{x_{i}}+b) \geq 1 \quad(i=1,2,\cdots,N)
$$
上記はハードマージンSVMの線形識別関数を求める問題で最適化すべき評価関数$f(\boldsymbol{w})$と条件$g_{i}(\boldsymbol{w},b)$から構成される。この問題をワンクッション置いて考えるために、ラグランジュ関数を導入する。

$$
\min \qquad L(\boldsymbol{w},b,\boldsymbol{\alpha})=\frac{1}{2}\boldsymbol{w}^{T}\boldsymbol{w}-\sum_{i=1}^{N}\alpha_{i}(t_{i}(\boldsymbol{w}^{T}\boldsymbol{x}+b)-1) \\
\mbox{subject to} \qquad \alpha_{i} \geq 0 \quad(\mbox{ラグランジュ未定乗数})
$$
ラグランジュ関数を展開すると
$$
L(\boldsymbol{w},b,\boldsymbol{\alpha})=\frac{1}{2}\boldsymbol{w}^{T}\boldsymbol{w}-\sum_{i=1}^{N}\alpha_{i}(t_{i}(\boldsymbol{w}^{T}\boldsymbol{x}+b)-1) \\
\hspace{4.2cm}= \frac{1}{2}\boldsymbol{w}^{T}\boldsymbol{w}-\sum_{i=1}^{N}\alpha_{i}t_{i}\boldsymbol{w}^{T}\boldsymbol{x_{i}}-b\sum_{i=1}^{N}\alpha_{i}t_{i}+\sum_{i=1}^{N}\alpha_{i}
$$

天下りではあるが、最適解$\boldsymbol{w_{0}},b_{0}$は次に示す最適化条件（KKT条件）を見たす解として得られる。

KKT条件

上記条件をラグランジュ関数に適用するとKKT条件(1)(2)の微分したときの形式が得られる。

これをラグランジュ関数に適用すると

双対問題

展開したラグランジュ関数とKKT条件より主問題と同等な問題（双対問題）が得られる。

主問題と双対問題のイメージは馬の鞍のようなものである。

最大マージン

まとめ

線形分子可能な問題に対してSVMは強力な手法であるが、計算コストとデータが大きくなったときの次元の呪いに弱いため、コスト度外視の課題にしようするのが良いかもしれない。
数学的に最良の識別関数が引けて、データの偏りに強いのはうれしいので、人命にかかわるものには使いたいかも。

追伸

Quiitaでtexが使えると聞いて色々試しましたが、大変なので途中から画像貼り付けに変えました。Cloudlatexでスライド作成したものがあったので、それを使いましたが、記事化へのコストが大きいのでやり方を考えないといけない。slideshareに挙げて所々捕捉形式の方が良いかも。