來(lái)吧，朋友!

讓我再一次比較完整的重復(fù)一下我們要解決的問(wèn)題：我們有屬于兩個(gè)類(lèi)別的樣本點(diǎn)（并不限定這些點(diǎn)在二維空間中）若干，如圖，

圓形的樣本點(diǎn)定為正樣本（連帶著，我們可以把正樣本所屬的類(lèi)叫做正類(lèi)），方形的點(diǎn)定為負(fù)例。我們想求得這樣一個(gè)線性函數(shù)（在n維空間中的線性函數(shù)）：

g(x)=wx+b

使得所有屬于正類(lèi)的點(diǎn)x₊代入以后有g(shù)(x₊)≥1，而所有屬于負(fù)類(lèi)的點(diǎn)x_-代入后有g(shù)(x_-)≤-1（之所以總跟1比較，無(wú)論正一還是負(fù)一，都是因?yàn)槲覀児潭碎g隔為1，注意間隔和幾何間隔的區(qū)別）。代入g(x)后的值如果在1和-1之間，我們就拒絕判斷。

求這樣的g(x)的過(guò)程就是求w（一個(gè)n維向量）和b（一個(gè)實(shí)數(shù)）兩個(gè)參數(shù)的過(guò)程（但實(shí)際上只需要求w，求得以后找某些樣本點(diǎn)代入就可以求得b）。因此在求g(x)的時(shí)候，w才是變量。

你肯定能看出來(lái)，一旦求出了w（也就求出了b），那么中間的直線H就知道了（因?yàn)樗褪莣x+b=0嘛，哈哈），那么H1和H2也就知道了（因?yàn)槿呤瞧叫械模蚁喔舻木嚯x還是||w||決定的）。那么w是誰(shuí)決定的？顯然是你給的樣本決定的，一旦你在空間中給出了那些個(gè)樣本點(diǎn)，三條直線的位置實(shí)際上就唯一確定了（因?yàn)槲覀兦蟮氖亲顑?yōu)的那三條，當(dāng)然是唯一的），我們解優(yōu)化問(wèn)題的過(guò)程也只不過(guò)是把這個(gè)確定了的東西算出來(lái)而已。

樣本確定了w，用數(shù)學(xué)的語(yǔ)言描述，就是w可以表示為樣本的某種組合：

w=α₁x₁+α₂x₂+…+α_nx_n

式子中的α_i是一個(gè)一個(gè)的數(shù)（在嚴(yán)格的證明過(guò)程中，這些α被稱(chēng)為拉格朗日乘子），而x_i是樣本點(diǎn)，因而是向量，n就是總樣本點(diǎn)的個(gè)數(shù)。為了方便描述，以下開(kāi)始嚴(yán)格區(qū)別數(shù)字與向量的乘積和向量間的乘積，我會(huì)用α₁x₁表示數(shù)字和向量的乘積，而用<x₁,x₂>表示向量x₁,x₂的內(nèi)積（也叫點(diǎn)積，注意與向量叉積的區(qū)別）。因此g(x)的表達(dá)式嚴(yán)格的形式應(yīng)該是：

g(x)=<w,x>+b

但是上面的式子還不夠好，你回頭看看圖中正樣本和負(fù)樣本的位置，想像一下，我不動(dòng)所有點(diǎn)的位置，而只是把其中一個(gè)正樣本點(diǎn)定為負(fù)樣本點(diǎn)（也就是把一個(gè)點(diǎn)的形狀從圓形變?yōu)榉叫危Y(jié)果怎么樣？三條直線都必須移動(dòng)（因?yàn)閷?duì)這三條直線的要求是必須把方形和圓形的點(diǎn)正確分開(kāi)）！這說(shuō)明w不僅跟樣本點(diǎn)的位置有關(guān)，還跟樣本的類(lèi)別有關(guān)（也就是和樣本的“標(biāo)簽”有關(guān)）。因此用下面這個(gè)式子表示才算完整：

w=α₁y₁x₁+α₂y₂x₂+…+α_ny_nx_n （式1）

