[ML] 機器學習技法：第四講 soft-margin SVM

ML：基礎技法學習
Package：scikit-learn
課程：機器學習技法
簡介：第四講 soft-margin SVM (support vector machine)

建議的 Library

• Linear LIBLINEAR
• non-linear LIBSVM

soft-margin SVM primal

$$\begin{array}{rl}\underset{b,\mathbf{w},\mathit{\xi }}{min}& \frac{1}{2}{\mathbf{w}}^T\mathbf{w}+C\cdot \sum _{n=1}^N{\xi }_n\\ subjectto& y_n({\mathbf{w}}^T{\mathbf{x}}_n+b)\ge 1-{\xi }_{n}and{\xi }_n\ge 0foralln\end{array}$$ QP of $\tilde{d}+1+N$ 個變數，$2N$ 個條件

從第一講得知
$$\begin{array}{rl}\underset{b,\mathbf{w}}{min}& \frac{1}{2}{\mathbf{w}}^T\mathbf{w}\\ subjectto& y_n({\mathbf{w}}^T{\mathbf{z}}_n+b)\ge 1foralln\end{array}$$ 從 Pocket 得知，希望得到最小的錯誤總數
$$\underset{b,\mathbf{w}}{min}\sum _{n=1}^N[y_n\ne sign({{\mathbf{w}}^{\mathbf{Tz}}}_n+b)]$$ 將兩者合併，並加入 C 參數，控制 trade-off
看是以 large margin 為主，還是 noise tolerance
$$\begin{array}{rl}\underset{b,\mathbf{w}}{min}& \frac{1}{2}{\mathbf{w}}^T\mathbf{w}+C\cdot \sum _{n=1}^N[y_n\ne sign({{\mathbf{w}}^{\mathbf{Tz}}}_n+b)]\\ s.t.& y_n({\mathbf{w}}^T{\mathbf{z}}_n+b)\ge 1forcorrectn\\ & y_n({\mathbf{w}}^T{\mathbf{z}}_n+b)\ge -\mathrm{\infty }forincorrectn\end{array}$$ 可再簡化為
$$\begin{array}{rl}\underset{b,\mathbf{w}}{min}& \frac{1}{2}{\mathbf{w}}^T\mathbf{w}+C\cdot \sum _{n=1}^N[y_n\ne sign({{\mathbf{w}}^{\mathbf{Tz}}}_n+b)]\\ s.t.& y_n({\mathbf{w}}^T{\mathbf{z}}_n+b)\ge 1-\mathrm{\infty }\cdot [y_n\ne sign({{\mathbf{w}}^{\mathbf{Tz}}}_n+b)]foralln\end{array}$$ $[y_n\ne sign({{\mathbf{w}}^{\mathbf{Tz}}}_n+b)]$ 不是 linear，所以不再是 QP
而且也無法分辨錯誤的距離大小
若改成記錄違反 margin 的距離呢？並用此取代計數錯誤的數目
當 $y_n=\pm 1$，距離可為 $margin(b,\mathbf{w})=\frac{1}{\Vert \mathbf{w}\Vert }{y}_n({\mathbf{w}}^T{\mathbf{x}}_n+b)$
可以以後面那項為代表，以 ${\xi }_n$ 表示離 $y_n({\mathbf{w}}^T{\mathbf{z}}_n+b)=1$ 有多遠，可得
$$\begin{array}{rl}\underset{b,\mathbf{w},\mathit{\xi }}{min}& \frac{1}{2}{\mathbf{w}}^T\mathbf{w}+C\cdot \sum _{n=1}^N{\xi }_n\\ s.t.& y_n({\mathbf{w}}^T{\mathbf{z}}_n+b)\ge 1-{\xi }_{n}and{\xi }_n\ge 0foralln\end{array}$$ 有 $\mathbf{w}$ 跟 $b$，共 $\tilde{d}+1$ 個變數，再加上 $N$ 個 ${\xi }_n$
並有兩個絛件，各有 $N$ 個

soft-margin SVM dual

