來(lái)吧，朋友!

現(xiàn)在我們已經(jīng)把一個(gè)本來(lái)線性不可分的文本分類(lèi)問(wèn)題，通過(guò)映射到高維空間而變成了線性可分的。就像下圖這樣：

圓形和方形的點(diǎn)各有成千上萬(wàn)個(gè)（畢竟，這就是我們訓(xùn)練集中文檔的數(shù)量嘛，當(dāng)然很大了）?，F(xiàn)在想象我們有另一個(gè)訓(xùn)練集，只比原先這個(gè)訓(xùn)練集多了一篇文章，映射到高維空間以后（當(dāng)然，也使用了相同的核函數(shù)），也就多了一個(gè)樣本點(diǎn)，但是這個(gè)樣本的位置是這樣的：

就是圖中黃色那個(gè)點(diǎn)，它是方形的，因而它是負(fù)類(lèi)的一個(gè)樣本，這單獨(dú)的一個(gè)樣本，使得原本線性可分的問(wèn)題變成了線性不可分的。這樣類(lèi)似的問(wèn)題（僅有少數(shù)點(diǎn)線性不可分）叫做“近似線性可分”的問(wèn)題。

以我們?nèi)祟?lèi)的常識(shí)來(lái)判斷，說(shuō)有一萬(wàn)個(gè)點(diǎn)都符合某種規(guī)律（因而線性可分），有一個(gè)點(diǎn)不符合，那這一個(gè)點(diǎn)是否就代表了分類(lèi)規(guī)則中我們沒(méi)有考慮到的方面呢（因而規(guī)則應(yīng)該為它而做出修改）？

其實(shí)我們會(huì)覺(jué)得，更有可能的是，這個(gè)樣本點(diǎn)壓根就是錯(cuò)誤，是噪聲，是提供訓(xùn)練集的同學(xué)人工分類(lèi)時(shí)一打瞌睡錯(cuò)放進(jìn)去的。所以我們會(huì)簡(jiǎn)單的忽略這個(gè)樣本點(diǎn)，仍然使用原來(lái)的分類(lèi)器，其效果絲毫不受影響。

但這種對(duì)噪聲的容錯(cuò)性是人的思維帶來(lái)的，我們的程序可沒(méi)有。由于我們?cè)镜膬?yōu)化問(wèn)題的表達(dá)式中，確實(shí)要考慮所有的樣本點(diǎn)（不能忽略某一個(gè)，因?yàn)槌绦蛩趺粗涝摵雎阅囊粋€(gè)呢？），在此基礎(chǔ)上尋找正負(fù)類(lèi)之間的最大幾何間隔，而幾何間隔本身代表的是距離，是非負(fù)的，像上面這種有噪聲的情況會(huì)使得整個(gè)問(wèn)題無(wú)解。這種解法其實(shí)也叫做“硬間隔”分類(lèi)法，因?yàn)樗残缘囊笏袠颖军c(diǎn)都滿足和分類(lèi)平面間的距離必須大于某個(gè)值。

因此由上面的例子中也可以看出，硬間隔的分類(lèi)法其結(jié)果容易受少數(shù)點(diǎn)的控制，這是很危險(xiǎn)的（盡管有句話說(shuō)真理總是掌握在少數(shù)人手中，但那不過(guò)是那一小撮人聊以自慰的詞句罷了，咱還是得民主）。

但解決方法也很明顯，就是仿照人的思路，允許一些點(diǎn)到分類(lèi)平面的距離不滿足原先的要求。由于不同的訓(xùn)練集各點(diǎn)的間距尺度不太一樣，因此用間隔（而不是幾何間隔）來(lái)衡量有利于我們表達(dá)形式的簡(jiǎn)潔。我們?cè)葘?duì)樣本點(diǎn)的要求是：

意思是說(shuō)離分類(lèi)面最近的樣本點(diǎn)函數(shù)間隔也要比1大。如果要引入容錯(cuò)性，就給1這個(gè)硬性的閾值加一個(gè)松弛變量，即允許

