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

Ch2 Dual Support Vector Machine
===

## Content
[TOC]

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

## [Motivation of Dual SVM](https://www.youtube.com/watch?v=VUp-17l03lk&list=PLXVfgk9fNX2IQOYPmqjqWsNUFl2kpk1U2&index=6)

- dual SVM 可以看成 SVM 的另外一種形式

### Non-Linear Support Vector Machine Revisited
- 當 non-linear transformed feature 的維度 $\tilde d$ 很大的時候，QP 就比較難解
- 能不能讓 SVM 不受 $\tilde d$ 限制呢?

### Todo: SVM 'without' $\tilde d$
- 本來的 SVM
- $\tilde d+1$ 個 variables
- $N$ 個 constraints
- 希望解一個對等的問題
- $N$ 個 variables
- $N+1$ 個 constraints
- 這邊其實牽扯到一些滿深入的最佳化理論，等等不會推導，直接說明最佳化理論告訴我們了什麼現象。
- 接下來要解的對等的問題我們稱為原來 SVM 的 **dual problem**

### Key Tool: Lagrange Multipliers
- 複習一下 [Lagrange Multipliers](https://hackmd.io/@johnnyasd12/Hyse98wCS#The-Lagrange-Multiplier) 就是把 constraint 乘上一個係數 $\lambda$ 然後加到 objective function 裡面去 (?)
- 本來給我 $C$ 的話很難解，改成給我 $\lambda$ 就很好解
- 現在 SVM 也會用到 Lagrange Multiplier，只是這次是把 $\lambda$ 當成變數，直接解。
- SVM 裡的每一個條件，就會對應到一個 Lagrange Multiplier
- 所以我們**有 $N$ 個 Lagrange Multiplier**
- 最後就會變成對偶問題 dual problem

### Starting Point: Constrained to 'Unconstrained'
- 之前的 Lagrange Multiplier 我們叫它 $\lambda$，不過在 SVM 的文獻裡面通常叫它 $\alpha$
- 本來的問題
- 目標 $\min_\limits{b,w}\frac 12w^Tw$
- 條件 $1-y_n(w^Tz_n+b)\leq 0 ,\forall n\in\{1,2,...,N\}$
- 為何要**把本來 $y_n(w^Tz_n+b)\geq 1$ 整理成現在小於等於 0 的形式，** 等等就知道
- 用 Lagrange Multiplier 我們就可以把本來的問題寫成看似 unconstrained 的形式
- $\mathcal L(b,w,\alpha)=\frac 12w^Tw+\sum_\limits{n=1}^N\alpha_n(1-y_n(w^Tz_n+b))$
- 注意這裡的 $\alpha$ 是 $N$ 維向量
- 可是這樣改的話我們解的問題就不會跟原本一樣了啊
- 所以我們要把問題改成這樣的架構
- $\min_\limits{b,w}(\max_\limits{\text{all}\,\alpha_n\geq 0}\mathcal L(b,w,\alpha))$
- 這句是什麼意思？就是今天任何一組 $b,w$ 進來我都去調整 $\alpha$，使得 Lagrange function $\mathcal L(b,w,\alpha)$ 最大，之後再去找可以最小化結果的 $b,w$
- 用這樣 min-max 的形式才能保證解的問題跟本來一樣，為什麼呢？
- 如果今天這組 $b,w$ 違反了本來的任何條件(有任何一個 $n$ 它的 $y_n(w^Tz_n+b)\geq 1$，裡面的 $\max$ 那一項就會變無限大，那麼外面的 $\min_\limits{b,w}$ 就不會挑這組 $b,w$
- **如果今天這組 $b,w$ 沒有違反本來的任何條件 (即所有 $1-y_n(w^Tz_n+b)$ 都小於等於 0)，那 $\max$ 那一項會使得所有的 $\alpha_n(1-y_n(w^Tz_n+b))=0$，** 那麼外面 minimize 的就是 $\frac 12w^Tw$ 本身，分開討論如下：
- 當 $1-y_n(w^Tz_n+b)<0$，則 $\alpha_n$ 為了 maximize 就會變成 0
- 當 $1-y_n(w^Tz_n+b)=0$，則 $\alpha_n$ 是多少乘起來都會是 0。***乾那要怎麼選 $\alpha_n$?***
- **也就是說 $1-y_n(w^Tz_n+b)$ 和 $\alpha_n$ 至少其中一個要是 $0$** ，等等講 **KKT condition 會提到，這叫 complementary slackness**
- **這也是為什麼剛剛要把 constraints 整理成小於等於 0 的形式吧**
- 所以我們的 constraints 其實隱藏在 min-max 的 optimization problem 裡面，那麼在做 $b,w$ 的 minimize 的時候，看起來是不需要考慮任何條件的。
- 太神拉~~~~~

### Fun Time: Lagrange Multiplier for SVM

## [Largange Dual SVM](https://www.youtube.com/watch?v=Yhwtvbzg9Fw&list=PLXVfgk9fNX2IQOYPmqjqWsNUFl2kpk1U2&index=7)

### Lagrange Dual Problem
- 好ㄌ我們現在有個新的最佳化問題
- 有個 Lagrange 函數 $\mathcal L(b,w,\alpha)$
- 注意這裡的 $\alpha$ 是 $N$ 維向量
- 要先對 $\alpha$ 做最大化 $\max_\limits{\forall \alpha_n\geq 0}\mathcal L(b,w,\alpha)$
- 再對 $b,w$ 做最小化 $\min_\limits{b,w}\max_\limits{\forall \alpha_n\geq 0}\mathcal L(b,w,\alpha)$
- 最佳化問題 $\min_\limits{b,w}\max_\limits{\forall \alpha_n\geq 0}\mathcal L(b,w,\alpha)$
- 對於任何(符合條件 $\forall \alpha'_n\geq 0$)的 $\alpha'$ 而言，$\max_\limits{\forall \alpha_n\geq 0}\mathcal L(b,w,\alpha)\geq \mathcal L(b,w,\alpha')$
- 在外面包一個 min 不等式也一樣成立$\min_\limits{b,w}\max_\limits{\forall \alpha_n\geq 0}\mathcal L(b,w,\alpha)\geq \min_\limits{b,w}\mathcal L(b,w,\alpha')$
- 既然對於任何的 $\alpha'$ 都成立 $\min_\limits{b,w}\max_\limits{\forall \alpha_n\geq 0}\mathcal L(b,w,\alpha)\geq \min_\limits{b,w}\mathcal L(b,w,\alpha')$
- (注意要符合條件 $\alpha'_n\geq 0,\forall n\in\{1,...,N\}$)
- 那麼當然 $\min_\limits{b,w}\max_\limits{\forall \alpha_n\geq 0}\mathcal L(b,w,\alpha)\geq \max_\limits{\forall\alpha'_n\geq 0}\min_\limits{b,w}\mathcal L(b,w,\alpha')$
- 有謎有發現 **min 跟 max 對調**了嘿嘿
- 那個 $\alpha'$ 的 $'$ 其實可以不用寫
- > Q: WHY??
- **min 跟 max 這樣交換之後的問題稱為 Lagrange dual problem**
- 它是由 Lagrange function 導出來的
- 我把 Lagrange dual problem 解決了，就得到原來問題解法的 **lower bound**，也就是說我最低可以到多低
> 林老师，我觉得第7页的推导稍微有些模糊，觉得这样证明更合适些
L(b1,w1,a1)=min(max(L(b,w,a)))
L(b2,w2,a2)=max(min(L(b,w,a)))
比较L(b1,w1,a2)和L(b1,w1,a1)的关系，因为L(b1,w1,a2) 和L(b1,w1,a1)的b和w相同，而L(b1,w1,a1)是各种a中最大的，所以L(b1,w1,a1)>=L(b1,w1,a2)
比较L(b1,w1,a2)和L(b2,w2,a2)的关系，因为L(b1,w1,a2) 和L(b2,w2,a2)的a相同，而L(b2,w2,a2)是各种b,w中最小的，所以L(b1,w1,a2)>=L(b2,w2,a2)
所以L(b1,w1,a1)>=L(b1,w1,a2)>=L(b2,w2,a2)

### Strong Duality of Quadratic Programming
- 剛剛導出來的這個 $\geq$ 我們稱為 **weak duality**
- 真希望它們是 **strong duality** 的啊，這樣解兩個問題就一樣意思了
- 這樣有什麼好處？右邊的式子解 $b,w$ 變成 unconstrained problem 啦~
- **Quadratic Programming 的理論告訴我們，滿足以下 3 條件，上面那兩個就有 strong duality 的關係**
- convex primal 原本問題是凸的
- feasible 有解的
- 以這個 case 來說就是 $z$ 是 linear separable
- linear constraints
- **strong duality 意思就是說，原本問題(primal)的最佳解 ($b,w,\alpha$) 就是對偶問題(dual)的最佳解。**
- > Q: 這個時候才能把 $\alpha'$ 的 $'$ 拿掉吧?

### Solving Lagrange Dual: Simplifications
- 又換一個問題啦
- $\max_\limits{\forall\alpha_n\geq 0}\min_\limits{b,w}\mathcal L(b,w,\alpha)$
- $\max_\limits{\forall\alpha_n\geq 0}[\min_\limits{b,w}\frac 12w^Tw+\sum_\limits{n=1}^N\alpha_n(1-y_n(w^Tz_n+b))]$
- 現在**裡面的 minimization 是 unconstrained 的，那就代表 optimal point 的 gradient 會是 0**
- optimal point 會滿足 $\frac{\partial\mathcal L(b,w,\alpha)}{\partial b}=0=-\sum_{n=1}^N\alpha_ny_n$
- 既然 optimal point 會滿足 $0=-\sum_{n=1}^N\alpha_ny_n$ 這個條件，代表我就算在 optimization problem 加入這個條件也不影響找到的點。
- 所以現在 optimization problem 變成 $\max_\limits{\forall\alpha_n\geq 0,\sum\alpha_ny_n=0}[\min_\limits{b,w}\frac 12w^Tw+\sum_\limits{n=1}^N\alpha_n(1-y_n(w^Tz_n))]$
- min 的 $b$ 其實可以刪掉因為它的係數和是 $0$
- 可是 $b$ 還是要解啊不然怎麼預測? 晚點會說明

- optimization problem $\max_\limits{\forall\alpha_n\geq 0,\sum\alpha_ny_n=0}[\min_\limits{b,w}\frac 12w^Tw+\sum_\limits{n=1}^N\alpha_n(1-y_n(w^Tz_n))]$
- 這邊其實再做一次跟剛才解 $b$ 相同的操作即可
- unconstrained optimization 的 optimal point 微分等於 0 解得 $w_i=\sum_{n=1}^N\alpha_ny_nz_{n,i}$，然後直接把它放到 outer problem 的 constraint
- 利用上面的 constraint 化簡一下得到 optimization problem $\max_\limits{\forall\alpha_n\geq 0,\sum y_n\alpha_n=0,w=\sum\alpha_ny_nz_n}[\min_\limits{b,w}\sum_\limits{n=1}^N\alpha_n-\frac 12w^Tw]$
- 這時候 inner problem 的 $w$ 也可以拿掉了，因為剛剛解 constraint 知道，只要算出 $\alpha$ 就會知道 $w$ 是多少
- 既然 $b,w$ 都拿掉了，inner problem 就不用解了
- 最後得到 optimization problem $\max_\limits{\forall\alpha_n\geq 0,\sum y_n\alpha_n=0,w=\sum\alpha_ny_nz_n}-\frac 12\|\sum_\limits{n=1}^N\alpha_ny_nz_n\|^2+\sum_\limits{n=1}^N\alpha_n$
- Lagrange dual problem，現在成了一個只有 $\alpha$ 的最佳化問題，太神拉

### KKT Optimality Conditions
- 根據剛剛的推導我們可以知道，如果解出來的 $b,w,\alpha$ 對原來的問題(primal)跟對偶問題(dual)都是最佳解，那麼它們會滿足某些條件
- $y_n(w^Tz_n+b)\geq 1$
- primal feasible：原來問題的條件
- $\alpha_n\geq 0$
- dual feasible：對偶問題的條件，要成立兩邊才對等
- $\sum y_n\alpha_n=0;w=\sum\alpha_ny_nz_n$
- dual-inner optimal：剛剛利用 **inner optimal 偏微分等於 0** 推導出來的
- $\alpha_n(1-y_n(w^Tz_n+b))=0$
- primal-inner optimal：這個條件又稱作 **complementary slackness**，意思是說 **Lagrange multiplier $\alpha_n$ 跟 constraint $1-y_n(w^Tz_n+b)$ 至少要有一個是 0**，為什麼呢？
- 複習 [這段](https://hackmd.io/Sr0QGaLfQGedOtM1hGpkcg#Starting-Point-Constrained-to-%E2%80%98Unconstrained%E2%80%99)，因為當 $w,b$ 滿足本來條件 $1-y_n(w^Tz_n+b)\leq 0$，小於等於 0 又分兩種情況
- 如果等於 0，那麼乘上 $\alpha_n$ 還是 0
- 如果小於 0，那麼 $\alpha_n$ 就會為了 maximize $\mathcal L(b,w,\alpha)$ 而變成 0
- 上面四個條件是 necessary (必要條件) for optimality，也就是說最佳解必定滿足這四個條件
- 其實也可以證明它也是 sufficient (充分條件)，意思是我滿足這四個條件，就一定是最佳解，不過證明頗複雜就不證了。

### Fun Time: KKT Optimality Conditions


## [Solving Dual SVM](https://www.youtube.com/watch?v=qGk0p7K07Mc&list=PLXVfgk9fNX2IQOYPmqjqWsNUFl2kpk1U2&index=8)

### Dual Formulation of Support Vector Machine
- 現在問題長這樣
- $\max_\limits{\alpha_n\geq 0\,\forall n\in\{1,...,N\},\sum y_n\alpha_n=0,w=\sum\alpha_ny_nz_n}-\frac 12\|\sum_\limits{n=1}^N\alpha_ny_nz_n\|^2+\sum_\limits{n=1}^N\alpha_n$
- 展開平方項。
- 不想要 maximize，那就 minimize 取負號
- 問題就轉化成這樣
- 優化 $\min_\limits{\alpha}\frac 12\sum_\limits{n=1}^N\sum_\limits{M=1}^N\alpha_n\alpha_my_ny_mz_n^Tz_m-\sum_\limits{n=1}^N\alpha_n$
- 條件 $\sum_\limits{n=1}^Ny_n\alpha_n=0;\\\alpha_n\geq 0,\forall n\in\{1,2,...,N\}$
- 看到沒有，現在的問題
- $N$ 個變數
- $N+1$ 個條件
- 是 convex 的
- QP 屌解

### Dual SVM with QP Solver
- $q_{n,m}$ 可能要思考一下
- $a_i^T$ 和 $c_i$ 分成兩部分
- $\sum_\limits{n=1}^Ny_n\alpha_n=0$ 對應到 $a_\geq,a_\leq,c_\geq,c_\leq$
- 本來條件是 $y^T\alpha=0$，可是 QP 要的是 $\geq$ 啊
- $=$ 可以寫成，同時 $\geq$ 和 $\leq$
- 也就是說 $y^T\alpha\geq 0$ 且 $y^T\alpha\leq 0$
- 就可以寫成 $y^T\alpha\geq 0$ 且 $-y^T\alpha\geq 0$
- $\alpha_n\geq 0$ 對應到 $a_n^T$
- 所有 $\alpha_n$ 都大於 0，意思就是 $\alpha$ 向量對任何 unit direction (例如 $\begin{bmatrix}0\\\vdots\\1\\0\end{bmatrix}$) 做內積都要大於 0
- 所以 $a_n^T$ 就是第 $n$ 個 unit direction
- 有些 QP solver 為了方便使用者
- 有提供 **equality 等式**的功能，就不用像上面那樣把等號拆解了。
- 有的也提供 **bound** 直接對 $\alpha_n$ 給上限或下限的功能

### Dual SVM with Special QP Solver
- 取名叫 $Q_D$ 代表對偶(dual)的
- 但是通常 $q_{n,m}=y_ny_mz_n^Tz_m$ 都是 non-zero 的，所以 $Q_D$ 會是 dense 的
- 當 $N$ 很大，$Q_D$ 就超大
- 所以通常會使用特製的 QP solver，專為 SVM 設計。
- 可能是要用到 $Q_D$ 才去算(?
- 又或者利用剛剛說的特殊的 constraint (equality & bound)，可以有效率的解出來

### Optimal ($b,w$)
- 解完了 $\alpha$，可以代換回我想解的 $w,b$ 了
- $w$ 直接代等式就出來了
- $b$ 利用條件 $\alpha_n(1-y_n(w^Tz_n+b))=0$
- 回想一下，$\alpha_n>0$ 的話，$1-y_n(w^Tz_n+b)$ 就要等於 0，也就是 $y_n(w^Tz_n+b)=1$
- **有謎有發現它就在胖胖的邊界上？ support vector!!!**
- 等號兩邊乘上 $y_n$，若 $\alpha_n>0$ 則 $y_n-(w^Tz_n+b)=0$
- $b=y_n-w^Tz_n$

### Fun Time: Optimal $(b,w)$
- $1(w^Tz+b)=1\tag 1$
- $-1(w^T(-z)+b)=1\tag 2$
- (1) - (2) 得 $b=0$

## [Messages behind Dual SVM](https://www.youtube.com/watch?v=agmmQh702aA&list=PLXVfgk9fNX2IQOYPmqjqWsNUFl2kpk1U2&index=9)

### Support Vectors Revisited
- 在邊界上，且 $\alpha_n>0$ 的點我們才稱 support vector
- 在邊界上，但 $\alpha_n=0$ 則不算
- **所以回想一下，其實可以知道我們計算 $w,b$ 都只需要 support vectors**
- $w$ 怎麼算？support vectors 的 linear combination $\sum_\limits{SV}\alpha_ny_nz_n$
- $b$ 怎麼算？計算任何一個 support vector 的 $y_n-w^Tz_n$
- 所以 SVM 可以看成是：我去找出 support vector 來計算 hyperplane

### Representation of Fattest Hyperplane
- 其實回想一下可以知道，SVM 跟 PLA 解出來的 $w$ 都是 data 的 linear combination
- 而且如果 linear regression/logistic regression 的 $w$ 從 0 出發做 SGD/GD，解出來的 $w$ 也會是 data 的 linear combination
- **這樣的結果我們稱 $w$ 'represented' by data**
- **SVM 特別之處是 $w$ 只由 support vectors 來表示**
- 而 PLA 的 $w$ 是由犯錯的那些 data points 來表示。

### Summary: Two Forms of Hard-Margin SVM
- Primal(原始的) Hard-Margin SVM
- $\tilde d+1$ 個 variables
- 所以希望 $\tilde d$ 小
- $N$ 個 constraints
- 物理意義：找到一個特別 scaling 過的 $w,b$
- Dual(對偶) Hard-Margin SVM
- $N$ 個 variables
- 所以希望 $N$ 小
- $N+1$ 個 simple constraints
- 物理意義：找到 support vectors 還有它們對應的 Lagrange multiplier $\alpha_n$，用來重建 fattest hyperplane
- 最後就可以用 $g_{SVM}(x)=\text{sign}(w^T\phi(x)+b)$ 來預測新的 data points

### Are We Done Yet?
- 一開始說不想碰 $\tilde d$，怕它太大很難算
- 可是它就藏在 $Q_D$ 裡面
- $q_{n,m}=y_ny_mz_n^Tz_m$ 要做內積 ($z$ 是 $\tilde d$ 維向量)
- **這樣當 $\tilde d$ 很大的話還是很難算 inner product 啊，下個章節的課程就要解決這個問題。**

### Fun Time
- 這題是用刪去法，因為 124 都不可能，只有 3 有可能所以才選 3

### Summary