1. 講講SVM
1.1 一個(gè)關(guān)于SVM的童話故事
支持向量機(jī)(Support Vector Machine,SVM)是眾多監(jiān)督學(xué)習(xí)方法中十分出色的一種,幾乎所有講述經(jīng)典機(jī)器學(xué)習(xí)方法的教材都會(huì)介紹。關(guān)于SVM,流傳著一個(gè)關(guān)于天使與魔鬼的故事。
傳說(shuō)魔鬼和天使玩了一個(gè)游戲,魔鬼在桌上放了兩種顏色的球。魔鬼讓天使用一根木棍將它們分開(kāi)。這對(duì)天使來(lái)說(shuō),似乎太容易了。天使不假思索地一擺,便完成了任務(wù)。魔鬼又加入了更多的球。隨著球的增多,似乎有的球不能再被原來(lái)的木棍正確分開(kāi),如下圖所示。

SVM實(shí)際上是在為天使找到木棒的最佳放置位置,使得兩邊的球都離分隔它們的木棒足夠遠(yuǎn)。依照SVM為天使選擇的木棒位置,魔鬼即使按剛才的方式繼續(xù)加入新球,木棒也能很好地將兩類(lèi)不同的球分開(kāi)。
看到天使已經(jīng)很好地解決了用木棒線性分球的問(wèn)題,魔鬼又給了天使一個(gè)新的挑戰(zhàn),如下圖所示。

按照這種球的擺法,世界上貌似沒(méi)有一根木棒可以將它們 完美分開(kāi)。但天使畢竟有法力,他一拍桌子,便讓這些球飛到了空中,然后憑借 念力抓起一張紙片,插在了兩類(lèi)球的中間。從魔鬼的角度看這些 球,則像是被一條曲線完美的切開(kāi)了。

后來(lái),“無(wú)聊”的科學(xué)家們把這些球稱為“數(shù)據(jù)”,把木棍稱為“分類(lèi)面”,找到最 大間隔的木棒位置的過(guò)程稱為“優(yōu)化”,拍桌子讓球飛到空中的念力叫“核映射”,在 空中分隔球的紙片稱為“分類(lèi)超平面”。這便是SVM的童話故事。
1.2 理解SVM:第一層
支持向量機(jī),因其英文名為support vector machine,故一般簡(jiǎn)稱SVM,通俗來(lái)講,它是一種二類(lèi)分類(lèi)模型,其基本模型定義為特征空間上的間隔最大的線性分類(lèi)器,其學(xué)習(xí)策略便是間隔最大化,最終可轉(zhuǎn)化為一個(gè)凸二次規(guī)劃問(wèn)題的求解。
線性分類(lèi)器:給定一些數(shù)據(jù)點(diǎn),它們分別屬于兩個(gè)不同的類(lèi),現(xiàn)在要找到一個(gè)線性分類(lèi)器把這些數(shù)據(jù)分成兩類(lèi)。如果用x表示數(shù)據(jù)點(diǎn),用y表示類(lèi)別(y可以取1或者0,分別代表兩個(gè)不同的類(lèi)),一個(gè)線性分類(lèi)器的學(xué)習(xí)目標(biāo)便是要在n維的數(shù)據(jù)空間中找到一個(gè)超平面(hyper plane),這個(gè)超平面的方程可以表示為( wT中的T代表轉(zhuǎn)置):
這里可以查看我之前的邏輯回歸章節(jié)回顧:點(diǎn)擊打開(kāi)
這個(gè)超平面可以用分類(lèi)函數(shù) 表示,當(dāng)f(x) 等于0的時(shí)候,x便是位于超平面上的點(diǎn),而f(x)大于0的點(diǎn)對(duì)應(yīng) y=1 的數(shù)據(jù)點(diǎn),f(x)小于0的點(diǎn)對(duì)應(yīng)y=-1的點(diǎn),如下圖所示:

1.2.1 函數(shù)間隔與幾何間隔
在超平面wx+b=0確定的情況下,|wx+b|能夠表示點(diǎn)x到距離超平面的遠(yuǎn)近,而通過(guò)觀察wx+b的符號(hào)與類(lèi)標(biāo)記y的符號(hào)是否一致可判斷分類(lèi)是否正確,所以,可以用(y(wx+b))的正負(fù)性來(lái)判定或表示分類(lèi)的正確性。于此,我們便引出了函數(shù)間隔*(functional margin)的概念。
函數(shù)間隔公式:
而超平面(w,b)關(guān)于數(shù)據(jù)集T中所有樣本點(diǎn)(xi,yi)的函數(shù)間隔最小值(其中,x是特征,y是結(jié)果標(biāo)簽,i表示第i個(gè)樣本),便為超平面(w, b)關(guān)于訓(xùn)練數(shù)據(jù)集T的函數(shù)間隔:
但這樣定義的函數(shù)間隔有問(wèn)題,即如果成比例的改變w和b(如將它們改成2w和2b),則函數(shù)間隔的值f(x)卻變成了原來(lái)的2倍(雖然此時(shí)超平面沒(méi)有改變),所以只有函數(shù)間隔還遠(yuǎn)遠(yuǎn)不夠。
幾何間隔
事實(shí)上,我們可以對(duì)法向量w加些約束條件,從而引出真正定義點(diǎn)到超平面的距離--幾何間隔(geometrical margin)的概念。假定對(duì)于一個(gè)點(diǎn) x ,令其垂直投影到超平面上的對(duì)應(yīng)點(diǎn)為 x0 ,w 是垂直于超平面的一個(gè)向量,為樣本x到超平面的距離,如下圖所示:

這里我直接給出幾何間隔的公式,詳細(xì)推到請(qǐng)查看博文:點(diǎn)擊進(jìn)入
幾何間隔:
從上述函數(shù)間隔和幾何間隔的定義可以看出:幾何間隔就是函數(shù)間隔除以||w||,而且函數(shù)間隔y(wx+b) = yf(x)實(shí)際上就是|f(x)|,只是人為定義的一個(gè)間隔度量,而幾何間隔|f(x)|/||w||才是直觀上的點(diǎn)到超平面的距離。
1.2.2 最大間隔分類(lèi)器的定義
對(duì)一個(gè)數(shù)據(jù)點(diǎn)進(jìn)行分類(lèi),當(dāng)超平面離數(shù)據(jù)點(diǎn)的“間隔”越大,分類(lèi)的確信度(confidence)也越大。所以,為了使得分類(lèi)的確信度盡量高,需要讓所選擇的超平面能夠最大化這個(gè)“間隔”值。這個(gè)間隔就是下圖中的Gap的一半。

通過(guò)由前面的分析可知:函數(shù)間隔不適合用來(lái)最大化間隔值,因?yàn)樵诔矫婀潭ㄒ院螅梢缘缺壤乜s放w的長(zhǎng)度和b的值,這樣可以使得 的值任意大,亦即函數(shù)間隔可以在超平面保持不變的情況下被取得任意大。但幾何間隔因?yàn)槌狭?,使得在縮放w和b的時(shí)候幾何間隔的值是不會(huì)改變的,它只隨著超平面的變動(dòng)而變動(dòng),因此,這是更加合適的一個(gè)間隔。換言之,這里要找的最大間隔分類(lèi)超平面中的“間隔”指的是幾何間隔。
如下圖所示,中間的實(shí)線便是尋找到的最優(yōu)超平面(Optimal Hyper Plane),其到兩條虛線邊界的距離相等,這個(gè)距離便是幾何間隔,兩條虛線間隔邊界之間的距離等于2倍幾何間隔,而虛線間隔邊界上的點(diǎn)則是支持向量。由于這些支持向量剛好在虛線間隔邊界上,所以它們滿足,對(duì)于所有不是支持向量的點(diǎn),則顯然有
。

OK,到此為止,算是了解到了SVM的第一層,對(duì)于那些只關(guān)心怎么用SVM的朋友便已足夠,不必再更進(jìn)一層深究其更深的原理。
1.2.3 最大間隔損失函數(shù)Hinge loss
SVM 求解使通過(guò)建立二次規(guī)劃原始問(wèn)題,引入拉格朗日乘子法,然后轉(zhuǎn)換成對(duì)偶的形式去求解,這是一種理論非常充實(shí)的解法。這里換一種角度來(lái)思考,在機(jī)器學(xué)習(xí)領(lǐng)域,一般的做法是經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化 (empirical risk minimization,ERM),即構(gòu)建假設(shè)函數(shù)(Hypothesis)為輸入輸出間的映射,然后采用損失函數(shù)來(lái)衡量模型的優(yōu)劣。求得使損失最小化的模型即為最優(yōu)的假設(shè)函數(shù),采用不同的損失函數(shù)也會(huì)得到不同的機(jī)器學(xué)習(xí)算法。SVM采用的就是Hinge Loss,用于“最大間隔(max-margin)”分類(lèi)。
- 對(duì)于訓(xùn)練集中的第i個(gè)數(shù)據(jù)xi
- 在W下會(huì)有一個(gè)得分結(jié)果向量f(xi,W)
- 第j類(lèi)的得分為我們記作f(xi,W)j
要理解這個(gè)公式,首先先看下面這張圖片:

- 在生活中我們都會(huì)認(rèn)為沒(méi)有威脅的才是最好的,比如拿成績(jī)來(lái)說(shuō),自己考了第一名99分,而第二名緊隨其后98分,那么就會(huì)有不安全的感覺(jué),就會(huì)認(rèn)為那家伙隨時(shí)都有可能超過(guò)我。如果第二名是85分,那就會(huì)感覺(jué)安全多了,第二名需要花費(fèi)很大的力氣才能趕上自己。拿這個(gè)例子套到上面這幅圖也是一樣的。
- 上面這幅圖delta左邊的紅點(diǎn)是一個(gè)安全警戒線,什么意思呢?也就是說(shuō)預(yù)測(cè)錯(cuò)誤得分超過(guò)這個(gè)安全警戒線就會(huì)得到一個(gè)懲罰權(quán)重,讓這個(gè)預(yù)測(cè)錯(cuò)誤值退回到安全警戒線以外,這樣才能夠保證預(yù)測(cè)正確的結(jié)果具有唯一性。
- 對(duì)應(yīng)到公式中,
就是錯(cuò)誤分類(lèi)的得分。后面一項(xiàng)就是 正確得分 - delta = 安全警戒線值,兩項(xiàng)的差代表的就是懲罰權(quán)重,越接近正確得分,權(quán)重越大。當(dāng)錯(cuò)誤得分在警戒線以外時(shí),兩項(xiàng)相減得到負(fù)數(shù),那么損失函數(shù)的最大值是0,也就是沒(méi)有損失。
- 一直往復(fù)循環(huán)訓(xùn)練數(shù)據(jù),直到最小化損失函數(shù)為止,也就找到了分類(lèi)超平面。
1.3 深入SVM:第二層
1.3.1 從線性可分到線性不可分
接著考慮之前得到的目標(biāo)函數(shù)(令函數(shù)間隔=1):
轉(zhuǎn)換為對(duì)偶問(wèn)題,解釋一下什么是對(duì)偶問(wèn)題,對(duì)偶問(wèn)題是實(shí)質(zhì)相同但從不同角度提出不同提法的一對(duì)問(wèn)題。
由于求 的最大值相當(dāng)于求
的最小值,所以上述目標(biāo)函數(shù)等價(jià)于(w由分母變成分子,從而也有原來(lái)的max問(wèn)題變?yōu)閙in問(wèn)題,很明顯,兩者問(wèn)題等價(jià)):
因?yàn)楝F(xiàn)在的目標(biāo)函數(shù)是二次的,約束條件是線性的,所以它是一個(gè)凸二次規(guī)劃問(wèn)題。這個(gè)問(wèn)題可以用現(xiàn)成的QP (Quadratic Programming) 優(yōu)化包進(jìn)行求解。一言以蔽之:在一定的約束條件下,目標(biāo)最優(yōu),損失最小。
此外,由于這個(gè)問(wèn)題的特殊結(jié)構(gòu),還可以通過(guò)拉格朗日對(duì)偶性(Lagrange Duality)變換到對(duì)偶變量 (dual variable) 的優(yōu)化問(wèn)題,即通過(guò)求解與原問(wèn)題等價(jià)的對(duì)偶問(wèn)題(dual problem)得到原始問(wèn)題的最優(yōu)解,這就是線性可分條件下支持向量機(jī)的對(duì)偶算法,這樣做的優(yōu)點(diǎn)在于:一者對(duì)偶問(wèn)題往往更容易求解;二者可以自然的引入核函數(shù),進(jìn)而推廣到非線性分類(lèi)問(wèn)題。
詳細(xì)過(guò)程請(qǐng)參考文章末尾給出的參考鏈接。
1.3.2 核函數(shù)Kernel
事實(shí)上,大部分時(shí)候數(shù)據(jù)并不是線性可分的,這個(gè)時(shí)候滿足這樣條件的超平面就根本不存在。在上文中,我們已經(jīng)了解到了SVM處理線性可分的情況,那對(duì)于非線性的數(shù)據(jù)SVM咋處理呢?對(duì)于非線性的情況,SVM 的處理方法是選擇一個(gè)核函數(shù) κ(?,?) ,通過(guò)將數(shù)據(jù)映射到高維空間,來(lái)解決在原始空間中線性不可分的問(wèn)題。
具體來(lái)說(shuō),在線性不可分的情況下,支持向量機(jī)首先在低維空間中完成計(jì)算,然后通過(guò)核函數(shù)將輸入空間映射到高維特征空間,最終在高維特征空間中構(gòu)造出最優(yōu)分離超平面,從而把平面上本身不好分的非線性數(shù)據(jù)分開(kāi)。如圖所示,一堆數(shù)據(jù)在二維空間無(wú)法劃分,從而映射到三維空間里劃分:


通常人們會(huì)從一些常用的核函數(shù)中選擇(根據(jù)問(wèn)題和數(shù)據(jù)的不同,選擇不同的參數(shù),實(shí)際上就是得到了不同的核函數(shù)),例如:多項(xiàng)式核、高斯核、線性核。
讀者可能還是沒(méi)明白核函數(shù)到底是個(gè)什么東西?我再簡(jiǎn)要概括下,即以下三點(diǎn):
- 實(shí)際中,我們會(huì)經(jīng)常遇到線性不可分的樣例,此時(shí),我們的常用做法是把樣例特征映射到高維空間中去(映射到高維空間后,相關(guān)特征便被分開(kāi)了,也就達(dá)到了分類(lèi)的目的);
- 但進(jìn)一步,如果凡是遇到線性不可分的樣例,一律映射到高維空間,那么這個(gè)維度大小是會(huì)高到可怕的。那咋辦呢?
- 此時(shí),核函數(shù)就隆重登場(chǎng)了,核函數(shù)的價(jià)值在于它雖然也是將特征進(jìn)行從低維到高維的轉(zhuǎn)換,但核函數(shù)絕就絕在它事先在低維上進(jìn)行計(jì)算,而將實(shí)質(zhì)上的分類(lèi)效果表現(xiàn)在了高維上,避免了直接在高維空間中的復(fù)雜計(jì)算。
如果數(shù)據(jù)中出現(xiàn)了離群點(diǎn)outliers,那么就可以使用松弛變量來(lái)解決。
1.3.3 總結(jié)
不準(zhǔn)確的說(shuō),SVM它本質(zhì)上即是一個(gè)分類(lèi)方法,用 w^T+b 定義分類(lèi)函數(shù),于是求w、b,為尋最大間隔,引出1/2||w||^2,繼而引入拉格朗日因子,化為對(duì)拉格朗日乘子a的求解(求解過(guò)程中會(huì)涉及到一系列最優(yōu)化或凸二次規(guī)劃等問(wèn)題),如此,求w.b與求a等價(jià),而a的求解可以用一種快速學(xué)習(xí)算法SMO,至于核函數(shù),是為處理非線性情況,若直接映射到高維計(jì)算恐維度爆炸,故在低維計(jì)算,等效高維表現(xiàn)。
OK,理解到這第二層,已經(jīng)能滿足絕大部分人一窺SVM原理的好奇心,針對(duì)于面試來(lái)說(shuō)已經(jīng)足夠了。
1.4 SVM的應(yīng)用
SVM在很多諸如文本分類(lèi),圖像分類(lèi),生物序列分析和生物數(shù)據(jù)挖掘,手寫(xiě)字符識(shí)別等領(lǐng)域有很多的應(yīng)用,但或許你并沒(méi)強(qiáng)烈的意識(shí)到,SVM可以成功應(yīng)用的領(lǐng)域遠(yuǎn)遠(yuǎn)超出現(xiàn)在已經(jīng)在開(kāi)發(fā)應(yīng)用了的領(lǐng)域。
2. SVM的一些問(wèn)題
-
是否存在一組參數(shù)使SVM訓(xùn)練誤差為0?
答:存在
-
訓(xùn)練誤差為0的SVM分類(lèi)器一定存在嗎?
答:一定存在
-
加入松弛變量的SVM的訓(xùn)練誤差可以為0嗎?
答:使用SMO算法訓(xùn)練的線性分類(lèi)器并不一定能得到訓(xùn)練誤差為0的模型。這是由 于我們的優(yōu)化目標(biāo)改變了,并不再是使訓(xùn)練誤差最小。
-
**帶核的SVM為什么能分類(lèi)非線性問(wèn)題? **
答:核函數(shù)的本質(zhì)是兩個(gè)函數(shù)的內(nèi)積,通過(guò)核函數(shù)將其隱射到高維空間,在高維空間非線性問(wèn)題轉(zhuǎn)化為線性問(wèn)題, SVM得到超平面是高維空間的線性分類(lèi)平面。其分類(lèi)結(jié)果也視為低維空間的非線性分類(lèi)結(jié)果, 因而帶核的SVM就能分類(lèi)非線性問(wèn)題。
-
如何選擇核函數(shù)?
- 如果特征的數(shù)量大到和樣本數(shù)量差不多,則選用LR或者線性核的SVM;
- 如果特征的數(shù)量小,樣本的數(shù)量正常,則選用SVM+高斯核函數(shù);
- 如果特征的數(shù)量小,而樣本的數(shù)量很大,則需要手工添加一些特征從而變成第一種情況。
3. LR和SVM的聯(lián)系與區(qū)別
3.1 相同點(diǎn)
- 都是線性分類(lèi)器。本質(zhì)上都是求一個(gè)最佳分類(lèi)超平面。
- 都是監(jiān)督學(xué)習(xí)算法。
- 都是判別模型。判別模型不關(guān)心數(shù)據(jù)是怎么生成的,它只關(guān)心信號(hào)之間的差別,然后用差別來(lái)簡(jiǎn)單對(duì)給定的一個(gè)信號(hào)進(jìn)行分類(lèi)。常見(jiàn)的判別模型有:KNN、SVM、LR,常見(jiàn)的生成模型有:樸素貝葉斯,隱馬爾可夫模型。
3.2 不同點(diǎn)
- LR是參數(shù)模型,svm是非參數(shù)模型,linear和rbf則是針對(duì)數(shù)據(jù)線性可分和不可分的區(qū)別;
- 從目標(biāo)函數(shù)來(lái)看,區(qū)別在于邏輯回歸采用的是logistical loss,SVM采用的是hinge loss,這兩個(gè)損失函數(shù)的目的都是增加對(duì)分類(lèi)影響較大的數(shù)據(jù)點(diǎn)的權(quán)重,減少與分類(lèi)關(guān)系較小的數(shù)據(jù)點(diǎn)的權(quán)重。
- SVM的處理方法是只考慮support vectors,也就是和分類(lèi)最相關(guān)的少數(shù)點(diǎn),去學(xué)習(xí)分類(lèi)器。而邏輯回歸通過(guò)非線性映射,大大減小了離分類(lèi)平面較遠(yuǎn)的點(diǎn)的權(quán)重,相對(duì)提升了與分類(lèi)最相關(guān)的數(shù)據(jù)點(diǎn)的權(quán)重。
- 邏輯回歸相對(duì)來(lái)說(shuō)模型更簡(jiǎn)單,好理解,特別是大規(guī)模線性分類(lèi)時(shí)比較方便。而SVM的理解和優(yōu)化相對(duì)來(lái)說(shuō)復(fù)雜一些,SVM轉(zhuǎn)化為對(duì)偶問(wèn)題后,分類(lèi)只需要計(jì)算與少數(shù)幾個(gè)支持向量的距離,這個(gè)在進(jìn)行復(fù)雜核函數(shù)計(jì)算時(shí)優(yōu)勢(shì)很明顯,能夠大大簡(jiǎn)化模型和計(jì)算。
- logic 能做的 svm能做,但可能在準(zhǔn)確率上有問(wèn)題,svm能做的logic有的做不了。
4. 線性分類(lèi)器與非線性分類(lèi)器的區(qū)別以及優(yōu)劣
線性和非線性是針對(duì)模型參數(shù)和輸入特征來(lái)講的;比如輸入x,模型y=ax+ax^2 那么就是非線性模型,如果輸入是x和X^2則模型是線性的。
-
線性分類(lèi)器可解釋性好,計(jì)算復(fù)雜度較低,不足之處是模型的擬合效果相對(duì)弱些。
LR,貝葉斯分類(lèi),單層感知機(jī)、線性回歸
-
非線性分類(lèi)器效果擬合能力較強(qiáng),不足之處是數(shù)據(jù)量不足容易過(guò)擬合、計(jì)算復(fù)雜度高、可解釋性不好。
決策樹(shù)、RF、GBDT、多層感知機(jī)
SVM兩種都有(看線性核還是高斯核)
5. 代碼實(shí)現(xiàn)
新聞分類(lèi) GitHub:點(diǎn)擊進(jìn)入

6. 參考文獻(xiàn)
支持向量機(jī)通俗導(dǎo)論(理解SVM的三層境界)
作者:@mantchs
GitHub:https://github.com/NLP-LOVE/ML-NLP
歡迎大家加入討論!共同完善此項(xiàng)目!群號(hào):【541954936】點(diǎn)擊進(jìn)入