AI有道

一個有良心的公眾號

Hard-Margin SVM，必須將所有的樣本都分類正確才行。這往往需要更多更復雜的特征轉換，甚至造成過擬合。本文將介紹一種Soft-Margin SVM，目的是讓分類錯誤的點越少越好，而不是必須將所有點分類正確，也就是允許有noise存在。這種做法很大程度上不會使模型過于復雜，不會造成過擬合，而且分類效果是令人滿意的。

——前言

1

Motivation and Primal Problem

SVM同樣可能會造成overfit。原因有兩個，一個是由于我們的SVM模型（即kernel）過于復雜，轉換的維度太多，過于powerful了；另外一個是由于我們堅持要將所有的樣本都分類正確，即不允許錯誤存在，造成模型過于復雜。如下圖所示，左邊的圖Φ1是線性的，雖然有幾個點分類錯誤，但是大部分都能完全分開。右邊的圖Φ4是四次多項式，所有點都分類正確了，但是模型比較復雜，可能造成過擬合。直觀上來說，左邊的圖是更合理的模型。

如何避免過擬合？方法是允許有分類錯誤的點，即把某些點當作是noise，放棄這些noise點，但是盡量讓這些noise個數越少越好。回顧一下我們在機器學習基石筆記中介紹的pocket算法，pocket的思想不是將所有點完全分開，而是找到一條分類線能讓分類錯誤的點最少。而Hard-Margin SVM的目標是將所有點都完全分開，不允許有錯誤點存在。為了防止過擬合，我們可以借鑒pocket的思想，即允許有犯錯誤的點，目標是讓這些點越少越好。

為了引入允許犯錯誤的點，我們將Hard-Margin SVM的目標和條件做一些結合和修正，轉換為如下形式：

我們再對上述的條件做修正，將兩個條件合并，得到：

這個式子存在兩個不足的地方。首先，最小化目標中第二項是非線性的，不滿足QP的條件，所以無法使用dual或者kernel SVM來計算。然后，對于犯錯誤的點，有的離邊界很近，即error小，而有的離邊界很遠，error很大，上式的條件和目標沒有區分small error和large error。這種分類效果是不完美的。

為了改正這些不足，我們繼續做如下修正：

修正后的表達式中，我們引入了新的參數ξn來表示每個點犯錯誤的程度值，ξn≥0。通過使用error值的大小代替是否有error，讓問題變得易于求解，滿足QP形式要求。這種方法類似于我們在機器學習基石筆記中介紹的0/1 error和squared error。這種soft-margin SVM引入新的參數ξ。

至此，最終的Soft-Margin SVM的目標為：

條件是：

其中，ξn表示每個點犯錯誤的程度，ξn=0，表示沒有錯誤，ξn越大，表示錯誤越大，即點距離邊界（負的）越大。參數C表示盡可能選擇寬邊界和盡可能不要犯錯兩者之間的權衡，因為邊界寬了，往往犯錯誤的點會增加。large C表示希望得到更少的分類錯誤，即不惜選擇窄邊界也要盡可能把更多點正確分類；small C表示希望得到更寬的邊界，即不惜增加錯誤點個數也要選擇更寬的分類邊界。

與之對應的QP問題中，由于新的參數ξn的引入，總共參數個數為d^+1+N，限制條件添加了ξn≥0，則總條件個數為2N。

2

Dual Problem

接下來，我們將推導Soft-Margin SVM的對偶dual形式，從而讓QP計算更加簡單，并便于引入kernel算法。首先，我們把Soft-Margin SVM的原始形式寫出來：

然后，跟我們在第二節課中介紹的Hard-Margin SVM做法一樣，構造一個拉格朗日函數。因為引入了ξn，原始問題有兩類條件，所以包含了兩個拉格朗日因子αn和βn。拉格朗日函數可表示為如下形式：

接下來，我們利用Lagrange dual problem，將Soft-Margin SVM問題轉換為如下形式：

根據之前介紹的KKT條件，我們對上式進行簡化。上式括號里面的是對拉格朗日函數L(b,w,ξ,α,β)計算最小值。那么根據梯度下降算法思想：最小值位置滿足梯度為零。

我們先對ξn做偏微分：

根據上式，得到βn=C?αn，因為有βn≥0，所以限制0≤αn≤C。將βn=C?αn代入到dual形式中并化簡，我們發現βn和ξn都被消去了：

這個形式跟Hard-Margin SVM中的dual形式是基本一致的，只是條件不同。那么，我們分別令拉個朗日函數L對b和w的偏導數為零，分別得到：

經過化簡和推導，最終標準的Soft-Margin SVM的Dual形式如下圖所示：