$$\begin{array}{rl}\underset{\mathit{\alpha }}{min}& \frac{1}{2}\sum _{n=1}^N\sum _{m=1}^N{\alpha }_n{\alpha }_m{y}_n{y}_m{\mathbf{z}}_n^T{\mathbf{z}}_m-\sum _{n=1}^N{\alpha }_n\\ subjectto& \sum _{n=1}^N{y}_n{\alpha }_n=0;\\ & C\ge {\alpha }_n\ge 0,forn=1,2,\cdots ,N\\ implicitly& \mathbf{w}=\sum _{n=1}^N{\alpha }_n{y}_n{\mathbf{z}}_n;\\ & {\beta }_n=C-{\alpha }_n,forn=1,2,\cdots ,N\end{array}$$ QP of $N$ 個變數，$2N+1$ 個條件

利用 Lagrange multipliers，隱藏限制條件，此處將 ${\lambda }_n$ 用 ${\alpha }_n$ & ${\beta }_n$ 取代
$$L(b,\mathbf{w},\mathit{\xi },\mathit{\alpha },\mathit{\beta })=\frac{1}{2}{\mathbf{w}}^T\mathbf{w}+C\cdot \sum _{n=1}^N{\xi }_n+\sum _{n=1}^N{\alpha }_n(1-{\xi }_n-y_n({\mathbf{w}}^T{\mathbf{z}}_n+b))+\sum _{n=1}^N{\beta }_n\cdot (-{\xi }_n)$$ 當 $\underset{all{\alpha }_n\ge 0,{\beta }_n\ge 0}{max}L(b,\mathbf{w},\mathit{\xi },\mathit{\alpha },\mathit{\beta })$ 會發現

• $(b,\mathbf{w},\mathit{\xi })$ 違反限制條件時，會導致
•  $1-{\xi }_n-y_n({\mathbf{w}}^T{\mathbf{z}}_n+b)>0$
  又因 $L(b,\mathbf{w},\mathit{\xi },\mathit{\alpha },\mathit{\beta })$ 針對 ${\alpha }_n$ 取 max 的緣故，${\alpha }_n$ 越大越好
•  $-{\xi }_n>0$
  又因 $L(b,\mathbf{w},\mathit{\xi },\mathit{\alpha },\mathit{\beta })$ 針對 ${\beta }_n$ 取 max 的緣故，${\beta }_n$ 越大越好
• 使得 $L(b,\mathbf{w},\mathit{\xi },\mathit{\alpha },\mathit{\beta })\to \mathrm{\infty }$
• $(b,\mathbf{w},\mathit{\xi })$ 符合限制條件時，會導致
• $1-{\xi }_n-y_n({\mathbf{w}}^T{\mathbf{z}}_n+b)\le 0$
  又因 $L(b,\mathbf{w},\mathit{\xi },\mathit{\alpha },\mathit{\beta })$ 針對 ${\alpha }_n$ 取 max 的緣故，${\alpha }_n$ 與 $1-{\xi }_n-y_n({\mathbf{w}}^T{\mathbf{z}}_n+b)$ 兩者至少有一個必須為 0
•  $-{\xi }_n\le 0$
  又因 $L(b,\mathbf{w},\mathit{\xi },\mathit{\alpha },\mathit{\beta })$ 針對 ${\beta }_n$ 取 max 的緣故，${\beta }_n$ 與 $-{\xi }_n$ 兩者至少有一個必須為 0
• 使得 $L(b,\mathbf{w},\mathit{\xi },\mathit{\alpha },\mathit{\beta })\to \frac{1}{2}{\mathbf{w}}^T\mathbf{w}$

