前言

? ?最開(kāi)始接觸SVM是在吳恩達(dá)的課程上，展示了一個(gè)例子：用SVM將人聲從環(huán)境聲中單獨(dú)剝離出來(lái)。后來(lái)，在吳教授的Coursera機(jī)器學(xué)習(xí)課程中監(jiān)督學(xué)習(xí)部分的末尾，講述了SVM。但是他所講述的SVM是基于邏輯回歸修改而得來(lái)的。 這個(gè)東西確實(shí)不太好明白，目前我也只是將自己的理解結(jié)合July的資料整理描述出來(lái)，在未來(lái)會(huì)繼續(xù)的修正與更新這塊內(nèi)容，下面就開(kāi)始我的粗淺的認(rèn)識(shí)。

一、什么是SVM？

??SVM（Support Vector Machine）即支持向量機(jī)，主要是用于分類任務(wù)（或者說(shuō)二分類任務(wù)）中使用。對(duì)于分類任務(wù)，最基本的思路就是：基于訓(xùn)練集，在樣本空間中，找到一個(gè)劃分超平面（Hyper Plane），將不同類別的樣本劃分開(kāi)來(lái)。但是，可以將訓(xùn)練樣本分開(kāi)的超平面可能有很多，我們是根據(jù)什么來(lái)選擇到底哪一個(gè)是所需要的呢？ SVM是90年代中期發(fā)展起來(lái)的，基于統(tǒng)計(jì)學(xué)習(xí)理論的機(jī)器學(xué)習(xí)算法，它通過(guò)使結(jié)構(gòu)化風(fēng)險(xiǎn)最小來(lái)提高機(jī)器的泛化能力，從而實(shí)現(xiàn)經(jīng)驗(yàn)風(fēng)險(xiǎn)和置信范圍的最小化。（結(jié)構(gòu)化風(fēng)險(xiǎn)和經(jīng)驗(yàn)風(fēng)險(xiǎn)在劃分軟間隔的時(shí)候會(huì)說(shuō)明。） 通俗來(lái)講，它是一種二類分類模型，其基本模型定義為特征空間上的間隔最大的線性分類器，即支持向量機(jī)的學(xué)習(xí)策略便是間隔（Margin）最大化，最終可轉(zhuǎn)化為一個(gè)凸二次規(guī)劃問(wèn)題的求解。

1.1 線性分類

在樣本空間中，劃分超平面可以通過(guò)如下線性方程來(lái)描述： 類別用y表示，數(shù)據(jù)用x表示。其中：y取值為1或-1。分別代表對(duì)應(yīng)的類別。但是，為什么會(huì)取-1和+1呢？這個(gè)標(biāo)準(zhǔn)其實(shí)源自邏輯回歸(logistic regression)。

1.1.1 分類取值1或-1的標(biāo)準(zhǔn)：邏輯回歸

Logistic回歸目的是從特征學(xué)習(xí)出一個(gè)0/1分類模型，而這個(gè)模型是將特性的線性組合作為自變量，由于自變量的取值范圍是負(fù)無(wú)窮到正無(wú)窮。因此，使用logistic函數(shù)（或稱作sigmoid函數(shù)）將自變量映射到(0,1)上，映射后的值被認(rèn)為是屬于y=1的概率。? ? 形式化表示就是? ? 假設(shè)函數(shù)

? ?其中x是n維特征向量，函數(shù)g就是sigmoid函數(shù)。? ?函數(shù)的圖像是：

??可以看到，sigmoid函數(shù)將所有數(shù)據(jù)都映射到了[0,1]之間，? ?而假設(shè)函數(shù)就是特征屬于y=1的概率。

? ??當(dāng)我們要判別一個(gè)新來(lái)的特征屬于哪個(gè)類時(shí)，只需讓大于0.5就是y=1的類，反之屬于y=0類。? ? 再審視一下，發(fā)現(xiàn)只和有關(guān)，>0，那么，g(z)只不過(guò)是用來(lái)映射，真實(shí)的類別決定權(quán)還在。還有當(dāng)時(shí)，=1，反之=0。如果我們只從出發(fā)，希望模型達(dá)到的目標(biāo)無(wú)非就是讓訓(xùn)練數(shù)據(jù)中y=1的特征，而是y=0的特征。Logistic回歸就是要學(xué)習(xí)得到，使得正例的特征遠(yuǎn)大于0，負(fù)例的特征遠(yuǎn)小于0，強(qiáng)調(diào)在全部訓(xùn)練實(shí)例上達(dá)到這個(gè)目標(biāo)。

1.1.2 邏輯回歸表述SVM

類似于邏輯回歸，SVM中，用y = ±1代替邏輯回歸中y = 1和0；用w和b代替。以前的，其中認(rèn)為?，F(xiàn)在我們替換b為，后面替換為（即）。這樣，我們讓，進(jìn)一步。也就是說(shuō)除了y由y=0變?yōu)閥=-1，只是標(biāo)記不同外，與logistic回歸的形式化表示沒(méi)區(qū)別。? ? 再明確下假設(shè)函數(shù)

? ??上面提到過(guò)我們只需考慮的正負(fù)問(wèn)題，而不用關(guān)心g(z)，因此我們這里將g(z)做一個(gè)簡(jiǎn)化，將其簡(jiǎn)單映射到y(tǒng)=-1和y=1上。映射關(guān)系如下：
? ? 于此，想必已經(jīng)解釋明白了為何線性分類的標(biāo)準(zhǔn)一般用1 或者-1 來(lái)標(biāo)示。

1.1.3 線性分類的簡(jiǎn)單例子

下面舉個(gè)簡(jiǎn)單的例子（硬間隔），一個(gè)二維平面(一個(gè)超平面，在二維空間中的例子就是一條直線)，如下圖所示，平面上有兩種不同的點(diǎn)，分別用兩種不同的顏色表示，一種為紅顏色的點(diǎn)，另一種則為藍(lán)顏色的點(diǎn)，紅顏色的線表示一個(gè)可行的超平面。