因?yàn)樗沙谧兞渴欠秦?fù)的，因此最終的結(jié)果是要求間隔可以比1小。但是當(dāng)某些點(diǎn)出現(xiàn)這種間隔比1小的情況時(shí)（這些點(diǎn)也叫離群點(diǎn)），意味著我們放棄了對(duì)這些點(diǎn)的精確分類(lèi)，而這對(duì)我們的分類(lèi)器來(lái)說(shuō)是種損失。但是放棄這些點(diǎn)也帶來(lái)了好處，那就是使分類(lèi)面不必向這些點(diǎn)的方向移動(dòng)，因而可以得到更大的幾何間隔（在低維空間看來(lái)，分類(lèi)邊界也更平滑）。顯然我們必須權(quán)衡這種損失和好處。好處很明顯，我們得到的分類(lèi)間隔越大，好處就越多?；仡櫸覀?cè)嫉挠查g隔分類(lèi)對(duì)應(yīng)的優(yōu)化問(wèn)題：

||w||²就是我們的目標(biāo)函數(shù)（當(dāng)然系數(shù)可有可無(wú)），希望它越小越好，因而損失就必然是一個(gè)能使之變大的量（能使它變小就不叫損失了，我們本來(lái)就希望目標(biāo)函數(shù)值越小越好）。那如何來(lái)衡量損失，有兩種常用的方式，有人喜歡用

而有人喜歡用

其中l(wèi)都是樣本的數(shù)目。兩種方法沒(méi)有大的區(qū)別。如果選擇了第一種，得到的方法的就叫做二階軟間隔分類(lèi)器，第二種就叫做一階軟間隔分類(lèi)器。把損失加入到目標(biāo)函數(shù)里的時(shí)候，就需要一個(gè)懲罰因子（cost，也就是libSVM的諸多參數(shù)中的C），原來(lái)的優(yōu)化問(wèn)題就變成了下面這樣：

這個(gè)式子有這么幾點(diǎn)要注意：

一是并非所有的樣本點(diǎn)都有一個(gè)松弛變量與其對(duì)應(yīng)。實(shí)際上只有“離群點(diǎn)”才有，或者也可以這么看，所有沒(méi)離群的點(diǎn)松弛變量都等于0（對(duì)負(fù)類(lèi)來(lái)說(shuō)，離群點(diǎn)就是在前面圖中，跑到H2右側(cè)的那些負(fù)樣本點(diǎn)，對(duì)正類(lèi)來(lái)說(shuō)，就是跑到H1左側(cè)的那些正樣本點(diǎn)）。

二是松弛變量的值實(shí)際上標(biāo)示出了對(duì)應(yīng)的點(diǎn)到底離群有多遠(yuǎn)，值越大，點(diǎn)就越遠(yuǎn)。

三是懲罰因子C決定了你有多重視離群點(diǎn)帶來(lái)的損失，顯然當(dāng)所有離群點(diǎn)的松弛變量的和一定時(shí)，你定的C越大，對(duì)目標(biāo)函數(shù)的損失也越大，此時(shí)就暗示著你非常不愿意放棄這些離群點(diǎn)，最極端的情況是你把C定為無(wú)限大，這樣只要稍有一個(gè)點(diǎn)離群，目標(biāo)函數(shù)的值馬上變成無(wú)限大，馬上讓問(wèn)題變成無(wú)解，這就退化成了硬間隔問(wèn)題。

四是懲罰因子C不是一個(gè)變量，整個(gè)優(yōu)化問(wèn)題在解的時(shí)候，C是一個(gè)你必須事先指定的值，指定這個(gè)值以后，解一下，得到一個(gè)分類(lèi)器，然后用測(cè)試數(shù)據(jù)看看結(jié)果怎么樣，如果不夠好，換一個(gè)C的值，再解一次優(yōu)化問(wèn)題，得到另一個(gè)分類(lèi)器，再看看效果，如此就是一個(gè)參數(shù)尋優(yōu)的過(guò)程，但這和優(yōu)化問(wèn)題本身決不是一回事，優(yōu)化問(wèn)題在解的過(guò)程中，C一直是定值，要記住。

五是盡管加了松弛變量這么一說(shuō)，但這個(gè)優(yōu)化問(wèn)題仍然是一個(gè)優(yōu)化問(wèn)題（汗，這不廢話么），解它的過(guò)程比起原始的硬間隔問(wèn)題來(lái)說(shuō)，沒(méi)有任何更加特殊的地方。

