---
tags: 機器學習技法
---

Ch4 Soft-Margin Support Vector Machine
===

## Content
[TOC]

## [Slides & Videos](https://www.csie.ntu.edu.tw/~htlin/mooc/)

## [Motivation and Primal Problem](https://www.youtube.com/watch?v=K7ZcAYXuU_A&list=PLXVfgk9fNX2IQOYPmqjqWsNUFl2kpk1U2&index=15&t=0s)

### Cons of Hard-Margin SVM
- feature transform $\phi$ 太過 powerful
- 硬要 separable => 任何資料都可以 shatter
- 會去 overfit 到 noise 上

### Give Up on Some Examples
- pocket PLA 可以容忍誤差
- 那就跟 hard-margin SVM 結合吧~
- 結合 pocket 和 SVM 後
- 優化目標 $\min_\limits{b,w}\frac 12w^Tw+C\cdot\sum_\limits{n=1}^N 1[\![y_n\neq\text{sign}(w^Tz_n+b)]\!]$
- 權衡兩者的是 hyperparameter $C$
- 條件
- 做對的點還是要符合條件 $y_n(w^Tz_n+b)\geq 1$
- 做錯的點就不管惹 $y_n(w^Tz_n+b)\geq -\infty$

### Soft-Margin SVM
- 現在有了新問題
- 優化 $\min_\limits{b,w}\frac 12w^Tw+C\cdot\sum_\limits{n=1}^N 1[\![y_n\neq\text{sign}(w^Tz_n+b)]\!]$
- 合併兩條件 $y_n(w^Tz_n+b)\geq 1-\infty\cdot 1[\![y_n\neq\text{sign}(w^Tz_n+b)]\!]$
- 根據 $y_n$ 是否等於 $\text{sign}(w^Tz_n+b)$ 分別討論就知道這跟本來條件一樣
- 這樣有兩個缺點
- 不能用 QP 解了 (因為 constraint 不是 linear 的)
- 沒辦法分辨小的 error 或大的 error
- 於是把問題改成
- 優化 $\min_\limits{b,w,\xi}\frac 12w^Tw+C\cdot\sum_\limits{n=1}^N\xi_n$
- $\xi_n$ 表示我們的 point 離那個目標的 boundary 到底有多遠(不是距離，只是表達遠近)
- 把問題變成 minimize 我們犯了多大的錯誤，而不是犯了幾個錯誤
- 這樣就是 quadratic objective 了
- 條件 $y_n(w^Tz_n+b)\geq 1-\xi_n\,\text{ and }\,\xi_n\geq 0,\forall n\in\{1,...,N\}$
- 如果第 $n$ 筆資料合乎本來的 SVM 條件，那這項就是 $y_n(w^Tz_n+b)\geq 1$ 因為 $\xi_n=0$
- 所以當 $\xi_n>0$ 就是不合乎本來條件
- 這樣就是 linear constraint 了
- **思考：那為何 $\xi_n$ 會是「違反的量」？**
- 假設第 $n$ 個 data 有違反，且違反的量是 $a_n$，也就是說 $y_n(w^Tz_n+b)=1-a_n,a_n>0$
- 看看條件可以得到 $1-a_n\geq 1-\xi_n$，移項得到 $\xi_n\geq a_n$
- 然而 objective function 要 minimize $\xi_n$，所以 optimal point 的解 $\xi_n=a_n$。
- > Q: 這樣想應該沒錯吧 @@

- 那麼 $C$ 現在就變成了 large-margin 和 margin violation $\xi_n$ 的 trade-off
- 現在 QP 多了 $N$ 個變數 $\xi_n$ 要解
- $\tilde d+1+N$ 個變數
- $2N$ 個 constraints
- 接下來我們要再移除對 $\tilde d$ 的依賴，跟之前一樣