? ?從上圖中我們可以看出，這條紅顏色的線把紅顏色的點(diǎn)和藍(lán)顏色的點(diǎn)分開(kāi)來(lái)了。而這條紅顏色的線就是我們上面所說(shuō)的超平面，也就是說(shuō)，這個(gè)所謂的超平面的的確確便把這兩種不同顏色的數(shù)據(jù)點(diǎn)分隔開(kāi)來(lái)，在超平面一邊的數(shù)據(jù)點(diǎn)所對(duì)應(yīng)的??全是 -1 ，而在另一邊全是 1 。

? ?接著，我們可以令分類函數(shù)（提醒：下文很大篇幅都在討論著這個(gè)分類函數(shù)，或者說(shuō)模型）：

?

? ?顯然，如果f(x) = 0?,那么x?是位于超平面上的點(diǎn)。

? ?? ?如圖所示，距離超平面最近的幾個(gè)訓(xùn)練樣本點(diǎn)使得為1，這些樣本點(diǎn)稱為支持向量（Support Vector），兩個(gè)異類向量到超平面的距離之和為：。找到有最大間隔的劃分超平面，也就是使最大化，要求滿足條件（s.t.的意思是：subject to）這也就是使得最小化。這就是支持向量機(jī)的基本型。
? ? 當(dāng)然，有些時(shí)候，或者說(shuō)大部分時(shí)候數(shù)據(jù)并不是線性可分的，這個(gè)時(shí)候滿足這樣條件的超平面就根本不存在(不過(guò)關(guān)于如何處理這樣的問(wèn)題我們后面會(huì)講)，這里先從最簡(jiǎn)單的情形開(kāi)始推導(dǎo)，就假設(shè)數(shù)據(jù)都是線性可分的，亦即這樣的超平面是存在的。? ? 而且值得注意的是，這里的Margin是硬間隔，即沒(méi)有或者不考慮誤分類的情況。

??請(qǐng)注意，下面的篇幅將按下述3點(diǎn)走：

咱們就要確定上述分類函數(shù)f(x) = w.x + b（w.x表示w與x的內(nèi)積）中的兩個(gè)參數(shù)w和b，通俗理解的話w是法向量，b是截距；

那如何確定w和b呢？答案是尋找兩條邊界端或極端劃分直線中間的最大間隔（之所以要尋最大間隔是為了能更好的劃分不同類的點(diǎn)，下文你將看到：為尋最大間隔，導(dǎo)出，繼而引入拉格朗日函數(shù)和對(duì)偶變量，化為對(duì)單一因數(shù)對(duì)偶變量的求解，當(dāng)然，這是后話），從而確定最終的最大間隔分類超平面hyper plane和分類函數(shù)；

進(jìn)而把尋求分類函數(shù)f(x) = w.x + b的問(wèn)題轉(zhuǎn)化為對(duì)w，b的最優(yōu)化問(wèn)題，最終化為對(duì)偶因子的求解。

? ?

二、深入了解SVM

2.1 線性可分到線性不可分

2.1.1 從原始問(wèn)題到對(duì)偶問(wèn)題的求解

雖然上文1.3節(jié)給出了目標(biāo)函數(shù)，卻沒(méi)有講怎么來(lái)求解?，F(xiàn)在就讓我們來(lái)處理這個(gè)問(wèn)題?；貞浺幌轮暗玫降哪繕?biāo)函數(shù)（subject to導(dǎo)出的則是約束條件）：

? ? ?由于求的最大值相當(dāng)于求的最小值，所以上述問(wèn)題等價(jià)于（w由分母變成分子，從而也有原來(lái)的max問(wèn)題變?yōu)閙in問(wèn)題，很明顯，兩者問(wèn)題等價(jià)）：

轉(zhuǎn)化到這個(gè)形式后，我們的問(wèn)題成為了一個(gè)凸優(yōu)化問(wèn)題，或者更具體的說(shuō)，因?yàn)楝F(xiàn)在的目標(biāo)函數(shù)是二次的，約束條件是線性的，所以它是一個(gè)凸二次規(guī)劃問(wèn)題。這個(gè)問(wèn)題可以用任何現(xiàn)成的?QP (Quadratic Programming)?的優(yōu)化包進(jìn)行求解，歸結(jié)為一句話即是：在一定的約束條件下，目標(biāo)最優(yōu)，損失最小；

但雖然這個(gè)問(wèn)題確實(shí)是一個(gè)標(biāo)準(zhǔn)的 QP 問(wèn)題，但是它也有它的特殊結(jié)構(gòu)，通過(guò)?Lagrange Duality?變換到對(duì)偶變量 (dual variable) 的優(yōu)化問(wèn)題之后，可以找到一種更加有效的方法來(lái)進(jìn)行求解，而且通常情況下這種方法比直接使用通用的 QP 優(yōu)化包進(jìn)行優(yōu)化要高效得多。

? ??也就說(shuō)，除了用解決QP問(wèn)題的常規(guī)方法之外，還可以通過(guò)求解對(duì)偶問(wèn)題得到最優(yōu)解，這就是線性可分條件下支持向量機(jī)的對(duì)偶算法，這樣做的優(yōu)點(diǎn)在于：一者對(duì)偶問(wèn)題往往更容易求解；二者可以自然的引入核函數(shù)，進(jìn)而推廣到非線性分類問(wèn)題。

