# 2 -- Dual Support Vector Machine
上節課我們主要介紹了線性支持向量機(Linear Support Vector Machine)。Linear SVM的目標是找出最“胖”的分割線進行正負類的分離,方法是使用二次規劃來求出分類線。本節課將從另一個方面入手,研究對偶支持向量機(Dual Support Vector Machine),嘗試從新的角度計算得出分類線,推廣SVM的應用范圍。
### **Motivation of Dual SVM**
首先,我們回顧一下,對于非線性SVM,我們通常可以使用非線性變換將變量從x域轉換到z域中。然后,在z域中,根據上一節課的內容,使用線性SVM解決問題即可。上一節課我們說過,使用SVM得到large-margin,減少了有效的VC Dimension,限制了模型復雜度;另一方面,使用特征轉換,目的是讓模型更復雜,減小。所以說,非線性SVM是把這兩者目的結合起來,平衡這兩者的關系。那么,特征轉換下,求解QP問題在z域中的維度設為,如果模型越復雜,則越大,相應求解這個QP問題也變得很困難。當無限大的時候,問題將會變得難以求解,那么有沒有什么辦法可以解決這個問題呢?一種方法就是使SVM的求解過程不依賴,這就是我們本節課所要討論的主要內容。

比較一下,我們上一節課所講的Original SVM二次規劃問題的變量個數是,有N個限制條件;而本節課,我們把問題轉化為對偶問題(’Equivalent’ SVM),同樣是二次規劃,只不過變量個數變成N個,有N+1個限制條件。這種對偶SVM的好處就是問題只跟N有關,與無關,這樣就不存在上文提到的當無限大時難以求解的情況。

如何把問題轉化為對偶問題(’Equivalent’ SVM),其中的數學推導非常復雜,本文不做詳細數學論證,但是會從概念和原理上進行簡單的推導。
還記得我們在《機器學習基石》課程中介紹的Regularization中,在最小化的過程中,也添加了限制條件:。我們的求解方法是引入拉格朗日因子,將有條件的最小化問題轉換為無條件的最小化問題:,最終得到的w的最優化解為:

所以,在regularization問題中,是已知常量,求解過程變得容易。那么,對于dual SVM問題,同樣可以引入,將條件問題轉換為非條件問題,只不過是未知參數,且個數是N,需要對其進行求解。

如何將條件問題轉換為非條件問題?上一節課我們介紹的SVM中,目標是:,條件是:。首先,我們令拉格朗日因子為(區別于regularization),構造一個函數:

這個函數右邊第一項是SVM的目標,第二項是SVM的條件和拉格朗日因子的乘積。我們把這個函數稱為拉格朗日函數,其中包含三個參數:b,w,。

下面,我們利用拉格朗日函數,把SVM構造成一個非條件問題:

該最小化問題中包含了最大化問題,怎么解釋呢?首先我們規定拉格朗日因子,根據SVM的限定條件可得:,如果沒有達到最優解,即有不滿足的情況,因為,那么必然有。對于這種大于零的情況,其最大值是無解的。如果對于所有的點,均滿足,那么必然有,則當時,其有最大值,最大值就是我們SVM的目標:。因此,這種轉化為非條件的SVM構造函數的形式是可行的。
### **Lagrange Dual SVM**
現在,我們已經將SVM問題轉化為與拉格朗日因子有關的最大最小值形式。已知,那么對于任何固定的,且,一定有如下不等式成立:

對上述不等式右邊取最大值,不等式同樣成立:

上述不等式表明,我們對SVM的min和max做了對調,滿足這樣的關系,這叫做Lagrange dual problem。不等式右邊是SVM問題的下界,我們接下來的目的就是求出這個下界。
已知是一種弱對偶關系,在二次規劃QP問題中,如果滿足以下三個條件:
* **函數是凸的(convex primal)**
* **函數有解(feasible primal)**
* **條件是線性的(linear constraints)**
那么,上述不等式關系就變成強對偶關系,變成=,即一定存在滿足條件的解,使等式左邊和右邊都成立,SVM的解就轉化為右邊的形式。
經過推導,SVM對偶問題的解已經轉化為無條件形式:

其中,上式括號里面的是對拉格朗日函數計算最小值。那么根據梯度下降算法思想:最小值位置滿足梯度為零。首先,令對參數b的梯度為零:

也就是說,最優解一定滿足。那么,我們把這個條件代入計算max條件中(與同為條件),并進行化簡:

這樣,SVM表達式消去了b,問題化簡了一些。然后,再根據最小值思想,令對參數w的梯度為零:

即得到:

也就是說,最優解一定滿足。那么,同樣我們把這個條件代入并進行化簡:

這樣,SVM表達式消去了w,問題更加簡化了。這時候的條件有3個:
* all 
* 
* 
SVM簡化為只有的最佳化問題,即計算滿足上述三個條件下,函數最小值時對應的是多少。
總結一下,SVM最佳化形式轉化為只與有關:

其中,滿足最佳化的條件稱之為Karush-Kuhn-Tucker(KKT):

