統計學習方法—SVM推導

• 2019 年 10 月 3 日
• 筆記

SVM

  支援向量機是一種二分類模型，它以間隔最大作為優化目標，因此它比感知機僅僅以誤分類推動的模型要優勝不少。數據線性可分時，SVM直接以間隔最大訓練出一個線性分類模型。當數據線性不可分時，SVM通過軟間隔最大化解決這種問題。此時的模型仍是一個線性模型，若採用核方法和軟間隔最大化，則得到一個非線性模型。可以看到SVM在解決變複雜的情況時是逐步改進的。

1. 定義

  前面已經學習過的線性分類有感知機和(Logistic)回歸。感知機對誤分類點進行優化，得到一個對訓練樣本的分類超平面，但這個超平面並不是最優的，而且只能用於數據線性可分的情況。而(Logistic)回歸是一個對數線性模型，它將數據映射到0到1之間，對有較大差異的數據有較好適應性。通常，(Logistic)回歸中的線性部分(w^Tx+b > 0)時，該模型輸出就大於0.5 這時輸入(x)被分為(y=1)那一類。

  上面已說到，SVM問題分三個階段，一是線性可分、二是線性不可分但可放棄部分奇異點用線性分割、三是線性不可分且數據本身就非線性可分。解決這些問題都是一步一步來的，圖1 是一個線性可分的SVM示意圖，中間是得到的分類超平面，兩端虛線是支援向量到超平面的最大間隔線。而這條線上的就是支援向量，支援向量到超平面的間隔是所有樣本點中最近的。

1.1 函數間隔和幾何間隔

  數據集中，一個點離超平面越遠，那麼確信其判斷正確性的可能就越大，它可以由(boldsymbol{wcdot x}+b)來表示。若要建立一個即可判斷確信度又能判斷其分類正確性的函數，則需要引進一個符號變數，巧合的是(yin{-1,1})，並且若分類正確(boldsymbol{wcdot x} +b)與(y)的符號是一致的。那麼可由(y(boldsymbol{wcdot x} + b))來表示分類的正確性和確信度，這就是函數間隔的意義。

  對於給定樣本集和超平面，超平面關於樣本點((boldsymbol{x_i},y_i))的函數間隔為
[ widehat gamma_i = y_i(boldsymbol{wcdot x_i} + b) ]
超平面關於數據集的函數間隔為
[ widehat gamma = underset {i} {min} ;widehat gamma _i ]
事實上，超平面關於整個數據集的函數間隔就是超平面關於支援向量的函數間隔。顯然，我們需要優化的便是這個關於支援向量的間隔，使它最大也就使得超平面對數據集中所有點都有較遠距離。

  但是直接對函數間隔最大化有個問題，函數間隔是關於參數(boldsymbol{w},b)的函數，若(boldsymbol{w},b)成比例的增加，這時超平面是不會變的，但是函數間隔會按相同比例增加。所以直接最大化函數間隔得到的結果肯定是無窮大了，因此需要對其進行規範化。這裡對法向量(w)進行標準化，標準化後的結果就是幾何間隔
[ gamma_i = y_ifrac { boldsymbol{w cdot x_i} +b } {||boldsymbol{w}||} ]
其中，(||boldsymbol{w}||)是第二範式。

  在二維情形下，(boldsymbol{w}cdot boldsymbol{x} + b/ ||w||)就是點到直線的距離公式沒加絕對值符號，標準化後的幾何間隔就不會因(boldsymbol{w},b)按比例放縮而產生變化。同樣，超平面關於數據集的幾何間隔為
[ gamma = underset i {min} ; gamma _i ]
函數間隔與幾何間隔只是相差一個標準化因子
[ gamma_i = frac {widehat gamma_i} {||boldsymbol{w}||}\ gamma = frac {widehat gamma} {||boldsymbol{w}||} ]

1.2 間隔最大化

  定義了幾何間隔後，就能通過最大化支援向量到超平面的幾何間隔得到一個最優的分類超平面。在感知機中，學習的方法是最小化誤差距離。這種方法只要超平面能夠正確分類已知的數據，學習過程便結束。而對SVM中最大化幾何間隔來說，當還未能正確分類所有樣本點時，數據集中幾何間隔最小的樣本點是負的，此時的最大化過程是找到一個能夠正確分割數據集的超平面。當幾何間隔學習到大於0的時侯，超平面已能將數據集正確分割，但學習過程不會停止，SVM希望讓最靠近超平面的樣本點的分類結果仍有較大的確信度，這就是最大化幾何間隔的目的。

  現在導出其數學表達，目的是求解關於參數(boldsymbol{w},b)的超平面，使超平面到數據集中幾何間隔最小的的點關於它的幾何間隔最大