? ? 至于上述提到，關(guān)于什么是Lagrange duality？簡(jiǎn)單地來(lái)說(shuō)，通過(guò)給每一個(gè)約束條件加上一個(gè) Lagrange multiplier(拉格朗日乘子)，即引入拉格朗日乘子，如此我們便可以通過(guò)拉格朗日函數(shù)將約束條件融和到目標(biāo)函數(shù)里去(也就是說(shuō)把條件融合到一個(gè)函數(shù)里頭，現(xiàn)在只用一個(gè)函數(shù)表達(dá)式便能清楚的表達(dá)出我們的問(wèn)題，n為樣本個(gè)數(shù))：

? ?然后我們令

? ? 容易驗(yàn)證，當(dāng)某個(gè)約束條件不滿足時(shí)，例如，那么我們顯然有（只要令即可）。而當(dāng)所有約束條件都滿足時(shí)，則有，亦即我們最初要最小化的量。因此，在要求約束條件得到滿足的情況下最小化，實(shí)際上等價(jià)于直接最小化。（當(dāng)然，這里也有約束條件，就是）

因?yàn)槿绻s束條件沒(méi)有得到滿足，會(huì)等于無(wú)窮大，自然不會(huì)是我們所要求的最小值。具體寫出來(lái)，我們現(xiàn)在的目標(biāo)函數(shù)變成了：

? ? 這里用表示這個(gè)問(wèn)題的最優(yōu)值，這個(gè)問(wèn)題和我們最初的問(wèn)題是等價(jià)的。不過(guò)，現(xiàn)在我們來(lái)把最小和最大的位置交換一下（稍后，你將看到，當(dāng)下面式子滿足了一定的條件之后，這個(gè)式子d?便是上式P?的對(duì)偶形式表示）：

? ? 當(dāng)然，交換以后的問(wèn)題不再等價(jià)于原問(wèn)題，這個(gè)新問(wèn)題的最優(yōu)值用來(lái)表示。并且，我們有≤?，這在直觀上也不難理解，最大值中最小的一個(gè)總也比最小值中最大的一個(gè)要大吧！??總之，第二個(gè)問(wèn)題的最優(yōu)值在這里提供了一個(gè)第一個(gè)問(wèn)題的最優(yōu)值的一個(gè)下界，在滿足某些條件的情況下，這兩者相等，這個(gè)時(shí)候我們就可以通過(guò)求解第二個(gè)問(wèn)題來(lái)間接地求解第一個(gè)問(wèn)題。

? ? 也就是說(shuō)，下面我們將先求L 對(duì)w、b的極小，再求L 對(duì)的極大。而且，之所以從minmax的原始問(wèn)題，轉(zhuǎn)化為maxmin的對(duì)偶問(wèn)題，一者因?yàn)槭堑慕平?#xff0c;二者，轉(zhuǎn)化為對(duì)偶問(wèn)題后，更容易求解。

2.1.2 KKT條件

??? 與此同時(shí)，上段說(shuō)“在滿足某些條件的情況下”，這所謂的“滿足某些條件”就是要滿足KKT條件。那KKT條件的表現(xiàn)形式是什么呢？據(jù)維基百科：KKT 條件的介紹，一般地，一個(gè)最優(yōu)化數(shù)學(xué)模型能夠表示成下列標(biāo)準(zhǔn)形式：

? ? 其中，f(x)是需要最小化的函數(shù)，h(x)是等式約束，g(x)是不等式約束，p和q分別為等式約束和不等式約束的數(shù)量。同時(shí)，我們得明白以下兩個(gè)定理：

• 凸優(yōu)化的概念：?為一凸集，??為一凸函數(shù)。凸優(yōu)化就是要找出一點(diǎn)??，使得每一??滿足??。
• KKT條件的意義：它是一個(gè)非線性規(guī)劃（Nonlinear Programming）問(wèn)題能有最優(yōu)化解法的必要和充分條件。

? ? 那到底什么是所謂Karush-Kuhn-Tucker條件呢？KKT條件就是指上面最優(yōu)化數(shù)學(xué)模型的標(biāo)準(zhǔn)形式中的最小點(diǎn)?x*?必須滿足下面的條件：

? ? 經(jīng)過(guò)論證，我們這里的問(wèn)題是滿足 KKT 條件的（首先已經(jīng)滿足Slater condition，再者f和gi也都是可微的，即L對(duì)w和b都可導(dǎo)），因此現(xiàn)在我們便轉(zhuǎn)化為求解第二個(gè)問(wèn)題。也就是說(shuō)，現(xiàn)在，咱們的原問(wèn)題通過(guò)滿足一定的條件，已經(jīng)轉(zhuǎn)化成了對(duì)偶問(wèn)題。而求解這個(gè)對(duì)偶學(xué)習(xí)問(wèn)題，分為3個(gè)步驟，首先要讓L(w，b，a)?關(guān)于??和??最小化，然后求對(duì)α的極大，最后利用SMO算法求解對(duì)偶因子。

2.1.3 求解對(duì)偶問(wèn)題的步驟

? ??（1）首先固定，要讓??關(guān)于??和??最小化，我們分別對(duì)w，b求偏導(dǎo)數(shù)，即令??和??等于零。

? ? 以上結(jié)果代回上述的??

? ? 得到：

? ? 提醒：有讀者可能會(huì)問(wèn)上述推導(dǎo)過(guò)程如何而來(lái)？說(shuō)實(shí)話，其具體推導(dǎo)過(guò)程是比較復(fù)雜的，如下圖所示：

? ? ? 最后，得到：

（2）求的極大值，這塊交由SMO算法處理，具體可以參考相關(guān)論文資料。

不得不提醒下讀者：經(jīng)過(guò)上面第一個(gè)步驟的求w和b，得到的拉格朗日函數(shù)式子已經(jīng)沒(méi)有了變量w，b，只有，而反過(guò)來(lái)，求得的將能導(dǎo)出w，b的解，最終得出分離超平面和分類決策函數(shù)。為何呢？因?yàn)?/span>如果求出了，根據(jù)，即可求出w。然后通過(guò)，即可求出b?。

