一、SVM引入

SVM全稱Support Vector Machine。在深度神經網路流行前是非常通用的機器學習模型。主要講解來源於B站視頻。

SVM白板推導?

www.bilibili.com

在這裡只是做一下SVM的學習筆記與公式推導和理解，明白SVM的數學推導，什麼是支持向量。這裡主要以Hard Margin SVM為例。

SVM示意圖

SVM最開始是用於分類問題。對於一個二分類問題，我們希望找到一個超平面來將兩類數據分隔開來。數學上的表述如下：

SVM數學表述

這個公式非常好理解，對於樣本 x_{i} 將它代入超平面表達式得到 w^{T}x_{i}+b ，如果這個值在超平面上方，即 w^{T}x_{i}+b＞0 ，則有輸出 y_{i}=1 ；如果這個值在超平面下方，即 w^{T}x_{i}+b＜0 ，則有輸出 y_{i}=-1 。

顯然，只要這個超平面能正確分類，那麼它可以是任意的。但是我們希望模型能足夠魯棒，例如L1超平面它雖然可以把兩類數據分隔開，但是顯然它對於雜訊點是非常敏感的，如果新的測試樣本中存在一定雜訊，導致數據越界，那麼它很容易出現分類錯誤。L2一定是更好的選擇。

多個超平面示意圖

因此我們需要以一定的規則來選擇最優決策平面 w^{T}x+b 。

點到超平面的距離公式表達為： distance =frac{1}{||w||}|w^{T}x_{i}+b|

此處有一個變換就是因為 y_{i} 與 w^{T}x_{i}+b 的乘積始終是正的，因此可以通過乘上這個 y_{i} 來去除絕對值。這裡的 min_{w,b,x_{i}} 表示希望找到一個 w ， b ， x_{i} 使得 frac{1}{||w||}y_{i}(w^{T}x_{i}+b) 的值最小，即：所有點到超平面的距離中尋找min最近的那個點。

而我們希望離超平面最近的點到超平面的距離最遠，即：

max_{w,b}frac{1}{||w||}min_{x_{i}}(w^{T}x_{i}+b)y_{i} （1）

通過控制 w 和 b 來使得距離最遠，通過控制 x_{i}選中離超平面最近的點。

由於上面我們有約束條件 w^{T}x_{i}+b＞0 ，那麼我們一定有 min(w^{T}x_{i}+b)=xi ， xi 是一個非常小的數。這裡我們可以令這個 xi=1 。原因是：如果超平面 w^{T}x+b 可以正確分類樣本，那麼總存在一個放縮變換 zeta w ightarrow w^{} ， zeta b ightarrow b^{} 使得等式右邊為1。

因此，我們可以將（1）式改寫：

max_{w,b}frac{1}{||w||}

約束條件 s.t. y_{i}(w^{T}x_{i}+b)≥1

對於優化問題我們通常寫成求最小值，因此對式子求倒數，並將max改為min，因此SVM的最終目標是一個優化問題：

min_{w,b}frac{1}{2}w^{T}w （2）

s.t. 1 - y_{i}(w^{T}x_{i}+b)leq0

二、SVM求解

對於這個帶有約束條件的最優化問題，最常用的方法就是拉格朗日乘數法，令拉格朗日函數：

L(w,b,lambda) =frac{1}{2}w^{T}w+sum_{i=1}^{N}{lambda_{i}( 1 - y_{i}(w^{T}x_{i}+b))}

=frac{1}{2}w^{T}w+sum_{i=1}^{N}{lambda_{i}} -sum_{i=1}^{N}{lambda_{i}y_{i}w^{T}x_{i}}+sum_{i=1}^{N}{lambda_{i}y_{i}b}

我們在上面提到的式（2）可以寫成如下的等價形式：

min_{w,b}max_{lambda}L(w,b,lambda) （3）

s.t lambda_{i}geq0

等價變化

