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

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

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

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

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

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

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

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

統(tǒng)計(jì)學(xué)習(xí)因此而引入了泛化誤差界的概念，就是指真實(shí)風(fēng)險(xiǎn)應(yīng)該由兩部分內(nèi)容刻畫，一是經(jīng)驗(yàn)風(fēng)險(xiǎn)，代表了分類器在給定樣本上的誤差；二是置信風(fēng)險(xiǎn)，代表了我們?cè)诙啻蟪潭壬峡梢孕湃畏诸惼髟谖粗谋旧戏诸惖慕Y(jié)果。很顯然，第二部分是沒(méi)有辦法精確計(jì)算的，因此只能給出一個(gè)估計(jì)的區(qū)間，也使得整個(gè)誤差只能計(jì)算上界，而無(wú)法計(jì)算準(zhǔn)確的值（所以叫做泛化誤差界，而不叫泛化誤差）。

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

泛化誤差界的公式為：

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

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

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

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

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

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

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

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

從文本分類系統(tǒng)的處理流程來(lái)看，無(wú)論待分類的文本是中文還是英文，在訓(xùn)練階段之前都要經(jīng)過(guò)一個(gè)預(yù)處理的步驟，去除無(wú)用的信息，減少后續(xù)步驟的復(fù)雜度和計(jì)算負(fù)擔(dān)。

對(duì)中文文本來(lái)說(shuō)，首先要經(jīng)歷一個(gè)分詞的過(guò)程，就是把連續(xù)的文字流切分成一個(gè)一個(gè)單獨(dú)的詞匯（因?yàn)樵~匯將作為訓(xùn)練階段“特征”的最基本單位），例如原文是“中華人民共和國(guó)今天成立了”的文本就要被切分成“中華／人民／共和國(guó)／今天／成立／了”這樣的形式。而對(duì)英文來(lái)說(shuō)，沒(méi)有這個(gè)步驟（更嚴(yán)格的說(shuō)，并不是沒(méi)有這個(gè)步驟，而是英文只需要通過(guò)空格和標(biāo)點(diǎn)便很容易將一個(gè)一個(gè)獨(dú)立的詞從原文中區(qū)分出來(lái)）。中文分詞的效果對(duì)文本分類系統(tǒng)的表現(xiàn)影響很大，因?yàn)樵诤竺娴牧鞒讨校际褂妙A(yù)處理之后的文本信息，不再參考原始文本，因此分詞的效果不好，等同于引入了錯(cuò)誤的訓(xùn)練數(shù)據(jù)。分詞本身也是一個(gè)值得大書(shū)特書(shū)的問(wèn)題，目前比較常用的方法有詞典法，隱馬爾科夫模型和新興的CRF方法。

預(yù)處理中在分詞之后的“去停止詞”一步對(duì)兩者來(lái)說(shuō)是相同的，都是要把語(yǔ)言中一些表意能力很差的輔助性文字從原始文本中去除，對(duì)中文文本來(lái)說(shuō)，類似“我們”，“在”，“了”，“的”這樣的詞匯都會(huì)被去除，英文中的“ an”，“in”，“the”等也一樣。這一步驟會(huì)參照一個(gè)被稱為“停止詞表”的數(shù)據(jù)（里面記錄了應(yīng)該被去除的詞，有可能是以文件形式存儲(chǔ)在硬盤上，也有可能是以數(shù)據(jù)結(jié)構(gòu)形式放在內(nèi)存中）來(lái)進(jìn)行。

對(duì)中文文本來(lái)說(shuō)，到此就已初審合格，可以參加訓(xùn)練了（笑）。而英文文本還有進(jìn)一步簡(jiǎn)化和壓縮的空間。我們都知道，英文中同一個(gè)詞有所謂詞形的變化（相對(duì)的，詞義本身卻并沒(méi)有變），例如名詞有單復(fù)數(shù)的變化，動(dòng)詞有時(shí)態(tài)的變化，形容詞有比較級(jí)的變化等等，還包括這些變化形式的某種組合。而正因?yàn)樵~義本身沒(méi)有變化，僅僅詞形不同的詞就不應(yīng)該作為獨(dú)立的詞來(lái)存儲(chǔ)和和參與分類計(jì)算。去除這些詞形不同，但詞義相同的詞，僅保留一個(gè)副本的步驟就稱為“詞根還原”，例如在一篇英文文檔中，經(jīng)過(guò)詞根還原后，“computer”，“compute”，“computing”，“computational”這些詞全都被處理成“compute”（大小寫轉(zhuǎn)換也在這一步完成，當(dāng)然，還要記下這些詞的數(shù)目作為compute的詞頻信息）。

經(jīng)過(guò)預(yù)處理步驟之后，原始文檔轉(zhuǎn)換成了非常節(jié)省資源，也便于計(jì)算的形式，后面的訓(xùn)練階段大同小異（僅僅抽取出的特征不同而已，畢竟，一個(gè)是中文詞匯的集合，一個(gè)是英文詞匯的集合嘛）。

下一章節(jié)侃侃分類問(wèn)題本身的分類。