故此式子與原本的求解一樣，如下，只是限制條件被隱藏到 max 中
$$SVM\equiv \underset{b,\mathbf{w},\mathit{\xi }}{min}(\underset{all{\alpha }_n\ge 0,{\beta }_n\ge 0}{max}L(b,\mathbf{w},\mathit{\xi },\mathit{\alpha },\mathit{\beta }))=\underset{b,\mathbf{w},\mathit{\xi }}{min}(\mathrm{\infty }ifviolate;\frac{1}{2}{\mathbf{w}}^T\mathbf{w}iffeasible)$$
此時 $(b,\mathbf{w},\mathit{\xi })$ 仍在式子最外面，如何把它跟裡面的 ${\alpha }_n,{\beta }_n$ 交換呢？
這樣才能初步得到 2N 個變數的式子
任取一個 ${\mathit{\alpha }}^{\prime },{\mathit{\beta }}^{\prime }$ with ${\alpha }_n^{\prime }\ge 0,{\beta }_n^{\prime }\ge 0$，因取 max 一定比任意還大，可得下式
$\underset{b,\mathbf{w},\mathit{\xi }}{min}(\underset{all{\alpha }_n\ge 0,{\beta }_n\ge 0}{max}L(b,\mathbf{w},\mathit{\xi },\mathit{\alpha },\mathit{\beta }))\ge \underset{b,\mathbf{w},\mathit{\xi }}{min}L(b,\mathbf{w},\mathit{\xi },{\mathit{\alpha }}^{\prime },{\mathit{\beta }}^{\prime })$
那如果對 ${\mathit{\alpha }}^{\prime }\ge 0,{\mathit{\beta }}^{\prime }\ge 0$ 取 max，也不影響此等式，如下
$\underset{b,\mathbf{w},\mathit{\xi }}{min}(\underset{all{\alpha }_n\ge 0,{\beta }_n\ge 0}{max}L(b,\mathbf{w},\mathit{\xi },\mathit{\alpha },\mathit{\beta }))\ge \underset{Lagrangedualproblem}{\underbrace{\underset{all{\alpha }_n^{\prime }\ge 0,{\beta }_n^{\prime }\ge 0}{max}(\underset{b,\mathbf{w},\mathit{\xi }}{min}L(b,\mathbf{w},\mathit{\xi },{\mathit{\alpha }}^{\prime },{\mathit{\beta }}^{\prime }))\stackrel{{\mathit{\alpha }}^{\prime }=\mathit{\alpha },{\mathit{\beta }}^{\prime }=\mathit{\beta }}{\to }\underset{all{\alpha }_n\ge 0,{\beta }_n\ge 0}{max}(\underset{b,\mathbf{w},\mathit{\xi }}{min}L(b,\mathbf{w},\mathit{\xi },\mathit{\alpha },\mathit{\beta }))}}$
比較直覺的想法，就像是「從最大的一群中取最小」一定 $\ge$ 「從最小的一群中取最大」
$$\underset{original(primal))SVM}{\underbrace{\underset{b,\mathbf{w},\mathit{\xi }}{min}(\underset{all{\alpha }_n\ge 0,{\beta }_n\ge 0}{max}L(b,\mathbf{w},\mathit{\xi },\mathit{\alpha },\mathit{\beta }))}}\ge \underset{Lagrangedual}{\underbrace{\underset{all{\alpha }_n\ge 0,{\beta }_n\ge 0}{max}(\underset{b,\mathbf{w},\mathit{\xi }}{min}L(b,\mathbf{w},\mathit{\xi },\mathit{\alpha },\mathit{\beta }))}}$$ 目前的關係稱作 $\ge$ weak duality

但這還不夠，最好是 $=$ strong duality，才能初步得到 2N 個變數的式子
幸運的是，在 QP 中，只要滿足以下條件，便是 strong duality

• convex primal (原來的問題為 convex)
• feasible primal (原來的問題有解的，也就是線性可分)
• linear constraints (限制條件為線性的)