這個等價變換的意義在於，將原本帶有N個約束條件（樣本有N個）的最優化問題轉為不帶約束條件的問題。SVM求解的問題是一個二次凸優化問題，是一個具有強對偶性的問題，根據強對偶性，我們可以將其（3）式進一步的等價：

max_{lambda}min_{w,b}L(w,b,lambda) （4）

s.t lambda_{i}geq0

根據強對偶性還具有如下的KKT條件：

KKT條件

好了，根據（4）式就與KKT條件就可以開始求解了。從（4）式我們可以觀察出，它是一個沒有約束的求最值問題，這種問題我們可以用求偏導數並使偏導數等於0來做：

L(w,b,lambda) =frac{1}{2}w^{T}w+sum_{i=1}^{N}{lambda_{i}} -sum_{i=1}^{N}{lambda_{i}y_{i}w^{T}x_{i}}+sum_{i=1}^{N}{lambda_{i}y_{i}b} (5)

frac{partial L(w,b,lambda)}{partial b}=sum_{i=1}^{N}{lambda_{i}y_{i}}=0 (6)

frac{partial L(w,b,lambda)}{partial w}=frac{1}{2}·2·w - sum_{i=1}^{N}{lambda_{i}y_{i}x_{i}}=0

w = sum_{i=1}^{N}{lambda_{i}y_{i}x_{i}} (7)

將（6）（7）兩式代入（5）中：

L(w,b,lambda) =-frac{1}{2}sum_{i=1}^{N}sum_{j=1}^{N}lambda_{i}lambda_{j}y_{i}y_{j}x_{i}x_{j}^{T} + sum_{i=1}^{N}{lambda_{i}}

因此我們的（4）式也可以轉換到了：

max_{lambda}L(w,b,lambda) =-frac{1}{2}sum_{i=1}^{N}sum_{j=1}^{N}lambda_{i}lambda_{j}y_{i}y_{j}x_{i}x_{j}^{T} + sum_{i=1}^{N}{lambda_{i}}

s.t lambda_{i}geq0

改寫為最小化則轉換到了最終優化形式：

min_{lambda}L(w,b,lambda) =frac{1}{2}sum_{i=1}^{N}sum_{j=1}^{N}lambda_{i}lambda_{j}y_{i}y_{j}x_{i}x_{j}^{T} - sum_{i=1}^{N}{lambda_{i}}

s.t lambda_{i}geq0

實際上根據（7）式，我們已經知道了需要求解的參數之一：

w^{*} = sum_{i=1}^{N}{lambda_{i}y_{i}x_{i}}

數據中第k個樣本滿足：

1-y_{k}(w^{T}x_{k}+b^{*})=0

y_{k}(w^{T}x_{k}+b^{*})=1

y_{k}^{2}(w^{T}x_{k}+b^{*})=y_{k} （ y_{k}^{2} 其值就是1）

b^{*} = y_{k}-w^{T}x_{k}

b^{*} = y_{k}- sum_{i=1}^{N}{(lambda_{i}y_{i}x_{i}})^{T}x_{k}

至此，我們解出了超平面。那什麼是支持向量呢？我們觀察KKT條件的最後三條：

當樣本點 x_{i} 沒有落在虛線上，即： w^{T}x_{i}+b epm1 ，有 1-y_{i}(w^{T}x_{i}+b) e0 ，此時根據KKT條件的第二條，必須要有 lambda_{i}=0 。

當樣本點 x_{i} 落在虛線上，即： w^{T}x_{i}+b=1或-1 ，有 1-y_{i}(w^{T}x_{i}+b)=0 ，此時根據KKT條件的第二條， lambda_{i} 取值沒有限制。

而我們的求解參數 w^{*} 和 b^{*} 是和 lambda_{i} 息息相關，如果樣本點不落在虛線上，那麼其lambda_{i}=0，在累加 w^{*} 時它的貢獻值始終為0。

也就是說，只有落在虛線上的點才對求解參數有影響，而這些點就被稱為支持向量。

推薦閱讀：

相关文章