上節課我們主要介紹了Kernel SVM。先将特征轉換和計算内積這兩個步驟合并起來，簡化計算、提高計算速度，再用Dual SVM的求解方法來解決。Kernel SVM不僅能解決簡單的線性分類問題，也可以求解非常複雜甚至是無限多元的分類問題，關鍵在于核函數的選擇，例如線性核函數、多項式核函數和高斯核函數等等。但是，我們之前講的這些方法都是Hard-Margin SVM，即必須将所有的樣本都分類正确才行。這往往需要更多更複雜的特征轉換，甚至造成過拟合。本節課将介紹一種Soft-Margin SVM，目的是讓分類錯誤的點越少越好，而不是必須将所有點分類正确，也就是允許有noise存在。這種做法很大程度上不會使模型過于複雜，不會造成過拟合，而且分類效果是令人滿意的。
上節課我們說明了一點，就是SVM同樣可能會造成overfit。原因有兩個，一個是由于我們的SVM模型（即kernel）過于複雜，轉換的次元太多，過于powerful了；另外一個是由于我們堅持要将所有的樣本都分類正确，即不允許錯誤存在，造成模型過于複雜。如下圖所示，左邊的圖Φ1是線性的，雖然有幾個點分類錯誤，但是大部分都能完全分開。右邊的圖Φ4是四次多項式，所有點都分類正确了，但是模型比較複雜，可能造成過拟合。直覺上來說，左邊的圖是更合理的模型。
如何避免過拟合？方法是允許有分類錯誤的點，即把某些點當作是noise，放棄這些noise點，但是盡量讓這些noise個數越少越好。回顧一下我們在機器學習基石筆記中介紹的pocket算法，pocket的思想不是将所有點完全分開，而是找到一條分類線能讓分類錯誤的點最少。而Hard-Margin SVM的目标是将所有點都完全分開，不允許有錯誤點存在。為了防止過拟合，我們可以借鑒pocket的思想，即允許有犯錯誤的點，目标是讓這些點越少越好。
為了引入允許犯錯誤的點，我們将Hard-Margin SVM的目标和條件做一些結合和修正，轉換為如下形式：
修正後的條件中，對于分類正确的點，仍需滿足y_n(w^Tz_n+b)\geq 1，而對于noise點，滿足y_n(w^Tz_n+b)\geq -\infty，即沒有限制。修正後的目标除了\frac12w^Tw項，還添加了y_n\neq sign(w^Tz_n+b)，即noise點的個數。參數C的引入是為了權衡目标第一項和第二項的關系，即權衡large margin和noise tolerance的關系。
我們再對上述的條件做修正，将兩個條件合并，得到：
這個式子存在兩個不足的地方。首先，最小化目标中第二項是非線性的，不滿足QP的條件，是以無法使用dual或者kernel SVM來計算。然後，對于犯錯誤的點，有的離邊界很近，即error小，而有的離邊界很遠，error很大，上式的條件和目标沒有區分small error和large error。這種分類效果是不完美的。
為了改正這些不足，我們繼續做如下修正：
修正後的表達式中，我們引入了新的參數\xi_n來表示每個點犯錯誤的程度值，ξn≥0。通過使用error值的大小代替是否有error，讓問題變得易于求解，滿足QP形式要求。這種方法類似于我們在機器學習基石筆記中介紹的0/1 error和squared error。這種soft-margin SVM引入新的參數ξ。
至此，最終的Soft-Margin SVM的目标為： min(b,w,\xi)\ \frac12w^Tw+C\cdot\sum_{n=1}^N\xi_n
條件是： y_n(w^Tz_n+b)\geq 1-\xi_n
\xi_n\geq0
其中，\xi_n表示每個點犯錯誤的程度，\xi_n=0，表示沒有錯誤，\xi_n越大，表示錯誤越大，即點距離邊界（負的）越大。參數C表示盡可能選擇寬邊界和盡可能不要犯錯兩者之間的權衡，因為邊界寬了，往往犯錯誤的點會增加。large C表示希望得到更少的分類錯誤，即不惜選擇窄邊界也要盡可能把更多點正确分類；small C表示希望得到更寬的邊界，即不惜增加錯誤點個數也要選擇更寬的分類邊界。
與之對應的QP問題中，由于新的參數\xi_n的引入，總共參數個數為\hat d+1+N，限制條件添加了\xi_n\geq0，則總條件個數為2N。
接下來，我們将推導Soft-Margin SVM的對偶dual形式，進而讓QP計算更加簡單，并便于引入kernel算法。首先，我們把Soft-Margin SVM的原始形式寫出來：
然後，跟我們在第二節課中介紹的Hard-Margin SVM做法一樣，構造一個拉格朗日函數。因為引入了\xi_n，原始問題有兩類條件，是以包含了兩個拉格朗日因子\alpha_n和\beta_n。拉格朗日函數可表示為如下形式：
接下來，我們跟第二節課中的做法一樣，利用Lagrange dual problem，将Soft-Margin SVM問題轉換為如下形式：
根據之前介紹的KKT條件，我們對上式進行簡化。上式括号裡面的是對拉格朗日函數L(b,w,\xi,\alpha,\beta)計算最小值。那麼根據梯度下降算法思想：最小值位置滿足梯度為零。
我們先對\xi_n做偏微分：
\frac{\partial L}{\partial \xi_n}=0=C-\alpha_n-\beta_n
根據上式，得到\beta_n=C-\alpha_n，因為有\beta_n\geq0，是以限制0\leq\alpha_n\leq C。将\beta_n=C-\alpha_n代入到dual形式中并化簡，我們發現\beta_n和\xi_n都被消去了：
這個形式跟Hard-Margin SVM中的dual形式是基本一緻的，隻是條件不同。那麼，我們分别令拉個朗日函數L對b和w的偏導數為零，分别得到： \sum_{n=1}^N\alpha_ny_n=0 w=\sum_{n=1}^N\alpha_ny_nz_n
經過化簡和推導，最終标準的Soft-Margin SVM的Dual形式如下圖所示：
Soft-Margin SVM Dual與Hard-Margin SVM Dual基本一緻，隻有一些條件不同。Hard-Margin SVM Dual中\alpha_n\geq0，而Soft-Margin SVM Dual中0\leq\alpha_n\leq C，且新的拉格朗日因子\beta_n=C-\alpha_n。在QP問題中，Soft-Margin SVM Dual的參數\alpha_n同樣是N個，但是，條件由Hard-Margin SVM Dual中的N+1個變成2N+1個，這是因為多了N個\alpha_n的上界條件。
對于Soft-Margin SVM Dual這部分推導不太清楚的同學，可以看下第二節課的筆記：中國台灣大學林軒田機器學習技法課程學習筆記2 – Dual Support Vector Machine
推導完Soft-Margin SVM Dual的簡化形式後，就可以利用QP，找到Q，p，A，c對應的值，用軟體工具包得到\alpha_n的值。或者利用核函數的方式，同樣可以簡化計算，優化分類效果。Soft-Margin SVM Dual計算\alpha_n的方法過程與Hard-Margin SVM Dual的過程是相同的。
但是如何根據\alpha_n的值計算b呢？在Hard-Margin SVM Dual中，有complementary slackness條件：\alpha_n(1-y_n(w^Tz_n+b))=0，找到SV，即\alpha_s>0的點，計算得到b=y_s-w^Tz_s。
那麼，在Soft-Margin SVM Dual中，相應的complementary slackness條件有兩個（因為兩個拉格朗日因子\alpha_n和\beta_n）： \alpha_n(1-\xi_n-y_n(w^Tz_n+b))=0 \beta_n\xi_n=(C-\alpha_n)\xi=0
找到SV，即\alpha_s>0的點，由于參數\xi_n的存在，還不能完全計算出b的值。根據第二個complementary slackness條件，如果令C-\alpha_n\neq0，即\alpha_n\neq C，則一定有\xi_n=0，代入到第一個complementary slackness條件，即可計算得到b=y_s-w^Tz_s。我們把0<\alpha_s<C的點稱為free SV。引入核函數後，b的表達式為： b=y_s-\sum_{SV}\alpha_ny_nK(x_n,x_s)
上面求解b提到的一個假設是\alpha_s<C，這個假設是否一定滿足呢？如果沒有free SV，所有\alpha_s大于零的點都滿足\alpha_s=C怎麼辦？一般情況下，至少存在一組SV使\alpha_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)的選擇非常重要。
我們再來看看\alpha_n取不同值是對應的實體意義。已知0\leq\alpha_n\leq C滿足兩個complementary slackness條件： \alpha_n(1-\xi_n-y_n(w^Tz_n+b))=0 \beta_n\xi_n=(C-\alpha_n)\xi=0
若\alpha_n=0，得ξn=0。\xi_n=0表示該點沒有犯錯，\alpha_n=0表示該點不是SV。是以對應的點在margin之外（或者在margin上），且均分類正确。
若0<\alpha_n<C，得\xi_n=0，且y_n(w^Tz_n+b)=1。\xi_n=0表示該點沒有犯錯，y_n(w^Tz_n+b)=1表示該點在margin上。這些點即free SV，确定了b的值。
若\alpha_n=C，不能确定\xi_n是否為零，且得到1-y_n(w^Tz_n+b)=\xi_n，這個式表示該點偏離margin的程度，\xi_n越大，偏離margin的程度越大。隻有當\xi_n=0時，該點落在margin上。是以這種情況對應的點在margin之内負方向（或者在margin上），有分類正确也有分類錯誤的。這些點稱為bounded SV。
是以，在Soft-Margin SVM Dual中，根據\alpha_n的取值，就可以推斷資料點在空間的分布情況。
在Soft-Margin SVM Dual中，kernel的選擇、C等參數的選擇都非常重要，直接影響分類效果。例如，對于Gaussian SVM，不同的參數(C,γ)，會得到不同的margin，如下圖所示。
其中橫坐标是C逐漸增大的情況，縱坐标是γ逐漸增大的情況。不同的(C,γ)組合，margin的差别很大。那麼如何選擇最好的(C,γ)等參數呢？最簡單最好用的工具就是validation。
validation我們在機器學習基石課程中已經介紹過，隻需要将由不同(C,γ)等參數得到的模型在驗證集上進行cross validation，選取E_{cv}最小的對應的模型就可以了。例如上圖中各種(C,γ)組合得到的E_{cv}如下圖所示：
因為左下角的Ecv(C,γ)最小，是以就選擇該(C,γ)對應的模型。通常來說，Ecv(C,γ）并不是(C,γ)的連續函數，很難使用最優化選擇（例如梯度下降）。一般做法是選取不同的離散的(C,γ)值進行組合，得到最小的Ecv(C,γ)，其對應的模型即為最佳模型。這種算法就是我們之前在機器學習基石中介紹過的V-Fold cross validation，在SVM中使用非常廣泛。
V-Fold cross validation的一種極限就是Leave-One-Out CV，也就是驗證集隻有一個樣本。對于SVM問題，它的驗證集Error滿足： E_{loocv}\leq \frac{SV}{N}
也就是說留一法驗證集Error大小不超過支援向量SV占所有樣本的比例。下面做簡單的證明。令樣本總數為N，對這N個點進行SVM分類後得到margin，假設第N個點(x_N,y_N)的\alpha_N=0，不是SV，即遠離margin（正距離）。這時候，如果我們隻使用剩下的N-1個點來進行SVM分類，那麼第N個點(x_N,y_N)必然是分類正确的點，所得的SVM margin跟使用N個點的到的是完全一緻的。這是因為我們假設第N個點是non-SV，對SV沒有貢獻，不影響margin的位置和形狀。是以前N-1個點和N個點得到的margin是一樣的。
那麼，對于non-SV的點，它的g^-=g，即對第N個點，它的Error必然為零： e_{non-SV}=err(g^-,non-SV)=err(g,non-SV)=0
另一方面，假設第N個點\alpha_N\neq0，即對于SV的點，它的Error可能是0，也可能是1，必然有： e_{SV}\leq1
綜上所述，即證明了E_{loocv}\leq \frac{SV}{N}。這符合我們之前得到的結論，即隻有SV影響margin，non-SV對margin沒有任何影響，可以舍棄。
SV的數量在SVM模型選擇中也是很重要的。一般來說，SV越多，表示模型可能越複雜，越有可能會造成過拟合。是以，通常選擇SV數量較少的模型，然後在剩下的模型中使用cross-validation，比較選擇最佳模型。
本節課主要介紹了Soft-Margin SVM。我們的出發點是與Hard-Margin SVM不同，不一定要将所有的樣本點都完全分開，允許有分類錯誤的點，而使margin比較寬。然後，我們增加了ξn作為分類錯誤的懲罰項，根據之前介紹的Dual SVM，推導出了Soft-Margin SVM的QP形式。得到的\alpha_n除了要滿足大于零，還有一個上界C。接着介紹了通過\alpha_n值的大小，可以将資料點分為三種：non-SVs，free SVs，bounded SVs，這種更清晰的實體解釋便于資料分析。最後介紹了如何選擇合适的SVM模型，通常的辦法是cross-validation和利用SV的數量進行篩選。
注明：
文章中所有的圖檔均來自中國台灣大學林軒田《機器學習技法》課程