學習SVM(五)理解線性SVM的鬆弛因子
原文連結:學習SVM(五)理解線性SVM的鬆弛因子
先說一個事引出這個部落格的內容,我最近投的一篇論文被拒稿,用到的方法使SVM(很慚愧,還在用20年前的演算法,當然這並不是重點),審稿意見裡面有一段話是這樣說的(說的很中肯):“該方法本身的特點來看就很難達到100%正確率”,當然這並不是說SVM無法做到100%,我理解的很難達到的原因就是在於SVM演算法本身的鬆弛因子的引入。
為什麼要引入鬆弛因子
從前面四個內容來看,SVM理論可以完美的找到正負樣本間的最大的分類間隔,這意味著不僅僅可以實現對訓練資料的分類,還保證了決策平面是最理想的。那麼SVM為什麼還要引入鬆弛因子呢?我們可以看下面這個例子:
實線的決策平面分開了所有的正負樣本,但是造成的結果是最大分類間隔非常小,而虛線雖然沒有完全區分開所有的正負樣本,但是保證了分類間隔更大,這個例子可以說明,不一定實線完全分類的決策平面就是最好的。 同時,還有一種情況,如果左上角的圓再向右側移動的話,那麼樣本的資料本身就是線性不可分的。 綜合上面的兩點考慮,SVM引入了鬆弛因子
。
新的目標函式
在原有的約束條件上加入一個鬆弛因子
,要求,那麼約束條件變為:
很顯然,由於鬆弛因子是一個正數,那麼新的約束條件一定沒有原來的條件“嚴格”,也就是鬆弛了。 同時,目標函式同樣發生變化:
這個目標函式的變化是通過間隔鬆弛向量的範數定義的泛化誤差界推導的出來,但是這不是SVM的重點,重點在於改變的目標函式對決策平面的影響。 除了一階軟間隔分類器,SVM的目標函式還有二階軟間隔分類器的形式:
而無論是上述哪種情況,實際上都是為目標函式引入一個損失,而上面的引數C被稱之為懲罰因子。 懲罰因子的大小決定了對離群點的容忍程度(鬆弛的程度),比如,如果C是一個非常大的值,那麼很小的鬆弛因子都會讓目標函式的值邊的很大,然後目標是在求一個最小值,這就意味著哪怕是個很小的鬆弛都不願意容忍。還有一種極端的情況是如果C選定成一個無窮大的值,那麼軟分類間隔問題(soft margin)會退化稱為一個硬分類間隔問題(hard margin)。
可以拿一個很直觀的例子說明懲罰因子C的影響,C越大意味著對訓練資料而言能得到很好的分類結果,但是同時最大分類間隔就會變小,畢竟我們做模型不是為了在訓練資料上有個多麼優異的結果。相反的,如果C比較小,那麼間隔就會變大,模型也就有了相對而言更好的泛化能力。
最後新的目標函式(採用一階正規化):
這裡的約束條件是2n個。
軟分類間隔問題的求解 在前面我們就已經知道,有了目標函式之後,後面的工作就是引入拉格朗日乘子,對偶問題轉化後求導,解出拉格朗日乘子後反帶回去求w和b,這個討論對於引得目標函式來說是一樣的,而且推導的過程在前面四部分中解釋的已經非常清楚,對於新的問題,只是加了兩個引數:
1.目標函式本身多出來的一個鬆弛因子。
2.拉格朗日乘子法為新的約束條件引入的引數。
需要注意的是,引數C是一個已知量,是人為設定的!
拉格朗日函式:
其中,a和u是拉格朗日乘子,對偶後就變成了:
解決min問題,求偏導:
將三式帶入到L中求得:
帶入到上面的對偶問題中:
再次轉化問題:
此時的約束條件為:
這個約束條件中的後三個是可以轉化的,因為u是一個大於等於0的數(拉格朗日性質決定的),同時由於C-a=u,即C-a>=0。同時由於a>=0,後三個條件最後就變成:
那麼最後整理得到的對偶問題就是:
這個結果和學習SVM(三)理解SVM中的對偶問題最後的結果很像,只是多出了些約束。