# 4 -- Soft-Margin Support Vector Machine 上節課我們主要介紹了Kernel SVM。先將特征轉換和計算內積這兩個步驟合并起來，簡化計算、提高計算速度，再用Dual SVM的求解方法來解決。Kernel SVM不僅能解決簡單的線性分類問題，也可以求解非常復雜甚至是無限多維的分類問題，關鍵在于核函數的選擇，例如線性核函數、多項式核函數和高斯核函數等等。但是，我們之前講的這些方法都是Hard-Margin SVM，即必須將所有的樣本都分類正確才行。這往往需要更多更復雜的特征轉換，甚至造成過擬合。本節課將介紹一種Soft-Margin SVM，目的是讓分類錯誤的點越少越好，而不是必須將所有點分類正確，也就是允許有noise存在。這種做法很大程度上不會使模型過于復雜，不會造成過擬合，而且分類效果是令人滿意的。 ### **Motivation and Primal Problem** 上節課我們說明了一點，就是SVM同樣可能會造成overfit。原因有兩個，一個是由于我們的SVM模型（即kernel）過于復雜，轉換的維度太多，過于powerful了；另外一個是由于我們堅持要將所有的樣本都分類正確，即不允許錯誤存在，造成模型過于復雜。如下圖所示，左邊的圖是線性的，雖然有幾個點分類錯誤，但是大部分都能完全分開。右邊的圖是四次多項式，所有點都分類正確了，但是模型比較復雜，可能造成過擬合。直觀上來說，左邊的圖是更合理的模型。  如何避免過擬合？方法是允許有分類錯誤的點，即把某些點當作是noise，放棄這些noise點，但是盡量讓這些noise個數越少越好。回顧一下我們在機器學習基石筆記中介紹的pocket算法，pocket的思想不是將所有點完全分開，而是找到一條分類線能讓分類錯誤的點最少。而Hard-Margin SVM的目標是將所有點都完全分開，不允許有錯誤點存在。為了防止過擬合，我們可以借鑒pocket的思想，即允許有犯錯誤的點，目標是讓這些點越少越好。  為了引入允許犯錯誤的點，我們將Hard-Margin SVM的目標和條件做一些結合和修正，轉換為如下形式：  修正后的條件中，對于分類正確的點，仍需滿足，而對于noise點，滿足，即沒有限制。修正后的目標除了項，還添加了，即noise點的個數。參數C的引入是為了權衡目標第一項和第二項的關系，即權衡large margin和noise tolerance的關系。 我們再對上述的條件做修正，將兩個條件合并，得到：  這個式子存在兩個不足的地方。首先，最小化目標中第二項是非線性的，不滿足QP的條件，所以無法使用dual或者kernel SVM來計算。然后，對于犯錯誤的點，有的離邊界很近，即error小，而有的離邊界很遠，error很大，上式的條件和目標沒有區分small error和large error。這種分類效果是不完美的。  為了改正這些不足，我們繼續做如下修正：  修正后的表達式中，我們引入了新的參數來表示每個點犯錯誤的程度值，。通過使用error值的大小代替是否有error，讓問題變得易于求解，滿足QP形式要求。這種方法類似于我們在機器學習基石筆記中介紹的0/1 error和squared error。這種soft-margin SVM引入新的參數。 至此，最終的Soft-Margin SVM的目標為：  條件是：   其中，表示每個點犯錯誤的程度，，表示沒有錯誤，越大，表示錯誤越大，即點距離邊界（負的）越大。參數C表示盡可能選擇寬邊界和盡可能不要犯錯兩者之間的權衡，因為邊界寬了，往往犯錯誤的點會增加。large C表示希望得到更少的分類錯誤，即不惜選擇窄邊界也要盡可能把更多點正確分類；small C表示希望得到更寬的邊界，即不惜增加錯誤點個數也要選擇更寬的分類邊界。 與之對應的QP問題中，由于新的參數的引入，總共參數個數為，限制條件添加了，則總條件個數為2N。  ### **Dual Problem** 接下來，我們將推導Soft-Margin SVM的對偶dual形式，從而讓QP計算更加簡單，并便于引入kernel算法。首先，我們把Soft-Margin SVM的原始形式寫出來：  然后，跟我們在第二節課中介紹的Hard-Margin SVM做法一樣，構造一個拉格朗日函數。因為引入了，原始問題有兩類條件，所以包含了兩個拉格朗日因子和。拉格朗日函數可表示為如下形式：  接下來，我們跟第二節課中的做法一樣，利用Lagrange dual problem，將Soft-Margin SVM問題轉換為如下形式：  根據之前介紹的KKT條件，我們對上式進行簡化。上式括號里面的是對拉格朗日函數計算最小值。那么根據梯度下降算法思想：最小值位置滿足梯度為零。 我們先對做偏微分：  根據上式，得到，因為有，所以限制。將代入到dual形式中并化簡，我們發現和都被消去了：  這個形式跟Hard-Margin SVM中的dual形式是基本一致的，只是條件不同。那么，我們分別令拉個朗日函數L對b和w的偏導數為零，分別得到：   經過化簡和推導，最終標準的Soft-Margin SVM的Dual形式如下圖所示：  Soft-Margin SVM Dual與Hard-Margin SVM Dual基本一致，只有一些條件不同。Hard-Margin SVM Dual中，而Soft-Margin SVM Dual中，且新的拉格朗日因子。在QP問題中，Soft-Margin SVM Dual的參數同樣是N個，但是，條件由Hard-Margin SVM Dual中的N+1個變成2N+1個，這是因為多了N個的上界條件。 對于Soft-Margin SVM Dual這部分推導不太清楚的同學，可以看下第二節課的筆記：[2 – Dual Support Vector Machine](http://blog.csdn.net/red_stone1/article/details/73822768) ### **Messages behind Soft-Margin SVM** 推導完Soft-Margin SVM Dual的簡化形式后，就可以利用QP，找到Q，p，A，c對應的值，用軟件工具包得到的值。或者利用核函數的方式，同樣可以簡化計算，優化分類效果。Soft-Margin SVM Dual計算的方法過程與Hard-Margin SVM Dual的過程是相同的。  但是如何根據的值計算b呢？在Hard-Margin SVM Dual中，有complementary slackness條件：，找到SV，即的點，計算得到。 那么，在Soft-Margin SVM Dual中，相應的complementary slackness條件有兩個（因為兩個拉格朗日因子和）：   找到SV，即的點，由于參數的存在，還不能完全計算出b的值。根據第二個complementary slackness條件，如果令，即，則一定有，代入到第一個complementary slackness條件，即可計算得到。我們把的點稱為free SV。引入核函數后，b的表達式為：  上面求解b提到的一個假設是，這個假設是否一定滿足呢？如果沒有free SV，所有大于零的點都滿足怎么辦？一般情況下，至少存在一組SV使的概率是很大的。如果出現沒有free SV的情況，那么b通常會由許多不等式條件限制取值范圍，值是不確定的，只要能找到其中滿足KKT條件的任意一個b值就可以了。這部分細節比較復雜，不再贅述。  接下來，我們看看C取不同的值對margin的影響。例如，對于Soft-Margin Gaussian SVM，C分別取1，10，100時，相應的margin如下圖所示：  從上圖可以看出，C=1時，margin比較粗，但是分類錯誤的點也比較多，當C越來越大的時候，margin越來越細，分類錯誤的點也在減少。正如前面介紹的，C值反映了margin和分類正確的一個權衡。C越小，越傾向于得到粗的margin，寧可增加分類錯誤的點；C越大，越傾向于得到高的分類正確率，寧可margin很細。我們發現，當C值很大的時候，雖然分類正確率提高，但很可能把noise也進行了處理，從而可能造成過擬合。也就是說Soft-Margin Gaussian SVM同樣可能會出現過擬合現象，所以參數的選擇非常重要。 我們再來看看取不同值是對應的物理意義。已知滿足兩個complementary slackness條件：   若，得。表示該點沒有犯錯，表示該點不是SV。所以對應的點在margin之外（或者在margin上），且均分類正確。 若，得，且。表示該點沒有犯錯，表示該點在margin上。這些點即free SV，確定了b的值。 若，不能確定是否為零，且得到，這個式表示該點偏離margin的程度，越大，偏離margin的程度越大。只有當時，該點落在margin上。所以這種情況對應的點在margin之內負方向（或者在margin上），有分類正確也有分類錯誤的。這些點稱為bounded SV。 所以，在Soft-Margin SVM Dual中，根據的取值，就可以推斷數據點在空間的分布情況。  ### **Model Selection** 在Soft-Margin SVM Dual中，kernel的選擇、C等參數的選擇都非常重要，直接影響分類效果。例如，對于Gaussian SVM，不同的參數，會得到不同的margin，如下圖所示。  其中橫坐標是C逐漸增大的情況，縱坐標是逐漸增大的情況。不同的組合，margin的差別很大。那么如何選擇最好的等參數呢？最簡單最好用的工具就是validation。 validation我們在機器學習基石課程中已經介紹過，只需要將由不同等參數得到的模型在驗證集上進行cross validation，選取最小的對應的模型就可以了。例如上圖中各種組合得到的如下圖所示：  因為左下角的最小，所以就選擇該對應的模型。通常來說，并不是的連續函數，很難使用最優化選擇（例如梯度下降）。一般做法是選取不同的離散的值進行組合，得到最小的，其對應的模型即為最佳模型。這種算法就是我們之前在機器學習基石中介紹過的V-Fold cross validation，在SVM中使用非常廣泛。 V-Fold cross validation的一種極限就是Leave-One-Out CV，也就是驗證集只有一個樣本。對于SVM問題，它的驗證集Error滿足：  也就是說留一法驗證集Error大小不超過支持向量SV占所有樣本的比例。下面做簡單的證明。令樣本總數為N，對這N個點進行SVM分類后得到margin，假設第N個點的，不是SV，即遠離margin（正距離）。這時候，如果我們只使用剩下的N-1個點來進行SVM分類，那么第N個點必然是分類正確的點，所得的SVM margin跟使用N個點的到的是完全一致的。這是因為我們假設第N個點是non-SV，對SV沒有貢獻，不影響margin的位置和形狀。所以前N-1個點和N個點得到的margin是一樣的。 那么，對于non-SV的點，它的，即對第N個點，它的Error必然為零：  另一方面，假設第N個點，即對于SV的點，它的Error可能是0，也可能是1，必然有：  綜上所述，即證明了。這符合我們之前得到的結論，即只有SV影響margin，non-SV對margin沒有任何影響，可以舍棄。 SV的數量在SVM模型選擇中也是很重要的。一般來說，SV越多，表示模型可能越復雜，越有可能會造成過擬合。所以，通常選擇SV數量較少的模型，然后在剩下的模型中使用cross-validation，比較選擇最佳模型。 ### **總結** 本節課主要介紹了Soft-Margin SVM。我們的出發點是與Hard-Margin SVM不同，不一定要將所有的樣本點都完全分開，允許有分類錯誤的點，而使margin比較寬。然后，我們增加了作為分類錯誤的懲罰項，根據之前介紹的Dual SVM，推導出了Soft-Margin SVM的QP形式。得到的除了要滿足大于零，還有一個上界C。接著介紹了通過值的大小，可以將數據點分為三種：non-SVs，free SVs，bounded SVs，這種更清晰的物理解釋便于數據分析。最后介紹了如何選擇合適的SVM模型，通常的辦法是cross-validation和利用SV的數量進行篩選。 **_注明：_** 文章中所有的圖片均來自臺灣大學林軒田《機器學習技法》課程