其中的y_i就是第i個(gè)樣本的標(biāo)簽，它等于1或者-1。其實(shí)以上式子的那一堆拉格朗日乘子中，只有很少的一部分不等于0（不等于0才對(duì)w起決定作用），這部分不等于0的拉格朗日乘子后面所乘的樣本點(diǎn)，其實(shí)都落在H1和H2上，也正是這部分樣本（而不需要全部樣本）唯一的確定了分類(lèi)函數(shù)，當(dāng)然，更嚴(yán)格的說(shuō)，這些樣本的一部分就可以確定，因?yàn)槔绱_定一條直線，只需要兩個(gè)點(diǎn)就可以，即便有三五個(gè)都落在上面，我們也不是全都需要。這部分我們真正需要的樣本點(diǎn)，就叫做支持（撐）向量！（名字還挺形象吧，他們“撐”起了分界線）

式子也可以用求和符號(hào)簡(jiǎn)寫(xiě)一下：

因此原來(lái)的g(x)表達(dá)式可以寫(xiě)為：

注意式子中x才是變量，也就是你要分類(lèi)哪篇文檔，就把該文檔的向量表示代入到 x的位置，而所有的x_i統(tǒng)統(tǒng)都是已知的樣本。還注意到式子中只有x_i和x是向量，因此一部分可以從內(nèi)積符號(hào)中拿出來(lái)，得到g(x)的式子為：

發(fā)現(xiàn)了什么？w不見(jiàn)啦！從求w變成了求α。

但肯定有人會(huì)說(shuō)，這并沒(méi)有把原問(wèn)題簡(jiǎn)化呀。嘿嘿，其實(shí)簡(jiǎn)化了，只不過(guò)在你看不見(jiàn)的地方，以這樣的形式描述問(wèn)題以后，我們的優(yōu)化問(wèn)題少了很大一部分不等式約束（記得這是我們解不了極值問(wèn)題的萬(wàn)惡之源）。但是接下來(lái)先跳過(guò)線性分類(lèi)器求解的部分，來(lái)看看 SVM在線性分類(lèi)器上所做的重大改進(jìn)——核函數(shù)。

生存？還是毀滅？——哈姆雷特

可分？還是不可分？——支持向量機(jī)

之前一直在討論的線性分類(lèi)器,器如其名（汗，這是什么說(shuō)法啊），只能對(duì)線性可分的樣本做處理。如果提供的樣本線性不可分，結(jié)果很簡(jiǎn)單，線性分類(lèi)器的求解程序會(huì)無(wú)限循環(huán)，永遠(yuǎn)也解不出來(lái)。這必然使得它的適用范圍大大縮小，而它的很多優(yōu)點(diǎn)我們實(shí)在不原意放棄，怎么辦呢？是否有某種方法，讓線性不可分的數(shù)據(jù)變得線性可分呢？

有！其思想說(shuō)來(lái)也簡(jiǎn)單，來(lái)用一個(gè)二維平面中的分類(lèi)問(wèn)題作例子，你一看就會(huì)明白。事先聲明，下面這個(gè)例子是網(wǎng)絡(luò)早就有的，我一時(shí)找不到原作者的正確信息，在此借用，并加進(jìn)了我自己的解說(shuō)而已。

例子是下面這張圖：

我們把橫軸上端點(diǎn)a和b之間紅色部分里的所有點(diǎn)定為正類(lèi)，兩邊的黑色部分里的點(diǎn)定為負(fù)類(lèi)。試問(wèn)能找到一個(gè)線性函數(shù)把兩類(lèi)正確分開(kāi)么？不能，因?yàn)槎S空間里的線性函數(shù)就是指直線，顯然找不到符合條件的直線。

但我們可以找到一條曲線，例如下面這一條：

顯然通過(guò)點(diǎn)在這條曲線的上方還是下方就可以判斷點(diǎn)所屬的類(lèi)別（你在橫軸上隨便找一點(diǎn)，算算這一點(diǎn)的函數(shù)值，會(huì)發(fā)現(xiàn)負(fù)類(lèi)的點(diǎn)函數(shù)值一定比0大，而正類(lèi)的一定比0小）。這條曲線就是我們熟知的二次曲線，它的函數(shù)表達(dá)式可以寫(xiě)為：