???如前面所說(shuō)，這個(gè)問(wèn)題有更加高效的優(yōu)化算法，即我們常說(shuō)的SMO（Sequential Minimal Optization）算法。

2.2 核函數(shù)（線性不可分）

2.2.1、特征空間的隱式映射：核函數(shù)

? ? 咱們首先給出核函數(shù)的來(lái)頭：

• 在上文中，我們已經(jīng)了解到了SVM處理線性可分的情況，而對(duì)于非線性的情況，SVM 的處理方法是選擇一個(gè)核函數(shù)??，通過(guò)將數(shù)據(jù)映射到高維空間，來(lái)解決在原始空間中線性不可分的問(wèn)題。由于核函數(shù)的優(yōu)良品質(zhì)，這樣的非線性擴(kuò)展在計(jì)算量上并沒(méi)有比原來(lái)復(fù)雜多少，這一點(diǎn)是非常難得的。當(dāng)然，這要?dú)w功于核方法——除了 SVM 之外，任何將計(jì)算表示為數(shù)據(jù)點(diǎn)的內(nèi)積的方法，都可以使用核方法進(jìn)行非線性擴(kuò)展。

? ? 也就是說(shuō)，Minsky和Papert早就在20世紀(jì)60年代就已經(jīng)明確指出線性學(xué)習(xí)器計(jì)算能力有限。為什么呢？因?yàn)榭傮w上來(lái)講，現(xiàn)實(shí)世界復(fù)雜的應(yīng)用需要有比線性函數(shù)更富有表達(dá)能力的假設(shè)空間，也就是說(shuō)，目標(biāo)概念通常不能由給定屬性的簡(jiǎn)單線性函數(shù)組合產(chǎn)生，而是應(yīng)該一般地尋找待研究數(shù)據(jù)的更為一般化的抽象特征。

? ? 而下文我們將具體介紹的核函數(shù)則提供了此種問(wèn)題的解決途徑，從下文你將看到，核函數(shù)通過(guò)把數(shù)據(jù)映射到高維空間來(lái)增加第一節(jié)所述的線性學(xué)習(xí)器的能力，使得線性學(xué)習(xí)器對(duì)偶空間的表達(dá)方式讓分類操作更具靈活性和可操作性。因?yàn)?span style="font-weight:700;">訓(xùn)練樣例一般是不會(huì)獨(dú)立出現(xiàn)的，它們總是以成對(duì)樣例的內(nèi)積形式出現(xiàn)，而用對(duì)偶形式表示學(xué)習(xí)器的優(yōu)勢(shì)在為在該表示中可調(diào)參數(shù)的個(gè)數(shù)不依賴輸入屬性的個(gè)數(shù)，通過(guò)使用恰當(dāng)?shù)暮撕瘮?shù)來(lái)替代內(nèi)積，可以隱式得將非線性的訓(xùn)練數(shù)據(jù)映射到高維空間，而不增加可調(diào)參數(shù)的個(gè)數(shù)(當(dāng)然，前提是核函數(shù)能夠計(jì)算對(duì)應(yīng)著兩個(gè)輸入特征向量的內(nèi)積)。

? ??1、簡(jiǎn)而言之：在線性不可分的情況下，支持向量機(jī)通過(guò)某種事先選擇的非線性映射(核函數(shù))將輸入變量映射到一個(gè)高維特征空間，在這個(gè)空間中構(gòu)造最優(yōu)分類超平面。我們使用SVM進(jìn)行數(shù)據(jù)集分類工作的過(guò)程首先是同預(yù)先選定的一些非線性映射將輸入空間映射到高維特征空間(下圖很清晰的表達(dá)了通過(guò)映射到高維特征空間，而把平面上本身不好分的非線性數(shù)據(jù)分了開(kāi)來(lái))：? ? 使得在高維屬性空間中有可能最訓(xùn)練數(shù)據(jù)實(shí)現(xiàn)超平面的分割，避免了在原輸入空間中進(jìn)行非線性曲面分割計(jì)算。SVM數(shù)據(jù)集形成的分類函數(shù)具有這樣的性質(zhì)：它是一組以支持向量為參數(shù)的非線性函數(shù)的線性組合，因此分類函數(shù)的表達(dá)式僅和支持向量的數(shù)量有關(guān)，而獨(dú)立于空間的維度，在處理高維輸入空間的分類時(shí)，這種方法尤其有效，其工作原理如下圖所示：? ?2、具體點(diǎn)說(shuō)：在我們遇到核函數(shù)之前，如果用原始的方法，那么在用線性學(xué)習(xí)器學(xué)習(xí)一個(gè)非線性關(guān)系，需要選擇一個(gè)非線性特征集，并且將數(shù)據(jù)寫成新的表達(dá)形式，這等價(jià)于應(yīng)用一個(gè)固定的非線性映射，將數(shù)據(jù)映射到特征空間，在特征空間中使用線性學(xué)習(xí)器，因此，考慮的假設(shè)集是這種類型的函數(shù)：這里?：X->F是從輸入空間到某個(gè)特征空間的映射，這意味著建立非線性學(xué)習(xí)器分為兩步：

首先使用一個(gè)非線性映射將數(shù)據(jù)變換到一個(gè)特征空間F，

然后在特征空間使用線性學(xué)習(xí)器分類。