[ arg underset {w,b} {max};underset {i} {min} ;gamma_i tag{1.2-a} ]
若對該式直接計算，難度非常大，因為(gamma) 的分子和分母都包含了變數(boldsymbol{w},b)，因此先將其等價替換為函數間隔，問題變為
[ arg underset {w,b} {max};underset {i} {min} ;frac {widehat gamma_i}{||boldsymbol{w}||} tag{1.2-b} ]
因為(||boldsymbol{w}||)與 (i)無關，可以直接將其提出來
[ arg underset {w,b} {max};left { frac {1}{||boldsymbol{w}||} underset {i} {min} ; widehat gamma_i right } tag{1.2-c} \ ]
為了簡化計算，需要利用函數間隔的性質：函數間隔的大小隨(boldsymbol{w},b)的放縮而放縮，對於同一組(boldsymbol{w},b) 所有樣本的函數間隔的相對間隔也是按相同比例放縮。所以我們可以用函數間隔最小的點作為基準點，將其函數間隔令為1。那麼其他點的函數間隔只是按(1/gamma)的比例進行放縮，並不影響其相對超平面的位置，也不會影響超平面的位置。直接將其令為1後就不能這樣寫作一個式子了，需要將其他點函數間隔大於1的約束單獨寫出來，則問題變為解一個規劃問題
[ begin{aligned} underset {w,b} {max} ;; &frac {1} {||boldsymbol{w}||}\ underset i {min} ;;&widehat gamma_i geqslant 1,;;; i=1,2,cdots, n end{aligned} ]
同樣為了計算方便，將最大化(||boldsymbol{w}||^{-1})改為等價的最小化(||boldsymbol{w}||^2)，於是問題變為二次規劃問題
[ begin{aligned} underset {w,b} {min} ;; & frac 1 2 {||boldsymbol{w}||^2} \ underset i {min} ;;&widehat gamma_i geqslant 1,;;; i=1,2,cdots, n end{aligned} ]
  其中(1/ 2)是為了簡化計算結果。這就是SVM要解決的基本問題，下面討論SVM如何解決這一問題，並且對於更複雜的情形如何處理。

2. 線性可分SVM

  定義中導出的問題實際就是根據線性可分的情況推導的，因此我們只需要求解基本情況的二次規劃問題就能得到一個線性可分的SVM模型。求解這類帶約束優化問題的基本思路就是先通過拉格朗日函數轉化為無約束優化問題。
[ L(w,b,lambda) = frac 1 2 ||boldsymbol{w}||^2 +sum_i^n lambda_i – sum_i^n lambda_i [y_i(boldsymbol{boldsymbol{w}cdot x_i} + b) ] ]
注意(boldsymbol{w},; boldsymbol{x_i})是維度相同的向量，對於這個廣義拉格朗日的最小化問題可以求偏導令為0，再利用KKT條件約束來解，但這樣計算量太大。因為這個函數是凸函數，所以可以求解其對偶問題來得到原問題等價的解。關於對偶性在另一篇筆記拉格朗日對偶性（lagrange duality）。

2.1 對偶問題

  首先寫出原問題的極小極大形式
[ underset {boldsymbol{w},b}{min}; L(boldsymbol{w},b,lambda) = underset {w,b} {min}; underset {lambda} {max} ;L(boldsymbol{w},b,lambda) ]
其對偶問題便是極大極小問題
[ underset {lambda} {max} ;underset {w,b} {min}; L(boldsymbol{w},b,lambda) ]
在原問題中，先求關於(lambda)的極大，便會對(lambda)求偏導得到一串等式，但這個結果實際上就是原來的約束條件。仍未簡化問題，但若先對(boldsymbol{w},b)先計算極小，則會得到一個較易計算的式子。這是使用對偶性的原因。具體關於對偶性在拉格朗日對偶性（lagrange duality）中，這裡直接使用，不再介紹。

  那麼可以先求解內部的極小問題，對(boldsymbol{w},b)求偏導並令為0得