oft-Margin SVM Dual與Hard-Margin SVM Dual基本一致，只有一些條件不同。Hard-Margin SVM Dual中αn≥0，而Soft-Margin SVM Dual中0≤αn≤C，且新的拉格朗日因子βn=C?αn。在QP問題中，Soft-Margin SVM Dual的參數αn同樣是N個，但是，條件由Hard-Margin SVM Dual中的N+1個變成2N+1個，這是因為多了N個αn的上界條件。

3

Messages behind Soft-Margin SVM

推導完Soft-Margin SVM Dual的簡化形式后，就可以利用QP，找到Q，p，A，c對應的值，用軟件工具包得到αnαn的值。或者利用核函數的方式，同樣可以簡化計算，優化分類效果。Soft-Margin SVM Dual計算αn的方法過程與Hard-Margin SVM Dual的過程是相同的。

那么，在Soft-Margin SVM Dual中，相應的complementary slackness條件有兩個（因為兩個拉格朗日因子αn和βn）：

上面求解b提到的一個假設是αs<C，這個假設是否一定滿足呢？如果沒有free SV，所有αs大于零的點都滿足αs=C怎么辦？一般情況下，至少存在一組SV使αs<C的概率是很大的。如果出現沒有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同樣可能會出現過擬合現象，所以參數(γ,C)的選擇非常重要。

我們再來看看αnαn取不同值是對應的物理意義。已知0≤αn≤C滿足兩個complementary slackness條件：

所以，在Soft-Margin SVM Dual中，根據αnαn的取值，就可以推斷數據點在空間的分布情況。

4

Model Selection

在Soft-Margin SVM Dual中，kernel的選擇、C等參數的選擇都非常重要，直接影響分類效果。例如，對于Gaussian SVM，不同的參數(C,γ)，會得到不同的margin，如下圖所示。

其中橫坐標是C逐漸增大的情況，縱坐標是γ逐漸增大的情況。不同的(C,γ)組合，margin的差別很大。那么如何選擇最好的(C,γ)等參數呢？最簡單最好用的工具就是validation。

validation我們在機器學習基石課程中已經介紹過，只需要將由不同(C,γ)等參數得到的模型在驗證集上進行cross validation，選取Ecv最小的對應的模型就可以了。例如上圖中各種(C,γ)組合得到的Ecv如下圖所示：

因為左下角的Ecv(C,γ)最小，所以就選擇該(C,γ)對應的模型。通常來說，Ecv(C,γ)并不是(C,γ)的連續函數，很難使用最優化選擇（例如梯度下降）。一般做法是選取不同的離散的(C,γ)值進行組合，得到最小的Ecv(C,γ)，其對應的模型即為最佳模型。這種算法就是我們之前在機器學習基石中介紹過的V-Fold cross validation，在SVM中使用非常廣泛。

V-Fold cross validation的一種極限就是Leave-One-Out CV，也就是驗證集只有一個樣本。對于SVM問題，它的驗證集Error滿足：

也就是說留一法驗證集Error大小不超過支持向量SV占所有樣本的比例。下面做簡單的證明。令樣本總數為N，對這N個點進行SVM分類后得到margin，假設第N個點的αN=0，不是SV，即遠離margin（正距離）。這時候，如果我們只使用剩下的N-1個點來進行SVM分類，那么第N個點必然是分類正確的點，所得的SVM margin跟使用N個點的到的是完全一致的。這是因為我們假設第N個點是non-SV，對SV沒有貢獻，不影響margin的位置和形狀。所以前N-1個點和N個點得到的margin是一樣的。

那么，對于non-SV的點，它的g?=g，即對第N個點，它的Error必然為零：

另一方面，假設第N個點αN≠0，即對于SV的點，它的Error可能是0，也可能是1，必然有：

SV的數量在SVM模型選擇中也是很重要的。一般來說，SV越多，表示模型可能越復雜，越有可能會造成過擬合。所以，通常選擇SV數量較少的模型，然后在剩下的模型中使用cross-validation，比較選擇最佳模型。

往期回顧

【1】線性支持向量機（LSVM）

【2】對偶支持向量機（DSVM）

【3】核支持向量機（KSVM）

【4】干貨 | 吳恩達deeplearning.ai專項課程歷史文章匯總

【5】簡單的梯度下降算法，你真的懂了嗎？

【6】重磅 | 吳恩達新書《Machine Learning Yearning》最新版分享

【7】力薦 | 臺大林軒田《機器學習基石》資源匯總

【8】重磅 | “吳恩達deeplearningai”官方微信公眾號已經上線！

您不一定要贊賞，但請點個贊吧

長按二維碼

掃描關注

點擊 |?閱讀原文 | 查看更多干貨內容

總結

以上是生活随笔為你收集整理的一文详解SVM的Soft-Margin机制的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。