對於 SVM 滿足這些條件並不困難，故解以下的式子，如同解原本的式子
$$\underset{all{\alpha }_n\ge 0,{\beta }_n\ge 0}{max}\left(\underset{b,\mathbf{w},\mathit{\xi }}{min}\underset{L(b,\mathbf{w},\mathit{\xi },\mathit{\alpha },\mathit{\beta })}{\underbrace{\frac{1}{2}{\mathbf{w}}^T\mathbf{w}+C\cdot \sum _{n=1}^N{\xi }_n+\sum _{n=1}^N{\alpha }_n(1-{\xi }_n-y_n({\mathbf{w}}^T{\mathbf{z}}_n+b))+\sum _{n=1}^N{\beta }_n\cdot (-{\xi }_n)}}\right)$$
但如何把內部的 $(b,\mathbf{w},\mathit{\xi })$ 拿掉呢？
內部的問題，當最佳化時，必定符合
$$\begin{array}{rl}\frac{\partial L(b,\mathbf{w},\mathit{\xi },\mathit{\alpha },\mathit{\beta })}{\partial b}& =0=-\sum _{n=1}^N{\alpha }_n{y}_n\Rightarrow \sum _{n=1}^N{\alpha }_n{y}_n=0\\ \frac{\partial L(b,\mathbf{w},\mathit{\xi },\mathit{\alpha },\mathit{\beta })}{\partial \mathbf{w}}& =\mathbf{0}=\mathbf{w}-\sum _{n=1}^N{\alpha }_n{y}_n{\mathbf{z}}_n\Rightarrow \mathbf{w}=\sum _{n=1}^N{\alpha }_n{y}_n{\mathbf{z}}_n\\ \frac{\partial L(b,\mathbf{w},\mathit{\xi },\mathit{\alpha },\mathit{\beta })}{\partial {\xi }_n}& =0=C-{\alpha }_n-{\beta }_n\Rightarrow {\beta }_n=C-{\alpha }_n\end{array}$$ 從以上的這些條件，可得
$$\begin{array}{rl}dual& =\underset{all{\alpha }_n\ge 0,{\beta }_n\ge 0}{max}(\underset{b,\mathbf{w},\mathit{\xi }}{min}\frac{1}{2}{\mathbf{w}}^T\mathbf{w}+C\cdot \sum _{n=1}^N{\xi }_n+\sum _{n=1}^N{\alpha }_n(1-{\xi }_n-y_n({\mathbf{w}}^T{\mathbf{z}}_n+b))+\sum _{n=1}^N{\beta }_n\cdot (-{\xi }_n))\\ & =\underset{all{\alpha }_n\ge 0,{\beta }_n\ge 0}{max}(\underset{b,\mathbf{w},\mathit{\xi }}{min}\frac{1}{2}{\mathbf{w}}^T\mathbf{w}+C\cdot \sum _{n=1}^N{\xi }_n+\sum _{n=1}^N{\alpha }_n\cdot -{\xi }_n+\sum _{n=1}^N{\alpha }_n(1-y_n({\mathbf{w}}^T{\mathbf{z}}_n+b))+\sum _{n=1}^N{\beta }_n\cdot (-{\xi }_n))\\ & =\underset{all{\alpha }_n\ge 0,{\beta }_n\ge 0}{max}(\underset{b,\mathbf{w},\mathit{\xi }}{min}\frac{1}{2}{\mathbf{w}}^T\mathbf{w}+\sum _{n=1}^N(C-{\alpha }_n-{\beta }_n){\xi }_n+\sum _{n=1}^N{\alpha }_n(1-y_n({\mathbf{w}}^T{\mathbf{z}}_n+b)))\\ [\because 0=C-{\alpha }_n-{\beta }_n]& =\underset{all{\alpha }_n\ge 0,{\beta }_n\ge 0,{\beta }_n=C-{\alpha }_n}{max}(\underset{b,\mathbf{w},\mathit{\xi }}{min}\frac{1}{2}{\mathbf{w}}^T\mathbf{w}+\sum _{n=1}^N{\alpha }_n(1-y_n({\mathbf{w}}^T{\mathbf{z}}_n+b)))\\ [\because {\beta }_n\ge 0\Rightarrow {\alpha }_n\le C]& =\underset{allC\ge {\alpha }_n\ge 0,{\beta }_n=C-{\alpha }_n}{max}(\underset{b,\mathbf{w},\mathit{\xi }}{min}\frac{1}{2}{\mathbf{w}}^T\mathbf{w}+\sum _{n=1}^N{\alpha }_n(1-y_n({\mathbf{w}}^T{\mathbf{z}}_n+b)))\\ & =\underset{allC\ge {\alpha }_n\ge 0,{\beta }_n=C-{\alpha }_n}{max}(\underset{b,\mathbf{w},\mathit{\xi }}{min}\frac{1}{2}{\mathbf{w}}^T\mathbf{w}+\sum _{n=1}^N{\alpha }_n(1-y_n{\mathbf{w}}^T{\mathbf{z}}_n)-\sum _{n=1}^N{\alpha }_n{y}_n\cdot b)\\ [\because \sum _{n=1}^N{\alpha }_n{y}_n=0]& =\underset{allC\ge {\alpha }_n\ge 0,{\beta }_n=C-{\alpha }_n,\sum _{n=1}^N{\alpha }_n{y}_n=0}{max}(\underset{b,\mathbf{w}}{min}\frac{1}{2}{\mathbf{w}}^T\mathbf{w}+\sum _{n=1}^N{\alpha }_n(1-y_n{\mathbf{w}}^T{\mathbf{z}}_n))\\ & =\underset{allC\ge {\alpha }_n\ge 0,{\beta }_n=C-{\alpha }_n,\sum _{n=1}^N{\alpha }_n{y}_n=0}{max}(\underset{b,\mathbf{w},\mathit{\xi }}{min}\frac{1}{2}{\mathbf{w}}^T\mathbf{w}+\sum _{n=1}^N{\alpha }_n-\sum _{n=1}^N{\alpha }_n{y}_n{\mathbf{w}}^T{\mathbf{z}}_n)\\ & =\underset{allC\ge {\alpha }_n\ge 0,{\beta }_n=C-{\alpha }_n,\sum _{n=1}^N{\alpha }_n{y}_n=0}{max}(\underset{b,\mathbf{w},\mathit{\xi }}{min}\frac{1}{2}{\mathbf{w}}^T\mathbf{w}+\sum _{n=1}^N{\alpha }_n-{\mathbf{w}}^T\sum _{n=1}^N{\alpha }_n{y}_n{\mathbf{z}}_n)\\ [\because \mathbf{w}=\sum _{n=1}^N{\alpha }_n{y}_n{\mathbf{z}}_n]& =\underset{allC\ge {\alpha }_n\ge 0,{\beta }_n=C-{\alpha }_n,\sum _{n=1}^N{\alpha }_n{y}_n=0,\mathbf{w}=\sum _{n=1}^N{\alpha }_n{y}_n{\mathbf{z}}_n}{max}(\underset{b,\mathbf{w},\mathit{\xi }}{min}\frac{1}{2}{\mathbf{w}}^T\mathbf{w}+\sum _{n=1}^N{\alpha }_n-{\mathbf{w}}^T\mathbf{w})\\ & =\underset{allC\ge {\alpha }_n\ge 0,{\beta }_n=C-{\alpha }_n,\sum _{n=1}^N{\alpha }_n{y}_n=0,\mathbf{w}=\sum _{n=1}^N{\alpha }_n{y}_n{\mathbf{z}}_n}{max}(\underset{b,\mathbf{w},\mathit{\xi }}{min}-\frac{1}{2}{\mathbf{w}}^T\mathbf{w}+\sum _{n=1}^N{\alpha }_n)\\ & =\underset{allC\ge {\alpha }_n\ge 0,{\beta }_n=C-{\alpha }_n,\sum _{n=1}^N{\alpha }_n{y}_n=0,\mathbf{w}=\sum _{n=1}^N{\alpha }_n{y}_n{\mathbf{z}}_n}{max}(\underset{b,\mathbf{w},\mathit{\xi }}{min}-\frac{1}{2}{\Vert \sum _{n=1}^N{\alpha }_n{y}_n{\mathbf{z}}_n\Vert }^2+\sum _{n=1}^N{\alpha }_n)\\ [\because nob,\mathbf{w},\mathit{\xi }removemin]& =\underset{allC\ge {\alpha }_n\ge 0,{\beta }_n=C-{\alpha }_n,\sum _{n=1}^N{\alpha }_n{y}_n=0,\mathbf{w}=\sum _{n=1}^N{\alpha }_n{y}_n{\mathbf{z}}_n}{max}-\frac{1}{2}{\Vert \sum _{n=1}^N{\alpha }_n{y}_n{\mathbf{z}}_n\Vert }^2+\sum _{n=1}^N{\alpha }_n\\ & =\underset{allC\ge {\alpha }_n\ge 0,{\beta }_n=C-{\alpha }_n,\sum _{n=1}^N{\alpha }_n{y}_n=0,\mathbf{w}=\sum _{n=1}^N{\alpha }_n{y}_n{\mathbf{z}}_n}{min}\frac{1}{2}{\Vert \sum _{n=1}^N{\alpha }_n{y}_n{\mathbf{z}}_n\Vert }^2-\sum _{n=1}^N{\alpha }_n\\ & =\underset{allC\ge {\alpha }_n\ge 0,{\beta }_n=C-{\alpha }_n,\sum _{n=1}^N{\alpha }_n{y}_n=0,\mathbf{w}=\sum _{n=1}^N{\alpha }_n{y}_n{\mathbf{z}}_n}{min}\frac{1}{2}\sum _{n=1}^N{\alpha }_n{y}_n{\mathbf{z}}_n^T\left(\sum _{m=1}^N{\alpha }_m{y}_m{\mathbf{z}}_m\right)-\sum _{n=1}^N{\alpha }_n\\ & =\underset{allC\ge {\alpha }_n\ge 0,{\beta }_n=C-{\alpha }_n,\sum _{n=1}^N{\alpha }_n{y}_n=0,\mathbf{w}=\sum _{n=1}^N{\alpha }_n{y}_n{\mathbf{z}}_n}{min}\frac{1}{2}\sum _{n=1}^N\sum _{m=1}^N{\alpha }_n{\alpha }_m{y}_n{y}_m{\mathbf{z}}_n^T{\mathbf{z}}_m-\sum _{n=1}^N{\alpha }_n\end{array}$$
將限制條件移出