學(xué)習(xí)方法：使用樣例（或稱樣本，訓(xùn)練集）來(lái)合成計(jì)算機(jī)程序的過(guò)程稱為學(xué)習(xí)方法[22]。

監(jiān)督學(xué)習(xí)：學(xué)習(xí)過(guò)程中使用的樣例是由輸入/輸出對(duì)給出時(shí)，稱為監(jiān)督學(xué)習(xí)[22]。最典型的監(jiān)督學(xué)習(xí)例子就是文本分類問(wèn)題，訓(xùn)練集是一些已經(jīng)明確分好了類別文檔組成，文檔就是輸入，對(duì)應(yīng)的類別就是輸出。

非監(jiān)督學(xué)習(xí)：學(xué)習(xí)過(guò)程中使用的樣例不包含輸入/輸出對(duì)，學(xué)習(xí)的任務(wù)是理解數(shù)據(jù)產(chǎn)生的過(guò)程 [22]。典型的非監(jiān)督學(xué)習(xí)例子是聚類，類別的數(shù)量，名稱，事先全都沒(méi)有確定，由計(jì)算機(jī)自己觀察樣例來(lái)總結(jié)得出。

TSR（Term Space Reduction）：特征空間的壓縮，即降維，也可以叫做特征提取。包括特征選擇和特征抽取兩大類方法。

分類狀態(tài)得分（CSV，Categorization Status Value)：用于描述將文檔歸于某個(gè)類別下有多大的可信度。

準(zhǔn)確率（Precision）：在所有被判斷為正確的文檔中，有多大比例是確實(shí)正確的。

召回率（Recall）：在所有確實(shí)正確的文檔中，有多大比例被我們判為正確。

假設(shè)：計(jì)算機(jī)對(duì)訓(xùn)練集背后的真實(shí)模型（真實(shí)的分類規(guī)則）的猜測(cè)稱為假設(shè)。可以把真實(shí)的分類規(guī)則想像為一個(gè)目標(biāo)函數(shù)，我們的假設(shè)則是另一個(gè)函數(shù)，假設(shè)函數(shù)在所有的訓(xùn)練數(shù)據(jù)上都得出與真實(shí)函數(shù)相同（或足夠接近）的結(jié)果。

泛化性：一個(gè)假設(shè)能夠正確分類訓(xùn)練集之外數(shù)據(jù)（即新的，未知的數(shù)據(jù)）的能力稱為該假設(shè)的泛化性[22]。

一致假設(shè)：一個(gè)假設(shè)能夠?qū)λ杏?xùn)練數(shù)據(jù)正確分類，則稱這個(gè)假設(shè)是一致的[22]。

過(guò)擬合：為了得到一致假設(shè)而使假設(shè)變得過(guò)度復(fù)雜稱為過(guò)擬合[22]。想像某種學(xué)習(xí)算法產(chǎn)生了一個(gè)過(guò)擬合的分類器，這個(gè)分類器能夠百分之百的正確分類樣本數(shù)據(jù)（即再拿樣本中的文檔來(lái)給它，它絕對(duì)不會(huì)分錯(cuò)），但也就為了能夠?qū)颖就耆_的分類，使得它的構(gòu)造如此精細(xì)復(fù)雜，規(guī)則如此嚴(yán)格，以至于任何與樣本數(shù)據(jù)稍有不同的文檔它全都認(rèn)為不屬于這個(gè)類別！

超平面（Hyper Plane）：n維空間中的線性函數(shù)唯一確定了一個(gè)超平面。一些較直觀的例子，在二維空間中，一條直線就是一個(gè)超平面；在三維空間中，一個(gè)平面就是一個(gè)超平面。

線性可分和不可分：如果存在一個(gè)超平面能夠正確分類訓(xùn)練數(shù)據(jù)，并且這個(gè)程序保證收斂，這種情況稱為線形可分。如果這樣的超平面不存在，則稱數(shù)據(jù)是線性不可分的[22]。

正樣本和負(fù)樣本：對(duì)某個(gè)類別來(lái)說(shuō)，屬于這個(gè)類別的樣本文檔稱為正樣本；不屬于這個(gè)類別的文檔稱為負(fù)樣本。

規(guī)劃：對(duì)于目標(biāo)函數(shù)，等式或不等式約束都是線性函數(shù)的問(wèn)題稱為線性規(guī)劃問(wèn)題。對(duì)于目標(biāo)函數(shù)是二次的，而約束都是線性函數(shù)的最優(yōu)化問(wèn)題稱為二次規(guī)劃問(wèn)題[22]。

對(duì)偶問(wèn)題：

給定一個(gè)帶約束的優(yōu)化問(wèn)題

目標(biāo)函數(shù)：min f(x)

約束條件：C(x) ≥0

可以通過(guò)拉格朗日乘子構(gòu)造拉格朗日函數(shù)

L(x,λ)=f(x)- λ^TC(x)

令g(λ)= f(x)- λ^TC(x)

則原問(wèn)題可以轉(zhuǎn)化為

目標(biāo)函數(shù)：max g(λ)

