はじめてのパターン認識 8章　ハードマージンSVM

# 注意
当記事は「はじめてのパターン認識」輪読会で担当した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クラス分類手法であり、その線形識別関数は最適化によって求まる。

マージンのイメージ
------------
![fig1.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/488577/2bb91fea-fd51-a87d-3837-6b0742baa463.png)

線形識別境界$(\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
$$

![fig3.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/488577/6626f983-4c2f-e87d-ebc0-1ed53b0d1df4.png)

条件②線形識別境界と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.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/488577/1f6d2310-eac8-3d29-cc1c-bf87dc23b947.png)

上記条件をラグランジュ関数に適用するとKKT条件(1)(2)の微分したときの形式が得られる。
![kkt2.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/488577/20b8031f-bab3-6bf1-e70c-db677424265b.png)

これをラグランジュ関数に適用すると
![tenkai.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/488577/0a3b86a4-b1ba-0ae3-3c64-0dde60d0be22.png)

双対問題
------------
展開したラグランジュ関数とKKT条件より主問題と同等な問題（双対問題）が得られる。
![qw.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/488577/33e8537e-9ea8-8d36-0f8f-6bd7d21775a1.png)


主問題と双対問題のイメージは馬の鞍のようなものである。
![qwe.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/488577/6da4ca86-061a-8fe1-020f-0f281fcb2c88.png)

最大マージン
------------
![qwer.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/488577/ec3fd331-c0cf-fe4e-6796-3df7dec3f63e.png)


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

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