↑ 點擊上方藍字" 奶糖貓 ",加個關注如何

SVM概述

支持向量機(SVM)是一種有監督的分類算法，並且它絕大部分處理的也是二分類問題，先通過一系列圖片瞭解幾個關於SVM的概念。

上圖中有橙色點和藍色點分別代表兩類標籤，如果想要將其分類，需要怎麼做呢？ 可能有的夥伴會想到上一篇文章講到的邏輯迴歸擬合決策邊界，這肯定是一種不錯的方法，本文所講的SVM也是可以解決這種分類問題 的； 既然都是分類算法，所以通過一個例子可以比對出二者的相同點和不同點。

超平面

可以看到，這裏給出了兩種劃分方式，就圖中實線而言，在邏輯迴歸中可以稱作決策邊界，而在SVM中它被稱爲超平面( hyperplane )。

上面例子中數據點都分佈在二維平面上，所以此時超平面就爲一條直線。如果給出的數據集是三、四、... 、N維呢？此時超平面對應的維度就是二、三、...、N-1維的，下圖展示了數據集多維時的超平面。

最大間隔

對於這個例子，可以將其準確分類的超平面可能有多個，其中具有最大間隔(兩條虛線之間的距離)的超平面就是SVM要找的最優解，這個最優解對應兩側虛線所穿過的樣本點，就是“支持向量( support vector )”,支持向量到超平面的距離被稱爲間隔( margin )，如下圖繪製標識。

公式推導

超平面方程

我們利用SVM算法建模最後想要從衆多超平面中求解具有最大間隔的超平面，所以這也是一個最優化問題。

這裏需要了解一下最優化問題的兩個基本因素：

• 目標函數：你希望什麼東西的什麼指標達到最好。

• 優化對象：你希望改變哪些因素使目標函數達到最優。在線性SVM算法中，目標函數就是“間隔”，優化對象則是“超平面”。

所以首先需要推導“超平面”的方程，二維空間內“超平面”的公式也就是直線方程，如下：

這裏將x變成x1，y變成x2的操作是爲了將其向量化：

最後將其整理成：

一般的向量爲列向量，所以這裏對進行了轉置，並且向量與我們所設直線是相互垂直的，只需要假定直線斜率a爲一個常數，繪圖即可證明，其中控制着直線的方向，b則控制着直線的位置，所以直線方程中需要改變 和b使目標函數達到最優。

間隔公式

“間隔”就是圖中點到“超平面”的距離，公式如下：

其中d代表間隔，代表的是的二範數(模)，即對所有元素的平方和開平方：

建模的目標就是爲了找到最大間隔，其中最大間隔W=2d，只要W越大，則代表該模型分類的效果越好，最後也就變成了求解d最大化的問題。

約束條件

針對上述我們所建分類器，當我們輸入數據給分類器時，它會返回一個類別標籤，這裏先規定藍色爲負樣本(-1)、紅色爲正樣本(+1)，我們可以得到一組公式，如果超平面能夠準確對圖中樣本點分類，則可得到以下公式：

上述公式可歸化成：

s.t.表示"subject to"即服從某種條件

這裏再回顧一下上面的最大間隔方程，求最大間隔的思想可以概括爲求 最小的 點到超平面的幾何距離的 最大化 。最小是爲了分類時不同類別都能夠得到準確分類，距離最大化則是爲了獲取”最大間隔“，以達到對分類器調優，公式如下：

如果我們希望最優的超平面的間隔的幾何距離爲,即所有樣本點到超平面的幾何距離至少爲，所以下面公式一定成立。

這裏將其設定爲1。可以這麼想，不論我們設定的是幾，將等式兩邊同時除以，和b的係數縮小了倍，但超平面是不動的，係數是可以同比例縮放的，可以類比直線方程。固定之後，可以得到以下公式：

這裏對做了一定處理，最大化和最小化是等價的，這樣做是爲了在進行最優化時對目標函數求導方便，對最優解沒有影響。

其中第一個公式爲我們的目標函數，第二公式也就是這個最優化問題中的約束條件，由於是一個凸函數，所以這個問題是凸優化問題。

求解最優化問題

最優化問題分類

最優化問題一般可分爲兩大類：無約束優化問題和約束優化問題，而約束優化問題又可分爲含等式約束優化問題和含不等式約束優化問題。

• 對於無約束優化問題，可以對函數求導，然後令其爲零，從候選值中選取最優值，並加以驗證；若函數爲凸函數，則可以保證是最優解。隨機梯度下降和批量梯度下降就是無約束優化方法。