約束條件：λ≥0

這個(gè)新的優(yōu)化問(wèn)題就稱為原問(wèn)題的對(duì)偶問(wèn)題（兩個(gè)問(wèn)題在取得最優(yōu)解時(shí)達(dá)到的條件相同）。

SVM算法
支持向量機(jī)(Support Vector Machine)是Cortes和Vapnik于1995年首先提出的，它在解決小樣本、非線性及高維模式識(shí)別中表現(xiàn)出許多特有的優(yōu)勢(shì)，并能夠推廣應(yīng)用到函數(shù)擬合等其他機(jī)器學(xué)習(xí)問(wèn)題中[10]。
支持向量機(jī)方法是建立在統(tǒng)計(jì)學(xué)習(xí)理論的VC 維理論和結(jié)構(gòu)風(fēng)險(xiǎn)最小原理基礎(chǔ)上的，根據(jù)有限的樣本信息在模型的復(fù)雜性（即對(duì)特定訓(xùn)練樣本的學(xué)習(xí)精度，Accuracy）和學(xué)習(xí)能力（即無(wú)錯(cuò)誤地識(shí)別任意樣本的能力）之間尋求最佳折衷，以期獲得最好的推廣能力[14]（或稱泛化能力）。
SVM 方法有很堅(jiān)實(shí)的理論基礎(chǔ)，SVM 訓(xùn)練的本質(zhì)是解決一個(gè)二次規(guī)劃問(wèn)題（Quadruple Programming，指目標(biāo)函數(shù)為二次函數(shù)，約束條件為線性約束的最優(yōu)化問(wèn)題），得到的是全局最優(yōu)解，這使它有著其他統(tǒng)計(jì)學(xué)習(xí)技術(shù)難以比擬的優(yōu)越性。SVM 分類器的文本分類效果很好，是最好的分類器之一。同時(shí)使用核函數(shù)將原始的樣本空間向高維空間進(jìn)行變換，能夠解決原始樣本線性不可分的問(wèn)題。其缺點(diǎn)是核函數(shù)的選擇缺乏指導(dǎo)，難以針對(duì)具體問(wèn)題選擇最佳的核函數(shù)；另外SVM 訓(xùn)練速度極大地受到訓(xùn)練集規(guī)模的影響，計(jì)算開(kāi)銷比較大，針對(duì)SVM 的訓(xùn)練速度問(wèn)題，研究者提出了很多改進(jìn)方法，包括Chunking 方法、Osuna 算法、SMO 算法和交互SVM 等等[14]。
SVM分類器的優(yōu)點(diǎn)在于通用性較好，且分類精度高、分類速度快、分類速度與訓(xùn)練樣本個(gè)數(shù)無(wú)關(guān)，在查準(zhǔn)和查全率方面都優(yōu)于kNN及樸素貝葉斯方法[8]。
與其它算法相比，SVM算法的理論基礎(chǔ)較為復(fù)雜，但應(yīng)用前景很廣，我打算專門寫一個(gè)系列的文章，詳細(xì)的討論SVM算法，stay tuned！

介紹過(guò)了幾個(gè)很具代表性的算法之后，不妨用國(guó)內(nèi)外的幾組實(shí)驗(yàn)數(shù)據(jù)來(lái)比較一下他們的優(yōu)劣。
在中文語(yǔ)料上的試驗(yàn)，文獻(xiàn)[6]使用了復(fù)旦大學(xué)自然語(yǔ)言處理實(shí)驗(yàn)室提供的基準(zhǔn)語(yǔ)料對(duì)當(dāng)前的基于詞向量空間文本模型的幾種分類算法進(jìn)行了測(cè)試，這一基準(zhǔn)語(yǔ)料分為20個(gè)類別，共有9804篇訓(xùn)練文檔，以及9833篇測(cè)試文檔。在經(jīng)過(guò)統(tǒng)一的分詞處理、噪聲詞消除等預(yù)處理之后，各個(gè)分類方法的性能指標(biāo)如下。

                      

其中F1 測(cè)度是一種綜合了查準(zhǔn)率與召回率的指標(biāo)，只有當(dāng)兩個(gè)值均比較大的時(shí)候，對(duì)應(yīng)的F1測(cè)度才比較大，因此是比單一的查準(zhǔn)或召回率更加具有代表性的指標(biāo)。
由比較結(jié)果不難看出，SVM和kNN明顯優(yōu)于樸素貝葉斯方法（但他們也都優(yōu)于Rocchio方法，這種方法已經(jīng)很少再參加評(píng)測(cè)了）。
在英文語(yǔ)料上，路透社的Reuters-21578 “ModApt´e”是比較常用的測(cè)試集，在這個(gè)測(cè)試集上的測(cè)試由很多人做過(guò)，Sebastiani在文獻(xiàn)[23]中做了總結(jié)，相關(guān)算法的結(jié)果摘錄如下：
   

 

分類算法	在Reuters-21578 “ModApt´e”上的F1測(cè)度
Rocchio	0.776
樸素貝葉斯	0.795
kNN	0.823
SVM	0.864

