SVM Regularization and non-separable case

05-22

來自專欄機器學習

到目前為止，我們介紹SVM的推導都是假設了數據是線性可分的，將數據通過 $phi$ 映射到高維特徵空間會增加數據可分的概率，但是不能保證映射之後的數據都是可分的。同時由於異常點的影響，我們並非必須找到一個嚴格的分離超平面。例如如下圖所示，左圖是出的是optimal margin classifier, 當訓練集中出現一個異常點在右圖中的左上方，會導致decision boundary發生很大的變化，這樣產生的classifier會給出很小的margin，結果是不好的。

為了讓演算法能夠解決非線性可分數據集，同時對異常點敏感度減小，我們採用 $l_{1}$ regularization重寫優化問題如下：

$min_{gamma,w,b}frac{1}{2}||w||^{2}+Csum_{i=1}^{m}{xi_{i}}$

$s.t. y^{(i)}(w^{T}x^{(i)}+b)geq1-xi_{i},i=1,2,...,m$

$xi_{i}geq 0,i=1,...,m$

這樣就可以允許部分樣例的函數間隔小於1，如果一個樣本的functional margin是 $1-xi_{i}$ ，那麼在目標函數上就會有 $Cxi_{i}$ 的增長作為懲罰，參數C控制著兩個目標之間的相對權重：

盡量使得 $||w||^{2}$ 足夠小
保證絕大部分的樣例函數間隔 $geq1$

與之前相同，構造optimization problem的Lagrangian：

$L(w,b,xi,alpha,gamma)=frac{1}{2}||w||^{2}+Csum_{i=1}^{m}{xi_{i}}-sum_{i=1}^{m}{alpha_{i}[y^{(i)}(w^{T}x^{(i)}+b)-1+xi_{i}]}-sum_{i=1}^{m}{gamma_{i}xi_{i}}.$

其中拉格朗日乘子為 $alpha_{i},gamma_{i}geq0$ ，同樣的我們構造對偶問題

$heta_{D}(alpha,gamma)=min_{w,b,xi}L(w,b,xi,alpha,gamma)=min_{w,b,xi}[frac{1}{2}||w||^{2}+Csum_{i=1}^{m}{xi_{i}}-sum_{i=1}^{m}{alpha_{i}[y^{(i)}(w^{T}x^{(i)}+b)-1+xi_{i}]}-sum_{i=1}^{m}{gamma_{i}xi_{i}}.]$

針對參數 $w,b,xi$ 求取 $L(w,b,alpha)$ 的偏導數的到:

$abla_{w}L(w,b,xi,alpha,gamma)=w-sum_{i=1}^{m}{alpha_{i}y^{i}x^{i}}=0$ ,即得到 $w=sum_{i=1}^{m}{alpha_{i}y^{i}x^{i}}$ (1)
$frac{partial}{partial b}L(w,b,xi,alpha,gamma)=sum_{i=1}^{m}{alpha_{i}y^{(i)}}=0$ (2)
$frac{partial}{partial xi_{i}}L=C-alpha_{i}-gamma_{i}=0$ ，即得到 $C=alpha_{i}+gamma_{i}$ (3)

將(1)式子代入得到

$heta_{D}(alpha,gamma)=frac{1}{2}(sum_{i=1}^{m}{alpha_{i}y^{(i)}x^{(i)}})^{2}+Csum_{i=1}^{m}{xi_{i}}-sum_{i=1}^{m}{alpha_{i}}y^{(i)}w^{T}x^{(i)}-sum_{i=1}^{m}{alpha_{i}y^{(i)}b}+sum_{i=1}^{m}{alpha_{i}}-sum_{i=1}^{m}{alpha_{i}xi_{i}}-sum_{i=1}^{m}{gamma_{i}xi_{i}}$

$=$ $sum_{i=1}^{m}{alpha_{i}}-frac{1}{2}(sum_{i=1}^{m}{alpha_{i}y^{(i)}x^{(i)}})^{2}+sum_{i=1}^{m}{(C-alpha_{i}-gamma_{i})xi_{i}}-sum_{i=1}^{m}{alpha_{i}y^{(i)}b}$