支持向量機(Support Vector Machine, SVM)(二) Soft-margin


前面介紹了Hard-margin的SVM,找到一個分界線,能將數據進行有效的分類,但當數據中存在一定的噪聲SVM也會將噪聲擬合,因此存在著過擬合的風險,而Soft-Margin SVM的原理就是讓SVM能夠容忍一定的噪聲以減少過擬合的風險。簡單來說就是讓SVM容忍一點點錯誤,我們可以先把目標函數寫成:

那這邊用兩個不同角度來定義這個loss:

1.錯誤點的個數損失(0, 1) (不推X)

可以看到這個損失函數對w是不連續的,如果加入目標函數這會造成後續優化求導出現問題,所以這邊推薦使用這個方法。

2. 距離(Hinge Loss) (推薦O)

再來我們要怎麼定義這一個slack variable,也就是我要讓margin往內縮多少距離,這邊就要介紹到所謂的Hinge loss

補充一下,樣本點離超平面越遠,表示該樣本點很容易被分類,但是,我們在對損失函數進行優化時,不需要關注那些離超平面很遠的樣本點(即很容易被分類的樣本),為此我們可以通過對數據與高平面的距離選擇一個閥值,來過濾這些離超平面很遠的樣本,這也就是Hinge loss真正的精隨,不僅對訓練樣本數目的依賴大大減少,而且還提高了訓練效率

最後我們可以將目標式和限制式寫成:

這個slack variable是用在限制式內,所以在目標函數也需要考慮進去,因此將所有點的slack variable相加並且給予一個權重/懲罰參數C,用來調整slack variable在目標函數的重要性

接著,和Hard margin SVM一樣這是一個基於KKT條件的二次規劃問題,在這裡我們需要引入拉格朗日乘數(lagrange multiplier)來求得這個最佳解

接著分別對 w , b, ξ偏微分,並且令為零

整理過後

上方這個式子是一個二次規劃的問題,可以透過smo演算法得到每一個 λ 的值。
KKT條件:

而2、3兩種狀況就是我們這邊的 support vector,我們這邊必須利用第二種support vector來計算 b。
所以接下來就和Hard margin一樣透過smo演算法得到每一個 λ 的值,再利用0< λ < C的support vector計算 b。

接著我們的分類邊界就求出來了(其正負值對應二元分類)

最後整理一下soft-margin SVM的流程:

  • 先把L(w,b,λ)對 w 、b、ξ 偏微分,並且令其為零,然後代回L(w,b,λ),可以順便求出w*
  • 以smo算出 λ ,便可得到 support vector
  • 利用利用0< λ < C的support vector,並根據KKT條件來計算 b*
  • 得到我們的分類邊界



Source link

Leave a Reply

Your email address will not be published. Required fields are marked *

Previous Article

Taliban order Afghan women to cover faces in public

Next Article

How can I remove trailing zeros from a number in JavaScript? - 30 seconds of code

Related Posts