僅以F1測(cè)度來(lái)看，kNN是相當(dāng)接近SVM算法的，但F1只反映了分類效果（即分類分得準(zhǔn)不準(zhǔn)），而沒(méi)有考慮性能（即分類分得快不快）。綜合而論，SVM是效果和性能均不錯(cuò)的算法。

前面也提到過(guò)，訓(xùn)練階段的最終產(chǎn)物就是分類器，分類階段僅僅是使用這些分類器對(duì)新來(lái)的文檔分類而已，沒(méi)有過(guò)多可說(shuō)的東西。
下一章節(jié)是對(duì)到目前為止出現(xiàn)過(guò)的概念的列表及簡(jiǎn)單的解釋，也會(huì)引入一些后面會(huì)用到的概念。再之后會(huì)談及分類問(wèn)題本身的分類（繞口），中英文分類問(wèn)題的相似與不同之處以及幾種特征提取算法的概述和比較，路漫漫……

將樣本數(shù)據(jù)成功轉(zhuǎn)化為向量表示之后，計(jì)算機(jī)才算開(kāi)始真正意義上的“學(xué)習(xí)”過(guò)程。
再重復(fù)一次，所謂樣本，也叫訓(xùn)練數(shù)據(jù)，是由人工進(jìn)行分類處理過(guò)的文檔集合，計(jì)算機(jī)認(rèn)為這些數(shù)據(jù)的分類是絕對(duì)正確的，可以信賴的（但某些方法也有針對(duì)訓(xùn)練數(shù)據(jù)可能有錯(cuò)誤而應(yīng)對(duì)的措施）。接下來(lái)的一步便是由計(jì)算機(jī)來(lái)觀察這些訓(xùn)練數(shù)據(jù)的特點(diǎn)，來(lái)猜測(cè)一個(gè)可能的分類規(guī)則（這個(gè)分類規(guī)則也可以叫做分類器，在機(jī)器學(xué)習(xí)的理論著作中也叫做一個(gè)“假設(shè)”，因?yàn)楫吘故菍?duì)真實(shí)分類規(guī)則的一個(gè)猜測(cè)），一旦這個(gè)分類滿足一些條件，我們就認(rèn)為這個(gè)分類規(guī)則大致正確并且足夠好了，便成為訓(xùn)練階段的最終產(chǎn)品——分類器！再遇到新的，計(jì)算機(jī)沒(méi)有見(jiàn)過(guò)的文檔時(shí)，便使用這個(gè)分類器來(lái)判斷新文檔的類別。

舉一個(gè)現(xiàn)實(shí)中的例子，人們?cè)u(píng)價(jià)一輛車是否是“好車”的時(shí)候，可以看作一個(gè)分類問(wèn)題。我們也可以把一輛車的所有特征提取出來(lái)轉(zhuǎn)化為向量形式。在這個(gè)問(wèn)題中詞典向量可以為：
   D=（價(jià)格，最高時(shí)速，外觀得分，性價(jià)比，稀有程度）
則一輛保時(shí)捷的向量表示就可以寫成
    vp=（200萬(wàn)，320，9.5，3，9）
而一輛豐田花冠則可以寫成
   vt=（15萬(wàn)，220，6.0，8，3）
找不同的人來(lái)評(píng)價(jià)哪輛車算好車，很可能會(huì)得出不同的結(jié)論。務(wù)實(shí)的人認(rèn)為性價(jià)比才是評(píng)判的指標(biāo)，他會(huì)認(rèn)為豐田花冠是好車而保時(shí)捷不是；喜歡奢華的有錢人可能以稀有程度來(lái)評(píng)判，得出相反的結(jié)論；喜歡綜合考量的人很可能把各項(xiàng)指標(biāo)都加權(quán)考慮之后才下結(jié)論。
可見(jiàn)，對(duì)同一個(gè)分類問(wèn)題，用同樣的表示形式（同樣的文檔模型），但因?yàn)殛P(guān)注數(shù)據(jù)不同方面的特性而可能得到不同的結(jié)論。這種對(duì)文檔數(shù)據(jù)不同方面?zhèn)戎氐牟煌瑢?dǎo)致了原理和實(shí)現(xiàn)方式都不盡相同的多種方法，每種方法也都對(duì)文本分類這個(gè)問(wèn)題本身作了一些有利于自身的假設(shè)和簡(jiǎn)化，這些假設(shè)又接下來(lái)影響著依據(jù)這些方法而得到的分類器最終的表現(xiàn)，可謂環(huán)環(huán)相連，絲絲入扣，冥冥之中自有天意呀（這都什么詞兒……）。
比較常見(jiàn)，家喻戶曉，常年被評(píng)為國(guó)家免檢產(chǎn)品（？！）的分類算法有一大堆，什么決策樹(shù)，Rocchio，樸素貝葉斯，神經(jīng)網(wǎng)絡(luò)，支持向量機(jī)，線性最小平方擬合，kNN，遺傳算法，最大熵，Generalized Instance Set等等等等（這張單子還可以繼續(xù)列下去）。在這里只挑幾個(gè)最具代表性的算法侃一侃。