[ begin{aligned} triangledown _wL(boldsymbol{w},b,lambda) =boldsymbol{w} – sum_i^n lambda_i y_iboldsymbol{x_i}=0\ triangledown _bL(boldsymbol{w},b,lambda) =-sum_i^n lambda_i y_i = 0 end{aligned} ]
注意對(boldsymbol{w})的求導是對向量的求導，可查閱矩陣微分方面的內容。由上式得到
[ begin{aligned} boldsymbol{w} = sum_i^n lambda_i y_iboldsymbol{x_i}\ sum_i^n lambda_i y_i = 0 end{aligned} ]
帶入原拉格朗日函數
[ begin{aligned} L(w,b,lambda) =& frac 1 2 boldsymbol{w^Tw} +sum_i^n lambda_i – sum_i^n lambda_iy_i(boldsymbol{boldsymbol{w^T}cdot x_i} + b)\ =& frac 1 2 left( sum_i^nlambda_i y_i boldsymbol{x_i} right)^T boldsymbol{cdot} left ( sum_j^n lambda_j y_j boldsymbol{x_j} right)+sum_i^n lambda_i – sum_i^n lambda_iy_i left (left( sum_j^n lambda_j y_j boldsymbol{x_j} right)cdot boldsymbol{x_i}+b right)\ =& frac 1 2 sum_i^nlambda_i y_i boldsymbol{x_i} ^T boldsymbol{cdot} sum_j^n lambda_j y_j boldsymbol{x_j} +sum_i^n lambda_i – sum_i^n lambda_iy_i left (left( sum_j^n lambda_j y_j boldsymbol{x_j} right)cdot boldsymbol{x_i}+b right)\ =& frac 1 2 sum_i^nsum_j^n lambda_ilambda_jy_iy_j (boldsymbol{x_i^Tcdot x_j})+sum_i^n lambda_i – sum_i^nsum_j^n lambda_ilambda_jy_iy_j (boldsymbol{x_i^Tcdot x_j})-sum_i^nlambda_i y_ib\ =&- frac 1 2sum_i^nsum_j^n lambda_ilambda_jy_iy_j (boldsymbol{x_i^Tcdot x_j}) + sum_i^n lambda_i\ end{aligned} ]

這個函數是對(boldsymbol{w},b)求極小後的函數，那麼現在它只與(lambda)有關。這樣我們就得到了對偶問題，對(lambda)求極大
[ begin{aligned} underset lambda {max} ;; &- frac 1 2 sum_i^nsum_j^n lambda_ilambda_jy_iy_j (boldsymbol{x_i^Tcdot x_j}) + sum_i^n lambda_i\ s.t.;;& sum_i^n lambda_i y_i = 0 \ & lambda_i ge 0, ;; i=1,cdots,n end{aligned} ]
根據凸優化習慣，將極大化轉化為極小化
[ begin{aligned} underset lambda {min} ;; & frac 1 2 sum_i^nsum_j^n lambda_ilambda_jy_iy_j (boldsymbol{x_i^Tcdot x_j}) – sum_i^n lambda_i\ s.t.;;& sum_i^n lambda_i y_i = 0 \ & lambda_i ge 0, ;; i=1,cdots,n end{aligned} ]
其中，只有(lambda)是未知變數，當未知變數個數較少時，可以較輕鬆的算出來，比如李航書中給出一個(lambda)數量為3的例題，可以直接將下面約束中的等式將其中一個變數帶換掉，然後對兩個未知變數求偏導。依據不等式約束判斷是否符合，不符合則在邊界取得極值，兩個變數嘗試邊界也較簡單，分別帶入比較大小即可。可是該對偶問題的未知變數(lambda)的數量與樣本數成正比，機器學習中成千上萬的樣本量使得計算變得非常複雜，很多變數不能輕易消去，且帶邊界的時候有很多組合。於是下面介紹簡化這個問題的優化演算法——SMO。

2.2 序列最小最優演算法（SMO）

2.2.1 坐標下降法

  SMO演算法的思想與坐標下降法十分類似，因此先介紹下坐標下降法。它是一種非梯度優化演算法，梯度優化演算法是每次選擇梯度最大的方向進行優化，當然這使得每次優化的程度較大。不過計算量較多，尤其是變數較多的情況。而坐標下降法每次只對一個坐標方向進行優化，如此循環，對每個坐標軸依次優化。這樣的做法可能會使得優化過程顯得較為」曲折「，不過中間每步對單個坐標軸的計算比整個梯度的計算小得多。可以由下圖表示

  坐標下降法不一定是對坐標方向進行優化，也可以自己選擇一組基，對這組基的方向進行優化。不過它的優化方向仍是在一開始就決定了。SMO也是這種思想，在SVM的對偶問題中，其對偶變數為(boldsymbollambda)，而(boldsymbollambda)的數量與樣本的數量成正比。對如此多的變數同時優化無疑是比較困難的，因此借鑒坐標下降法，對其中一部分變數進行優化，不斷循環的對所有變數依次優化，這樣迭代可以得到一個期望的優化結果。

  對於SVM的對偶問題