• 對於含等式約束優化問題，常用的方法是利用拉格朗日乘子法將其轉化爲無約束優化問題求解。具體爲將約束條件和函數寫成一個函數，稱爲拉格朗日函數，係數爲拉格朗日乘子；通過拉格朗日函數對各個變量求導，令其爲零，從候選值中選取最優值，並加以驗證。

• 對於含不等式約束優化問題，主要通過KKT條件將其轉化成無約束優化問題求解。具體爲通過構建拉格朗日函數，在一些條件下求出最優值的必要條件，這個條件就是KKT條件。

A的必要條件就是A可以推出的結論

對於我們所構造出的最優化問題明顯是屬於含不等式約束優化問題，關於拉格朗日函數的概念不過多介紹，下面介紹拉格朗日乘子法，並通過拉格朗日乘子法引出對偶問題和KKT條件。

拉格朗日乘子法

拉格朗日乘子法的思想就是通過引入拉格朗日乘子，將有d個變量和k個約束條件的最優化問題轉化爲d+k個變量的無約束優化問題求解。

這裏感興趣的夥伴可以搜一下大佬的博客或者西瓜書上都有詳細介紹，真是後悔高數課上沒有仔細聽這部分。

通過引入拉格朗日乘子可以將上述的最優化問題轉化成下面形式：

其中需要注意的是,,通過拉格朗日函數我們可以將上述公式轉化爲：

有的夥伴這裏可能會不理解，爲什麼是拉格朗日函數最大值的最小化，下圖介紹了原因。

很明顯當時，目標函數取值爲正無窮是沒有意義的，而當時,兩者則是等價的 。

對偶問題

利用對偶性可以將上述原問題轉化成對偶問題，如下：

這個過程的主要操作就是將min和max互掉位置，並且二者之間有一個性質，即前者>=後者，這就好比 在高個子人羣中挑一個身高較矮的要高於在矮個子人羣中挑一個身高較高的 。默認情況下二者是呈弱對偶關係的，但在此目標函數和約束條件下是呈強對偶關係(等價關係)的。

在轉化成對偶問題之後，我們可以先求,分別令函數對求偏導，並使其等於0。

在將上述兩個式子帶入至構建的拉格朗日函數中，可得：

最後整理一下得出我們推導過後最終的優化問題，如下：

KKT條件

假設有這樣一個含不等式約束的優化問題：

如果想利用KKT條件處理此優化問題，需要利用拉格朗日乘子法將不等式約束、等式約束和目標函數合併寫成一個式子，如下：

KKT條件就是說取到的最優值必須滿足以下條件：

當原問題與對偶問題呈強對稱關係是此問題滿足KKT條件的充分必要條件，所以本文最優化問題滿足的條件如下：

根據這些條件，我們可以得出只有在樣本點爲支持向量(樣本點處於虛線上)時，可以取任意值，而其他位置的樣本點一定爲0。這就和邏輯迴歸有不同之處了，邏輯迴歸在擬合決策邊界時，所有樣本都會有影響，而SVM有作用的主要是邊界線附近的樣本。

因爲我們所設超平面方程爲，所以我們求得原始最優化問題的解爲，在L對求導時得到了的解，而對於,求解過程如下：

這裏需要注意的點是設定是支持向量，所以,就可以消去。最終獲取到的最優超平面方程如下：

總結

• 介紹了超平面與最大間隔的概念。

• 在二維空間內推導超平面方程並介紹間隔公式。

• 推導該優化問題的約束條件。

• 介紹了最優化問題的分類及對應解決思想。

• 通過拉格朗日乘子法引出對偶問題。

• 在對偶問題的基礎上講解KKT條件。

• 博主還是個菜鳥，歡迎指出文中出現的問題。

本文不包含代碼，着重於公式推導，對於手寫代碼比較重要的部分應該在於公式推導，只有瞭解每一步驟的思想及由來，才能更好的進行編程，下篇文章將會介紹一個簡化版的序列最小化(SMO)算法，感謝閱讀。

歡迎各位給奶糖貓留言 呀       在線陪聊

看到這點個“在看”吧         謝謝大爺呀

End

往期推薦：

1. 機器學習筆記(八)——隨機梯度上升(下降)算法調優

2. 機器學習筆記(七)——初識邏輯迴歸、兩種方法推導梯度公式

3. 機器學習筆記(六)——樸素貝葉斯構建“飢餓站臺”豆瓣短評情感分類器

4. 機器學習筆記(五)——輕鬆看透樸素貝葉斯

相關文章