在下一部分中,我們將利用KKT條件來計算最優化問題中的,進而得到b和w。
### **Solving Dual SVM**
上面我們已經得到了dual SVM的簡化版了,接下來,我們繼續對它進行一些優化。首先,將max問題轉化為min問題,再做一些條件整理和推導,得到:

顯然,這是一個convex的QP問題,且有N個變量,限制條件有N+1個。則根據上一節課講的QP解法,找到Q,p,A,c對應的值,用軟件工具包進行求解即可。

求解過程很清晰,但是值得注意的是,,大部分值是非零的,稱為dense。當N很大的時候,例如N=30000,那么對應的的計算量將會很大,存儲空間也很大。所以一般情況下,對dual SVM問題的矩陣,需要使用一些特殊的方法,這部分內容就不再贅述了。

得到之后,再根據之前的KKT條件,就可以計算出w和b了。首先利用條件得到w,然后利用條件,取任一即>0的點,得到,進而求得。

值得注意的是,計算b值,>0時,有成立。正好表示的是該點在SVM分類線上,即fat boundary。也就是說,滿足>0的點一定落在fat boundary上,這些點就是Support Vector。這是一個非常有趣的特性。
### **Messages behind Dual SVM**
回憶一下,上一節課中,我們把位于分類線邊界上的點稱為support vector(candidates)。本節課前面介紹了>0的點一定落在分類線邊界上,這些點稱之為support vector(注意沒有candidates)。也就是說分類線上的點不一定都是支持向量,但是滿足>0的點,一定是支持向量。

SV只由>0的點決定,根據上一部分推導的w和b的計算公式,我們發現,w和b僅由SV即>0的點決定,簡化了計算量。這跟我們上一節課介紹的分類線只由“胖”邊界上的點所決定是一個道理。也就是說,樣本點可以分成兩類:一類是support vectors,通過support vectors可以求得fattest hyperplane;另一類不是support vectors,對我們求得fattest hyperplane沒有影響。

回過頭來,我們來比較一下SVM和PLA的w公式:

我們發現,二者在形式上是相似的。由fattest hyperplane邊界上所有的SV決定,由所有當前分類錯誤的點決定。和都是原始數據點的線性組合形式,是原始數據的代表。

總結一下,本節課和上節課主要介紹了兩種形式的SVM,一種是Primal Hard-Margin SVM,另一種是Dual Hard_Margin SVM。Primal Hard-Margin SVM有個參數,有N個限制條件。當很大時,求解困難。而Dual Hard_Margin SVM有N個參數,有N+1個限制條件。當數據量N很大時,也同樣會增大計算難度。兩種形式都能得到w和b,求得fattest hyperplane。通常情況下,如果N不是很大,一般使用Dual SVM來解決問題。

這節課提出的Dual SVM的目的是為了避免計算過程中對的依賴,而只與N有關。但是,Dual SVM是否真的消除了對的依賴呢?其實并沒有。因為在計算的過程中,由z向量引入了,實際上復雜度已經隱藏在計算過程中了。所以,我們的目標并沒有實現。下一節課我們將繼續研究探討如何消除對的依賴。

### **總結**
本節課主要介紹了SVM的另一種形式:Dual SVM。我們這樣做的出發點是為了移除計算過程對的依賴。Dual SVM的推導過程是通過引入拉格朗日因子,將SVM轉化為新的非條件形式。然后,利用QP,得到最佳解的拉格朗日因子。再通過KKT條件,計算得到對應的w和b。最終求得fattest hyperplane。下一節課,我們將解決Dual SVM計算過程中對的依賴問題。
**_注明:_**
文章中所有的圖片均來自臺灣大學林軒田《機器學習技法》課程
- 臺灣大學林軒田機器學習筆記
- 機器學習基石
- 1 -- The Learning Problem
- 2 -- Learning to Answer Yes/No
- 3 -- Types of Learning
- 4 -- Feasibility of Learning
- 5 -- Training versus Testing
- 6 -- Theory of Generalization
- 7 -- The VC Dimension
- 8 -- Noise and Error
- 9 -- Linear Regression
- 10 -- Logistic Regression
- 11 -- Linear Models for Classification
- 12 -- Nonlinear Transformation
- 13 -- Hazard of Overfitting
- 14 -- Regularization
- 15 -- Validation
- 16 -- Three Learning Principles
- 機器學習技法
- 1 -- Linear Support Vector Machine
- 2 -- Dual Support Vector Machine
- 3 -- Kernel Support Vector Machine
- 4 -- Soft-Margin Support Vector Machine
- 5 -- Kernel Logistic Regression
- 6 -- Support Vector Regression
- 7 -- Blending and Bagging
- 8 -- Adaptive Boosting
- 9 -- Decision Tree
- 10 -- Random Forest
- 11 -- Gradient Boosted Decision Tree
- 12 -- Neural Network
- 13 -- Deep Learning
- 14 -- Radial Basis Function Network
- 15 -- Matrix Factorization
- 16(完結) -- Finale