問(wèn)題只是它不是一個(gè)線性函數(shù)，但是，下面要注意看了，新建一個(gè)向量y和a：

這樣g(x)就可以轉(zhuǎn)化為f(y)=<a,y>，你可以把y和a分別回帶一下，看看等不等于原來(lái)的g(x)。用內(nèi)積的形式寫(xiě)你可能看不太清楚，實(shí)際上f(y)的形式就是：

g(x)=f(y)=ay

在任意維度的空間中，這種形式的函數(shù)都是一個(gè)線性函數(shù)（只不過(guò)其中的a和y都是多維向量罷了），因?yàn)樽宰兞縴的次數(shù)不大于1。

看出妙在哪了么？原來(lái)在二維空間中一個(gè)線性不可分的問(wèn)題，映射到四維空間后，變成了線性可分的！因此這也形成了我們最初想解決線性不可分問(wèn)題的基本思路——向高維空間轉(zhuǎn)化，使其變得線性可分。

而轉(zhuǎn)化最關(guān)鍵的部分就在于找到x到y(tǒng)的映射方法。遺憾的是，如何找到這個(gè)映射，沒(méi)有系統(tǒng)性的方法（也就是說(shuō)，純靠猜和湊）。具體到我們的文本分類(lèi)問(wèn)題，文本被表示為上千維的向量，即使維數(shù)已經(jīng)如此之高，也常常是線性不可分的，還要向更高的空間轉(zhuǎn)化。其中的難度可想而知。

小Tips:為什么說(shuō)f(y)=ay是四維空間里的函數(shù)?

大家可能一時(shí)沒(méi)看明白。回想一下我們二維空間里的函數(shù)定義
  g(x)=ax+b
變量x是一維的，為什么說(shuō)它是二維空間里的函數(shù)呢？因?yàn)檫€有一個(gè)變量我們沒(méi)寫(xiě)出來(lái)，它的完整形式其實(shí)是
  y=g(x)=ax+b
即
  y=ax+b
看看，有幾個(gè)變量？?jī)蓚€(gè)。那是幾維空間的函數(shù)？（作者五歲的弟弟答：五維的。作者：……）
再看看
f(y)=ay
里面的y是三維的變量，那f(y)是幾維空間里的函數(shù)？（作者五歲的弟弟答：還是五維的。作者：……）

用一個(gè)具體文本分類(lèi)的例子來(lái)看看這種向高維空間映射從而分類(lèi)的方法如何運(yùn)作，想象一下，我們文本分類(lèi)問(wèn)題的原始空間是1000維的（即每個(gè)要被分類(lèi)的文檔被表示為一個(gè)1000維的向量），在這個(gè)維度上問(wèn)題是線性不可分的。現(xiàn)在我們有一個(gè)2000維空間里的線性函數(shù)

f(x^’)=<w^’,x^’>+b

注意向量的右上角有個(gè) ’哦。它能夠?qū)⒃瓎?wèn)題變得可分。式中的 w^’和x^’都是2000維的向量，只不過(guò)w^’是定值，而x^’是變量（好吧,嚴(yán)格說(shuō)來(lái)這個(gè)函數(shù)是2001維的,哈哈），現(xiàn)在我們的輸入呢，是一個(gè)1000維的向量x，分類(lèi)的過(guò)程是先把x變換為2000維的向量x^’，然后求這個(gè)變換后的向量x^’與向量w^’的內(nèi)積，再把這個(gè)內(nèi)積的值和b相加，就得到了結(jié)果，看結(jié)果大于閾值還是小于閾值就得到了分類(lèi)結(jié)果。

你發(fā)現(xiàn)了什么？我們其實(shí)只關(guān)心那個(gè)高維空間里內(nèi)積的值，那個(gè)值算出來(lái)了，分類(lèi)結(jié)果就算出來(lái)了。而從理論上說(shuō)， x^’是經(jīng)由x變換來(lái)的，因此廣義上可以把它叫做x的函數(shù)（有一個(gè)x，就確定了一個(gè)x^’，對(duì)吧，確定不出第二個(gè)），而w^’是常量，它是一個(gè)低維空間里的常量w經(jīng)過(guò)變換得到的，所以給了一個(gè)w 和x的值，就有一個(gè)確定的f(x^’)值與其對(duì)應(yīng)。這讓我們幻想，是否能有這樣一種函數(shù)K(w,x),他接受低維空間的輸入值，卻能算出高維空間的內(nèi)積值<w^’,x^’>？

