《機器學習實戰》學習總結（六）——支持向量機SVM（一）

摘要

1. 支持向量機簡介

2. 拉格朗日乘子法

3. 對偶問題

這幾天學習支持向量機的原理部分，發現比之前的演算法難了很多。查了很多資料，有了自己的一些理解，希望能給大家一些幫助。

支持向量機(support vector machines，SVM)是一種二分類模型，應用十分廣泛，當然其也可以用於回歸問題。這一節主要梳理支持向量機的基本概念、拉格朗日乘子和對偶問題。下一節主要梳理線性支持向量機、非線性支持向量機、核函數、SMO演算法和支持向量回歸的問題。

支持向量機

支持向量機(SVM)，最主要的用途就是用作分類。如下圖所示(圖片來自於網路，侵刪)，有圓形和方形兩種類別，我們希望找到一個劃分超平面，將兩種類別劃分開。

但是如右上圖所示，劃分超平面的方式有很多，我們應該努力尋找哪一個呢？

直觀上來講的話，我們應該尋找最中間紅色的那一個劃分超平面，因為其對樣本的魯棒性比較好，對於未知示例的泛化能力較強。

假設我們給定一個樣本空間的訓練集：

其中x為樣本特徵，y為類別標記，y=1為正例，y=-1為負例。

我們希望找到一個分離超平面，其線性方程為：

w=｛w1,w2...,wN｝是法向量，d是截距。w*x是內積。確定了w和b，分離超平面也就隨之確定了。

函數間隔與幾何間隔

下面給大家介紹兩個概念，函數間隔和幾何間隔。

函數間隔：對於給定的訓練樣本集D和超平面(w,b)，定義樣本點(xi,yi)到超平面的函數間隔為：

定義超平面(w,b)到訓練集D的函數間隔為所有樣本點的函數間隔的最小值，即：

函數間隔總是正數，因為當樣本為負類時，yi和(w*xi+b)都小於零。

函數間隔表示了分類預測的相對正確性和確信度，因為(w*xi+b)越大，說明樣本點離分離超平面越遠，分類正確的可能性也就越高。

同時我們需要格外注意一下，對於同一個樣本點和分離超平面，函數間隔可能會不一樣。這句話應該怎麼理解呢？我們如果成比例地改變係數w和b，比如把w和b變成2w和2b，分離超平面沒有發生任何改變，但是對於樣本點(xi,yi)，函數間隔卻變成了原來的兩倍。所以函數間隔只能表示分類預測的相對正確性和確信度。

幾何間隔

幾何間隔我們可以簡單理解為實際的距離。

樣本空間中點(xi,yi)到超平面的幾何間隔為：

這是高中學過的幾何知識。

定義超平面(w,b)到訓練集D的幾何間隔為所有樣本點的幾何間隔的最小值，即：

函數間隔和幾何間隔有如下關係：

當||w||=1時，兩者相等。如果超平面參數w和b成比例的改變(超平面沒有改變)，函數間隔也按此比例改變，而幾何間隔不變。

間隔最大化

SVM的基本思想就是求解能夠正確劃分數據集並且幾何間隔最大的分離超平面。通俗講就是樣本點到分離超平面的最小間隔的最大化，即對最難分的樣本點(離超平面最近的點)也有足夠大的確信度將它們分開。

可以表示成如下最優化問題：

即我們希望最大化數據集的幾何間隔。這時我們將幾何間隔和函數間隔進行轉換，得：

函數間隔的取值並不影響最優化問題的解。這句話是下面化簡步驟的核心，怎麼理解這句話呢？

所以優化問題轉換成如下：

這就是支持向量機的基本優化類型，這是一個凸二次優化問題。

對上述優化問題求解，得到最優解w*和b*，就得到了分離超平面：

並且這個最大間隔分離超平面是存在且唯一的。詳細的證明請見《統計學習方法》P101。

這個問題中的w*和b*應該怎麼求解？下面介紹拉格朗日乘子法和對偶問題。

拉格朗日乘子法

拉格朗日乘子法是一種尋求多元函數在約束條件下的極值的方法。通過引入拉格朗日乘子，可以將帶約束條件的優化問題轉換為不帶約束的優化問題。

這部分其實在高數部分已經學習過，給大家溫習一下。

有優化問題如下：

我們構造如下函數：

其中，λ稱為拉格朗日乘子。我們進行如下計算後即可求得極值：

通過計算我們就可以求得極值點x*和λ。

那這個定理是怎麼來的呢？

首先，由上述優化問題，我們可以得到兩個結論：

第一點比較好理解，關於第二點的結論可能很多人不是很能理解，給大家附上鏈接https://www.zhihu.com/question/38586401，這裡面講的很清楚，我不贅述。

由上述兩個結論，即可得兩個梯度的方向必相同或相反，即存在λ≠0使得：

這時候就得到了拉格朗日函數：

這就是拉格朗日乘子法的由來。

對偶問題

但有些時候，優化問題並不是那麼簡單，比如有如下優化問題：

稱此優化問題為原始問題，當有不等式優化時我們應該怎麼解？

我們現在需要找到優化問題的下界，即：

若方程（1）無解，則v就是原問題的一個下界，而最大的v就是問題的最優解。而問題（1）可以等價為：

存在λ≥0，使得問題（2）無解：

令：

而方程（2）無解的充要條件是：

我們希望找到最優的下界，所以：

所以原問題的對偶問題是：

我們求得了原始問題的對偶問題。不論原始問題的凸性如何，對偶問題一定是凸問題。我們假設原始問題的最優值為p*，對偶問題的最優值為d*。

因為：

所以：

所以：

所以：

所以：

即：

上述稱為弱對偶性，對偶問題提供了原問題最優解的一個下界。

那什麼時候對偶問題的解和原始問題的解相同呢？即d*=p*呢？給出兩個定理：

定理1：對於原始問題和對偶問題，假設函數f(x)和Cj(x)是凸函數，hi(x)是仿射函數，並且不等式約束Cj(x)嚴格成立，則存在x*，β*，λ*，使得x*是原始問題的解，β*，λ*是對偶問題的解，並且

定理2：對於原始問題和對偶問題，假設函數f(x)和Cj(x)是凸函數，hi(x)是仿射函數，並且不等式約束Cj(x)嚴格成立，x*和β*、λ*分別是原始問題和對偶問題的解的充分必要條件滿足下面(KKT條件)：

通過求解上式就可以求得原始問題的最優解。將拉格朗日乘子法和對偶問題法應用到SVM中也就可以得到w*和b*，最終得到分離超平面：

以上就是支持向量機原理的第一部分，推導部分有點長，希望大家可以自己手動推導一遍。下次一起學習線性支持向量機、非線性支持向量機、核函數、SMO演算法和支持向量回歸的問題。

聲明

最後，所有資料均本人自學整理所得，如有錯誤，歡迎指正，有什麼建議也歡迎交流，讓我們共同進步！轉載請註明作者與出處。

以上原理部分主要來自於《機器學習》—周志華，《統計學習方法》—李航，《機器學習實戰》—Peter Harrington。代碼部分主要來自於《機器學習實戰》，代碼用Python3實現，這是機器學習主流語言，本人也會儘力對代碼做出較為詳盡的注釋。