### Fun Time: Soft-Margin?
- $\xi_1$ 是 $11$ 很直覺
- 思考一下其他答案會有什麼結果 (注意題目說 At the optimal solution)
- $1$ 明顯不符合條件
- $21$ 看起來符合呀，因為 $-10\geq 1-21$，但是因為上面要 minimize $\xi_n$ 所以 optimal point 還是會縮小到 $\xi_1=11$

## [Dual Problem](https://www.youtube.com/watch?v=fTHTqW5Uq4U&list=PLXVfgk9fNX2IQOYPmqjqWsNUFl2kpk1U2&index=15)

### Lagrange Dual
- 現在的問題 (primal problem)
- 優化 $\min_\limits{b,w,\xi}\frac 12w^Tw+C\cdot\sum_\limits{n=1}^N\xi_n$
- 條件 $y_n(w^Tz_n+b)\geq 1-\xi_n\,\text{ and }\,\xi_n\geq 0,\forall n\in\{1,...,N\}$
- 轉化成對偶問題 (dual problem)
- 把**所有 constraint 都移項變成小於等於 0，再乘上 Lagrange Multiplier 就可以丟到 objective function 裡面了**
- > 要變成小於等於 0 是因為我們是要 minimize objective function 吧，如果是 maximize 的話應該要整理成 大於等於 0 的形式
- $\mathcal L(b,w,\xi,\alpha,\beta)=\frac 12w^Tw+C\cdot\sum_\limits{n=1}^N\xi_n\\+\sum_\limits{n=1}^N\alpha_n\cdot(1-\xi_n-y_n(w^Tz_n+b))+\sum_\limits{n=1}^N\beta_n\cdot(-\xi_n)$
- $\xi,\alpha,\beta$ 都是 $N$ 維向量
- 轉化成 Lagrange Dual Problem 之後就可以跟之前一樣用 max-min 的形式寫下來，然後用 KKT condition 簡化這個問題。
- $\max_\limits{\alpha_n\geq 0,\beta_n\geq 0}[\min_\limits{b,w,\xi}\mathcal L(b,w,\xi,\alpha,\beta)]$
- 這邊可以複習
- [Lagrange Multiplier](https://hackmd.io/@johnnyasd12/Hyse98wCS#The-Lagrange-Multiplier)
- [Dual SVM](https://hackmd.io/@johnnyasd12/HkyoeuCRS#Key-Tool-Lagrange-Multipliers)

### Simplify $\xi_n$ and $\beta_n$
- 複習 [KKT condition](https://hackmd.io/@johnnyasd12/HkyoeuCRS#KKT-Optimality-Conditions)
- 利用 dual-inner optimal 偏微分等於 0，可以知道 $\frac{\partial\mathcal L}{\partial\xi_n}=0=C-\alpha_n-\beta_n$，所以 optimal point 的 $\beta_n=C-\alpha_n$
- 又 $\alpha_n\geq 0, \beta_n=C-\alpha_n\geq 0$，如此我們就可以寫成 $0\leq\alpha_n\leq C,\beta_n=C-\alpha_n$
- 把 $\xi_n$ 的項整理在一起，發現係數是 0，所以可以忽略
- 回想：跟之前推導 dual hard-margin SVM 的 $b$ 一樣

### Other Simplifications
- 簡化後，現在的問題 $\max_\limits{0\leq\alpha_n\leq C,\beta_n=C-\alpha_n}[\min_\limits{b,w}\frac 12w^Tw+\sum_n\alpha_n(1-y_n(w^Tz_n+b))]$
- 發現 inner problem 跟之前的 [dual SVM](https://hackmd.io/@johnnyasd12/HkyoeuCRS#Starting-Point-Constrained-to-%E2%80%98Unconstrained%E2%80%99) 一樣啊
- 根本只有 outer problem 的 constraints 不一樣而已
- 所以 inner problem 解法就跟 [dual SVM](https://hackmd.io/@johnnyasd12/HkyoeuCRS#Starting-Point-Constrained-to-%E2%80%98Unconstrained%E2%80%99) 一樣啦

### Standard Soft-Margin SVM Dual
- 現在的對偶問題 dual problem
- 最佳化 $\min_\limits\alpha\frac 12\sum_n\sum_m\alpha_n\alpha_my_ny_mz_n^Tz_m-\sum_n\alpha_n$
- 受限於 $\sum_ny_n\alpha_n=0\\0\leq\alpha_n\leq C,\forall n\in\{1,...,N\}$
- implicitly $w=\sum_n\alpha_ny_nz_n;\\\beta_n=C-\alpha_n,\forall n\in\{1,...,N\}$
- > Q: implicitly 意思?
- 幾乎跟本來 [hard-margin SVM 的 dual 形式](https://hackmd.io/@johnnyasd12/HkyoeuCRS#Dual-Formulation-of-Support-Vector-Machine) 一模一樣，(大概)只有條件不同而已
- 對照一下 
- 就只是多了條件 $\alpha_n\leq C$ 讓它不能無窮大，然後多了一些變數 $\beta_n$，可以直接用 $C-\alpha_n$ 算出來
- **所以 $C$ 就是 $\alpha_n$ 的 upper bound**
- 就是另外一個 convex QP
- $N$ 個 variables
- $2N+1$ 個 constraints

### Fun Time: Soft-Margin SVM Dual
- 所以當 $C$ 增加 $2$，就代表 $\alpha_n$ 的 upper bound 也增加 $2$

## [Messages behind Soft-Margin SVM](https://www.youtube.com/watch?v=5z7ujI3YBBE&list=PLXVfgk9fNX2IQOYPmqjqWsNUFl2kpk1U2&index=16)

### Kernel Soft-Margin SVM
- soft-margin 和 [hard-margin SVM]() 的差異
- **多了 upper-bound 的條件 (就是 $\alpha_n\leq C$)**
- **因為這是一個新的 QP 問題，所以 KKT condition 會不一樣，也因此 $b$ 的算法會不一樣。**
- 其他部份幾乎都跟 hard-margin 一樣
- 可以複習一下本來的 hard-margin SVM QP
- 
- 剩下問題就是 $b$ 怎麼算？

### Solving for $b$
- 回想之前 hard-margin SVM 的 **complementary slackness：Lagrange multiplier 和 primal constraint([回顧](https://hackmd.io/WPBgCzUwTM-d-LR6dBp4zw?both#Lagrange-Dual)) 乘積會是 0**，所以
1. $\alpha_n(1-\xi_n-y_n(w^Tz_n+b))=0$
2. $\beta_n(-\xi_n)=0$ 所以 $(C-\alpha_n)\xi_n=0$
- 看第 1. 點，則可以利用 support vector 計算 $b=y_s-y_s\xi_s-w^Tz_s$
- 但是這樣要先求 $\xi_s$，而 $\xi_s$ 又是違反的量所以要先知道 $b$。雞生蛋蛋生雞？
- 真希望 $y_s\xi_s$ 這項可以不見ㄏㄏ
- 可以啊，我讓 $\xi_s=0$ 不就好了，那根據第 2. 點，這時候 $C-\alpha_n\neq 0$
- 所以只要當 $\alpha_s<C$，就可以直接計算 $b=y_s-w^Tz_s=y_s-\sum_\limits{\text{SV indices}\,n}\alpha_ny_nK(x_n,x_s)$
- 可以回想[這裡](https://hackmd.io/@johnnyasd12/HJ_CkNwJI#Kernel-Transform--Inner-Product)
- 但是如果找不到 $\alpha_s\neq C$ 的話就只能用一堆不等式來解 $b$ 的 range 了。這邊比較複雜就不說ㄌ。
- **像這樣符合 $0<\alpha_n<C$ 的 support vector 又稱為 free support vector (free SV)**

### Soft-Margin Gaussian SVM in Action
- 灰灰的部分是 margin
- $C$ 越大就表示越不能接受錯誤，**而 margin 小一點沒關係**
- 對 noise 的容忍度就更不高 -> 更容易 overfit

### Physical Meaning of $\alpha_n$
- 剛剛的 complementary slackness:
1. $\alpha_n(1-\xi_n-y_n(w^Tz_n+b))=0$
2. $(C-\alpha_n)\xi_n=0$
- **free support vector ($0<\alpha_n<C$)**
- 因為 $0<\alpha_n<C$ 所以根據第 2. 點，$\xi_n=0$
- $\alpha_n\neq 0$ 又 $\xi_n=0$ 所以根據第 1. 點，$1-y_n(w^Tz_n+b)=0$
- 這條件不就剛好在那個胖胖的邊界上了嗎
- **所以 free support vector 就是在 fat boundary 上的那些點(上圖方框)**
- **非 support vector ($\alpha_n=0$)**
- $\xi_n=0$ 沒有任何違反
- 絕大多數都會在 margin 外面，極少數會剛好在 fat boundary 上
- **bounded support vector ($\alpha_n=C$)**
- $\alpha_n\neq 0$ 所以根據第 1. 點，$1-\xi_n-y_n(w^Tz_n+b)=0$
- **$\xi_n=1-y_n(w^Tz_n+b)$ 也就是說 $\xi_n$ 正好紀錄了「違反的量」**
- **所以 bounded support vector 就是有違反 margin 的 vector (上圖三角形)**
- 違反也分兩種：分對(少量違反) & 分錯(大量違反)
- 也是有極少數的情形 $\alpha_n=C$ 的時候它剛剛好在 fat boundary 上
- 這時候 $\xi_n=0$ 吧
- 這樣一來，根據 $\alpha_n$ 就可以分析資料，例如
- 檢查看看哪些 data 可能是有 noise 的 ($\alpha_n=C$ 吧)
- 哪些 data 可能有幫助 ($\alpha_n<C$ 吧)
- 哪些 data 是可有可無的冗員 ($\alpha_n=0$ 吧)

### Fun Time: Messages behind Soft-Margin SVM
- 最好狀況就 bounded SV 全對
- 最差狀況就 bounded SV 全錯

## [Model Selection](https://www.youtube.com/watch?v=ahogAa5Rnmc&list=PLXVfgk9fNX2IQOYPmqjqWsNUFl2kpk1U2&index=17)

### Practical Need: Model Selection
- 橫軸是 $C$，縱軸是 $\gamma$
- 選擇 model 最簡單的工具就 validation

### Selection by Cross Validation
- cross validation 滿常用來挑選 soft-margin SVM

### Leave-One-Out CV Error for SVM
- leave-one-out cross validation error 在 SVM 上有個很有趣的點
- 我們可以證明 $E_{loocv}\leq\dfrac{\text{#SV}}{N}$
- 假設我們用所有 data 訓練出來的 SVM $g$，它的每個 data 分別對應到 optimal value $\alpha_1,...,\alpha_N$
- 而 leave-one-out 第 $n$ 次取出的 validation data $(x_n,y_n)$ 對應到 $\alpha_n$
- > Q: 雖然 slide 上是寫 $(x_N,y_N)$ 不過我覺得小寫 $n$ 比較合適？
- 當 $\alpha_n=0$，則去掉這筆 data 訓練所得到的 SVM $g^-$ 就跟 $g$ 相同，也就是說同一組 $\alpha$ 一樣會是最佳解 -> $e_{non-SV}=0$
- 同理，$e_{SV}\leq 1$
- **所以啦，leave-one-out 平均出來的 error rate 會小於等於 SV 的比例**

### Selection by # SV
- 使用 #SV 來選擇 model 有些地方要注意
- 它不是平滑函數所以難以最佳化
- **它只是 $E_{loocv}$ 的 upper bound**，不代表 error 真的做到最好
- **所以 #SV 通常用來 safety check 如果 cross validation 太花時間**

### Fun Time: Loocv and # SV
- **注意這邊會影響的是 # SV 而不是 # bounded SV**

### Summary
- **我們常常說的 SVM 幾乎就是指 soft-margin SVM**
- 下節會說，如何把類似 SVM 的機制延伸到其他 model