Rocchio算法
Rocchio算法應(yīng)該算是人們思考文本分類問(wèn)題時(shí)最先能想到，也最符合直覺(jué)的解決方法。基本的思路是把一個(gè)類別里的樣本文檔各項(xiàng)取個(gè)平均值（例如把所有“體育”類文檔中詞匯“籃球”出現(xiàn)的次數(shù)取個(gè)平均值，再把“裁判”取個(gè)平均值，依次做下去），可以得到一個(gè)新的向量，形象的稱之為“質(zhì)心”，質(zhì)心就成了這個(gè)類別最具代表性的向量表示。再有新文檔需要判斷的時(shí)候，比較新文檔和質(zhì)心有多么相像（八股點(diǎn)說(shuō)，判斷他們之間的距離）就可以確定新文檔屬不屬于這個(gè)類。稍微改進(jìn)一點(diǎn)的Rocchio算法不盡考慮屬于這個(gè)類別的文檔（稱為正樣本），也考慮不屬于這個(gè)類別的文檔數(shù)據(jù)（稱為負(fù)樣本），計(jì)算出來(lái)的質(zhì)心盡量靠近正樣本同時(shí)盡量遠(yuǎn)離負(fù)樣本。Rocchio算法做了兩個(gè)很致命的假設(shè)，使得它的性能出奇的差。一是它認(rèn)為一個(gè)類別的文檔僅僅聚集在一個(gè)質(zhì)心的周圍，實(shí)際情況往往不是如此（這樣的數(shù)據(jù)稱為線性不可分的）；二是它假設(shè)訓(xùn)練數(shù)據(jù)是絕對(duì)正確的，因?yàn)樗鼪](méi)有任何定量衡量樣本是否含有噪聲的機(jī)制，因而也就對(duì)錯(cuò)誤數(shù)據(jù)毫無(wú)抵抗力。
不過(guò)Rocchio產(chǎn)生的分類器很直觀，很容易被人類理解，算法也簡(jiǎn)單，還是有一定的利用價(jià)值的（做漢奸狀），常常被用來(lái)做科研中比較不同算法優(yōu)劣的基線系統(tǒng)（Base Line）。

樸素貝葉斯算法（Naive Bayes）
貝葉斯算法關(guān)注的是文檔屬于某類別概率。文檔屬于某個(gè)類別的概率等于文檔中每個(gè)詞屬于該類別的概率的綜合表達(dá)式。而每個(gè)詞屬于該類別的概率又在一定程度上可以用這個(gè)詞在該類別訓(xùn)練文檔中出現(xiàn)的次數(shù)（詞頻信息）來(lái)粗略估計(jì)，因而使得整個(gè)計(jì)算過(guò)程成為可行的。使用樸素貝葉斯算法時(shí)，在訓(xùn)練階段的主要任務(wù)就是估計(jì)這些值。
樸素貝葉斯算法的公式只有一個(gè)
                     

其中P(d| Ci)=P(w1|Ci) P(w2|Ci) …P(wi|Ci) P(w1|Ci) …P(wm|Ci) （式1）

P(wi|Ci)就代表詞匯wi屬于類別Ci的概率。
這其中就蘊(yùn)含著樸素貝葉斯算法最大的兩個(gè)缺陷。
首先，P(d| Ci)之所以能展開(kāi)成（式1）的連乘積形式，就是假設(shè)一篇文章中的各個(gè)詞之間是彼此獨(dú)立的，其中一個(gè)詞的出現(xiàn)絲毫不受另一個(gè)詞的影響（回憶一下概率論中變量彼此獨(dú)立的概念就可以知道），但這顯然不對(duì)，即使不是語(yǔ)言學(xué)專家的我們也知道，詞語(yǔ)之間有明顯的所謂“共現(xiàn)”關(guān)系，在不同主題的文章中，可能共現(xiàn)的次數(shù)或頻率有變化，但彼此間絕對(duì)談不上獨(dú)立。
其二，使用某個(gè)詞在某個(gè)類別訓(xùn)練文檔中出現(xiàn)的次數(shù)來(lái)估計(jì)P(wi|Ci)時(shí)，只在訓(xùn)練樣本數(shù)量非常多的情況下才比較準(zhǔn)確（考慮扔硬幣的問(wèn)題，得通過(guò)大量觀察才能基本得出正反面出現(xiàn)的概率都是二分之一的結(jié)論，觀察次數(shù)太少時(shí)很可能得到錯(cuò)誤的答案），而需要大量樣本的要求不僅給前期人工分類的工作帶來(lái)更高要求（從而成本上升），在后期由計(jì)算機(jī)處理的時(shí)候也對(duì)存儲(chǔ)和計(jì)算資源提出了更高的要求。