在上文我提到過(guò)對(duì)偶形式，而這個(gè)對(duì)偶形式就是線性學(xué)習(xí)器的一個(gè)重要性質(zhì)，這意味著假設(shè)可以表達(dá)為訓(xùn)練點(diǎn)的線性組合，因此決策規(guī)則可以用測(cè)試點(diǎn)和訓(xùn)練點(diǎn)的內(nèi)積來(lái)表示：如果有一種方式可以在特征空間中直接計(jì)算內(nèi)積〈φ(x_i?·?φ(x)〉，就像在原始輸入點(diǎn)的函數(shù)中一樣，就有可能將兩個(gè)步驟融合到一起建立一個(gè)非線性的學(xué)習(xí)器，這樣直接計(jì)算法的方法稱為核函數(shù)方法，于是，核函數(shù)便橫空出世了。? ? 這里我直接給出一個(gè)定義：核是一個(gè)函數(shù)K，對(duì)所有x，z(-X，滿足，這里φ是從X到內(nèi)積特征空間F的映射。? ??3、總而言之，舉個(gè)簡(jiǎn)單直接點(diǎn)的例子，如@Wind所說(shuō)：如果不是用核技術(shù)，就會(huì)先計(jì)算線性映射phy(x1)和phy(x2),然后計(jì)算這兩個(gè)特征的內(nèi)積，使用了核技術(shù)之后，先把phy(x1)和phy(x2)的通用表達(dá)式子：< phy(x1)，phy(x2) >=k( <x1,x2> )計(jì)算出來(lái)，注意到這里的< ， >表示內(nèi)積，k( , )就是對(duì)應(yīng)的核函數(shù)，這個(gè)表達(dá)往往非常簡(jiǎn)單，所以計(jì)算非常方便。? ? OK，接下來(lái)，咱們就進(jìn)一步從外到里，來(lái)探探這個(gè)核函數(shù)的真面目。

2.2.2、核函數(shù)：如何處理非線性數(shù)據(jù)

? ? 在2.1節(jié)中我們介紹了線性情況下的支持向量機(jī)，它通過(guò)尋找一個(gè)線性的超平面來(lái)達(dá)到對(duì)數(shù)據(jù)進(jìn)行分類的目的。不過(guò)，由于是線性方法，所以對(duì)非線性的數(shù)據(jù)就沒(méi)有辦法處理。舉個(gè)例子來(lái)說(shuō)，則是如下圖所示的兩類數(shù)據(jù)，分別分布為兩個(gè)圓圈的形狀，這樣的數(shù)據(jù)本身就是線性不可分的，此時(shí)咱們?cè)撊绾伟堰@兩類數(shù)據(jù)分開(kāi)呢(下文將會(huì)有一個(gè)相應(yīng)的三維空間圖)？

??

? ? 事實(shí)上，上圖所述的這個(gè)數(shù)據(jù)集，是用兩個(gè)半徑不同的圓圈加上了少量的噪音生成得到的，所以，一個(gè)理想的分界應(yīng)該是一個(gè)“圓圈”而不是一條線（超平面）。如果用??和??來(lái)表示這個(gè)二維平面的兩個(gè)坐標(biāo)的話，我們知道一條二次曲線（圓圈是二次曲線的一種特殊情況）的方程可以寫作這樣的形式：

? ? 注意上面的形式，如果我們構(gòu)造另外一個(gè)五維的空間，其中五個(gè)坐標(biāo)的值分別為?,?,?,?,?，那么顯然，上面的方程在新的坐標(biāo)系下可以寫作：

? ? 關(guān)于新的坐標(biāo)??，這正是一個(gè) hyper plane 的方程！也就是說(shuō)，如果我們做一個(gè)映射??，將??按照上面的規(guī)則映射為??，那么在新的空間中原來(lái)的數(shù)據(jù)將變成線性可分的，從而使用之前我們推導(dǎo)的線性分類算法就可以進(jìn)行處理了。這正是?Kernel?方法處理非線性問(wèn)題的基本思想。

? ? 再進(jìn)一步描述 Kernel 的細(xì)節(jié)之前，不妨再來(lái)看看這個(gè)例子映射過(guò)后的直觀例子。當(dāng)然，你我可能無(wú)法把 5 維空間畫出來(lái)，不過(guò)由于我這里生成數(shù)據(jù)的時(shí)候就是用了特殊的情形，具體來(lái)說(shuō)，我這里的超平面實(shí)際的方程是這個(gè)樣子（圓心在??軸上的一個(gè)正圓）：

? ? 因此我只需要把它映射到?,?,??這樣一個(gè)三維空間中即可，下圖即是映射之后的結(jié)果，將坐標(biāo)軸經(jīng)過(guò)適當(dāng)?shù)男D(zhuǎn)，就可以很明顯地看出，數(shù)據(jù)是可以通過(guò)一個(gè)平面來(lái)分開(kāi)的(pluskid：下面的gif 動(dòng)畫，先用 Matlab 畫出一張張圖片，再用 Imagemagick 拼貼成)：

? ? 現(xiàn)在讓我們?cè)倩氐?SVM 的情形，假設(shè)原始的數(shù)據(jù)時(shí)非線性的，我們通過(guò)一個(gè)映射??將其映射到一個(gè)高維空間中，數(shù)據(jù)變得線性可分了，這個(gè)時(shí)候，我們就可以使用原來(lái)的推導(dǎo)來(lái)進(jìn)行計(jì)算，只是所有的推導(dǎo)現(xiàn)在是在新的空間，而不是原始空間中進(jìn)行。當(dāng)然，推導(dǎo)過(guò)程也并不是可以簡(jiǎn)單地直接類比的，例如，原本我們要求超平面的法向量??，但是如果映射之后得到的新空間的維度是無(wú)窮維的（確實(shí)會(huì)出現(xiàn)這樣的情況，比如后面會(huì)提到的 高斯核Gaussian Kernel?），要表示一個(gè)無(wú)窮維的向量描述起來(lái)就比較麻煩。于是我們不妨先忽略過(guò)這些細(xì)節(jié)，直接從最終的結(jié)論來(lái)分析，回憶一下，我們上一次2.1節(jié)中得到的最終的分類函數(shù)是這樣的：

? ? 現(xiàn)在則是在映射過(guò)后的空間，即：

? ??而其中的??也是通過(guò)求解如下 dual 問(wèn)題而得到的：

