（一）SVM的八股簡介

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

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

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

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

結(jié)構(gòu)風險最小聽上去文縐縐，其實說的也無非是下面這回事。

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

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

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

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

泛化誤差界的公式為：

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

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

SVM正是這樣一種努力最小化結(jié)構(gòu)風險的算法。

SVM其他的特點就比較容易理解了。

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

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

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

下一節(jié)開始正式討論SVM。別嫌我說得太詳細哦。