kNN算法則又有所不同，在kNN算法看來(lái)，訓(xùn)練樣本就代表了類別的準(zhǔn)確信息（因此此算法產(chǎn)生的分類器也叫做“基于實(shí)例”的分類器），而不管樣本是使用什么特征表示的。其基本思想是在給定新文檔后，計(jì)算新文檔特征向量和訓(xùn)練文檔集中各個(gè)文檔的向量的相似度，得到K篇與該新文檔距離最近最相似的文檔，根據(jù)這K篇文檔所屬的類別判定新文檔所屬的類別（注意這也意味著kNN算法根本沒(méi)有真正意義上的“訓(xùn)練”階段）。這種判斷方法很好的克服了Rocchio算法中無(wú)法處理線性不可分問(wèn)題的缺陷，也很適用于分類標(biāo)準(zhǔn)隨時(shí)會(huì)產(chǎn)生變化的需求（只要?jiǎng)h除舊訓(xùn)練文檔，添加新訓(xùn)練文檔，就改變了分類的準(zhǔn)則）。
kNN唯一的也可以說(shuō)最致命的缺點(diǎn)就是判斷一篇新文檔的類別時(shí)，需要把它與現(xiàn)存的所有訓(xùn)練文檔全都比較一遍，這個(gè)計(jì)算代價(jià)并不是每個(gè)系統(tǒng)都能夠承受的（比如我將要構(gòu)建的一個(gè)文本分類系統(tǒng)，上萬(wàn)個(gè)類，每個(gè)類即便只有20個(gè)訓(xùn)練樣本，為了判斷一個(gè)新文檔的類別，也要做20萬(wàn)次的向量比較！）。一些基于kNN的改良方法比如Generalized Instance Set就在試圖解決這個(gè)問(wèn)題。

下一節(jié)繼續(xù)講和訓(xùn)練階段有關(guān)的話題，包括概述已知性能最好的SVM算法。明兒見(jiàn)！（北京人兒，呵呵）

訓(xùn)練，顧名思義，就是training（汗，這解釋），簡(jiǎn)單的說(shuō)就是讓計(jì)算機(jī)從給定的一堆文檔中自己學(xué)習(xí)分類的規(guī)則（如果學(xué)不對(duì)的話，還要，打屁屁？）。

開(kāi)始訓(xùn)練之前，再多說(shuō)幾句關(guān)于VSM這種文檔表示模型的話。
舉個(gè)例子，假設(shè)說(shuō)把我正在寫的“文本分類入門”系列文章的第二篇抽出來(lái)當(dāng)作一個(gè)需要分類的文本，則可以用如下的向量來(lái)表示這個(gè)文本，以便于計(jì)算機(jī)理解和處理。

    w2=（文本，5，統(tǒng)計(jì)學(xué)習(xí)，4，模型，0，……）

這個(gè)向量表示在w2所代表的文本中，“文本”這個(gè)詞出現(xiàn)了5次（這個(gè)信息就叫做詞頻），“統(tǒng)計(jì)學(xué)習(xí)”這個(gè)詞出現(xiàn)了4次，而“模型”這個(gè)詞出現(xiàn)了0次，依此類推，后面的詞沒(méi)有列出。
而系列的第三篇文章可以表示為

    w3=（文本，9，統(tǒng)計(jì)學(xué)習(xí)，4，模型，10，……）

其含義同上。如果還有更多的文檔需要表示，我們都可以使用這種方式。
只通過(guò)觀察w2和w3我們就可以看出實(shí)際上有更方便的表示文本向量的方法，那就是把所有文檔都要用到的詞從向量中抽離出來(lái)，形成共用的數(shù)據(jù)結(jié)構(gòu)（也可以仍是向量的形式），這個(gè)數(shù)據(jù)結(jié)構(gòu)就叫做詞典，或者特征項(xiàng)集合。
例如我們的問(wèn)題就可以抽離出一個(gè)詞典向量

    D=（文本，統(tǒng)計(jì)學(xué)習(xí)，模型，……）

所有的文檔向量均可在參考這個(gè)詞典向量的基礎(chǔ)上簡(jiǎn)化成諸如

    w2=（5，4，0，……）
    w3=（9，4，10，……）

的形式，其含義沒(méi)有改變。
5，4，10這些數(shù)字分別叫做各個(gè)詞在某個(gè)文檔中的權(quán)重，實(shí)際上單單使用詞頻作為權(quán)重并不多見(jiàn)，也不十分有用，更常見(jiàn)的做法是使用地球人都知道的TF/IDF值作為權(quán)重。（關(guān)于TF/IDF的詳細(xì)解釋，Google的吳軍研究員寫了非常通俗易懂的文章，發(fā)布于Google黑板報(bào)，鏈接地址是http://googlechinablog.com/2006/06/blog-post_27.html，有興趣不妨一讀）TF/IDF作為一個(gè)詞對(duì)所屬文檔主題的貢獻(xiàn)程度來(lái)說(shuō)，是非常重要的度量標(biāo)準(zhǔn)，也是將文檔轉(zhuǎn)化為向量表示過(guò)程中的重要一環(huán)。