??? 這樣一來(lái)問(wèn)題就解決了嗎？似乎是的：拿到非線性數(shù)據(jù)，就找一個(gè)映射??，然后一股腦把原來(lái)的數(shù)據(jù)映射到新空間中，再做線性 SVM 即可。不過(guò)事實(shí)上沒(méi)有這么簡(jiǎn)單！其實(shí)剛才的方法稍想一下就會(huì)發(fā)現(xiàn)有問(wèn)題：在最初的例子里，我們對(duì)一個(gè)二維空間做映射，選擇的新空間是原始空間的所有一階和二階的組合，得到了五個(gè)維度；如果原始空間是三維，那么我們會(huì)得到 19 維的新空間，這個(gè)數(shù)目是呈爆炸性增長(zhǎng)的，這給??的計(jì)算帶來(lái)了非常大的困難，而且如果遇到無(wú)窮維的情況，就根本無(wú)從計(jì)算了。所以就需要 Kernel 出馬了。

??? 不妨還是從最開(kāi)始的簡(jiǎn)單例子出發(fā)，設(shè)兩個(gè)向量和，而即是到前面2.2.1節(jié)說(shuō)的五維空間的映射，因此映射過(guò)后的內(nèi)積為：

? ? ? ??（公式說(shuō)明：上面的這兩個(gè)推導(dǎo)過(guò)程中，所說(shuō)的前面的五維空間的映射，這里說(shuō)的前面便是文中2.2.1節(jié)的所述的映射方式，仔細(xì)看下2.2.1節(jié)的映射規(guī)則，再看那第一個(gè)推導(dǎo)，其實(shí)就是計(jì)算x1，x2各自的內(nèi)積，然后相乘相加即可，第二個(gè)推導(dǎo)則是直接平方，去掉括號(hào)，也很容易推出來(lái)）

? ? 另外，我們又注意到：

? ? ?二者有很多相似的地方，實(shí)際上，我們只要把某幾個(gè)維度線性縮放一下，然后再加上一個(gè)常數(shù)維度，具體來(lái)說(shuō)，上面這個(gè)式子的計(jì)算結(jié)果實(shí)際上和映射

? ? ?之后的內(nèi)積的結(jié)果是相等的，那么區(qū)別在于什么地方呢？

一個(gè)是映射到高維空間中，然后再根據(jù)內(nèi)積的公式進(jìn)行計(jì)算；

而另一個(gè)則直接在原來(lái)的低維空間中進(jìn)行計(jì)算，而不需要顯式地寫出映射后的結(jié)果。

? ? （公式說(shuō)明：上面之中，最后的兩個(gè)式子，第一個(gè)算式，是帶內(nèi)積的完全平方式，可以拆開(kāi)，然后，通過(guò)湊一個(gè)得到，第二個(gè)算式，也是根據(jù)第一個(gè)算式湊出來(lái)的）

? ? 回憶剛才提到的映射的維度爆炸，在前一種方法已經(jīng)無(wú)法計(jì)算的情況下，后一種方法卻依舊能從容處理，甚至是無(wú)窮維度的情況也沒(méi)有問(wèn)題。

??? 我們把這里的計(jì)算兩個(gè)向量在隱式映射過(guò)后的空間中的內(nèi)積的函數(shù)叫做核函數(shù)?(Kernel Function) ，例如，在剛才的例子中，我們的核函數(shù)為：

? ??核函數(shù)能簡(jiǎn)化映射空間中的內(nèi)積運(yùn)算——?jiǎng)偤谩芭銮伞钡氖?#xff0c;在我們的?SVM 里需要計(jì)算的地方數(shù)據(jù)向量總是以內(nèi)積的形式出現(xiàn)的。對(duì)比剛才我們上面寫出來(lái)的式子，現(xiàn)在我們的分類函數(shù)為：

? ? 其中??由如下 dual 問(wèn)題計(jì)算而得：

? ? 這樣一來(lái)計(jì)算的問(wèn)題就算解決了，避開(kāi)了直接在高維空間中進(jìn)行計(jì)算，而結(jié)果卻是等價(jià)的！當(dāng)然，因?yàn)槲覀冞@里的例子非常簡(jiǎn)單，所以我可以手工構(gòu)造出對(duì)應(yīng)于的核函數(shù)出來(lái)，如果對(duì)于任意一個(gè)映射，想要構(gòu)造出對(duì)應(yīng)的核函數(shù)就很困難了。

2.2.3、幾個(gè)核函數(shù)

? ? 通常人們會(huì)從一些常用的核函數(shù)中選擇（根據(jù)問(wèn)題和數(shù)據(jù)的不同，選擇不同的參數(shù)，實(shí)際上就是得到了不同的核函數(shù)），例如：

• 多項(xiàng)式核，顯然剛才我們舉的例子是這里多項(xiàng)式核的一個(gè)特例（R = 1，d = 2）。雖然比較麻煩，而且沒(méi)有必要，不過(guò)這個(gè)核所對(duì)應(yīng)的映射實(shí)際上是可以寫出來(lái)的，該空間的維度是，其中??是原始空間的維度。
• 高斯核，這個(gè)核就是最開(kāi)始提到過(guò)的會(huì)將原始空間映射為無(wú)窮維空間的那個(gè)家伙。不過(guò)，如果選得很大的話，高次特征上的權(quán)重實(shí)際上衰減得非?？?#xff0c;所以實(shí)際上（數(shù)值上近似一下）相當(dāng)于一個(gè)低維的子空間；反過(guò)來(lái)，如果選得很小，則可以將任意的數(shù)據(jù)映射為線性可分——當(dāng)然，這并不一定是好事，因?yàn)殡S之而來(lái)的可能是非常嚴(yán)重的過(guò)擬合問(wèn)題。不過(guò)，總的來(lái)說(shuō)，通過(guò)調(diào)控參數(shù)，高斯核實(shí)際上具有相當(dāng)高的靈活性，也是使用最廣泛的核函數(shù)之一。下圖所示的例子便是把低維線性不可分的數(shù)據(jù)通過(guò)高斯核函數(shù)映射到了高維空間：
• 線性核，這實(shí)際上就是原始空間中的內(nèi)積。這個(gè)核存在的主要目的是使得“映射后空間中的問(wèn)題”和“映射前空間中的問(wèn)題”兩者在形式上統(tǒng)一起來(lái)了(意思是說(shuō)，咱們有的時(shí)候，寫代碼，或?qū)懝降臅r(shí)候，只要寫個(gè)模板或通用表達(dá)式，然后再代入不同的核，便可以了，于此，便在形式上統(tǒng)一了起來(lái)，不用再分別寫一個(gè)線性的，和一個(gè)非線性的)。

