機器學習入門筆記6

來自專欄 機器學習筆記

繼SVM

上期筆記不完整，今天參考《統計學習方法》重新整理一下。

1.什麼是支持向量（機）？

在二類分類模型中，我們希望找到一個分離超平面，將所有點分成兩類。在分類過程中，距離超平面最近的點最關鍵（因為最難將其正確分類），這些點稱為支持向量。為了使這些點距離超平面盡量遠，我們用間隔最大化的優化方法。這就是支持向量機的思想。

2.線性可分SVM

原始問題的推導：

間隔最大化：

其中，γ 是幾何間隔。

若用函數間隔表示，等價於：

取函數間隔為1，得出原始問題：

其中，s.t.構成間隔邊界（虛線），邊界上的點為支持向量。如圖：

對偶問題的推導：

寫出拉格朗日函數：

根據拉格朗日對偶性，原始問題的對偶問題為：

將其帶入L(w,b,α),得：

所以，對偶問題：

為了方便，將原始問題和對偶問題放在一起

原始問題：

對偶問題：

原始問題求解的是w，而對偶問題求解的是α，如何求解w,b呢？根據定理：

小結：SVM的對偶問題是先求α，再間接求出w,b。由（7.25）和（7.26）可知，w*,b*只依賴於訓練數據中α*(i)>0的樣本點(xi,yi)，即支持向量，而其他樣本點對w*,b*沒有影響，因為其他樣本點的α=0。

證明：由KKT的互補條件可知。

看兩道例題加深理解：

原始問題：

對偶問題：

3.線性不可分的SVM

線性不可分意味著某些樣本點不能滿足函數間隔大於等於1的約束條件。為此，可以對每個樣本點引入一個鬆弛變數。

與線性可分的SVM不同，支持向量並非全在邊界上，間隔邊界之間也存在少量的樣本點，也是支持向量。

其中，

4.非線性SVM與核函數：

非線性如何變為線性？映射z=φ(x)——將超曲面變成超平面——z為線性分類空間的點。

將z=φ(x)代入線性SVM的目標函數中的內積：φ(xi)·φ(xj)=K(xi,xj)，即核函數。

核函數的定義：只要能找出一個映射φ(x)就行，使K(x,z)=φ(x)·φ(z)，則K(x,z)為核函數。

如果逐個計算φ(xi)，還要求內積，這樣非常慢，因此我們可以直接用經過驗證的核函數（即，可以找到一個映射使其滿足定義）。看以下例子加深理解：

那麼，核函數的條件是什麼呢？一般我們用的核函數為正定核函數。而正定核函數的充要條件為

即：對任意x向量，其二次型函數恆大於0. 該充要條件也可以作為核函數的定義。

常用核函數：略。

5.SMO演算法（序列最小最優演算法）——大大提高演算法速度。

SMO思路：重複「選兩個變數α，一個是違反KKT條件最嚴重的哪一個，另一個由約束條件確定」直到所有變數都滿足KKT條件。

那麼如何找這兩個變數呢？

其中，g(xi)為預測值。

第二個變數由約束條件求出。略

推薦閱讀：