[ begin{aligned} underset lambda {min} ;; & frac 1 2 sum_i^nsum_j^n lambda_ilambda_jy_iy_j (boldsymbol{x_i^Tcdot x_j}) – sum_i^n lambda_i\ s.t.;;& sum_i^n lambda_i y_i = 0 \ & lambda_i ge 0, ;; i=1,cdots,n end{aligned} ]
由於(boldsymbollambda)數量等於樣本((boldsymbol{x_i},y_i))數量，使得這個二次規劃問題計算量較大，因此選擇其中兩個作為變數，其他看做常數，對這兩個變數解二次規劃問題，並且這時兩個變數滿足約束$sum_i^n lambda_i y_i = 0 $ ，所以這個問題有解析解，求解速度非常快。

• Q：為什麼選兩個變數？

  同樣是因為約束條件$sum_i^n lambda_i y_i = 0 $ ，(lambda_i)在更新後需要滿足它們之間的等式，所以需要同時更新兩個變數。

2.2.2 SMO求解方法

  不失一般性，假設選擇的兩個變數為(lambda_1,lambda_2) ，其他變數看作常數，則原二次規劃問題變為
[ begin{aligned} underset {lambda_1,lambda_2} {min} ;;;;;;;; & W(lambda_1,lambda_2)=frac 1 2 lambda_1^2(x_1^Tx_1)+frac 1 2 lambda_2^2(x_2^Tx_2) + lambda_1lambda_2y_1y_2(x_1^Tx_2) + \ &;;;;;;;;;;;;;;; lambda_1y_1sum_{i=3}^nlambda_iy_i(x_1^Tx_i) + lambda_2y_2sum_{i=3}^nlambda_iy_i(x_2^Tx_i) -(lambda_1+lambda_2)+ Constant \ s.t.;;;;;;;;;& lambda_1y_1+lambda_2y_2=-sum_{i=3}^nlambda_iy_i= zeta \ & lambda_i ge 0, ;; i=1,2 end{aligned} ]
對這兩個變數的優化中，其中的等式約束給出了它們之間的關係。那麼可用其中一個表示另一個變為一個變數的優化，這裡用(lambda_1)表示(lambda_2)，且目標函數中的常數項不需要再考慮
[ lambda_1 =y_1zeta – lambda_2 y_1y_2 tag{2.2.2-1} ]
  通過等式約束得到兩個變數之間的關係後，將其帶入原優化表達式，便能夠對單變數進行優化，這當然是我們希望看到的情況，不過除了等式約束還有不等式約束。好在只有兩個變數，我們可以先計算出單變數迭代的結果，再考察是否滿足不等式約束，對結果進行修剪。

2.2.2.1 求解等式約束

   簡化表達，記
[ v_i = sum_{j=3}^n lambda_jy_j(x_i^Tx_j) ]
則目標函數可寫作
[ begin{aligned} W(lambda_1,lambda_2)=& frac 1 2 lambda_1^2(x_1^Tx_1)+frac 1 2 lambda_2^2(x_2^Tx_2) + lambda_1lambda_2y_1y_2(x_1^Tx_2) + \ &;;;;; lambda_1y_1v_1 + lambda_2y_2v_2 -(lambda_1+lambda_2) \ end{aligned} tag{2.2.2.1-1} ]
將((2.2.1-1))代入得到
[ begin{aligned} W(lambda_2)=& frac 1 2 (zeta – lambda_2 y_2)^2(x_1^Tx_1)+frac 1 2 lambda_2^2(x_2^Tx_2) + (zeta – lambda_2 y_2)lambda_2y_2(x_1^Tx_2) + \ &;;;;; (zeta – lambda_2 y_2)v_1 + lambda_2y_2v_2 -y_1(zeta – lambda_2 y_2)-lambda_2 \ end{aligned} tag{2.2.2.1-1} ]
對(lambda_2)求偏導，
[ frac {partial W} {part lambda_2} = lambda_2 (x_1^Tx_1) – zeta y_2(x_1^Tx_1) + lambda_2(x_2^Tx_2) -2lambda_2 (x_1^Tx_2) + zeta y_2 (x_1^Tx_2) \ -y_2 v_1 + y_2 v_2 + y_1y_2 – 1 ]
令為0
[ begin{aligned} (x_1^Tx_1+x_2^Tx_2-2x_1^Tx_2)lambda_2 =& zeta; y_2[;(x_1^Tx_1)-(x_1^Tx_2)] + y_2(v_1-v_2)+y_2(y_2-y_1)\ =& y_2;[ zeta (x_1^Tx_1-x_1^Tx_2) + (v_1-v_2)+(y_2-y_1) ] end{aligned}tag{2.2.2.1-2} ]

