SVM
1 Star2 Stars3 Stars4 Stars5 Stars 給文章打分!
Loading...

SVM與感知機模型有很多相似之處,SVM主要解決的也是二分類問題,也是判別式方法,同樣需要找到一個決策超平面對樣本進行劃分。不同的是在SVM中尋找距離正負樣本間隔最大的超平面,這也是SVM優越性的表現,並且SVM很容易可以植入核方法,使得SVM可以解決非線性分類問題。

首先SVM的分類決策函式的形式與感知機模型相同:

決策超平面S為:

SVM需要找到距離正負樣本間隔最大的S,那麼就要定義什麼是間隔。

函式間隔:

如果決策超平面是,那麼點xi到S的函式間隔為:

定義超平面關於訓練資料集T的函式間隔為超平面關於T中所有樣本點(xi, yi)的函式間隔的最小值:

由這個定義可以看出,一個超平面關於一個資料集的函式間隔由該資料集上某點到該平面的最小函式間隔決定

函式間隔的問題是對w和b進行翻倍,那麼函式間隔也會翻倍。

所以定義幾何間隔:

同樣,定義一個超平面對於一個資料集的幾何距離為:

函式間隔和幾何間隔有如下關係:

那麼接下來的問題就是如何使間隔最大化了!

最大間隔分離超平面

求使某個資料集最大間隔超平面可以看成是下面這個最優化問題:

通過上面提到的函式間隔和幾何間隔的關係,,上面的最優化問題也可以寫作:

由於的取值不影響最優化的解,所以可以令其值為1,又因為最大化相當於最小化,所以上面的最優化問題可以寫作:

這是一個很經典的凸二次規劃問題,需要使用拉格朗日乘子,反正我是不會。。。

解出w和b即求出了將正負樣本分開並且間隔最大的超平面,也就得到了SVM的決策函式!

對偶演算法:

使用拉格朗日演算法並經過一系列推導可以得到SVM的對偶演算法:

即求解最優化問題:

這個最優化問題我也是不會解的,但是其形式與感知機的對偶問題是有一定相似性的!

現在假設求出對偶問題的最優解為:,則原問題的解為:

選擇的一個正分量

對應於的例項xi,有:

即此時xi在間隔邊界上,即xi是支援向量!

線性SVM和軟間隔最大化

上面的SVM可以解決線性可分的二分類問題,但是可能存在這種情況,即大部分樣本是線性可分的,但是存在少量的outlier,這時候就要使用軟間隔最大化。求出的分離超平面仍然是線性的。

線性SVM相當於最優化:

其中,是鬆弛變數,表示某些點到超平面的函式間隔可以小於1,甚至是負的(在超平面的另一側)。當然對於這樣的點要進行懲罰,而就是懲罰項!

該問題的對偶問題是:

該問題的解同樣是:

選擇的一個分量

注意,在使用軟間隔的SVM中,支援向量就相對複雜一點,那些在最大間隔上的點和那些小於最大間隔的點和分錯的點都是支援向量!

可以用下圖表示:

SVM相當於是使用合頁損失函式

合頁損失函式的形式如下圖:

其中虛線是感知機使用的損失函式,只要分類正確損失就是0。粗實線是SVM使用的損失函式,即合頁損失函式,必須大於函式間隔時,損失才是0!

因為SVM的對偶形式中出現了,這使得核方法可以很方便的植入到SVM中去!

相關文章

程式語言 最新文章