• $\mathbf{w}=\sum _{n=1}^N{\alpha }_n{y}_n{\mathbf{z}}_n$ 只是求 $\mathbf{w}$ 並不限制 $\mathit{\alpha }$
• ${\beta }_n=C-{\alpha }_n$ 只是求 ${\beta }_n$ 並不限制 $\mathit{\alpha }$

可得
$$\begin{array}{rl}\underset{\mathit{\alpha }}{min}& \frac{1}{2}\sum _{n=1}^N\sum _{m=1}^N{\alpha }_n{\alpha }_m{y}_n{y}_m{\mathbf{z}}_n^T{\mathbf{z}}_m-\sum _{n=1}^N{\alpha }_n\\ subjectto& \sum _{n=1}^N{y}_n{\alpha }_n=0;\\ & C\ge {\alpha }_n\ge 0,forn=1,2,\cdots ,N\\ implicitly& \mathbf{w}=\sum _{n=1}^N{\alpha }_n{y}_n{\mathbf{z}}_n;\\ & {\beta }_n=C-{\alpha }_n,forn=1,2,\cdots ,N\end{array}$$ 求 $\alpha$ 共 $N$ 個變數
限制條件 ${\alpha }_n$ 有 $2N$ 個，加上 $\sum _{n=1}^N{y}_n{\alpha }_n=0$，共 $2N+1$