將(zeta = y_1lambda_1^{old} +y_2lambda_2^{old})與(v_1,v_2)代入得到右邊
[ begin{aligned} &y_2 left [ (y_1lambda_1^{old}+y_2lambda_2^{old})(x_1^Tx_1-x_1^Tx_2) +left ( sum_{j=3}^nlambda_j^{old}y_j(x_1^Tx_j) right)- left ( sum_{j=3}^nlambda_j^{old}y_j(x_2^Tx_j) right) +y_2 – y_1 right]\ =& y_2 left [ y_2lambda_2^{old}(x_1^Tx_1+x_2^Tx_2-2x_1^Tx_2)+ left ( sum_{j=1}^nlambda_j^{old}y_j(x_1^Tx_j) right)- left ( sum_{j=1}^nlambda_j^{old}y_j(x_2^Tx_j) right) +y_2-y_1 right]\ end{aligned} ]
上式將後面求和缺少的前兩項補上了，這樣前面湊出來的部分正好和(2.2.2.1-2)的左端係數相同，再看後面部分的求和(sum_{j=1}^nlambda_j^{old}y_j(x_1^Tx_j)) ，若加上偏置(b)，則表示的正是輸入數據(x_1)到超平面的函數間隔，後面還有個(y_1)，表示(x_1)的正確類別，這似乎是故意湊好的，它們之差就是對(x_i)的預測值和它的真實值的差。且SVM中的函數間隔是以支援向量的1作為標準，與(y)的取值({-1,1})可以說是一個標準下的比較。對上式稍作調整
[ begin{aligned} & y_2 left [ y_2lambda_2^{old}(x_1^Tx_1+x_2^Tx_2-2x_1^Tx_2)+ left ( sum_{j=1}^nlambda_j^{old}y_j(x_1^Tx_j) right)- left ( sum_{j=1}^nlambda_j^{old}y_j(x_2^Tx_j) right) +y_2-y_1 right]\ =&lambda_2^{old}(x_1^Tx_1+x_2^Tx_2-2x_1^Tx_2) + y_2left [left ( sum_{j=1}^nlambda_j^{old}y_j(x_1^Tx_j) -bright)-y_1 right] – y_2left [ left ( sum_{j=1}^nlambda_j^{old}y_j(x_2^Tx_j) -b right) -y_2 right] end{aligned} ]
為表述方便，令對(x)的預測值為函數(g(x))，其實這就是SVM的分類函數
[ g(x) = sum_{i=1}^nlambda_iy_i(x^Tx_i) -b ]
令預測值與真實值之差為(E)
[ E_i = g(x_i) -y_i ]
將右端結果帶回式((2.2.2.1-2))
[ begin{aligned} (x_1^Tx_1+x_2^Tx_2-2x_1^Tx_2)lambda_2 =& lambda_2^{old}(x_1^Tx_1+x_2^Tx_2-2x_1^Tx_2) + y_2(E_1-E_2) end{aligned} ]
令(eta=(x_1^Tx_1+x_2^Tx_2-2x_1^Tx_2)),帶入得到未修剪的(lambda_2^{new,unc})
[ lambda_2^{new,unc} = lambda_2^{old} + frac {y_2(E_1-E_2)}{eta} ]

2.2.2.2 不等式約束修剪

   上面求解了優化問題在等式約束下的解，對於這兩個變數來說，等式約束實際上把他們約束在一條平面直線上，而(lambda ge 0)便將它們約束到第一象限。其且它們的係數不是-1就是1，這意味著它們組成的直線只有兩個方向，(45^o或135^o) 。這樣就能通過作圖來確定它們的上下界，且通過關係式的直線，只需確定(lambda_2)的範圍即可。這裡只有下界限制，後面軟間隔需要添加合頁損失函數，那時會有上界，不過處理方法都相同，先看這裡的情況，注意變數只有(lambda_2)

  如圖，當(y_1 ne y_2)時，約束區域是圖中的實心線，(lambda_2)的下界與直線在(lambda_2)軸上的截距有關，且(lambda_2)上的截距可表示為
[ lambda_2 – lambda_1 = b ]
當截距(b>0)，即綠線情況時，才會取這個截距為下界，不然就取0，即
[ L = max(0,b) ]
  當(y_1 = y_2)時，其下界只需滿足(lambda_2 ge 0)即可，不過這種情況為它帶來了上界，圖中很清楚，若(lambda_2)的數值超過其在(lambda_2)軸上的截距(b=lambda_1+lambda_2)，則(lambda_1)會小於0，因此
