本文轉自徐飛翔的“《SVM筆記系列之一》什么是支持向量機SVM？”

版權聲明：本文為博主原創文章，遵循CC 4.0 BY-SA版權協議，轉載請附上原文出處鏈接和本聲明。

SVM的起源支持向量機(Support Vector Machine, SVM)是一種被廣泛使用的機器學習算法，自從被Vapnik等人提出來之后便被廣泛使用和發展。傳統的支持向量機一般是二類分類器，其基本出發點很簡單，就是找到一個策略，能夠讓線性分類器的分類超平面能夠最大程度的把兩類的樣本最好地分割開，這里我們討論下什么叫做最好地分割開，和實現這個對整個分類器的意義。

最好地分割數據在進行接下來的討論之前，為了簡化我們的討論從而直面問題所在，我們進行以下假設：

1） 我們現在的兩類數據是線性可分的， 也就是總是存在一個超平面可以將數據完美的分開。

2） 我們的數據維度是二維的，也就是特征維只有兩個，類標簽用+1， -1表示，這樣方便我們繪制圖像。

我在前篇博文《機器學習系列之 感知器模型》中已經介紹到了感知器這一簡單的線性分類器。感知器很原始，只能對線性可分的數據進行準確分割，而且由于其激活函數選用的是階躍函數，因此不能通過梯度的方法進行參數更新，而是只能采用錯誤驅動的策略進行參數更新，這樣我們的超平面其實是不確定的，因為其取決于具體隨機到的是哪個樣本點進行更新，這是一個不穩定的結果。而且，由于采用了這種參數更新策略，感知器的超平面即使是能夠將線性數據完美地分割開，也經常會出現超平面非常接近某一個類的樣本，而偏離另一個類的樣本的這種情況，特別是在真實情況下的數據是疊加了噪聲的情況下。　　

如下圖所示，其中綠線是感知器的運行結果，因為其算法的不穩定性，所以每次的結果都可能不同，選中的這一次我們可以看出來雖然綠線將兩類數據完美地分割開了，但是和藍色樣本很接近，如果新來的測試樣本疊加一個噪聲，這個超平面就很容易將它分類錯誤，而最佳分類面粉色線則對噪聲有著更好地容忍。

樣本噪聲剛才我們談到了樣本集上疊加的噪聲，噪聲廣泛存在于真實數據集中，無法避免，因此我們的分類超平面要能夠對噪聲進行一定的容忍。一般我們假設噪聲為高斯噪聲，如下圖所示：

其中紅點為實際的采樣到的樣本位置? ，而藍點是可能的樣本的實際位置，因為噪聲N的疊加才使得其偏離到了紅點位置，其中藍點的位置滿足高斯分布。

最佳分類超平面

也就是說我們根據點訓練出來的感知器的分類器超平面很可能會出現可以完美地劃分點，但是卻不能正確地劃分對新來的測試樣本的現象。因為新來的樣本很可能位于藍色的樣本點的位置，也就是表現出了嚴重的過擬合現象， 而我們的支持向量機的機制可以很好地減免這種現象，具有更好的泛化能力。我們用幾張圖來表述下導致這種過擬合的原因：

Figure 1, 感知器分類超平面能將線性可分的樣本完美分割，但是由于樣本疊加了高斯噪聲N NN，所以當測試樣本的數據出現在超平面“穿過”的“綠圈”之內時，就可能會出現錯分的情況，這就是過擬合的一種表現。

Figure 2,假設我們的樣本集都是獨立同分布采樣的，那么其疊加的高斯噪聲N應該都是相同分布的，因此這個綠圈的大小應該都是相同的，因此最佳的分類超平面應該是可以和距離它最接近的若干個樣本的邊界相切的。我們把最接近超平面的若干個樣本點稱為支持向量，支持向量和超平面的距離越遠，相當于我們可以容忍的噪聲的高斯分布的方差越小，泛化性能越好。注意，這里的高斯分布的方差是我們假設的，不一定是實際數據集疊加的高斯噪聲分布的方差，但是假設的越大，總是能帶來更好的泛化能力。

SVM提出我們在上面談到了最佳分類超平面應能夠使得支持向量距離超平面的距離最大，這個就是支持向量機的基本機制的最優化的目標，我們需要解決這個問題就必須要先數學形式化我們這個目的，只有這樣才能進行最優化和求解。

數學形式化表述我們這里對SVM問題進行數學上的形式化表述，以便于求解，這里主要討論SVM的原問題，實際上，SVM通常轉化為對偶問題進行求解，我們將在下一篇文章里討論SVM的對偶問題。

函數間隔和幾何間隔我們剛才的表述中，我們知道了SVM的關鍵就是：使得支持向量距離分類超平面的距離之和最小，這里涉及到了“距離”這個概念，因此我們就必須要定義這個“距離”。這個距離可以定義為函數間隔(functional margin)和幾何間隔(geometric margin)。我們分別來觀察下這兩個間隔。

函數間隔

我們表征一個樣本點到達一個超平面的距離，直接可以表述為:

其中為正確的標簽，為+1或− 1，乘上的目的是當分類正確的時候為正，而當分類錯誤的時候，為負，負數的最大值不超過0，所以也就不存在最大間隔了。整個式子也很好理解，當使得時，該樣本點就處于超平面上，當使得大于0時，該樣本點處于超平面之外，該值越大離超平面就越遠。

幾何間隔函數間隔可以在一定程度上表征距離，但是存在一個問題，就是在W和b同時增大一個相同的倍數時，變成時，因為當時，其零點還是相同的，所以表示的還是相同的超平面。但是我們從函數間隔的定義中可以看出，如果兩者都放大倍，那么其函數間隔也被放大了倍，這個就不符合我們的需求了，我們希望的是只要是相同的一個樣本點和一個固定的超平面，那么它們之間的距離應該是一定的，這個也是符合我們直觀的。因此我們將函數間隔標準化，定義了幾何間隔：

　是L2范式，由于這個標準化因子的作用，使得的值不會隨著放大因子的變化而變化了。很容易看出：

最大化最小距離定義了幾何間隔和函數間隔之后，我們就需要最大化最小距離了，這個聽起來挺繞口的，其實意思很簡單，就是求得一組W和b的情況下的最小樣本距離，然后在不同的W和b的情況下最大化這個最小樣本距離，最后得出的結果就是能夠使得支持向量到超平面的距離最大的超平面了。我們觀察下公式可能會更直觀一些：

這個就是最小幾何間隔距離，我們現在最大化它，有：

將兩者寫在一起，可以表述為：

容易看出其中的 , ? 其實是和約束條件等價的。我們做一些恒等變換有:

這里我們要想一下：的具體取值會不會影響到最優化后的W和b的取值呢？答案是不會的，因為我們只要令**所有支持向量，也就是距離超平面最近的若干個樣本點到超平面的距離為單位量，比如為1即可，這個可以通過等比例調整W和b容易地做到，其他樣本也會隨著進行相應的縮放。這樣對整個超平面的最優化點是沒有任何影響的。**所以我們現在將設為常數1。現在有：

此時最大化問題轉化為最小化問題：

至此，我們得到了SVM的標準原問題表達。注意到這個式子里的，當存在使得時，這個就被稱之為支持向量。如下圖的虛線上的紅色樣本和藍色樣本所示，雖然樣本有很多個，但是有效的，決定超平面的樣本，也就是支持向量一共就只有五個，其到決策面的距離被標準化為了1。

我們接下來將會討論SVM原問題拉格朗日函數形式以及其對偶問題，以便于更好地解決這個最優化問題。