2.2.4、核函數(shù)的本質(zhì)

上面說(shuō)了這么一大堆，讀者可能還是沒(méi)明白核函數(shù)到底是個(gè)什么東西？我再簡(jiǎn)要概括下，即以下三點(diǎn)：

實(shí)際中，我們會(huì)經(jīng)常遇到線性不可分的樣例，此時(shí)，我們的常用做法是把樣例特征映射到高維空間中去(如上文2.2節(jié)最開(kāi)始的那幅圖所示，映射到高維空間后，相關(guān)特征便被分開(kāi)了，也就達(dá)到了分類的目的)；

但進(jìn)一步，如果凡是遇到線性不可分的樣例，一律映射到高維空間，那么這個(gè)維度大小是會(huì)高到可怕的(如上文中19維乃至無(wú)窮維的例子)。那咋辦呢？

此時(shí)，核函數(shù)就隆重登場(chǎng)了，核函數(shù)的價(jià)值在于它雖然也是講特征進(jìn)行從低維到高維的轉(zhuǎn)換，但核函數(shù)絕就絕在它事先在低維上進(jìn)行計(jì)算，而將實(shí)質(zhì)上的分類效果表現(xiàn)在了高維上，也就如上文所說(shuō)的避免了直接在高維空間中的復(fù)雜計(jì)算。

? ? 最后引用這里的一個(gè)例子舉例說(shuō)明下核函數(shù)解決非線性問(wèn)題的直觀效果。

? ??假設(shè)現(xiàn)在你是一個(gè)農(nóng)場(chǎng)主，圈養(yǎng)了一批羊群，但為預(yù)防狼群襲擊羊群，你需要搭建一個(gè)籬笆來(lái)把羊群圍起來(lái)。但是籬笆應(yīng)該建在哪里呢？你很可能需要依據(jù)牛群和狼群的位置建立一個(gè)“分類器”，比較下圖這幾種不同的分類器，我們可以看到支持向量機(jī)完成了一個(gè)很完美的解決方案。

? ? 這個(gè)例子從側(cè)面簡(jiǎn)單說(shuō)明了支持向量機(jī)使用非線性分類器的優(yōu)勢(shì)，而邏輯模式以及決策樹(shù)模式都是使用了直線方法。

2.2.5、當(dāng)滿足什么條件的時(shí)候，k(.,.)才是核函數(shù)呢？

?ht關(guān)于核函數(shù)的選取和為什么他可以在低維計(jì)算等效成高維計(jì)算，請(qǐng)看這篇文章核函數(shù)

2.3、使用松弛變量處理 outliers 方法（軟間隔問(wèn)題）

??? 在本文第一節(jié)最開(kāi)始討論支持向量機(jī)的時(shí)候，我們就假定，數(shù)據(jù)是線性可分的，亦即我們可以找到一個(gè)可行的超平面將數(shù)據(jù)完全分開(kāi)。后來(lái)為了處理非線性數(shù)據(jù)，在上文2.2節(jié)使用 Kernel 方法對(duì)原來(lái)的線性 SVM 進(jìn)行了推廣，使得非線性的的情況也能處理。雖然通過(guò)映射??將原始數(shù)據(jù)映射到高維空間之后，能夠線性分隔的概率大大增加，但是對(duì)于某些情況還是很難處理。

? ? 例如可能并不是因?yàn)閿?shù)據(jù)本身是非線性結(jié)構(gòu)的，而只是因?yàn)閿?shù)據(jù)有噪音。對(duì)于這種偏離正常位置很遠(yuǎn)的數(shù)據(jù)點(diǎn)，我們稱之為 outlier ，在我們?cè)瓉?lái)的 SVM 模型里，outlier 的存在有可能造成很大的影響，因?yàn)槌矫姹旧砭褪侵挥猩贁?shù)幾個(gè) support vector 組成的，如果這些 support vector 里又存在 outlier 的話，其影響就很大了。例如下圖：

??? 用黑圈圈起來(lái)的那個(gè)藍(lán)點(diǎn)是一個(gè) outlier ，它偏離了自己原本所應(yīng)該在的那個(gè)半空間，如果直接忽略掉它的話，原來(lái)的分隔超平面還是挺好的，但是由于這個(gè) outlier 的出現(xiàn)，導(dǎo)致分隔超平面不得不被擠歪了，變成途中黑色虛線所示（這只是一個(gè)示意圖，并沒(méi)有嚴(yán)格計(jì)算精確坐標(biāo)），同時(shí) margin 也相應(yīng)變小了。當(dāng)然，更嚴(yán)重的情況是，如果這個(gè) outlier 再往右上移動(dòng)一些距離的話，我們將無(wú)法構(gòu)造出能將數(shù)據(jù)分開(kāi)的超平面來(lái)。

