Dual Support Vector Machine

Motivation of Dual SVM

我們在利用 QP 解決非線性 SVM 時，會對資料做一個特征轉換，轉換后的資料 $z$z 的維度為 $\tilde{d}+1$d~+1 ，此時 QP 有 $\tilde{d}+1$d~+1 個變量，$N$N 個約束條件，當 $\tilde{d}$d~ 很大時很難解，所以我們希望使非線性 SVM 與 $\tilde{d}$d~ 無關。目標是下圖的結果， ‘Equivalent’ SVM 就稱為原始 SVM 的對偶問題。但推導的數學很複雜，所以我們就來簡單得直覺理解一下。

要用到的工具是 Lagrange Multipliers，用法就是將原來的線性約束條件，乘上一個$\lambda$λ項再加入原式求解。

我們在上一節最後得到的最優化問題是 $min_{b,w} \frac{1}{2} w^Tw$minb,w​21​wTw ，約束條件共有n個 $y_n(w^Tz_n+b)\geq1 \text{ for n=1,2,…,N} $ 。 所以我們就定義了一個lagrange function $L(b,w,\alpha)=\frac{1}{2}w^Tw+\sum_{n=1}^N \alpha_n(1-y_n(w^Tz_n+b))$L(b,w,α)=21​wTw+∑n=1N​αn​(1−yn​(wTzn​+b)) ，這裡的 $\alpha$α 其實就是$\lambda$λ ，只是因為書寫習慣。現在我們可以寫出沒有約束條件的最優化問題，$min (max_{\text{ all }\alpha_n\geq0} L(b,w,\alpha))$min(max all αn​≥0​L(b,w,α)) ，如上圖claim中所示。

我們先來理解這個minmax問題，先固定外層的min，對每一組固定的b,w，我們要用各種不同的$\alpha_n$αn​ 來嘗試，且滿足所有 $\alpha _n \geq 0$αn​≥0，找出largrange function的最大值。然後再從所有不同組b,w對應的 largrange function 最大值中，挑出最小的一個。為什麼把式子改寫成這樣，就能達到和原來一樣的功能呢，現在再分析一下可能發生的兩種情況：

1. $1-y_n(w^Tz_n+b)$1−yn​(wTzn​+b) 中有些項 > 0 ，這樣為了得到 lagrange function 的最大值，對應的$\alpha_n$αn​ 會趨近無窮大，得到的值也會趨近無窮大，因此這組 w,b 在和其他組 w,b 的lagrange function 最大值的比拼中就會敗下陣來，因為lagrange function 的最大值要最小才能獲勝，趨近無窮大的值顯然不會是最小。
2. $1-y_n(w^Tz_n+b)$1−yn​(wTzn​+b) 中所有項都非正，符合這個條件的 w,b 才有可能是最後的勝者。而為了得到lagrange function的最大值，$\alpha_n$αn​乘以一個非負值要最大，那$\alpha_n$αn​就會等於0，這樣我們最優化問題最優化的還是原來的$\frac{1}{2}w^Tw$21​wTw。而$1-y_n(w^Tz_n+b)\leq 0 \text{ for all n=1,2,…,n}​$1−yn​(wTzn​+b)≤0 for all n=1,2,…,n​ （所有項都非負）正是我們之前想要消滅的約束條件。可見我們把約束條件藏在了max中。

Lagrange Dual SVM

接下來我們再繼續跟著下圖化簡。