在這個(gè)轉(zhuǎn)化過(guò)程中隱含了一個(gè)很嚴(yán)重的問(wèn)題。注意看看詞典向量D，你覺(jué)得它會(huì)有多大？或者說(shuō)，你覺(jué)得它會(huì)包含多少個(gè)詞？
假設(shè)我們的系統(tǒng)僅僅處理漢語(yǔ)文本，如果不做任何處理，這個(gè)詞典向量會(huì)包含漢語(yǔ)中所有的詞匯，我手頭有一本商務(wù)印書(shū)館出版的《現(xiàn)代漢語(yǔ)詞典》第5版（2005年5月出版），其中收錄了65，000個(gè)詞，D大致也應(yīng)該有這么大，也就是說(shuō)，D是一個(gè)65，000維的向量，而所有的文本向量w2,w3,wn也全都是65，000維的！（這是文本分類這一問(wèn)題本身的一個(gè)特性，稱為“高維性”）想一想，大部分文章僅僅千余字，包含的詞至多幾百，為了表示這樣一個(gè)文本，卻要使用65，000維的向量，這是對(duì)存儲(chǔ)資源和計(jì)算能力多大的浪費(fèi)呀！（這又是文本分類問(wèn)題的另一個(gè)特性，稱為“向量稀疏性”，后面會(huì)專門有一章討論這些特性，并指出解決的方法，至少是努力的方向）
中國(guó)是一個(gè)人口眾多而資源稀少的國(guó)家，我們不提倡一味發(fā)展粗放型的經(jīng)濟(jì)，我們所需要的可持續(xù)發(fā)展是指資源消耗少，生產(chǎn)效率高，環(huán)境污染少……跑題了……
這么多的詞匯當(dāng)中，諸如“體育”，“經(jīng)濟(jì)”，“金融”，“處理器”等等，都是極其能夠代表文章主題的，但另外很多詞，像“我們”，“在”，“事情”，“里面”等等，在任何主題的文章中都很常見(jiàn)，根本無(wú)法指望通過(guò)這些詞來(lái)對(duì)文本類別的歸屬作個(gè)判斷。這一事實(shí)首先引發(fā)了對(duì)文本進(jìn)行被稱為“去停止詞”的預(yù)處理步驟（對(duì)英文來(lái)說(shuō)還有詞根還原，但這些與訓(xùn)練階段無(wú)關(guān)，不贅述，會(huì)在以后講述中英文文本分類方法區(qū)別的章節(jié)中討論），與此同時(shí)，我們也從詞典向量D中把這些詞去掉。
但經(jīng)過(guò)停止詞處理后剩下的詞匯仍然太多，使用了太多的特征來(lái)表示文本，就是常說(shuō)的特征集過(guò)大，不僅耗費(fèi)計(jì)算資源，也因?yàn)闀?huì)引起“過(guò)擬合問(wèn)題”而影響分類效果[22]。
這個(gè)問(wèn)題是訓(xùn)練階段要解決的第一個(gè)問(wèn)題，即如何選取那些最具代表性的詞匯（更嚴(yán)格的說(shuō)法應(yīng)該是，那些最具代表性的特征，為了便于理解，可以把特征暫時(shí)當(dāng)成詞匯來(lái)想象）。對(duì)這個(gè)問(wèn)題的解決，有人叫它特征提取，也有人叫它降維。
特征提取實(shí)際上有兩大類方法。一類稱為特征選擇（Term Selection），指的是從原有的特征（那許多有用無(wú)用混在一起的詞匯）中提取出少量的，具有代表性的特征，但特征的類型沒(méi)有變化（原來(lái)是一堆詞，特征提取后仍是一堆詞，數(shù)量大大減少了而已）。另一類稱為特征抽取（Term Extraction）的方法則有所不同，它從原有的特征中重構(gòu)出新的特征（原來(lái)是一堆詞，重構(gòu)后變成了別的，例如LSI將其轉(zhuǎn)為矩陣，文檔生成模型將其轉(zhuǎn)化為某個(gè)概率分布的一些參數(shù)），新的特征具有更強(qiáng)的代表性，并耗費(fèi)更少的計(jì)算資源。（特征提取的各種算法會(huì)有專門章節(jié)討論）
訓(xùn)練階段，計(jì)算機(jī)根據(jù)訓(xùn)練集中的文檔，使用特征提取找出最具代表性的詞典向量（仍然是不太嚴(yán)格的說(shuō)法），然后參照這個(gè)詞典向量把這些訓(xùn)練集文檔轉(zhuǎn)化為向量表示，之后的所有運(yùn)算便都使用這些向量進(jìn)行，不再理會(huì)原始的文本形式的文檔了（換言之，失寵了，后后）。

下一章繼續(xù)訓(xùn)練，咱們之間還沒(méi)完。（怎么聽(tīng)著像要找人尋仇似的）

