（一）SVM的八股簡(jiǎn)介

支持向量機(Support Vector Machine)是Cortes和Vapnik于1995年首先提出的，它在解決小樣本、非線(xiàn)性及高維模式識別中表現出許多特有的優(yōu)勢，并能夠推廣應用到函數擬合等其他機器學(xué)習問(wèn)題中[10]。
支持向量機方法是建立在統計學(xué)習理論的VC 維理論和結構風(fēng)險最小原理基礎上的，根據有限的樣本信息在模型的復雜性（即對特定訓練樣本的學(xué)習精度，Accuracy）和學(xué)習能力（即無(wú)錯誤地識別任意樣本的能力）之間尋求最佳折衷，以期獲得最好的推廣能力[14]（或稱(chēng)泛化能力）。

以上是經(jīng)常被有關(guān)SVM 的學(xué)術(shù)文獻引用的介紹，有點(diǎn)八股，我來(lái)逐一分解并解釋一下。

Vapnik是統計機器學(xué)習的大牛，這想必都不用說(shuō)，他出版的《Statistical Learning Theory》是一本完整闡述統計機器學(xué)習思想的名著(zhù)。在該書(shū)中詳細的論證了統計機器學(xué)習之所以區別于傳統機器學(xué)習的本質(zhì)，就在于統計機器學(xué)習能夠精確的給出學(xué)習效果，能夠解答需要的樣本數等等一系列問(wèn)題。與統計機器學(xué)習的精密思維相比，傳統的機器學(xué)習基本上屬于摸著(zhù)石頭過(guò)河，用傳統的機器學(xué)習方法構造分類(lèi)系統完全成了一種技巧，一個(gè)人做的結果可能很好，另一個(gè)人差不多的方法做出來(lái)卻很差，缺乏指導和原則。

所謂VC維是對函數類(lèi)的一種度量，可以簡(jiǎn)單的理解為問(wèn)題的復雜程度，VC維越高，一個(gè)問(wèn)題就越復雜。正是因為SVM關(guān)注的是VC維，后面我們可以看到，SVM解決問(wèn)題的時(shí)候，和樣本的維數是無(wú)關(guān)的（甚至樣本是上萬(wàn)維的都可以，這使得SVM很適合用來(lái)解決文本分類(lèi)的問(wèn)題，當然，有這樣的能力也因為引入了核函數）。

結構風(fēng)險最小聽(tīng)上去文縐縐，其實(shí)說(shuō)的也無(wú)非是下面這回事。

機器學(xué)習本質(zhì)上就是一種對問(wèn)題真實(shí)模型的逼近（我們選擇一個(gè)我們認為比較好的近似模型，這個(gè)近似模型就叫做一個(gè)假設），但毫無(wú)疑問(wèn)，真實(shí)模型一定是不知道的（如果知道了，我們干嗎還要機器學(xué)習？直接用真實(shí)模型解決問(wèn)題不就可以了？對吧，哈哈）既然真實(shí)模型不知道，那么我們選擇的假設與問(wèn)題真實(shí)解之間究竟有多大差距，我們就沒(méi)法得知。比如說(shuō)我們認為宇宙誕生于150億年前的一場(chǎng)大爆炸，這個(gè)假設能夠描述很多我們觀(guān)察到的現象，但它與真實(shí)的宇宙模型之間還相差多少？誰(shuí)也說(shuō)不清，因為我們壓根就不知道真實(shí)的宇宙模型到底是什么。

這個(gè)與問(wèn)題真實(shí)解之間的誤差，就叫做風(fēng)險（更嚴格的說(shuō)，誤差的累積叫做風(fēng)險）。我們選擇了一個(gè)假設之后（更直觀(guān)點(diǎn)說(shuō)，我們得到了一個(gè)分類(lèi)器以后），真實(shí)誤差無(wú)從得知，但我們可以用某些可以掌握的量來(lái)逼近它。最直觀(guān)的想法就是使用分類(lèi)器在樣本數據上的分類(lèi)的結果與真實(shí)結果（因為樣本是已經(jīng)標注過(guò)的數據，是準確的數據）之間的差值來(lái)表示。這個(gè)差值叫做經(jīng)驗風(fēng)險R_emp(w)。以前的機器學(xué)習方法都把經(jīng)驗風(fēng)險最小化作為努力的目標，但后來(lái)發(fā)現很多分類(lèi)函數能夠在樣本集上輕易達到100%的正確率，在真實(shí)分類(lèi)時(shí)卻一塌糊涂（即所謂的推廣能力差，或泛化能力差）。此時(shí)的情況便是選擇了一個(gè)足夠復雜的分類(lèi)函數（它的VC維很高），能夠精確的記住每一個(gè)樣本，但對樣本之外的數據一律分類(lèi)錯誤?；仡^看看經(jīng)驗風(fēng)險最小化原則我們就會(huì )發(fā)現，此原則適用的大前提是經(jīng)驗風(fēng)險要確實(shí)能夠逼近真實(shí)風(fēng)險才行（行話(huà)叫一致），但實(shí)際上能逼近么？答案是不能，因為樣本數相對于現實(shí)世界要分類(lèi)的文本數來(lái)說(shuō)簡(jiǎn)直九牛一毛，經(jīng)驗風(fēng)險最小化原則只在這占很小比例的樣本上做到?jīng)]有誤差，當然不能保證在更大比例的真實(shí)文本上也沒(méi)有誤差。