我們定義 $\alpha'$α′ 為滿足all $\text{all } \alpha_n' \geq 0$all αn′​≥0中的任意一個，因為對於同一組 b,w ，最大的 lagrange function 會大於任意的（$max_{\text{all }\alpha_n\geq 0}L(b,w,\alpha) \geq L(b,w,\alpha')$maxall αn​≥0​L(b,w,α)≥L(b,w,α′)），所以$min_{b,w} (max_{\text{all }\alpha_n \geq 0} L(b,w,\alpha)) \geq min_{b,w} L(b,w,\alpha')$minb,w​(maxall αn​≥0​L(b,w,α))≥minb,w​L(b,w,α′) 。又因為在同一組b,w情況下，右邊的其實是$\alpha'$α′的函數，$\alpha'$α′ 為滿足$\text{all }\alpha_n’ \geq 0 $ 中的任意一個，左邊大於右邊如果成立，那左邊就要大於右邊的最大值，也就是 $min_{b,w} (max_{\text{all }\alpha_n \geq 0} L(b,w,\alpha)) \geq max_{\text{all }\alpha_n'\geq 0}min_{b,w} L(b,w,\alpha')$minb,w​(maxall αn​≥0​L(b,w,α))≥maxall αn′​≥0​minb,w​L(b,w,α′) 。這樣來看，我們把原本的min max的順序交換了，所以右邊的式子就稱為 Lagrange dual problem，如果我們把 Lagrange dual problem 解決了，我們就能得到原來問題的下界（有 $\geq​$≥​ 號）。

右邊的式子是比較好解的問題，因為先求min那一層，而min那一層沒有約束條件，我們比較會接沒有約束條件的問題。但$\geq$≥是比較弱的關係，我們希望有比較強的關係，也就是=號，那樣我們就能找到滿足右邊對偶問題的一個解，它同時也滿足左邊的原始問題。在QP問題中，強對偶關係（等號）是可能發生的，只要滿足以下三個條件：1. 原始問題是凸的。 2. 原始問題是可解的（經過特征轉換后的資料是線性可分的）。3. 約束條件是線性的。

所以現在我們就先來解這個對偶問題。因為內層的min問題是沒有約束條件的，當極值發生時，偏導數為0，所以我們先用 lagrange function 對 b 求偏微分并令其等於0，然後我們就能得到下圖中中間部分紫色的式子。

我們將紫色的式子代入上圖上面部分，發現在紫色條件的約束下能去除b，於是得到了上圖下面部分。

類似地，我們將 lagrange function 對 $w_i$wi​ 求偏微分并令其等於0。再將得到的約束條件代入化簡式子，得到下圖化簡后的式子。

我們現在得到了這樣一個經過層層化簡后的式子，現在來回顧一下為了得到這個化簡式，使得原始問題和對偶問題的最優解是同一個$b,w,\alpha$b,w,α，需要的條件。

1. 原始問題可解，也就是經特征轉換的資料線性可分
2. 對偶問題可解，$\alpha_n\geq0$αn​≥0，這樣才把約束條件藏在max中
3. 對偶問題中的內層(min層)最優化的條件，也是lagrange function分別對$b,w_i$b,wi​求偏微分等于0得到的約束條件
4. 原始問題中的內層(max層)最優化的條件，在最優解時，一定滿足$\alpha_n(1-y_n(w^Tz_n+b))=0​$αn​(1−yn​(wTzn​+b))=0​ ， 也可稱為 complimentary slackness，兩者必定有一項等於0。

現在的對偶問題一共有三個條件（除去那些被隱藏起來的條件），分別是$\text{all }\alpha_n\geq0,\sum y_n\alpha_n=0,w=\sum \alpha_ny_nz_n$all αn​≥0,∑yn​αn​=0,w=∑αn​yn​zn​ ，其中 $w=\sum \alpha_n y_n z_n$w=∑αn​yn​zn​ 這個條件告訴我們可以通過$\alpha_n$αn​算出$w$w，對最大化沒有什麼約束。我們先捨去這個條件，解出$\alpha$α的最優化問題，之後再利用這個條件由$\alpha$α算出$w$w。

Solving Dual SVM

把SVM對偶問題的最大化乘以一個負號，改寫成最小化問題（我們更熟悉最小化），然後展開平方，得到下圖，我們終於達到了目標，得到了有N個變量，N+1個約束條件的QP問題。

!接下來就只要按QP Solver的格式，把一些輸入參數填好就行，參看下圖。其中第一個約束條件是等號，而不是大於號，解決方法就是把它分為兩個條件，一個是 $y\alpha \geq 0$yα≥0，另一個是 $-y\alpha \geq 0$−yα≥0 。但有些二次規劃程式會允許你用等號，有些會用bound($\alpha _n$αn​)的方式來代替$\alpha _n \geq 0​$αn​≥0​這一條。

