- 取得連結
- 以電子郵件傳送
- 其他應用程式
ML：基礎技法學習
Package：scikit-learn
課程：機器學習技法
簡介：第四講 soft-margin SVM (support vector machine)
兩組 complementary slackness
橫軸為 C，縱軸為 \(\gamma\)，\(E_{cv}\) 對於 SVM 非常常用
因上面的式子只是表達其錯誤上限，實際上的錯誤還是未知
實際上是用來排除不合理的 model，再進行 \(E_{cv}\) 的計算
Package：scikit-learn
課程：機器學習技法
簡介：第四講 soft-margin SVM (support vector machine)
建議的 Library
soft-margin SVM primal
$$
\begin{align*}
\underset{b,\mathbf{w},\boldsymbol\xi}{min} &\ \ \frac{1}{2}\mathbf{w}^T\mathbf{w}+C\cdot \sum_{n=1}^{N}\xi _n\\
subject\ to &\ \ y_n(\mathbf{w}^T\mathbf{x}_n+b) \geq 1-\xi _n\ and\ \xi _n\geq 0\ for\ all\ n
\end{align*}
$$
QP of \(\tilde{d}+1+N\) 個變數，\(2N\) 個條件
從第一講得知
$$ \begin{align*} \underset{b,\mathbf{w}}{min} &\ \ \frac{1}{2}\mathbf{w}^T\mathbf{w}\\ subject\ to &\ \ y_n(\mathbf{w}^T\mathbf{z}_n+b) \geq 1\ for\ all\ n \end{align*} $$ 從 Pocket 得知，希望得到最小的錯誤總數
$$ \underset{b,\mathbf{w}}{min}\sum_{n=1}^{N}\left [ y_n\neq sign(\mathbf{w^Tz}_n+b) \right ] $$ 將兩者合併，並加入 C 參數，控制 trade-off
看是以 large margin 為主，還是 noise tolerance
$$ \begin{align*} \underset{b,\mathbf{w}}{min} &\ \ \frac{1}{2}\mathbf{w}^T\mathbf{w}+C\cdot \sum_{n=1}^{N}\left [ y_n\neq sign(\mathbf{w^Tz}_n+b) \right ]\\ s.t. &\ \ y_n(\mathbf{w}^T\mathbf{z}_n+b) \geq 1\ for\ correct\ n \\ &\ \ y_n(\mathbf{w}^T\mathbf{z}_n+b) \geq -\infty \ for\ incorrect\ n \end{align*} $$ 可再簡化為
$$ \begin{align*} \underset{b,\mathbf{w}}{min} &\ \ \frac{1}{2}\mathbf{w}^T\mathbf{w}+C\cdot \sum_{n=1}^{N}\left [ y_n\neq sign(\mathbf{w^Tz}_n+b) \right ]\\ s.t. &\ \ y_n(\mathbf{w}^T\mathbf{z}_n+b) \geq 1-\infty\cdot \left [ y_n\neq sign(\mathbf{w^Tz}_n+b) \right ]\ for\ all\ n \\ \end{align*} $$ \(\left [ y_n\neq sign(\mathbf{w^Tz}_n+b) \right ]\) 不是 linear，所以不再是 QP
而且也無法分辨錯誤的距離大小
若改成記錄違反 margin 的距離呢？並用此取代計數錯誤的數目
當 \(y_n=\pm 1\)，距離可為 \(margin(b,\mathbf{w})=\frac{1}{\left \| \mathbf{w} \right \|} y_n(\mathbf{w}^T\mathbf{x}_n+b)\)
可以以後面那項為代表，以 \(\xi_n\) 表示離 \(y_n(\mathbf{w}^T\mathbf{z}_n+b)=1\) 有多遠，可得
$$ \begin{align*} \underset{b,\mathbf{w},\boldsymbol\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) \geq 1-\xi_n\ and\ \xi_n\geq 0\ for\ all\ n \\ \end{align*} $$ 有 \(\mathbf{w}\) 跟 \(b\)，共 \(\tilde{d}+1\) 個變數，再加上 \(N\) 個 \(\xi_n\)
並有兩個絛件，各有 \(N\) 個
$$ \begin{align*} \underset{b,\mathbf{w}}{min} &\ \ \frac{1}{2}\mathbf{w}^T\mathbf{w}\\ subject\ to &\ \ y_n(\mathbf{w}^T\mathbf{z}_n+b) \geq 1\ for\ all\ n \end{align*} $$ 從 Pocket 得知，希望得到最小的錯誤總數
$$ \underset{b,\mathbf{w}}{min}\sum_{n=1}^{N}\left [ y_n\neq sign(\mathbf{w^Tz}_n+b) \right ] $$ 將兩者合併，並加入 C 參數，控制 trade-off
看是以 large margin 為主，還是 noise tolerance
$$ \begin{align*} \underset{b,\mathbf{w}}{min} &\ \ \frac{1}{2}\mathbf{w}^T\mathbf{w}+C\cdot \sum_{n=1}^{N}\left [ y_n\neq sign(\mathbf{w^Tz}_n+b) \right ]\\ s.t. &\ \ y_n(\mathbf{w}^T\mathbf{z}_n+b) \geq 1\ for\ correct\ n \\ &\ \ y_n(\mathbf{w}^T\mathbf{z}_n+b) \geq -\infty \ for\ incorrect\ n \end{align*} $$ 可再簡化為
$$ \begin{align*} \underset{b,\mathbf{w}}{min} &\ \ \frac{1}{2}\mathbf{w}^T\mathbf{w}+C\cdot \sum_{n=1}^{N}\left [ y_n\neq sign(\mathbf{w^Tz}_n+b) \right ]\\ s.t. &\ \ y_n(\mathbf{w}^T\mathbf{z}_n+b) \geq 1-\infty\cdot \left [ y_n\neq sign(\mathbf{w^Tz}_n+b) \right ]\ for\ all\ n \\ \end{align*} $$ \(\left [ y_n\neq sign(\mathbf{w^Tz}_n+b) \right ]\) 不是 linear，所以不再是 QP
而且也無法分辨錯誤的距離大小
若改成記錄違反 margin 的距離呢？並用此取代計數錯誤的數目
當 \(y_n=\pm 1\)，距離可為 \(margin(b,\mathbf{w})=\frac{1}{\left \| \mathbf{w} \right \|} y_n(\mathbf{w}^T\mathbf{x}_n+b)\)
可以以後面那項為代表，以 \(\xi_n\) 表示離 \(y_n(\mathbf{w}^T\mathbf{z}_n+b)=1\) 有多遠，可得
$$ \begin{align*} \underset{b,\mathbf{w},\boldsymbol\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) \geq 1-\xi_n\ and\ \xi_n\geq 0\ for\ all\ n \\ \end{align*} $$ 有 \(\mathbf{w}\) 跟 \(b\)，共 \(\tilde{d}+1\) 個變數，再加上 \(N\) 個 \(\xi_n\)
並有兩個絛件，各有 \(N\) 個
soft-margin SVM dual
$$
\begin{align*}
\underset{\boldsymbol{\alpha}}{min} &\ \ \ \frac{1}{2}\sum_{n=1}^{N}\sum_{m=1}^{N}\alpha _n \alpha _m y_ny_m\mathbf{z}_n^T\mathbf{z}_m-\sum_{n=1}^{N}\alpha _n\\
subject\ to &\ \ \ \sum_{n=1}^{N}y_n \alpha _n=0;\\
&\ \ \ C\geq \alpha _n \geq0,for\ n=1,2,\cdots ,N\\
implicitly &\ \ \ \mathbf{w}=\sum_{n=1}^{N}\alpha _n y_n\mathbf{z}_n;\\
&\ \ \ \beta _n=C-\alpha _n,for\ n=1,2,\cdots ,N
\end{align*}
$$
QP of \(N\) 個變數，\(2N+1\) 個條件
利用 Lagrange multipliers，隱藏限制條件，此處將 \(\lambda _n\) 用 \(\alpha _n\) & \(\beta_n\) 取代
$$ L(b,\mathbf{w},\boldsymbol\xi,\boldsymbol\alpha,\boldsymbol\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 \geq 0,\beta _n \geq 0}{max}\ L(b,\mathbf{w},\boldsymbol\xi,\boldsymbol\alpha,\boldsymbol\beta)\) 會發現
$$ SVM\equiv \underset{b,\mathbf{w},\boldsymbol\xi}{min}\left (\underset{all\ \alpha _n \geq 0,\beta _n \geq 0}{max}\ L(b,\mathbf{w},\boldsymbol\xi,\boldsymbol\alpha,\boldsymbol\beta) \right )=\underset{b,\mathbf{w},\boldsymbol\xi}{min}\left (\infty\ if\ violate;\frac{1}{2}\mathbf{w}^T\mathbf{w}\ if\ feasible \right ) $$
此時 \((b,\mathbf{w},\boldsymbol\xi)\) 仍在式子最外面，如何把它跟裡面的 \(\alpha _n,\beta _n \) 交換呢？
這樣才能初步得到 2N 個變數的式子
任取一個 \(\boldsymbol{\alpha}',\boldsymbol{\beta}'\) with \({\alpha}'_n \ge 0,{\beta}'_n \ge 0\)，因取 max 一定比任意還大，可得下式
\(\underset{b,\mathbf{w},\boldsymbol\xi}{min}\left (\underset{all\ \alpha _n \geq 0,\beta _n \geq 0}{max}\ L(b,\mathbf{w},\boldsymbol\xi,\boldsymbol\alpha,\boldsymbol\beta) \right ) \geq \underset{b,\mathbf{w},\boldsymbol\xi}{min}\ L(b,\mathbf{w},\boldsymbol\xi,\boldsymbol{\alpha}',\boldsymbol{\beta}')\)
那如果對 \(\boldsymbol{\alpha}' \ge 0,\boldsymbol{\beta}' \ge 0\) 取 max，也不影響此等式，如下
\(\underset{b,\mathbf{w},\boldsymbol\xi}{min}\left (\underset{all\ \alpha _n \geq 0,\beta _n \geq 0}{max}\ L(b,\mathbf{w},\boldsymbol\xi,\boldsymbol\alpha,\boldsymbol\beta) \right ) \geq \underset{Lagrange\ dual\ problem}{\underbrace{\underset{all\ {\alpha}' _n \geq 0,{\beta}' _n \geq 0}{max}\left (\underset{b,\mathbf{w},\boldsymbol\xi}{min}\ L(b,\mathbf{w},\boldsymbol\xi,\boldsymbol{\alpha}',\boldsymbol{\beta}') \right )\overset{\boldsymbol{\alpha}'=\boldsymbol\alpha,\boldsymbol{\beta}'=\boldsymbol\beta}{\rightarrow} \underset{all\ \alpha _n \geq 0,\beta _n \geq 0}{max}\left (\underset{b,\mathbf{w},\boldsymbol\xi}{min}\ L(b,\mathbf{w},\boldsymbol\xi,\boldsymbol\alpha,\boldsymbol\beta) \right )}}\)
比較直覺的想法，就像是「從最大的一群中取最小」一定 \(\ge\) 「從最小的一群中取最大」
$$ \underset{original(primal))\ SVM}{\underbrace{\underset{b,\mathbf{w},\boldsymbol\xi}{min}\left (\underset{all\ \alpha _n \geq 0,\beta _n \geq 0}{max}\ L(b,\mathbf{w},\boldsymbol\xi,\boldsymbol\alpha,\boldsymbol\beta) \right )}} \geq \underset{Lagrange\ dual}{\underbrace{ \underset{all\ \alpha _n \geq 0,\beta _n \geq 0}{max}\left (\underset{b,\mathbf{w},\boldsymbol\xi}{min}\ L(b,\mathbf{w},\boldsymbol\xi,\boldsymbol\alpha,\boldsymbol\beta) \right )}} $$ 目前的關係稱作 \(\ge\) weak duality
但這還不夠，最好是 \(=\) strong duality，才能初步得到 2N 個變數的式子
幸運的是，在 QP 中，只要滿足以下條件，便是 strong duality
$$ \underset{all\ \alpha _n \geq 0,\beta _n \geq 0}{max}\left (\underset{b,\mathbf{w},\boldsymbol\xi}{min}\ \underset{L(b,\mathbf{w},\boldsymbol\xi,\boldsymbol\alpha,\boldsymbol\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},\boldsymbol\xi)\) 拿掉呢？
內部的問題，當最佳化時，必定符合
$$ \begin{align*} \frac{\partial L(b,\mathbf{w},\boldsymbol\xi,\boldsymbol\alpha,\boldsymbol\beta)}{\partial b}&=0=-\sum_{n=1}^{N}\alpha _ny_n \Rightarrow \sum_{n=1}^{N}\alpha _ny_n=0\\ \frac{\partial L(b,\mathbf{w},\boldsymbol\xi,\boldsymbol\alpha,\boldsymbol\beta)}{\partial \mathbf{w}}&=\mathbf{0}=\mathbf{w}-\sum_{n=1}^{N}\alpha _ny_n\mathbf{z}_n \Rightarrow \mathbf{w}=\sum_{n=1}^{N}\alpha _ny_n\mathbf{z}_n\\ \frac{\partial L(b,\mathbf{w},\boldsymbol\xi,\boldsymbol\alpha,\boldsymbol\beta)}{\partial \xi_n}&=0=C-\alpha _n-\beta _n \Rightarrow \beta_n=C-\alpha_n\\ \end{align*} $$ 從以上的這些條件，可得
$$ \begin{align*} dual&=\underset{all\ \alpha _n \geq 0,\beta _n \geq 0}{max}\left (\underset{b,\mathbf{w},\boldsymbol\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) \right )\\ &=\underset{all\ \alpha _n \geq 0,\beta _n \geq 0}{max}\left (\underset{b,\mathbf{w},\boldsymbol\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) \right )\\ &=\underset{all\ \alpha _n \geq 0,\beta _n \geq 0}{max}\left (\underset{b,\mathbf{w},\boldsymbol\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)) \right )\\ [\because 0=C-\alpha _n-\beta _n]&=\underset{all\ \alpha _n \geq 0,\beta _n \geq 0,\beta _n=C-\alpha _n}{max}\left (\underset{b,\mathbf{w},\boldsymbol\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)) \right )\\ [\because \beta _n \ge 0\Rightarrow \alpha_n \le C]&=\underset{all\ C \ge \alpha _n \geq 0,\ \beta _n=C-\alpha _n}{max}\left (\underset{b,\mathbf{w},\boldsymbol\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)) \right )\\ &= \underset{all\ C \ge \alpha _n \geq 0,\ \beta _n=C-\alpha _n}{max}\left (\underset{b,\mathbf{w},\boldsymbol\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 _ny_n\cdot b \right )\\ [\because \sum_{n=1}^{N}\alpha _ny_n=0] &= \underset{all\ C \ge \alpha _n \geq 0,\ \beta _n=C-\alpha _n,\ \sum_{n=1}^{N}\alpha _ny_n=0}{max}\left (\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) \right )\\ &= \underset{all\ C \ge \alpha _n \geq 0,\ \beta _n=C-\alpha _n,\ \sum_{n=1}^{N}\alpha _ny_n=0}{max}\left (\underset{b,\mathbf{w},\boldsymbol\xi}{min}\ \ \frac{1}{2}\mathbf{w}^T\mathbf{w}+\sum_{n=1}^{N}\alpha _n- \sum_{n=1}^{N}\alpha _ny_n\mathbf{w}^T\mathbf{z}_n \right )\\ &= \underset{all\ C \ge \alpha _n \geq 0,\ \beta _n=C-\alpha _n,\ \sum_{n=1}^{N}\alpha _ny_n=0}{max}\left (\underset{b,\mathbf{w},\boldsymbol\xi}{min}\ \ \frac{1}{2}\mathbf{w}^T\mathbf{w}+\sum_{n=1}^{N}\alpha _n- \mathbf{w}^T\sum_{n=1}^{N}\alpha _ny_n\mathbf{z}_n \right )\\ [\because \mathbf{w}=\sum_{n=1}^{N}\alpha _ny_n\mathbf{z}_n] &= \underset{all\ C \ge \alpha _n \geq 0,\ \beta _n=C-\alpha _n,\ \sum_{n=1}^{N}\alpha _ny_n=0,\ \mathbf{w}=\sum_{n=1}^{N}\alpha _ny_n\mathbf{z}_n}{max}\left (\underset{b,\mathbf{w},\boldsymbol\xi}{min}\ \ \frac{1}{2}\mathbf{w}^T\mathbf{w}+\sum_{n=1}^{N}\alpha _n- \mathbf{w}^T\mathbf{w} \right )\\ &= \underset{all\ C \ge \alpha _n \geq 0,\ \beta _n=C-\alpha _n,\ \sum_{n=1}^{N}\alpha _ny_n=0,\ \mathbf{w}=\sum_{n=1}^{N}\alpha _ny_n\mathbf{z}_n}{max}\left (\underset{b,\mathbf{w},\boldsymbol\xi}{min}\ \ -\frac{1}{2}\mathbf{w}^T\mathbf{w}+\sum_{n=1}^{N}\alpha _n \right )\\ &= \underset{all\ C \ge \alpha _n \geq 0,\ \beta _n=C-\alpha _n,\ \sum_{n=1}^{N}\alpha _ny_n=0,\ \mathbf{w}=\sum_{n=1}^{N}\alpha _ny_n\mathbf{z}_n}{max}\left (\underset{b,\mathbf{w},\boldsymbol\xi}{min}\ \ -\frac{1}{2}\left \| \sum_{n=1}^{N}\alpha _ny_n\mathbf{z}_n \right \|^2+\sum_{n=1}^{N}\alpha _n \right )\\ [\because no\ b, \mathbf{w}, \boldsymbol\xi\ remove\ min] &= \underset{all\ C \ge \alpha _n \geq 0,\ \beta _n=C-\alpha _n,\ \sum_{n=1}^{N}\alpha _ny_n=0,\ \mathbf{w}=\sum_{n=1}^{N}\alpha _ny_n\mathbf{z}_n}{max}\ \ -\frac{1}{2}\left \| \sum_{n=1}^{N}\alpha _ny_n\mathbf{z}_n \right \|^2+\sum_{n=1}^{N}\alpha _n\\ &= \underset{all\ C \ge \alpha _n \geq 0,\ \beta _n=C-\alpha _n,\ \sum_{n=1}^{N}\alpha _ny_n=0,\ \mathbf{w}=\sum_{n=1}^{N}\alpha _ny_n\mathbf{z}_n}{min}\ \ \frac{1}{2}\left \| \sum_{n=1}^{N}\alpha _ny_n\mathbf{z}_n \right \|^2-\sum_{n=1}^{N}\alpha _n\\ &= \underset{all\ C \ge \alpha _n \geq 0,\ \beta _n=C-\alpha _n,\ \sum_{n=1}^{N}\alpha _ny_n=0,\ \mathbf{w}=\sum_{n=1}^{N}\alpha _ny_n\mathbf{z}_n}{min}\ \ \frac{1}{2} \sum_{n=1}^{N}\alpha _ny_n\mathbf{z}_n^T\left (\sum_{m=1}^{N}\alpha _my_m\mathbf{z}_m \right ) -\sum_{n=1}^{N}\alpha _n\\ &= \underset{all\ C \ge \alpha _n \geq 0,\ \beta _n=C-\alpha _n,\ \sum_{n=1}^{N}\alpha _ny_n=0,\ \mathbf{w}=\sum_{n=1}^{N}\alpha _ny_n\mathbf{z}_n}{min}\ \ \frac{1}{2} \sum_{n=1}^{N}\sum_{m=1}^{N}\alpha _n\alpha _my_ny_m\mathbf{z}_n^T\mathbf{z}_m -\sum_{n=1}^{N}\alpha _n\\ \end{align*} $$
將限制條件移出
$$ \begin{align*} \underset{\boldsymbol{\alpha}}{min} &\ \ \ \frac{1}{2}\sum_{n=1}^{N}\sum_{m=1}^{N}\alpha _n \alpha _m y_ny_m\mathbf{z}_n^T\mathbf{z}_m-\sum_{n=1}^{N}\alpha _n\\ subject\ to &\ \ \ \sum_{n=1}^{N}y_n \alpha _n=0;\\ &\ \ \ C\geq \alpha _n \geq0,for\ n=1,2,\cdots ,N\\ implicitly &\ \ \ \mathbf{w}=\sum_{n=1}^{N}\alpha _n y_n\mathbf{z}_n;\\ &\ \ \ \beta _n=C-\alpha _n,for\ n=1,2,\cdots ,N \end{align*} $$ 求 \(\alpha\) 共 \(N\) 個變數
限制條件 \(\alpha_n\) 有 \(2N\) 個，加上 \(\sum_{n=1}^{N}y_n \alpha _n=0\)，共 \(2N+1\)
與 Hard margin 只差在 \(\alpha_n\) 有上限限制 \(C\)$$ L(b,\mathbf{w},\boldsymbol\xi,\boldsymbol\alpha,\boldsymbol\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 \geq 0,\beta _n \geq 0}{max}\ L(b,\mathbf{w},\boldsymbol\xi,\boldsymbol\alpha,\boldsymbol\beta)\) 會發現
- \((b,\mathbf{w},\boldsymbol\xi)\) 違反限制條件時，會導致
- \(1-\xi _n- y_n(\mathbf{w}^T\mathbf{z}_n+b)>0\)
又因 \(L(b,\mathbf{w},\boldsymbol\xi,\boldsymbol\alpha,\boldsymbol\beta) \) 針對 \(\alpha _n \) 取 max 的緣故，\(\alpha _n \) 越大越好 - \(-\xi _n>0\)
又因 \(L(b,\mathbf{w},\boldsymbol\xi,\boldsymbol\alpha,\boldsymbol\beta) \) 針對 \(\beta _n \) 取 max 的緣故，\(\beta _n \) 越大越好 - 使得 \(L(b,\mathbf{w},\boldsymbol\xi,\boldsymbol\alpha,\boldsymbol\beta)\rightarrow \infty \)
- \((b,\mathbf{w},\boldsymbol\xi)\) 符合限制條件時，會導致
- \(1- \xi_n - y_n(\mathbf{w}^T\mathbf{z}_n+b) \leq 0\)
又因 \(L(b,\mathbf{w},\boldsymbol\xi,\boldsymbol\alpha,\boldsymbol\beta) \) 針對 \(\alpha _n \) 取 max 的緣故，\(\alpha _n \) 與 \(1- \xi_n- y_n(\mathbf{w}^T\mathbf{z}_n+b)\) 兩者至少有一個必須為 0 - \(-\xi _n \leq 0\)
又因 \(L(b,\mathbf{w},\boldsymbol\xi,\boldsymbol\alpha,\boldsymbol\beta) \) 針對 \(\beta _n \) 取 max 的緣故，\(\beta _n \) 與 \(- \xi_n\) 兩者至少有一個必須為 0 - 使得 \(L(b,\mathbf{w},\boldsymbol\xi,\boldsymbol\alpha,\boldsymbol\beta)\rightarrow \frac{1}{2}\mathbf{w}^T\mathbf{w} \)
$$ SVM\equiv \underset{b,\mathbf{w},\boldsymbol\xi}{min}\left (\underset{all\ \alpha _n \geq 0,\beta _n \geq 0}{max}\ L(b,\mathbf{w},\boldsymbol\xi,\boldsymbol\alpha,\boldsymbol\beta) \right )=\underset{b,\mathbf{w},\boldsymbol\xi}{min}\left (\infty\ if\ violate;\frac{1}{2}\mathbf{w}^T\mathbf{w}\ if\ feasible \right ) $$
此時 \((b,\mathbf{w},\boldsymbol\xi)\) 仍在式子最外面，如何把它跟裡面的 \(\alpha _n,\beta _n \) 交換呢？
這樣才能初步得到 2N 個變數的式子
任取一個 \(\boldsymbol{\alpha}',\boldsymbol{\beta}'\) with \({\alpha}'_n \ge 0,{\beta}'_n \ge 0\)，因取 max 一定比任意還大，可得下式
\(\underset{b,\mathbf{w},\boldsymbol\xi}{min}\left (\underset{all\ \alpha _n \geq 0,\beta _n \geq 0}{max}\ L(b,\mathbf{w},\boldsymbol\xi,\boldsymbol\alpha,\boldsymbol\beta) \right ) \geq \underset{b,\mathbf{w},\boldsymbol\xi}{min}\ L(b,\mathbf{w},\boldsymbol\xi,\boldsymbol{\alpha}',\boldsymbol{\beta}')\)
那如果對 \(\boldsymbol{\alpha}' \ge 0,\boldsymbol{\beta}' \ge 0\) 取 max，也不影響此等式，如下
\(\underset{b,\mathbf{w},\boldsymbol\xi}{min}\left (\underset{all\ \alpha _n \geq 0,\beta _n \geq 0}{max}\ L(b,\mathbf{w},\boldsymbol\xi,\boldsymbol\alpha,\boldsymbol\beta) \right ) \geq \underset{Lagrange\ dual\ problem}{\underbrace{\underset{all\ {\alpha}' _n \geq 0,{\beta}' _n \geq 0}{max}\left (\underset{b,\mathbf{w},\boldsymbol\xi}{min}\ L(b,\mathbf{w},\boldsymbol\xi,\boldsymbol{\alpha}',\boldsymbol{\beta}') \right )\overset{\boldsymbol{\alpha}'=\boldsymbol\alpha,\boldsymbol{\beta}'=\boldsymbol\beta}{\rightarrow} \underset{all\ \alpha _n \geq 0,\beta _n \geq 0}{max}\left (\underset{b,\mathbf{w},\boldsymbol\xi}{min}\ L(b,\mathbf{w},\boldsymbol\xi,\boldsymbol\alpha,\boldsymbol\beta) \right )}}\)
比較直覺的想法，就像是「從最大的一群中取最小」一定 \(\ge\) 「從最小的一群中取最大」
$$ \underset{original(primal))\ SVM}{\underbrace{\underset{b,\mathbf{w},\boldsymbol\xi}{min}\left (\underset{all\ \alpha _n \geq 0,\beta _n \geq 0}{max}\ L(b,\mathbf{w},\boldsymbol\xi,\boldsymbol\alpha,\boldsymbol\beta) \right )}} \geq \underset{Lagrange\ dual}{\underbrace{ \underset{all\ \alpha _n \geq 0,\beta _n \geq 0}{max}\left (\underset{b,\mathbf{w},\boldsymbol\xi}{min}\ L(b,\mathbf{w},\boldsymbol\xi,\boldsymbol\alpha,\boldsymbol\beta) \right )}} $$ 目前的關係稱作 \(\ge\) weak duality
但這還不夠，最好是 \(=\) strong duality，才能初步得到 2N 個變數的式子
幸運的是，在 QP 中，只要滿足以下條件，便是 strong duality
- convex primal (原來的問題為 convex)
- feasible primal (原來的問題有解的，也就是線性可分)
- linear constraints (限制條件為線性的)
$$ \underset{all\ \alpha _n \geq 0,\beta _n \geq 0}{max}\left (\underset{b,\mathbf{w},\boldsymbol\xi}{min}\ \underset{L(b,\mathbf{w},\boldsymbol\xi,\boldsymbol\alpha,\boldsymbol\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},\boldsymbol\xi)\) 拿掉呢？
內部的問題，當最佳化時，必定符合
$$ \begin{align*} \frac{\partial L(b,\mathbf{w},\boldsymbol\xi,\boldsymbol\alpha,\boldsymbol\beta)}{\partial b}&=0=-\sum_{n=1}^{N}\alpha _ny_n \Rightarrow \sum_{n=1}^{N}\alpha _ny_n=0\\ \frac{\partial L(b,\mathbf{w},\boldsymbol\xi,\boldsymbol\alpha,\boldsymbol\beta)}{\partial \mathbf{w}}&=\mathbf{0}=\mathbf{w}-\sum_{n=1}^{N}\alpha _ny_n\mathbf{z}_n \Rightarrow \mathbf{w}=\sum_{n=1}^{N}\alpha _ny_n\mathbf{z}_n\\ \frac{\partial L(b,\mathbf{w},\boldsymbol\xi,\boldsymbol\alpha,\boldsymbol\beta)}{\partial \xi_n}&=0=C-\alpha _n-\beta _n \Rightarrow \beta_n=C-\alpha_n\\ \end{align*} $$ 從以上的這些條件，可得
$$ \begin{align*} dual&=\underset{all\ \alpha _n \geq 0,\beta _n \geq 0}{max}\left (\underset{b,\mathbf{w},\boldsymbol\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) \right )\\ &=\underset{all\ \alpha _n \geq 0,\beta _n \geq 0}{max}\left (\underset{b,\mathbf{w},\boldsymbol\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) \right )\\ &=\underset{all\ \alpha _n \geq 0,\beta _n \geq 0}{max}\left (\underset{b,\mathbf{w},\boldsymbol\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)) \right )\\ [\because 0=C-\alpha _n-\beta _n]&=\underset{all\ \alpha _n \geq 0,\beta _n \geq 0,\beta _n=C-\alpha _n}{max}\left (\underset{b,\mathbf{w},\boldsymbol\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)) \right )\\ [\because \beta _n \ge 0\Rightarrow \alpha_n \le C]&=\underset{all\ C \ge \alpha _n \geq 0,\ \beta _n=C-\alpha _n}{max}\left (\underset{b,\mathbf{w},\boldsymbol\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)) \right )\\ &= \underset{all\ C \ge \alpha _n \geq 0,\ \beta _n=C-\alpha _n}{max}\left (\underset{b,\mathbf{w},\boldsymbol\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 _ny_n\cdot b \right )\\ [\because \sum_{n=1}^{N}\alpha _ny_n=0] &= \underset{all\ C \ge \alpha _n \geq 0,\ \beta _n=C-\alpha _n,\ \sum_{n=1}^{N}\alpha _ny_n=0}{max}\left (\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) \right )\\ &= \underset{all\ C \ge \alpha _n \geq 0,\ \beta _n=C-\alpha _n,\ \sum_{n=1}^{N}\alpha _ny_n=0}{max}\left (\underset{b,\mathbf{w},\boldsymbol\xi}{min}\ \ \frac{1}{2}\mathbf{w}^T\mathbf{w}+\sum_{n=1}^{N}\alpha _n- \sum_{n=1}^{N}\alpha _ny_n\mathbf{w}^T\mathbf{z}_n \right )\\ &= \underset{all\ C \ge \alpha _n \geq 0,\ \beta _n=C-\alpha _n,\ \sum_{n=1}^{N}\alpha _ny_n=0}{max}\left (\underset{b,\mathbf{w},\boldsymbol\xi}{min}\ \ \frac{1}{2}\mathbf{w}^T\mathbf{w}+\sum_{n=1}^{N}\alpha _n- \mathbf{w}^T\sum_{n=1}^{N}\alpha _ny_n\mathbf{z}_n \right )\\ [\because \mathbf{w}=\sum_{n=1}^{N}\alpha _ny_n\mathbf{z}_n] &= \underset{all\ C \ge \alpha _n \geq 0,\ \beta _n=C-\alpha _n,\ \sum_{n=1}^{N}\alpha _ny_n=0,\ \mathbf{w}=\sum_{n=1}^{N}\alpha _ny_n\mathbf{z}_n}{max}\left (\underset{b,\mathbf{w},\boldsymbol\xi}{min}\ \ \frac{1}{2}\mathbf{w}^T\mathbf{w}+\sum_{n=1}^{N}\alpha _n- \mathbf{w}^T\mathbf{w} \right )\\ &= \underset{all\ C \ge \alpha _n \geq 0,\ \beta _n=C-\alpha _n,\ \sum_{n=1}^{N}\alpha _ny_n=0,\ \mathbf{w}=\sum_{n=1}^{N}\alpha _ny_n\mathbf{z}_n}{max}\left (\underset{b,\mathbf{w},\boldsymbol\xi}{min}\ \ -\frac{1}{2}\mathbf{w}^T\mathbf{w}+\sum_{n=1}^{N}\alpha _n \right )\\ &= \underset{all\ C \ge \alpha _n \geq 0,\ \beta _n=C-\alpha _n,\ \sum_{n=1}^{N}\alpha _ny_n=0,\ \mathbf{w}=\sum_{n=1}^{N}\alpha _ny_n\mathbf{z}_n}{max}\left (\underset{b,\mathbf{w},\boldsymbol\xi}{min}\ \ -\frac{1}{2}\left \| \sum_{n=1}^{N}\alpha _ny_n\mathbf{z}_n \right \|^2+\sum_{n=1}^{N}\alpha _n \right )\\ [\because no\ b, \mathbf{w}, \boldsymbol\xi\ remove\ min] &= \underset{all\ C \ge \alpha _n \geq 0,\ \beta _n=C-\alpha _n,\ \sum_{n=1}^{N}\alpha _ny_n=0,\ \mathbf{w}=\sum_{n=1}^{N}\alpha _ny_n\mathbf{z}_n}{max}\ \ -\frac{1}{2}\left \| \sum_{n=1}^{N}\alpha _ny_n\mathbf{z}_n \right \|^2+\sum_{n=1}^{N}\alpha _n\\ &= \underset{all\ C \ge \alpha _n \geq 0,\ \beta _n=C-\alpha _n,\ \sum_{n=1}^{N}\alpha _ny_n=0,\ \mathbf{w}=\sum_{n=1}^{N}\alpha _ny_n\mathbf{z}_n}{min}\ \ \frac{1}{2}\left \| \sum_{n=1}^{N}\alpha _ny_n\mathbf{z}_n \right \|^2-\sum_{n=1}^{N}\alpha _n\\ &= \underset{all\ C \ge \alpha _n \geq 0,\ \beta _n=C-\alpha _n,\ \sum_{n=1}^{N}\alpha _ny_n=0,\ \mathbf{w}=\sum_{n=1}^{N}\alpha _ny_n\mathbf{z}_n}{min}\ \ \frac{1}{2} \sum_{n=1}^{N}\alpha _ny_n\mathbf{z}_n^T\left (\sum_{m=1}^{N}\alpha _my_m\mathbf{z}_m \right ) -\sum_{n=1}^{N}\alpha _n\\ &= \underset{all\ C \ge \alpha _n \geq 0,\ \beta _n=C-\alpha _n,\ \sum_{n=1}^{N}\alpha _ny_n=0,\ \mathbf{w}=\sum_{n=1}^{N}\alpha _ny_n\mathbf{z}_n}{min}\ \ \frac{1}{2} \sum_{n=1}^{N}\sum_{m=1}^{N}\alpha _n\alpha _my_ny_m\mathbf{z}_n^T\mathbf{z}_m -\sum_{n=1}^{N}\alpha _n\\ \end{align*} $$
將限制條件移出
- \(\mathbf{w}=\sum_{n=1}^{N}\alpha _ny_n\mathbf{z}_n\) 只是求 \(\mathbf{w}\) 並不限制 \(\boldsymbol\alpha\)
- \(\beta_n=C-\alpha_n\) 只是求 \(\beta_n\) 並不限制 \(\boldsymbol\alpha\)
$$ \begin{align*} \underset{\boldsymbol{\alpha}}{min} &\ \ \ \frac{1}{2}\sum_{n=1}^{N}\sum_{m=1}^{N}\alpha _n \alpha _m y_ny_m\mathbf{z}_n^T\mathbf{z}_m-\sum_{n=1}^{N}\alpha _n\\ subject\ to &\ \ \ \sum_{n=1}^{N}y_n \alpha _n=0;\\ &\ \ \ C\geq \alpha _n \geq0,for\ n=1,2,\cdots ,N\\ implicitly &\ \ \ \mathbf{w}=\sum_{n=1}^{N}\alpha _n y_n\mathbf{z}_n;\\ &\ \ \ \beta _n=C-\alpha _n,for\ n=1,2,\cdots ,N \end{align*} $$ 求 \(\alpha\) 共 \(N\) 個變數
限制條件 \(\alpha_n\) 有 \(2N\) 個，加上 \(\sum_{n=1}^{N}y_n \alpha _n=0\)，共 \(2N+1\)
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{align*} 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_nb &= 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{align*} $$ 但 \(\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{align*} b &= y_n-\mathbf{w}^T\mathbf{z}_s\\ &= y_n-\sum_{n=1}^{N}\alpha _ny_n\mathbf{z}_n^T\mathbf{z}_s\\ &= y_n-\sum_{n=1}^{N}\alpha _ny_nK(\mathbf{z}_n,\mathbf{z}_s)\\ &= y_n-\sum_{SV\ indices\ n}\alpha _ny_nK(\mathbf{z}_n,\mathbf{z}_s)\\ \end{align*} $$
仍會有 overfit 的風險，需小心選取 \((\gamma,C)\)$$ \begin{align*} 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_nb &= 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{align*} $$ 但 \(\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{align*} b &= y_n-\mathbf{w}^T\mathbf{z}_s\\ &= y_n-\sum_{n=1}^{N}\alpha _ny_n\mathbf{z}_n^T\mathbf{z}_s\\ &= y_n-\sum_{n=1}^{N}\alpha _ny_nK(\mathbf{z}_n,\mathbf{z}_s)\\ &= y_n-\sum_{SV\ indices\ n}\alpha _ny_nK(\mathbf{z}_n,\mathbf{z}_s)\\ \end{align*} $$
\(\alpha_n\) 的意義
$$
\begin{align*}
\alpha_n(1- \xi_n- y_n(\mathbf{w}^T\mathbf{z}_n+b))&=0\\
(C-\alpha_n)\xi _n&=0
\end{align*}
$$
- \(\alpha_n=0,\xi_n=0\)
- non SV
- 可能遠離邊界或剛好在邊界上
- \(C>\alpha_n>0,\xi_n=0\)
- \(\square\) free SV
- 剛好在邊界上
- \(\alpha_n=C,\xi_n=1- y_n(\mathbf{w}^T\mathbf{z}_n+b)\) 即是違反的值
- \(\triangle\) bounded SV
- 違反或剛好在邊界上
- 可視情況用在資料的解析上，何者有幫助、何者無幫助、何者可能有 noise
Model Selection
利用 validation 選擇合適的參數橫軸為 C，縱軸為 \(\gamma\)，\(E_{cv}\) 對於 SVM 非常常用
$$
E_{loocv} \leq \frac{\#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} \leq 1\)
所以 \(E_{loocv} \leq \frac{\#SV}{N}\)
下圖為 SV 的個數，但可看出並無法用來挑選最佳 model當選擇的資料 \((\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} \leq 1\)
所以 \(E_{loocv} \leq \frac{\#SV}{N}\)
因上面的式子只是表達其錯誤上限，實際上的錯誤還是未知
實際上是用來排除不合理的 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()
留言
張貼留言