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

版權(quán)聲明：本文為博主原創(chuàng)文章，遵循CC 4.0 BY-SA版權(quán)協(xié)議，轉(zhuǎn)載請(qǐng)附上原文出處鏈接和本聲明。

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

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

1） 我們現(xiàn)在的兩類數(shù)據(jù)是線性可分的， 也就是總是存在一個(gè)超平面可以將數(shù)據(jù)完美的分開。

2） 我們的數(shù)據(jù)維度是二維的，也就是特征維只有兩個(gè)，類標(biāo)簽用+1， -1表示，這樣方便我們繪制圖像。

我在前篇博文《機(jī)器學(xué)習(xí)系列之 感知器模型》中已經(jīng)介紹到了感知器這一簡單的線性分類器。感知器很原始，只能對(duì)線性可分的數(shù)據(jù)進(jìn)行準(zhǔn)確分割，而且由于其激活函數(shù)選用的是階躍函數(shù)，因此不能通過梯度的方法進(jìn)行參數(shù)更新，而是只能采用錯(cuò)誤驅(qū)動(dòng)的策略進(jìn)行參數(shù)更新，這樣我們的超平面其實(shí)是不確定的，因?yàn)槠淙Q于具體隨機(jī)到的是哪個(gè)樣本點(diǎn)進(jìn)行更新，這是一個(gè)不穩(wěn)定的結(jié)果。而且，由于采用了這種參數(shù)更新策略，感知器的超平面即使是能夠?qū)⒕€性數(shù)據(jù)完美地分割開，也經(jīng)常會(huì)出現(xiàn)超平面非常接近某一個(gè)類的樣本，而偏離另一個(gè)類的樣本的這種情況，特別是在真實(shí)情況下的數(shù)據(jù)是疊加了噪聲的情況下。　　

如下圖所示，其中綠線是感知器的運(yùn)行結(jié)果，因?yàn)槠渌惴ǖ牟环€(wěn)定性，所以每次的結(jié)果都可能不同，選中的這一次我們可以看出來雖然綠線將兩類數(shù)據(jù)完美地分割開了，但是和藍(lán)色樣本很接近，如果新來的測試樣本疊加一個(gè)噪聲，這個(gè)超平面就很容易將它分類錯(cuò)誤，而最佳分類面粉色線則對(duì)噪聲有著更好地容忍。

樣本噪聲剛才我們談到了樣本集上疊加的噪聲，噪聲廣泛存在于真實(shí)數(shù)據(jù)集中，無法避免，因此我們的分類超平面要能夠?qū)υ肼曔M(jìn)行一定的容忍。一般我們假設(shè)噪聲為高斯噪聲，如下圖所示：

其中紅點(diǎn)為實(shí)際的采樣到的樣本位置? ，而藍(lán)點(diǎn)是可能的樣本的實(shí)際位置，因?yàn)樵肼昇的疊加才使得其偏離到了紅點(diǎn)位置，其中藍(lán)點(diǎn)的位置滿足高斯分布。

最佳分類超平面

也就是說我們根據(jù)點(diǎn)訓(xùn)練出來的感知器的分類器超平面很可能會(huì)出現(xiàn)可以完美地劃分點(diǎn)，但是卻不能正確地劃分對(duì)新來的測試樣本的現(xiàn)象。因?yàn)樾聛淼臉颖竞芸赡芪挥谒{(lán)色的樣本點(diǎn)的位置，也就是表現(xiàn)出了嚴(yán)重的過擬合現(xiàn)象， 而我們的支持向量機(jī)的機(jī)制可以很好地減免這種現(xiàn)象，具有更好的泛化能力。我們用幾張圖來表述下導(dǎo)致這種過擬合的原因：

Figure 1, 感知器分類超平面能將線性可分的樣本完美分割，但是由于樣本疊加了高斯噪聲N NN，所以當(dāng)測試樣本的數(shù)據(jù)出現(xiàn)在超平面“穿過”的“綠圈”之內(nèi)時(shí)，就可能會(huì)出現(xiàn)錯(cuò)分的情況，這就是過擬合的一種表現(xiàn)。

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

SVM提出我們?cè)谏厦嬲劦搅俗罴逊诸惓矫鎽?yīng)能夠使得支持向量距離超平面的距離最大，這個(gè)就是支持向量機(jī)的基本機(jī)制的最優(yōu)化的目標(biāo)，我們需要解決這個(gè)問題就必須要先數(shù)學(xué)形式化我們這個(gè)目的，只有這樣才能進(jìn)行最優(yōu)化和求解。