[ L = 0 ,\ H = b ]
綜上
[ begin{cases} max(0,lambda_2^{old} – lambda_1^{old})le lambda_2^{new} , ;; &y_1 ne y_2\ 0 le lambda_2^{new} le lambda_1^{old} + lambda_2^{old}, &y_1=y_2 end{cases} ]
  這是不等式約束(lambda ge 0)帶來的下界，將得到的未修剪(lambda_2^{new,unc})與之比較，若滿足上述約束，則(lambda_2^{new} = lambda_2^{new,unc}) ，若不滿足約束，則取下界值即可。 這種情況較簡單，在下一節解決軟間隔SVM的時候，加入合頁損失函數，不等式約束變為(0 le lambda le C) ，則變數不止有下界，還有上界了。不過仍可用相同的分析方法。

  這是添加了合頁損失函數後的約束空間，用截距的方法也比較容易分析，圖中綠色的線會確定一個(lambda_2)的下界，紅色的線會確定一個上界，注意仍考慮(lambda_2)的範圍。

  當(y_1 ne y_2)時，截距大於0的綠線會確定一個下界，截距小於0的紅線會確定一個上界
[ L = max(0, lambda_2^{old} – lambda_1^{old}) ,\ H = min(C, lambda_2^{old} – lambda_1^{old} +C ) ]
  當(y_1 = y_2)時， 截距大於C的綠線會確定一個下界，截距小於C的紅線會確定一個上界
[ L = max(0,lambda_1^{old}+ lambda_2^{old} – C),\ H = min(C,lambda_1^{old} + lambda_2^{old} ) ]
得到其不等式約束後，便可對前面求得的未修剪的(lambda_2^{new,unc}) 進行修剪，修剪後的數據代入SMO優化問題繼續迭代，直到達到迭代誤差要求。

2.2.2.3 變數的選擇方法

留坑

  最終，我們得到了分離超平面
[ sum_i^n lambda_i^* y_i (x^Tx_i)+ b^* = 0 ]
分類決策函數
[ f(x) = signleft ( sum_i^n lambda_i^* y_i (x^Tx_i) + b^* right) ]
上式意味著，分類決策函數只依賴於輸入樣本的(x)和訓練樣本的(x)之間的內積。這是後面引入核方法進行非線性推廣的基礎。同時，決策函數中的內積只需要計算輸入向量和樣本求出的支援向量之間的即可。因為其他非支援向量的係數(lambda)為0，支援向量機便是這樣一個由少數支援向量決定的分類模型。

3. 線性不可分SVM

  前述演算法是針對數據線性可分的情況，在數據不可分的情況該演算法無法收斂。不過在明白了線性可分SVM的基礎原理後，將其推廣至線性不可分的SVM其實並不難。

3.1 鬆弛變數

  若一組數據整體線性可分，只是有一些奇異點干擾。如下圖

這些少量的奇異點使得不能找到一個超平面將所有數據正確劃分，然而數據整體又是可分的，為了繼續使用線性SVM，我們需要對這些奇異點添加一個鬆弛變數(xi)。也就是對它們的錯誤進行一定程度的容忍，也就是使得這些奇異點的函數間隔加上鬆弛變數後能夠滿足大於等於1 的約束。
[ widehat gamma = y_i(wcdot x_i + b ) + xi_i ge 1 ]
既然對約束條件進行了弱化，那麼就需要在目標優化函數(frac 1 2 ||w||^2)中付出一定的代價
[ frac 1 2 ||w||^2 + C sum_i^n xi _i ]
其中，(xi ge 0)

  由此得到新的SVM優化問題
[ begin{aligned} underset {w,b,xi} {min} ;;; & frac 1 2 ||w||^2 + C sum_i^n xi _i\ s.t. ;;; & y_i(wcdot x_i + b) + xi_i ge 1\ & xi_i ge 0 end{aligned} ]
得到軟間隔下的優化問題後，步驟就與線性可分SVM相同了，先找到對偶問題，再用SMO演算法求解即可。

3.2 求解對偶問題

  找對偶問題也是按流程來就行了，先列出拉格朗日函數，轉化為極大極小問題，求解關於(w,b,xi)的極小問題，再對得到的極小函數求解關於(lambda,eta) 的極大問題，也就是對偶問題。

• 原始問題的拉格朗日函數

[ L(w,b,xi,lambda,eta) = frac 1 2 ||w||^2 + Csum_i^nxi_i – sum_i^nlambda_i[y_i(wcdot x_i+b)+xi_i -1] – sum_i^n eta_i xi_i tag{3.1} ]

其中，(lambda_ige 0,eta ge 0)。

  轉化為極大極小問題，先求解關於(w,b,xi) 的極小問題，對拉格朗日函數求關於(w,b,xi)的偏導並令為0