從大的方面說(shuō)優(yōu)化問(wèn)題解的過(guò)程，就是先試著確定一下w，也就是確定了前面圖中的三條直線，這時(shí)看看間隔有多大，又有多少點(diǎn)離群，把目標(biāo)函數(shù)的值算一算，再換一組三條直線（你可以看到，分類(lèi)的直線位置如果移動(dòng)了，有些原來(lái)離群的點(diǎn)會(huì)變得不再離群，而有的本來(lái)不離群的點(diǎn)會(huì)變成離群點(diǎn)），再把目標(biāo)函數(shù)的值算一算，如此往復(fù)（迭代），直到最終找到目標(biāo)函數(shù)最小時(shí)的w。

啰嗦了這么多，讀者一定可以馬上自己總結(jié)出來(lái)，松弛變量也就是個(gè)解決線性不可分問(wèn)題的方法罷了，但是回想一下，核函數(shù)的引入不也是為了解決線性不可分的問(wèn)題么？為什么要為了一個(gè)問(wèn)題使用兩種方法呢？

其實(shí)兩者還有微妙的不同。一般的過(guò)程應(yīng)該是這樣，還以文本分類(lèi)為例。在原始的低維空間中，樣本相當(dāng)?shù)牟豢煞?，無(wú)論你怎么找分類(lèi)平面，總會(huì)有大量的離群點(diǎn)，此時(shí)用核函數(shù)向高維空間映射一下，雖然結(jié)果仍然是不可分的，但比原始空間里的要更加接近線性可分的狀態(tài)（就是達(dá)到了近似線性可分的狀態(tài)），此時(shí)再用松弛變量處理那些少數(shù)“冥頑不化”的離群點(diǎn)，就簡(jiǎn)單有效得多啦。

本節(jié)中的（式1）也確實(shí)是支持向量機(jī)最最常用的形式。至此一個(gè)比較完整的支持向量機(jī)框架就有了，簡(jiǎn)單說(shuō)來(lái)，支持向量機(jī)就是使用了核函數(shù)的軟間隔線性分類(lèi)法。

下一節(jié)會(huì)說(shuō)說(shuō)松弛變量剩下的一點(diǎn)點(diǎn)東西，順便搞個(gè)讀者調(diào)查，看看大家還想侃侃SVM的哪些方面。

接下來(lái)要說(shuō)的東西其實(shí)不是松弛變量本身，但由于是為了使用松弛變量才引入的，因此放在這里也算合適，那就是懲罰因子C。回頭看一眼引入了松弛變量以后的優(yōu)化問(wèn)題：

注意其中C的位置，也可以回想一下C所起的作用（表征你有多么重視離群點(diǎn)，C越大越重視，越不想丟掉它們）。這個(gè)式子是以前做SVM的人寫(xiě)的，大家也就這么用，但沒(méi)有任何規(guī)定說(shuō)必須對(duì)所有的松弛變量都使用同一個(gè)懲罰因子，我們完全可以給每一個(gè)離群點(diǎn)都使用不同的C，這時(shí)就意味著你對(duì)每個(gè)樣本的重視程度都不一樣，有些樣本丟了也就丟了，錯(cuò)了也就錯(cuò)了，這些就給一個(gè)比較小的C；而有些樣本很重要，決不能分類(lèi)錯(cuò)誤（比如中央下達(dá)的文件啥的，笑），就給一個(gè)很大的C。

當(dāng)然實(shí)際使用的時(shí)候并沒(méi)有這么極端，但一種很常用的變形可以用來(lái)解決分類(lèi)問(wèn)題中樣本的“偏斜”問(wèn)題。

先來(lái)說(shuō)說(shuō)樣本的偏斜問(wèn)題，也叫數(shù)據(jù)集偏斜（unbalanced），它指的是參與分類(lèi)的兩個(gè)類(lèi)別（也可以指多個(gè)類(lèi)別）樣本數(shù)量差異很大。比如說(shuō)正類(lèi)有10，000個(gè)樣本，而負(fù)類(lèi)只給了100個(gè)，這會(huì)引起的問(wèn)題顯而易見(jiàn)，可以看看下面的圖：

方形的點(diǎn)是負(fù)類(lèi)。H，H₁，H₂是根據(jù)給的樣本算出來(lái)的分類(lèi)面，由于負(fù)類(lèi)的樣本很少很少，所以有一些本來(lái)是負(fù)類(lèi)的樣本點(diǎn)沒(méi)有提供，比如圖中兩個(gè)灰色的方形點(diǎn)，如果這兩個(gè)點(diǎn)有提供的話，那算出來(lái)的分類(lèi)面應(yīng)該是H’，H₂’和H₁，他們顯然和之前的結(jié)果有出入，實(shí)際上負(fù)類(lèi)給的樣本點(diǎn)越多，就越容易出現(xiàn)在灰色點(diǎn)附近的點(diǎn)，我們算出的結(jié)果也就越接近于真實(shí)的分類(lèi)面。但現(xiàn)在由于偏斜的現(xiàn)象存在，使得數(shù)量多的正類(lèi)可以把分類(lèi)面向負(fù)類(lèi)的方向“推”，因而影響了結(jié)果的準(zhǔn)確性。