數(shù)學(xué)形式化表述我們這里對(duì)SVM問題進(jìn)行數(shù)學(xué)上的形式化表述，以便于求解，這里主要討論SVM的原問題，實(shí)際上，SVM通常轉(zhuǎn)化為對(duì)偶問題進(jìn)行求解，我們將在下一篇文章里討論SVM的對(duì)偶問題。

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

函數(shù)間隔

我們表征一個(gè)樣本點(diǎn)到達(dá)一個(gè)超平面的距離，直接可以表述為:

其中為正確的標(biāo)簽，為+1或− 1，乘上的目的是當(dāng)分類正確的時(shí)候為正，而當(dāng)分類錯(cuò)誤的時(shí)候，為負(fù)，負(fù)數(shù)的最大值不超過0，所以也就不存在最大間隔了。整個(gè)式子也很好理解，當(dāng)使得時(shí)，該樣本點(diǎn)就處于超平面上，當(dāng)使得大于0時(shí)，該樣本點(diǎn)處于超平面之外，該值越大離超平面就越遠(yuǎn)。

幾何間隔函數(shù)間隔可以在一定程度上表征距離，但是存在一個(gè)問題，就是在W和b同時(shí)增大一個(gè)相同的倍數(shù)時(shí)，變成時(shí)，因?yàn)楫?dāng)時(shí)，其零點(diǎn)還是相同的，所以表示的還是相同的超平面。但是我們從函數(shù)間隔的定義中可以看出，如果兩者都放大倍，那么其函數(shù)間隔也被放大了倍，這個(gè)就不符合我們的需求了，我們希望的是只要是相同的一個(gè)樣本點(diǎn)和一個(gè)固定的超平面，那么它們之間的距離應(yīng)該是一定的，這個(gè)也是符合我們直觀的。因此我們將函數(shù)間隔標(biāo)準(zhǔn)化，定義了幾何間隔：

　是L2范式，由于這個(gè)標(biāo)準(zhǔn)化因子的作用，使得的值不會(huì)隨著放大因子的變化而變化了。很容易看出：

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

這個(gè)就是最小幾何間隔距離，我們現(xiàn)在最大化它，有：

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

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

這里我們要想一下：的具體取值會(huì)不會(huì)影響到最優(yōu)化后的W和b的取值呢？答案是不會(huì)的，因?yàn)槲覀冎灰?*所有支持向量，也就是距離超平面最近的若干個(gè)樣本點(diǎn)到超平面的距離為單位量，比如為1即可，這個(gè)可以通過等比例調(diào)整W和b容易地做到，其他樣本也會(huì)隨著進(jìn)行相應(yīng)的縮放。這樣對(duì)整個(gè)超平面的最優(yōu)化點(diǎn)是沒有任何影響的。**所以我們現(xiàn)在將設(shè)為常數(shù)1?，F(xiàn)在有：

此時(shí)最大化問題轉(zhuǎn)化為最小化問題：

至此，我們得到了SVM的標(biāo)準(zhǔn)原問題表達(dá)。注意到這個(gè)式子里的，當(dāng)存在使得時(shí)，這個(gè)就被稱之為支持向量。如下圖的虛線上的紅色樣本和藍(lán)色樣本所示，雖然樣本有很多個(gè)，但是有效的，決定超平面的樣本，也就是支持向量一共就只有五個(gè)，其到?jīng)Q策面的距離被標(biāo)準(zhǔn)化為了1。

我們接下來將會(huì)討論SVM原問題拉格朗日函數(shù)形式以及其對(duì)偶問題，以便于更好地解決這個(gè)最優(yōu)化問題。