[ triangledown_ w L(w,b,xi,lambda,eta)=w – sum_i^n lambda_i y_i x_i = 0\ triangledown _b L(w,b,xi,lambda,eta) = -sum_i^n lambda_iy_i = 0\ triangledown _xi L(w,b,xi,lambda,eta) = C – lambda_i – eta_i = 0 ]
得到
[ begin{eqnarray*} sum_i^nlambda_i y_i x_i &=& w tag{3.2} \ sum_i^nlambda_i y_i &=& 0 tag{3.3} \ C – lambda_i – eta_i &=& 0 tag{3.4} end{eqnarray*} ]
將它們帶回式((3.1))
[ begin{aligned} underset {w,b,xi} {min} ;;L(w,b,xi,lambda,eta) =& frac 1 2left ( sum_i^nlambda_iy_ix_i right)left ( sum_j^nlambda_jy_jx_j right) +(C -lambda_i-eta_i)sum_i^n xi_i -\ & ;;;;;; sum_i^n lambda_iy_isum_j^nlambda_jy_jx_j^Tx_i-sum_i^n lambda_iy_ib+sum_i^nlambda_i\ =& -frac 1 2 sum_i^nsum_j^nlambda_ilambda_jy_iy_j(x_i^Tx_j) + sum_i^nlambda_i end{aligned} ]
再對其求關於(lambda,eta) 的極大即得到對偶問題
[ begin{aligned} underset {lambda,eta}{max} ;; &-frac 1 2sum_i^nsum_j^nlambda_ilambda_jy_iy_j(x_i^Tx_j) + sum_i^Tlambda_i\ s.t.;; & sum_i^n lambda_iy_i = 0\ &C-lambda_i-eta_i = 0\ &lambda_i ge 0 , ;; i=1,cdots,n\ &eta _i ge 0 ,;; i=1,cdots,n end{aligned} ]
注意被優化函數中並沒有(eta)，和有關於它的等式，將(eta_i = C-lambda_i)帶入(eta_ige 0)
[ C ge lambda_i ]
整理得到
[ begin{aligned} underset {lambda}{max} ;; &-frac 1 2sum_i^nsum_j^nlambda_ilambda_jy_iy_j(x_i^Tx_j) + sum_i^Tlambda_i\ s.t.;; & sum_i^n lambda_iy_i = 0\ & 0le lambda_i le C ,;;;i=1,cdots,n end{aligned} ]
  相較與線性可分下的SVM，軟間隔SVM的對偶問題在形式上只比線性可分情況下的對偶問題多一個(lambda_i) 的上界約束C，對於求解過程中的差異主要表現在SMO演算法的修剪過程中，需要確定的約束範圍變小了。而這一變化在上節線性 可分SVM的SMO中已經給出了，後面的SMO過程可以說與線性可分SVM完全相同了。這樣就得到一個可以容忍雜訊奇異點干擾的SVM線性分類器了。

3.3 支援向量求解參數(w,b)

  求解出對偶問題的參數(lambda) 後，還需考慮一個問題，就是如何通過這個參數(lambda)和訓練數據({x,y})得到我們需要的參數(w,b) 。因為原始問題是凸二次規劃問題，可以通過KKT條件來從原始問題中找出(w,b) 與(lambda,x,y) 之間的關係。

  根據KKT條件中的梯度為0條件，可以很容易的得出(w)的表達式
[ triangledown_wL(w^*,b^*,xi^*,lambda^*,eta^*) = w^* – sum_i^nlambda_i^*y_ix_i = 0 ]
得到
[ w^* = sum_i^n lambda_i^* y_i x_i ]
  對於(b)，並沒有一個直接的等式讓我們求出其表達式。唯一一個等式是由鬆弛互補性得到的
[ lambda_i ( y_i(w^*cdot x + b^*) + xi_i^*-1) = 0 tag{3.5} ]
如果(lambda_i > 0)的話，那麼就能得到一個關於(b)的等式
[ begin{aligned} b^* =& (1-xi_i^*)y_i -w^*cdot x\ =&(1-xi_i^*)y_i – sum_j^nlambda_j^*y_j(x_i^Tx_j) end{aligned} tag{3.6} ]
其中，(xi_i^*)比較討厭，但是在一定條件下可以利用KKT中其他約束將其消去
[ begin{eqnarray*} triangledown_xi L(w^*,b^*,xi^*,lambda^*,eta^*) = C-lambda_i-eta_i = 0 tag{3.7} \ eta_i xi_i = 0 tag{3.8} end{eqnarray*} ]
由((3.7)與(3.8))可以得到，當(0<lambda_i < C) 時，(eta_i > 0)，(xi_i = 0)，此時
[ b = y_i -sum_j^nlambda_j^*y_j (x_i^Tx_j) ]
當(lambda_i = C) 時，則(xi_i)不一定等於0了，而是很有可能大於0，此時若用(lambda_i) 進行計算就得使用((3.6))的形式，因此在參數(b)的計算中，最好的情況是找一個(0<lambda_i < C)的點進行計算。

  事實上，如圖，當(0<lambda_i< C)時，樣本(x_i) 便是支援向量，其代價(xi_i = 0) ，正好在間隔邊界上。當(lambda_i = 0)時，該向量不是支援向量，位於正確分割的間隔邊界外。當$ lambda_i = C,;xi_i<1$ 時，此時(x_i)也是支援向量，被正確分割，位於超平面和正確分割邊界之間。當(lambda_i = C, ; xi_i = 1) 時，(x_i)是支援向量，位於超平面上。當(lambda_i = C,; xi_i > 1) 時，(x_i)是支援向量，位於誤分類一側。

  所以，(b) 的計算最好選擇恰在間隔邊界上的支援向量。