對(duì)付數(shù)據(jù)集偏斜問(wèn)題的方法之一就是在懲罰因子上作文章，想必大家也猜到了，那就是給樣本數(shù)量少的負(fù)類(lèi)更大的懲罰因子，表示我們重視這部分樣本（本來(lái)數(shù)量就少，再拋棄一些，那人家負(fù)類(lèi)還活不活了），因此我們的目標(biāo)函數(shù)中因松弛變量而損失的部分就變成了：

其中i=1…p都是正樣本，j=p+1…p+q都是負(fù)樣本。libSVM這個(gè)算法包在解決偏斜問(wèn)題的時(shí)候用的就是這種方法。

那C₊和C_-怎么確定呢？它們的大小是試出來(lái)的（參數(shù)調(diào)優(yōu)），但是他們的比例可以有些方法來(lái)確定。咱們先假定說(shuō)C₊是5這么大，那確定C_-的一個(gè)很直觀的方法就是使用兩類(lèi)樣本數(shù)的比來(lái)算，對(duì)應(yīng)到剛才舉的例子，C_-就可以定為500這么大（因?yàn)?0，000：100=100：1嘛）。

但是這樣并不夠好，回看剛才的圖，你會(huì)發(fā)現(xiàn)正類(lèi)之所以可以“欺負(fù)”負(fù)類(lèi)，其實(shí)并不是因?yàn)樨?fù)類(lèi)樣本少，真實(shí)的原因是負(fù)類(lèi)的樣本分布的不夠廣（沒(méi)擴(kuò)充到負(fù)類(lèi)本應(yīng)該有的區(qū)域）。說(shuō)一個(gè)具體點(diǎn)的例子，現(xiàn)在想給政治類(lèi)和體育類(lèi)的文章做分類(lèi)，政治類(lèi)文章很多，而體育類(lèi)只提供了幾篇關(guān)于籃球的文章，這時(shí)分類(lèi)會(huì)明顯偏向于政治類(lèi)，如果要給體育類(lèi)文章增加樣本，但增加的樣本仍然全都是關(guān)于籃球的（也就是說(shuō)，沒(méi)有足球，排球，賽車(chē)，游泳等等），那結(jié)果會(huì)怎樣呢？雖然體育類(lèi)文章在數(shù)量上可以達(dá)到與政治類(lèi)一樣多，但過(guò)于集中了，結(jié)果仍會(huì)偏向于政治類(lèi)！所以給C₊和C_-確定比例更好的方法應(yīng)該是衡量他們分布的程度。比如可以算算他們?cè)诳臻g中占據(jù)了多大的體積，例如給負(fù)類(lèi)找一個(gè)超球——就是高維空間里的球啦——它可以包含所有負(fù)類(lèi)的樣本，再給正類(lèi)找一個(gè)，比比兩個(gè)球的半徑，就可以大致確定分布的情況。顯然半徑大的分布就比較廣，就給小一點(diǎn)的懲罰因子。

但是這樣還不夠好，因?yàn)橛械念?lèi)別樣本確實(shí)很集中，這不是提供的樣本數(shù)量多少的問(wèn)題，這是類(lèi)別本身的特征（就是某些話題涉及的面很窄，例如計(jì)算機(jī)類(lèi)的文章就明顯不如文化類(lèi)的文章那么“天馬行空”），這個(gè)時(shí)候即便超球的半徑差異很大，也不應(yīng)該賦予兩個(gè)類(lèi)別不同的懲罰因子。

看到這里讀者一定瘋了，因?yàn)檎f(shuō)來(lái)說(shuō)去，這豈不成了一個(gè)解決不了的問(wèn)題？然而事實(shí)如此，完全的方法是沒(méi)有的，根據(jù)需要，選擇實(shí)現(xiàn)簡(jiǎn)單又合用的就好（例如libSVM就直接使用樣本數(shù)量的比）。