支持向量機SVM總結之問題描述

05-07

本系列開始對支持向量機SVM演算法的學習總結，由於SVM涉及到的數學知識很多，包括了向量、幾何間距、凸優化、核方法等。因此，會分幾個章節進行總結。盡量在一定的數學理論深度上將SVM的思想描述清楚，不過多深入其中的數學機制。總結主要是借鑒了cs229中的相關章節以及notes、林軒田的機器學習技法課程、還有其他博客的相關總結。

SVM可以說是傳統機器學習中，除去集成模型外，稱為off-the-shelf（拿來即用）且效果通常來說都比較好的有監督演算法，即可以用來解決分類問題，也可以用來解決回歸問題（支持向量回歸），為了問題描述更簡潔，只討論二分類問題。（後續有時間會討論支持向量回歸）

SVM核心思想

其實SVM的核心模型很簡單且很好理解，難的是他如何去最優化這個模型。首先，我先總結一下它的核心思想——margin。我們在解決分類問題時，預測樣本數據的標籤是1還是-1，本質上預測的是一個樣本屬於標籤1的概率是多少，若概率大於我們預設的閾值，則屬於標籤1，反之屬於標籤-1。

如上圖，是典型的分類問題的幾何展示，假設當前的樣本是二維的，叉數據表示標籤為1，圓圈數據表示標籤為-1，可以看出當前數據在二維平面上是線性可分的，我們的分類模型能夠在兩種不同標籤的數據之間劃分一個界限，類似於象棋中的「楚河漢界「，不同標籤的數據各佔一面。這裡有兩點備註說明一下：

線性可分的概念，這裡簡單得理解就是在某個n維空間中，能夠在n-1維空間上找到一個線性函數將n維空間上的數據分隔，舉例子：二維空間中找到一個直線分隔、三維空間中找到一個平面分隔。SVM演算法要求數據是線性可分的，如果不是線性可分，需要使用核函數將數據轉換到可以線性可分的維度。（後面詳細說明。）
線性可分中，能夠將數據分隔的線性函數我們稱為hyperplane，可以稱為超平面。我們的線性分類模型最終就是要得到這樣一個超平面能夠將數據很好的分隔。

下面為了描述方便，假設當前數據是二維的，那麼我們最終要求的就是一條直線，即wx+b這個函數中的w和b的參數值（高維的思想類似，只是w和b的維數要做相應的變更），能夠將數據按照「楚河漢界」一樣分隔，但是這樣的直線其實是有很多的，如下圖：

上圖中三條直線其實都滿足上面的要求，但是我們肯定是要得到一個最優的模型的，那麼怎麼算是最好的模型呢？即上面三條線哪條比較好呢？有兩個思路：

所有的數據點肯定要離這條直線越遠越好，這樣說明我對某個數據的分類預測正確的信心就越大。
離這條直線很近的點分錯的可能性很大，將直線稍微旋轉一下，可能就會改變一個數據的分類，此時模型的健壯性很差，容易受異常數據的影響。

因此我們最終要找的這條直線應當朝著最大化所有數據點到該直線間距的目標而去的，稱為maximize margin。那麼這個margin怎麼計算呢？

首先這個margin就是計算數據點到超平面（即直線）a的距離。這個點到直線的距離在高中已經學過了，很簡單，直接通過該數據點，畫一條與a平行的直線b，計算直線a按照與w垂直的方向平移到直線b的距離，可得到：

$gamma^{i}$ 表示第i個數據點到超平面的間距，||w||表示 $sqrt{w^{T}w}$ 。由於我們的分類標籤為1和-1，因此我們同時考慮兩種不同分類標籤數據的間距margin，如下：相當於上面的間距公式乘以標籤

間距margin公式

其次，由於對所有點求最大間隔這個優化問題很難，可以說是一個NP-hard難度問題。因此我們轉換一下思路，我們只要保證那些距離超平面（後面都以直線wx+b=0相稱）最近的那些數據點離直線wx+b盡量就可以了，形式化說法就是，我們定義 $gamma=min_{i=1,...,m}gamma^{i}$ 為所有數據點到直線wx+b最小的間距，我們的目標就是要找到一條直線，去最大化這個間距，即：

這裡有幾點說明：

該優化的目標函數是 $gamma$ ,優化的參數是 $gamma,w,b$
約束條件有兩個，第一個就是要求所有數據點的間距要大於 $gamma$ ，其實就是我上面說的距離直線最近的點，因此其他所有點肯定比這些點要遠。
第二個約束條件的意思是上述間距公式表示的是幾何間距，而優化函數我們習慣於對函數進行操作，因此還存在一個函數間距， $y^{(i)}(w^{T}x^{(i)}+b)$ ，為了將幾何間隔與函數間隔對應起來，對我們的 $gamma$ 公式進行scaling，不會對我們的優化問題有任何影響，因此可以將 $||w||=1$ ，此時也與第一個約束不等式對應起來（若不帶這個等式約束，則第一個約束條件要除以||w||）。

但是上述優化問題顯然很難解決，因為 $||w||=1$ 這個約束條件是非凸的（絕對值函數，並沒有一個明確的最優），並不好優化。因此要將上述問題進行轉化，將這個等式約束條件去掉：

上式，將等式約束去掉了，優化目標函數也變化了，但是這個優化函數也是個非凸的函數，也不好優化。那麼我們可以對間距函數繼續scaling，即同時調整w和b的倍數，使得

，即相當於距離wx+b=0最近的點到該直線的距離設為1，得到優化問題：

有的notes中的優化目標函數為2/||w||，原因是將正反兩種標籤的數據點到超平面直線的距離都加上了，道理是一樣的。如下圖所示。

圖上這些margin間距最小的點有個名字，叫做support vector，即支持向量，通常一個數據集中的支持向量的個數不會很多，因此SVM利用這種特性能夠提高演算法模型的效率，這個在後面講解具體演算法時會說到。

其實上述目標函數還是不好優化，因此還可以繼續轉化：

其實做了個最大最小化的轉化，此時得到一個二次函數，且是求在約束條件下，它的最小值，這是個凸函數，可以使用凸優化相關方法來解決該問題了。至於為什麼要加1/2,我理解是後面求偏導時，可以將w前面的係數約去，方便計算。

下一章繼續講解如何使用拉格朗日對偶方法來解決這個最優化問題。