4. 非線性SVM

  在線性SVM中，我們求解的目標都是一個線性的分離超平面
[ w^Tcdot x + b = 0 ]
只要參數(w，b) 得到了，那對於新的輸入向量(x) ，其不同分量與(w)分量的線性組合（也就是內積）加上(b) 便決定了分類結果。顯然以此定義的模型只能訓練出線性分類模型。

  若要實現對非線性模型的分類，我們需要得到一些關於(x) 分量的一些非線性組合。(w)是(x)的係數，那隻能從(x)入手了。如果將(x)的不同分量映射到一個更高維的空間，這些映射後的分量的線性組合也能實現(x) 原分量的非線性組合。比如
[ x = begin{bmatrix} x_1\ x_2 end{bmatrix};;; Rightarrow ;;; Phi = begin{bmatrix} x_1^2\ x_1x_2\ x_2^2 end{bmatrix} ]
其中，(x)的維度是2，說明這應該是一個在二維平面中分類的模型，(Phi) 是(x) 的一個映射，映射後的數據變為了三維的，但是其訓練後關於這三個變數的線性組合中變數仍只有(x_1,x_2) ，不過通過對它訓練，我們可以得到一個關於(x_1,x_2)的非線性模型，比如訓練得到的參數 (w=[1,0,1]^T) ，那實際上得到的是一個關於(x_1,x_2) 的一個圓。

  這種方法將原始數據映射到新的高維空間，也叫特徵空間（希爾伯特空間）。關於希爾伯特空間可參考上海交通大學公開課 ，希爾伯特空間可大致理解為有限的歐幾里得內積空間添加了完備性後的空間。這裡有一篇對這個公開課較好的總結 。由泰勒展開公式可知，一個函數展開到的階數越高，就越能擬合複雜的曲線。上面的例子中階數僅僅提升到2，若有較複雜的分割模型，它仍不能較好的完成任務。但是若將其提升到很高的維度，甚至是無窮大維，計算量是非常大甚至是難以計算的。因為既要計算(x)到(Phi)的映射，還要計算高維(Phi)與係數的乘積後的求和。

  現在似乎找到了解決非線性問題的一個方法，但是計算量太大了，幸運的是，在SVM的對偶問題中，目標函數與求解得到的分類決策函數都是輸入向量之間的內積
[ W(lambda) = frac 1 2 sum_i^nsum_j^n lambda_ilambda_jy_iy_j (x_i^Tx_j) – sum_i^n lambda_i ]
輸入向量使用相同的映射到高維空間，並且是內積的形式，那麼這種情況可以使用核方法來減少計算量。核方法可以跳過求解(x)到(Phi)的映射和計算映射後的函數的內積的過程。

  它的主要依據是，先定義一個關於原輸入向量內積的核函數，總可以將其拆解為輸入向量的映射之間的內積的形式。比如一個簡單的 平方核函數
[ K(x,z) = (xcdot z)^2 ]
它是關於輸入向量的內積的平方函數，可以通過將輸入向量映射到
[ Phi(x) = (x_1^2,sqrt2 x_1x_2,x_2^2)^T ]
可以驗證
[ Phi(x) cdot Phi(z) = (xcdot z)^2 = K(x,z) ]
當然拆解的映射函數不止這一種，這說明當需要將一個向量映射到高維空間並且作內積時，為了減少計算量，可以不用管映射函數，而只是計算核函數的值便等價與計算映射後的函數的內積。

  核函數肯定不是隨便定義一個都行的，它需要滿足正定核條件，正定核的充要條件是該核函數的Gram矩陣是半正定的。

5. Reference:

[1] Convex Optimization

[2] Pattern Recognition and Machine Learning.

[3] 統計學習方法