與 Hard margin 只差在 ${\alpha }_n$ 有上限限制 $C$

Kernel soft-margin SVM

b 的求解，必須為 free SV，極少數若無 free SV 則需滿足 KKT 條件(與 hard-margin 略有不同)

${\mathbf{x}}_n$ 可用 ${\mathbf{z}}_n$ 取代，延伸至更高維度的轉換

任意 ${\alpha }_n>0$，則 $1-{\xi }_n-y_n({\mathbf{w}}^T{\mathbf{z}}_n+b)$=0 (by KKT)
$$\begin{array}{rl}0& =1-{\xi }_n-y_n({\mathbf{w}}^T{\mathbf{z}}_n+b)\\ y_n({\mathbf{w}}^T{\mathbf{z}}_n+b)& =1-{\xi }_n\\ y_{n}b& =1-{\xi }_n-y_n{\mathbf{w}}^T{\mathbf{z}}_n\\ b& =\frac{1-{\xi }_n-y_n{\mathbf{w}}^T{\mathbf{z}}_n}{y_n}\\ if{y}_n& =\pm 1\\ b& =y_n-y_n{\xi }_n-{\mathbf{w}}^T{\mathbf{z}}_n\end{array}$$ 但 ${\xi }_n$ 來自 $b$，$b$ 又來自 ${\xi }_n$，無法求解
利用另一條件，任意 ${\beta }_n=C-{\alpha }_n>0$，則 $-{\xi }_n=0$ (by KKT)
故當 $C-{\alpha }_n>0\Rightarrow {\alpha }_n<C$，則 ${\xi }_n=0$ 同時滿足兩個條件的為 free SV，可得
$$\begin{array}{rl}b& =y_n-{\mathbf{w}}^T{\mathbf{z}}_s\\ & =y_n-\sum _{n=1}^N{\alpha }_n{y}_n{\mathbf{z}}_n^T{\mathbf{z}}_s\\ & =y_n-\sum _{n=1}^N{\alpha }_n{y}_{n}K({\mathbf{z}}_n,{\mathbf{z}}_s)\\ & =y_n-\sum _{SVindicesn}{\alpha }_n{y}_{n}K({\mathbf{z}}_n,{\mathbf{z}}_s)\end{array}$$