??? 為了處理這種情況，SVM 允許數(shù)據(jù)點(diǎn)在一定程度上偏離一下超平面（為了防止過(guò)擬合，SVM允許在一些樣本上預(yù)測(cè)出錯(cuò)，以滿足整體的的最大化Margin）。例如上圖中，黑色實(shí)線所對(duì)應(yīng)的距離，就是該 outlier 偏離的距離，如果把它移動(dòng)回來(lái)，就剛好落在原來(lái)的超平面上，而不會(huì)使得超平面發(fā)生變形了。

? ? 插播下一位讀者@Copper_PKU的理解：“換言之，在有松弛的情況下outline點(diǎn)也屬于支持向量SV，同時(shí)，對(duì)于不同的支持向量，拉格朗日參數(shù)的值也不同，如此篇論文《Large Scale Machine Learning》中的下圖所示：

? ??對(duì)于遠(yuǎn)離分類平面的點(diǎn)值為0；對(duì)于邊緣上的點(diǎn)值在[0, 1/L]之間，其中，L為訓(xùn)練數(shù)據(jù)集個(gè)數(shù)，即數(shù)據(jù)集大小；對(duì)于outline數(shù)據(jù)和內(nèi)部的數(shù)據(jù)值為1/L。更多請(qǐng)參看本文文末參考條目第51條。”

我們的優(yōu)化目標(biāo)是：

其中：l0/1為損失函數(shù)。（下面損失函數(shù)的形式用采用hinge損失函數(shù)）。

還可以將優(yōu)化目標(biāo)寫成更一般的形式：

其中，稱為結(jié)構(gòu)風(fēng)險(xiǎn)（Structural risk），用于描述模型f的某些性質(zhì)；第二項(xiàng)稱為經(jīng)驗(yàn)風(fēng)險(xiǎn)（Empirical risk），用于描述模型和訓(xùn)練數(shù)據(jù)的契合程度；C將二者折中。換一個(gè)角度說(shuō)，可以將上式理解成“正則化問(wèn)題”，為正則化項(xiàng)，C為正則化常數(shù)。（在吳恩達(dá)的機(jī)器學(xué)習(xí)課程中，效果等同于，其中為邏輯回歸中的正則化參數(shù)，或者說(shuō)是為了防止過(guò)擬合的懲罰因子）

? ? OK，繼續(xù)回到咱們的問(wèn)題。我們，原來(lái)的約束條件為：

??? 現(xiàn)在考慮到outlier問(wèn)題（即不是所有的樣本點(diǎn)都滿足這個(gè)條件，由噪聲數(shù)據(jù)或者其他情況造就，采用hinge損失形式），約束條件變成了：

? ? 其中稱為松弛變量 (slack variable)，對(duì)應(yīng)數(shù)據(jù)點(diǎn)允許偏離的 functional margin 的量。當(dāng)然，如果我們使任意大的話，那任意的超平面都是符合條件的了。所以，我們?cè)谠瓉?lái)的目標(biāo)函數(shù)（效果等效為L(zhǎng)ogistic regression中的Cost Function）后面加上一項(xiàng)，使得這些的總和也要最小：

? ? 其中??是一個(gè)參數(shù)，用于控制目標(biāo)函數(shù)中兩項(xiàng)（“尋找 margin 最大的超平面”和“保證數(shù)據(jù)點(diǎn)偏差量最小”）之間的權(quán)重。注意，其中??是需要優(yōu)化的變量（之一），而??是一個(gè)事先確定好的常量。完整地寫出來(lái)是這個(gè)樣子：

用之前的方法將限制或約束條件加入到目標(biāo)函數(shù)中，得到新的拉格朗日函數(shù)，如下所示：

? ? ?分析方法和前面一樣，轉(zhuǎn)換為另一個(gè)問(wèn)題之后，我們先讓針對(duì)、和最小化：

? ? ?將??帶回??并化簡(jiǎn)，得到和原來(lái)一樣的目標(biāo)函數(shù)：

? ? ?不過(guò)，由于我們得到而又有（作為 Lagrange multiplier 的條件），因此有，所以整個(gè) dual 問(wèn)題現(xiàn)在寫作：

? ? 把前后的結(jié)果對(duì)比一下（錯(cuò)誤修正：圖中的Dual formulation中的Minimize應(yīng)為maxmize）：

? ??可以看到唯一的區(qū)別就是現(xiàn)在 dual variable??多了一個(gè)上限?。而 Kernel 化的非線性形式也是一樣的，只要把換成即可。這樣一來(lái)，一個(gè)完整的，可以處理線性和非線性并能容忍噪音和 outliers 的支持向量機(jī)才終于介紹完畢了。

三、小結(jié)

? ??不準(zhǔn)確的說(shuō)，SVM它本質(zhì)上即是一個(gè)分類方法，用w^T+b定義分類函數(shù)，于是求w、b，為尋最大間隔，目標(biāo)是求函數(shù)1/2||w||^2的最小值，繼而引入拉格朗日因子，化為對(duì)拉格朗日乘子a的求解（求解過(guò)程中會(huì)涉及到一系列最優(yōu)化或凸二次規(guī)劃等問(wèn)題）。如此，通過(guò)對(duì)偶轉(zhuǎn)換，將求w.b與求等價(jià)，而的求解可以用一種快速學(xué)習(xí)算法SMO，至于核函數(shù)，是為處理非線性情況，若直接映射到高維計(jì)算恐維度爆炸，故在低維計(jì)算，等效高維表現(xiàn)。

本文主要參考了July大神的《支持向量機(jī)通俗導(dǎo)論（理解SVM的三層境界）》，周志華的《機(jī)器學(xué)習(xí)》還是吳恩達(dá)的機(jī)器學(xué)習(xí)課程，并在此基礎(chǔ)上加上了一些自己的理解。文中的圖主要是從July的文章中拿的，衷心感謝！

總結(jié)

以上是生活随笔為你收集整理的机器学习基础——支持向量机的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。