如果有這樣的函數(shù)，那么當(dāng)給了一個(gè)低維空間的輸入x以后，

g(x)=K(w,x)+b

f(x^’)=<w^’,x^’>+b

這兩個(gè)函數(shù)的計(jì)算結(jié)果就完全一樣，我們也就用不著費(fèi)力找那個(gè)映射關(guān)系，直接拿低維的輸入往g(x)里面代就可以了（再次提醒，這回的g(x)就不是線性函數(shù)啦，因?yàn)槟悴荒鼙ＷCK(w,x)這個(gè)表達(dá)式里的x次數(shù)不高于1哦）。

萬(wàn)幸的是，這樣的K(w,x)確實(shí)存在（發(fā)現(xiàn)凡是我們?nèi)祟?lèi)能解決的問(wèn)題，大都是巧得不能再巧，特殊得不能再特殊的問(wèn)題，總是恰好有些能投機(jī)取巧的地方才能解決，由此感到人類(lèi)的渺小），它被稱(chēng)作核函數(shù)（核，kernel），而且還不止一個(gè)，事實(shí)上，只要是滿足了Mercer條件的函數(shù)，都可以作為核函數(shù)。核函數(shù)的基本作用就是接受兩個(gè)低維空間里的向量，能夠計(jì)算出經(jīng)過(guò)某個(gè)變換后在高維空間里的向量?jī)?nèi)積值。幾個(gè)比較常用的核函數(shù)，俄，教課書(shū)里都列過(guò)，我就不敲了（懶！）。

回想我們上節(jié)說(shuō)的求一個(gè)線性分類(lèi)器，它的形式應(yīng)該是：

現(xiàn)在這個(gè)就是高維空間里的線性函數(shù)（為了區(qū)別低維和高維空間里的函數(shù)和向量，我改了函數(shù)的名字，并且給w和x都加上了 ’），我們就可以用一個(gè)低維空間里的函數(shù)（再一次的，這個(gè)低維空間里的函數(shù)就不再是線性的啦）來(lái)代替，

又發(fā)現(xiàn)什么了？f(x’) 和g(x)里的α，y，b全都是一樣一樣的！這就是說(shuō)，盡管給的問(wèn)題是線性不可分的，但是我們就硬當(dāng)它是線性問(wèn)題來(lái)求解，只不過(guò)求解過(guò)程中，凡是要求內(nèi)積的時(shí)候就用你選定的核函數(shù)來(lái)算。這樣求出來(lái)的α再和你選定的核函數(shù)一組合，就得到分類(lèi)器啦！

明白了以上這些，會(huì)自然的問(wèn)接下來(lái)兩個(gè)問(wèn)題：

1． 既然有很多的核函數(shù)，針對(duì)具體問(wèn)題該怎么選擇？

2． 如果使用核函數(shù)向高維空間映射后，問(wèn)題仍然是線性不可分的，那怎么辦？

第一個(gè)問(wèn)題現(xiàn)在就可以回答你：對(duì)核函數(shù)的選擇，現(xiàn)在還缺乏指導(dǎo)原則！各種實(shí)驗(yàn)的觀察結(jié)果（不光是文本分類(lèi)）的確表明，某些問(wèn)題用某些核函數(shù)效果很好，用另一些就很差，但是一般來(lái)講，徑向基核函數(shù)是不會(huì)出太大偏差的一種，首選。（我做文本分類(lèi)系統(tǒng)的時(shí)候，使用徑向基核函數(shù)，沒(méi)有參數(shù)調(diào)優(yōu)的情況下，絕大部分類(lèi)別的準(zhǔn)確和召回都在85%以上，可見(jiàn)。雖然libSVM的作者林智仁認(rèn)為文本分類(lèi)用線性核函數(shù)效果更佳，待考證）

對(duì)第二個(gè)問(wèn)題的解決則引出了我們下一節(jié)的主題：松弛變量。