仍會有 overfit 的風險，需小心選取 $(\gamma ,C)$

${\alpha }_n$ 的意義

兩組 complementary slackness

$$\begin{array}{rl}{\alpha }_n(1-{\xi }_n-y_n({\mathbf{w}}^T{\mathbf{z}}_n+b))& =0\\ (C-{\alpha }_n){\xi }_n& =0\end{array}$$

•  ${\alpha }_n=0,{\xi }_n=0$
• non SV
• 可能遠離邊界或剛好在邊界上
•  $C>{\alpha }_n>0,{\xi }_n=0$
• $◻$ free SV 
• 剛好在邊界上
•  ${\alpha }_n=C,{\xi }_n=1-y_n({\mathbf{w}}^T{\mathbf{z}}_n+b)$ 即是違反的值
• $\mathrm{△}$ bounded SV 
• 違反或剛好在邊界上
• 可視情況用在資料的解析上，何者有幫助、何者無幫助、何者可能有 noise

Model Selection

利用 validation 選擇合適的參數
橫軸為 C，縱軸為 $\gamma$，$E_{cv}$ 對於 SVM 非常常用

$$E_{loocv}\le \frac{\mathrm{\#}SV}{N}$$ $N$ 為資料個數

假設擁有 N 個資料 $({\mathbf{x}}_1,y_1),({\mathbf{x}}_1,y_1),\cdots ,({\mathbf{x}}_N,y_N)$
當選擇的資料 $({\mathbf{x}}_n,y_n)$，其對應的 ${\alpha }_n=0$，即是非 SV
也就是說即使被挑去做 validation 也不影響最佳化結果
而 non-SV 分類必為正確，故其 $e_{non-SV}=0$
錯誤的定義是跟 0 的差值，畢竟對於 sign 而言，只要大過 0 或小過 0 即可
所以此時的 $g_n$ 未取 sign，而放縮過的 ${\mathbf{w}}^T{\mathbf{z}}_n+b=\pm 1$($y_n=\pm 1$)
$e_{SV}$ 不是 0，就是 1，故 $e_{SV}\le 1$
所以 $E_{loocv}\le \frac{\mathrm{\#}SV}{N}$

下圖為 SV 的個數，但可看出並無法用來挑選最佳 model
因上面的式子只是表達其錯誤上限，實際上的錯誤還是未知
實際上是用來排除不合理的 model，再進行 $E_{cv}$ 的計算

程式碼

import numpy as np
import matplotlib.pyplot as plt
from sklearn import svm
from sklearn.model_selection import cross_val_score                                     
 
# 訓練資料
X = np.c_[(.4, -.7),
          (-1.5, -1),
          (-1.4, -.9),
          (-1.3, -1.2),
          (-1.1, -.2),
          (-1.2, -.4),
          (-.5, 1.2),
          (-1.5, 2.1),
          (1, 1),
          # --
          (1.3, .8),
          (1.2, .5),
          (.2, -2),
          (.5, -2.4),
          (.2, -2.3),
          (0, -2.7),
          (1.3, 2.1)].T
Y = np.r_[[0] * 8 + [1] * 8]
 
# C 越大表示越無法容忍錯誤
C = 1
# fit 表示訓練
# x^Tx'
g_svm_linear = svm.SVC(kernel='linear', C=C).fit(X, Y)
# (5+10x^Tx')^3
g_svm_poly = svm.SVC(kernel='poly', degree=3, coef0=5, gamma=10, C=C).fit(X, Y)
# exp(-2|x-x'|^2)
g_svm_rbf = svm.SVC(kernel='rbf', gamma=2, C=C).fit(X, Y)
 
# title for the plots
titles = ['linear kernel => $\mathbf{x}^T\mathbf{x}\'$',
          'polynomial kernel => $(5+10\mathbf{x}^T\mathbf{x}\')^3$',
          'Gaussian kernel => $e^{(-2|\mathbf{x}-\mathbf{x}\'|^2)}$',]
 
# 產生 meshgrid，共 200x100 的點
XX1, XX2 = np.mgrid[-2:2:200j, -3:3:100j]
 
for i, g_svm in enumerate([g_svm_linear, g_svm_poly, g_svm_rbf]):
    # 5-Fold Cross Validation
    scores = cross_val_score(g_svm, X, Y, cv=5)
    # 平均埴
    m = scores.mean()
    # 標準差
    sd = scores.std()
    
    plt.subplot(3, 1, i + 1)
    # 調整之間的空白高度
    plt.subplots_adjust(hspace=.6)
    
    # 代進值，得到距離
    # 回傳判斷結果
    YY = g_svm.predict(np.c_[XX1.ravel(), XX2.ravel()])
    # 重新排列結果，符合 XX1
    YY = YY.reshape(XX1.shape)  
 
    # 畫圖，contour 不填滿顏色，contourf 填滿顏色
    plt.contourf(XX1, XX2, YY, cmap=plt.cm.bone, alpha=0.5)
    
    # 得到 free SV 的距離
    margin = max(g_svm.decision_function(g_svm.support_vectors_))
    # 只取足夠距離的 free SV
    index0 = g_svm.decision_function(X[g_svm.support_[Y[g_svm.support_]==0]])+margin<0.1
    index1 = g_svm.decision_function(X[g_svm.support_[Y[g_svm.support_]==1]])-margin<0.1
    index = np.r_[index0, index1]
    
    # 畫出所有點
    plt.scatter(X[:, 0], X[:, 1], c=Y, cmap=plt.cm.Paired)
    # 將 free support vector 標示出來
    plt.scatter(g_svm.support_vectors_[index, 0], g_svm.support_vectors_[index, 1], color='g', linewidths=3, linestyle='-', s=100, facecolors='none')
 
    
    # 回傳距離
    YY = g_svm.decision_function(np.c_[XX1.ravel(), XX2.ravel()])
    # 重新排列結果，符合 XX1
    YY = YY.reshape(XX1.shape)  
    # 畫出界線
    plt.contour(XX1, XX2, YY, colors=['k', 'k', 'k'], linestyles=['--', '-', '--'], levels=[-margin, 0, margin])
    # 標題
    plt.title('{} Accuracy: {:0.2f}$\pm${:0.2f}'.format(titles[i],m,sd*3))
 
plt.show()

參考

sklearn.svm.SVC