統計學(xué)習因此而引入了泛化誤差界的概念，就是指真實(shí)風(fēng)險應該由兩部分內容刻畫(huà)，一是經(jīng)驗風(fēng)險，代表了分類(lèi)器在給定樣本上的誤差；二是置信風(fēng)險，代表了我們在多大程度上可以信任分類(lèi)器在未知文本上分類(lèi)的結果。很顯然，第二部分是沒(méi)有辦法精確計算的，因此只能給出一個(gè)估計的區間，也使得整個(gè)誤差只能計算上界，而無(wú)法計算準確的值（所以叫做泛化誤差界，而不叫泛化誤差）。

置信風(fēng)險與兩個(gè)量有關(guān)，一是樣本數量，顯然給定的樣本數量越大，我們的學(xué)習結果越有可能正確，此時(shí)置信風(fēng)險越??；二是分類(lèi)函數的VC維，顯然VC維越大，推廣能力越差，置信風(fēng)險會(huì )變大。

泛化誤差界的公式為：

R(w)≤R_emp(w)+Ф(n/h)

公式中R(w)就是真實(shí)風(fēng)險，R_emp(w)就是經(jīng)驗風(fēng)險，Ф(n/h)就是置信風(fēng)險。統計學(xué)習的目標從經(jīng)驗風(fēng)險最小化變?yōu)榱藢で蠼?jīng)驗風(fēng)險與置信風(fēng)險的和最小，即結構風(fēng)險最小。

SVM正是這樣一種努力最小化結構風(fēng)險的算法。

SVM其他的特點(diǎn)就比較容易理解了。

小樣本，并不是說(shuō)樣本的絕對數量少（實(shí)際上，對任何算法來(lái)說(shuō)，更多的樣本幾乎總是能帶來(lái)更好的效果），而是說(shuō)與問(wèn)題的復雜度比起來(lái)，SVM算法要求的樣本數是相對比較少的。

非線(xiàn)性，是指SVM擅長(cháng)應付樣本數據線(xiàn)性不可分的情況，主要通過(guò)松弛變量（也有人叫懲罰變量）和核函數技術(shù)來(lái)實(shí)現，這一部分是SVM的精髓，以后會(huì )詳細討論。多說(shuō)一句，關(guān)于文本分類(lèi)這個(gè)問(wèn)題究竟是不是線(xiàn)性可分的，尚沒(méi)有定論，因此不能簡(jiǎn)單的認為它是線(xiàn)性可分的而作簡(jiǎn)化處理，在水落石出之前，只好先當它是線(xiàn)性不可分的（反正線(xiàn)性可分也不過(guò)是線(xiàn)性不可分的一種特例而已，我們向來(lái)不怕方法過(guò)于通用）。

高維模式識別是指樣本維數很高，例如文本的向量表示，如果沒(méi)有經(jīng)過(guò)另一系列文章（《文本分類(lèi)入門(mén)》）中提到過(guò)的降維處理，出現幾萬(wàn)維的情況很正常，其他算法基本就沒(méi)有能力應付了，SVM卻可以，主要是因為SVM 產(chǎn)生的分類(lèi)器很簡(jiǎn)潔，用到的樣本信息很少（僅僅用到那些稱(chēng)之為“支持向量”的樣本，此為后話(huà)），使得即使樣本維數很高，也不會(huì )給存儲和計算帶來(lái)大麻煩（相對照而言，kNN算法在分類(lèi)時(shí)就要用到所有樣本，樣本數巨大，每個(gè)樣本維數再一高，這日子就沒(méi)法過(guò)了……）。

下一節開(kāi)始正式討論SVM。別嫌我說(shuō)得太詳細哦。