現在好像已經解決了問題，但實際上我們還要仔細來看一看Q里的內容。Q矩陣是又$q_{n,m}=y_n y_m z_n^Tz_m​$qn,m​=yn​ym​znT​zm​​組成的，而$q_{n,m}​$qn,m​​一般不是特殊的0值，也就是矩陣Q是密集的(dense)。如果要存儲這個Q矩陣就需要很大的內存空間，而且解起來也特別困難。所以在實務上解的時候，我們會選擇特別為SVM設計的QP程式，它不會把整個矩陣Q都存下來，需要用到的時候再計算，它還會用到一些SVM的特性作為特別的約束條件。

我們知道可以用QP來解出$\alpha$α，剛才也提到了可以用$w=\sum \alpha_n y_n z_n$w=∑αn​yn​zn​ 這個條件由$\alpha$α求得$w$w，還差如何求得$b$b。 回顧之前的4個KKT條件，從第一項$y_n(w^Tz_n+b)\geq1$yn​(wTzn​+b)≥1，我們可以推導出$b$b的範圍，而第四項 complementary slackness 連接了$\alpha$α和$b$b，我們可以求出$b$b的準確值。也就是只要存在一個大於0的$\alpha_n$αn​，就有$1-y_n(w^Tz_n+b)=0$1−yn​(wTzn​+b)=0，因為$y_n=\pm1$yn​=±1，我們可以改寫成$y_n=w^Tz_n+b$yn​=wTzn​+b，也就得到了$b=y_n-w^Tz_n$b=yn​−wTzn​。$1-y_n(w^Tz_n+b)=0$1−yn​(wTzn​+b)=0這個條件也很眼熟，就是我們設置的那條的胖胖邊界。於是我們就從 complementary slackness 中知道，當對應的$\alpha_n>0$αn​>0時，資料在胖胖邊界上，這份資料就是所謂的支持向量(SV)。

Messages behind Dual SVM

我們回顧一下支持向量，之前講到離分割線最近的點才定義了胖胖的邊界，其他點沒有貢獻，所以在胖胖邊界上的點是支持向量的候選。現在我們知道，$\alpha_n>0$αn​>0的胖胖邊界上的點，就是支持向量。我們可以通過看$w$w和$b$b的計算公式來理解，當$\alpha_n=0$αn​=0時，$w$w和$b$b的計算用不到對應點，其中$b$b的計算只要用任意一個$\alpha_n>0$αn​>0的點就足夠了，所以即使是在胖胖邊界上的點，如果$\alpha_n=0$αn​=0，那這個點也是沒用的，不算做支持向量。所以總結來說，SVM就是通過對偶最優化問題的解來找到支持向量，然後用這些支持向量來學習胖胖的邊界。

其實之前PLA中w的表示方式和SVM很像，SVM是$y_nz_n$yn​zn​對於$\alpha_n$αn​的線性組合，PLA中，當我們有分類錯誤的情況時，我們會把w加上分類錯誤的那組$y_nz_n$yn​zn​，如果w初始值是0，寫出來就是下圖的形式。w是$y_nz_n$yn​zn​的線性組合，當用梯度下降的回歸問題時也一樣。我們把這樣的w稱作能用資料表示的w。SVM就是可以只用資料中的SV部分表示的w。

現在可以對比一下 hard-margin 的原始問題和對偶問題，原始問題適合$\tilde{d}+1$d~+1比較小的情況，物理意義是把b,w進行了放縮；對偶問題適合$N$N比較小的情況，物理意義是找到SVs。但他們最後都是為了找到有胖胖邊界的b,w。

但其實我們仍然沒有在對偶問題中擺脫掉$\tilde{d}$d~，在求對偶問題中，我們要計算一個複雜的矩陣Q，其中每一項$q_{n,m}=y_ny_mz_n^Tz_m$qn,m​=yn​ym​znT​zm​，計算$z_n^Tz_m$znT​zm​內積時依舊是在d維空間中計算的，時間複雜度是$O(\tilde{d})$O(d~)，不過在下一章才會講到如何避免這樣的naive計算~

Summary