前文說(shuō)到使用統(tǒng)計(jì)學(xué)習(xí)方法進(jìn)行文本分類就是讓計(jì)算機(jī)自己來(lái)觀察由人提供的訓(xùn)練文檔集，自己總結(jié)出用于判別文檔類別的規(guī)則和依據(jù)。理想的結(jié)果當(dāng)然是讓計(jì)算機(jī)在理解文章內(nèi)容的基礎(chǔ)上進(jìn)行這樣的分類，然而遺憾的是，我們所說(shuō)的“理解”往往指的是文章的語(yǔ)義甚至是語(yǔ)用信息，這一類信息極其復(fù)雜，抽象，而且存在上下文相關(guān)性，對(duì)這類信息如何在計(jì)算機(jī)中表示都是尚未解決的問(wèn)題（往大里說(shuō)，這是一個(gè)“知識(shí)表示”的問(wèn)題，完全可以另寫一系列文章來(lái)說(shuō)了），更不要說(shuō)讓計(jì)算機(jī)來(lái)理解。
利用計(jì)算機(jī)來(lái)解決問(wèn)題的標(biāo)準(zhǔn)思路應(yīng)該是：為這種問(wèn)題尋找一種計(jì)算機(jī)可以理解的表示方法，或曰建立一個(gè)模型（一個(gè)文檔表示模型）；然后基于這個(gè)模型，選擇各方面滿足要求的算法來(lái)解決。用譚浩強(qiáng)的話說(shuō)，程序，就是數(shù)據(jù)+算法。（啥？你不知道譚浩強(qiáng)是誰(shuí)？上過(guò)學(xué)么？學(xué)過(guò)C么？這搗什么亂？）
既然文本的語(yǔ)義和語(yǔ)用信息很難轉(zhuǎn)換成計(jì)算機(jī)能夠理解的表示形式，接下來(lái)順理成章的，人們開(kāi)始用文章中所包含的較低級(jí)別的詞匯信息來(lái)表示文檔，一試之下，效果居然還不錯(cuò)。
統(tǒng)計(jì)學(xué)習(xí)方法進(jìn)行文本分類（以下就簡(jiǎn)稱為“統(tǒng)計(jì)學(xué)習(xí)方法”，雖然這個(gè)方法也可以應(yīng)用到除文本分類以外的多個(gè)領(lǐng)域）的一個(gè)重要前提由此產(chǎn)生，那就是認(rèn)為：文檔的內(nèi)容與其中所包含的詞有著必然的聯(lián)系，同一類文檔之間總存在多個(gè)共同的詞，而不同類的文檔所包含的詞之間差異很大[1]。
進(jìn)一步的，不光是包含哪些詞很重要，這些詞出現(xiàn)的次數(shù)對(duì)分類也很重要。
這一前提使得向量模型（俗稱的VSM，向量空間模型）成了適合文本分類問(wèn)題的文檔表示模型。在這種模型中，一篇文章被看作特征項(xiàng)集合來(lái)看，利用加權(quán)特征項(xiàng)構(gòu)成向量進(jìn)行文本表示，利用詞頻信息對(duì)文本特征進(jìn)行加權(quán)。它實(shí)現(xiàn)起來(lái)比較簡(jiǎn)單，并且分類準(zhǔn)確度也高，能夠滿足一般應(yīng)用的要求。[5]
而實(shí)際上，文本是一種信息載體，其所攜帶的信息由幾部分組成：如組成元素本身的信息（詞的信息）、組成元素之間順序關(guān)系帶來(lái)的信息以及上下文信息（更嚴(yán)格的說(shuō)，還包括閱讀者本身的背景和理解）[12]。
而VSM這種文檔表示模型，基本上完全忽略了除詞的信息以外所有的部分，這使得它能表達(dá)的信息量存在上限[12]，也直接導(dǎo)致了基于這種模型構(gòu)建的文本分類系統(tǒng)（雖然這是目前絕對(duì)主流的做法），幾乎永遠(yuǎn)也不可能達(dá)到人類的分類能力。后面我們也會(huì)談到，相比于所謂的分類算法，對(duì)特征的選擇，也就是使用哪些特征來(lái)代表一篇文檔，往往更能影響分類的效果。
對(duì)于擴(kuò)充文檔表示模型所包含的信息量，人們也做過(guò)有益的嘗試，例如被稱為L(zhǎng)SI（Latent Semantic Index潛在語(yǔ)義索引）的方法，就被實(shí)驗(yàn)證明保留了一定的語(yǔ)義信息（之所以說(shuō)被實(shí)驗(yàn)證明了，是因?yàn)槿藗冞€無(wú)法在形式上嚴(yán)格地證明它確實(shí)保留了語(yǔ)義信息，而且這種語(yǔ)義信息并非以人可以理解的方式被保留下來(lái)），此為后話。

前文說(shuō)到（就不能不用這種老舊的說(shuō)法？換換新的，比如Previously on "Prison Break"，噢，不對(duì)，是Previously on Text Categorizaiton……）統(tǒng)計(jì)學(xué)習(xí)方法其實(shí)就是一個(gè)兩階段的解決方案，（1）訓(xùn)練階段，由計(jì)算機(jī)來(lái)總結(jié)分類的規(guī)則；（2）分類階段，給計(jì)算機(jī)一些它從來(lái)沒(méi)見(jiàn)過(guò)的文檔，讓它分類（分不對(duì)就打屁屁）。

下一章就專門說(shuō)說(shuō)訓(xùn)練階段的二三事。