SVM-支持向量機(jī)算法概述-1

支持向量機(jī)（SupportVectorMachine）算法概述沈新蕊OutlineSVM的理論基礎(chǔ)線性判別函數(shù)和超平面間隔與幾何間隔核函數(shù)與松弛變量SVM的理論基礎(chǔ)支持向量機(jī)(SupportVectorMachine)是Cortes和Vapnik于1995年首先提出的，從誕生至今才10多年，發(fā)展史雖短，但其理論研究和算法實(shí)現(xiàn)方面卻都取得了突破性進(jìn)展，有力地推動(dòng)機(jī)器學(xué)習(xí)理論和技術(shù)的發(fā)展。這一切與支持向量機(jī)具有較完備的統(tǒng)計(jì)學(xué)習(xí)理論基礎(chǔ)的發(fā)展背景是密不可分的。它在解決小樣本、非線性及高維模式識別中表現(xiàn)出許多特有的優(yōu)勢，并能夠推廣應(yīng)用到函數(shù)擬合等其他機(jī)器學(xué)習(xí)問題中。SVM支持向量機(jī)支持向量機(jī)方法是建立在統(tǒng)計(jì)學(xué)習(xí)理論的VC維理論和結(jié)構(gòu)風(fēng)險(xiǎn)最小原理基礎(chǔ)上的，根據(jù)有限的樣本信息在模型的復(fù)雜性（即對特定訓(xùn)練樣本的學(xué)習(xí)精度，Accuracy）和學(xué)習(xí)能力（即無錯(cuò)誤地識別任意樣本的能力）之間尋求最佳折衷，以期獲得最好的推廣能力（或稱泛化能力）。VC維VC維是對函數(shù)類的一種度量，可以簡單的理解為問題的復(fù)雜程度，VC維越高，一個(gè)問題就越復(fù)雜。正是因?yàn)镾VM關(guān)注的是VC維，SVM解決問題的時(shí)候，和樣本的維數(shù)是無關(guān)的。結(jié)構(gòu)風(fēng)險(xiǎn)最小機(jī)器學(xué)習(xí)本質(zhì)上就是一種對問題真實(shí)模型的逼近，真實(shí)模型一定是不知道的，那么我們選擇的假設(shè)與問題真實(shí)解之間究竟有多大差距，我們就沒法得知。這個(gè)與問題真實(shí)解之間的誤差，就叫做風(fēng)險(xiǎn)（更嚴(yán)格的說，誤差的累積叫做風(fēng)險(xiǎn)）。我們選擇了一個(gè)假設(shè)之后，真實(shí)誤差未知，但我們可以用某些可以掌握的量來逼近它。最直觀的想法就是使用分類器在樣本數(shù)據(jù)上的分類的結(jié)果與真實(shí)結(jié)果之間的差值來表示。這個(gè)差值叫做經(jīng)驗(yàn)風(fēng)險(xiǎn)Remp(w)。結(jié)構(gòu)風(fēng)險(xiǎn)最小以前的機(jī)器學(xué)習(xí)方法都把經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化作為努力的目標(biāo)，但后來發(fā)現(xiàn)很多分類函數(shù)能夠在樣本集上輕易達(dá)到100%的正確率，在真實(shí)分類時(shí)卻一塌糊涂（即推廣能力差，或泛化能力差）。此時(shí)的情況便是選擇了一個(gè)足夠復(fù)雜的分類函數(shù)，能夠精確的記住每一個(gè)樣本，但對樣本之外的數(shù)據(jù)一律分類錯(cuò)誤。此原則適用的大前提是經(jīng)驗(yàn)風(fēng)險(xiǎn)要確實(shí)能夠逼近真實(shí)風(fēng)險(xiǎn)才行，但實(shí)際上能逼近么？不能，因?yàn)闃颖緮?shù)相對于現(xiàn)實(shí)世界要分類的文本數(shù)來說簡直九牛一毛，經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化原則只在這占很小比例的樣本上做到?jīng)]有誤差，當(dāng)然不能保證在更大比例的真實(shí)文本上也沒有誤差。泛化誤差界統(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)，代表了我們在多大程度上可以信任分類器在未知文本上分類的結(jié)果。顯然，第二部分是沒有辦法精確計(jì)算的，因此只能給出一個(gè)估計(jì)的區(qū)間，也使得整個(gè)誤差只能計(jì)算上界，無法計(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)會變大。泛化誤差界泛化誤差界的公式為：R(w)≤Remp(w)+Ф(n/h)公式中R(w)就是真實(shí)風(fēng)險(xiǎn)，Remp(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)的算法。其它概念小樣本，并不是說樣本的絕對數(shù)量少，而是說與問題的復(fù)雜度比起來，SVM算法要求的樣本數(shù)是相對比較少的。非線性，是指SVM擅長應(yīng)付樣本數(shù)據(jù)線性不可分的情況，主要通過松弛變量（也叫懲罰變量）和核函數(shù)技術(shù)來實(shí)現(xiàn)，這一部分是SVM的精髓。關(guān)于文本分類這個(gè)問題究竟是不是線性可分的，尚沒有定論，因此不能簡單的認(rèn)為它是線性可分的而作簡化處理，先當(dāng)它是線性不可分的（反正線性可分也不過是線性不可分的一種特例）。其它概念高維模式識別是指樣本維數(shù)很高，例如文本的向量表示，如果沒有經(jīng)過降維處理，出現(xiàn)幾萬維的情況很正常，其他算法基本就沒有能力應(yīng)付了，SVM卻可以，主要是因?yàn)镾VM產(chǎn)生的分類器很簡潔，用到的樣本信息很少（僅僅用到那些稱之為“支持向量”的樣本），使得即使樣本維數(shù)很高，也不會給存儲和計(jì)算帶來大麻煩。線性判別函數(shù)和超平面線性分類器是最簡單也很有效的分類器形式。在一個(gè)線性分類器中，可以看到SVM形成的思路并接觸很多SVM的核心概念。用一個(gè)二維空間里僅有兩類樣本的分類問題來舉例。如下圖所示：線性函數(shù)C1和C2是要區(qū)分的兩個(gè)類別，在二維平面中它們的樣本如上圖所示。中間的直線就是一個(gè)分類函數(shù)，它可以將兩類樣本完全分開。一般的，如果一個(gè)線性函數(shù)能夠?qū)颖就耆_的分開，就稱這些數(shù)據(jù)是線性可分的，否則稱為非線性可分的。線性函數(shù)什么叫線性函數(shù)呢？在一維空間里就是一個(gè)點(diǎn)，在二維空間里就是一條直線，三維空間里就是一個(gè)平面，如果不關(guān)注空間的維數(shù)，這種線性函數(shù)還有一個(gè)統(tǒng)一的名稱——超平面（HyperPlane）。實(shí)際上，一個(gè)線性函數(shù)是一個(gè)實(shí)值函數(shù)（即函數(shù)的值是連續(xù)的實(shí)數(shù)），而我們的分類問題需要離散的輸出值，例如用1表示某個(gè)樣本屬于類別C1，而用0表示不屬于，這時(shí)候只需要簡單的在實(shí)值函數(shù)的基礎(chǔ)上附加一個(gè)閾值即可，通過分類函數(shù)執(zhí)行時(shí)得到的值大于還是小于這個(gè)閾值來確定類別歸屬。線性函數(shù)

例如我們有一個(gè)線性函數(shù)：

g(x)=wx+b

取閾值為0，這樣當(dāng)有一個(gè)樣本xi需要判別的時(shí)候，我們就看g(xi)的值。若g(xi)>0，就判別為類別C1，若g(xi)<0，則判別為類別C2（等于的時(shí)候就拒絕判斷）。此時(shí)也等價(jià)于給函數(shù)g(x)附加一個(gè)符號函數(shù)sgn()，即f(x)=sgn[g(x)]是我們真正的判別函數(shù)。線性函數(shù)注意：一，式中的x不是二維坐標(biāo)系中的橫軸，而是樣本的向量表示，二，這個(gè)形式并不局限于二維的情況，在n維空間中仍然可以使用這個(gè)表達(dá)式，只是式中的w成為了n維向量（在二維的這個(gè)例子中，w是二維向量，為了表示起來方便簡潔）；三，g(x)不是中間那條直線的表達(dá)式，中間那條直線的表達(dá)式是g(x)=0，即wx+b=0，我們也把這個(gè)函數(shù)叫做分類面。間隔與幾何間隔中間那條分界線并不是唯一的，我們把它稍微旋轉(zhuǎn)一下，只要不把兩類數(shù)據(jù)分錯(cuò)，仍然可以達(dá)到上面說的效果，稍微平移一下，也可以。此時(shí)就牽涉到一個(gè)問題，對同一個(gè)問題存在多個(gè)分類函數(shù)的時(shí)候，哪一個(gè)函數(shù)更好呢？顯然必須要先找一個(gè)指標(biāo)來量化“好”的程度，通常使用的都是叫做“分類間隔”的指標(biāo)。幾何間隔對于文本分類這樣的不適定問題（有一個(gè)以上解的問題稱為不適定問題），需要有一個(gè)指標(biāo)來衡量解決方案（即我們通過訓(xùn)練建立的分類模型）的好壞，而分類間隔是一個(gè)比較好的指標(biāo)。在進(jìn)行文本分類的時(shí)候，可以讓計(jì)算機(jī)這樣來看待我們提供給它的訓(xùn)練樣本，每一個(gè)樣本由一個(gè)向量（那些文本特征所組成的向量）和一個(gè)標(biāo)記（標(biāo)示出這個(gè)樣本屬于哪個(gè)類別）組成。幾何間隔如：

Di=(xi,yi)

xi就是文本向量（維數(shù)很高），yi就是分類標(biāo)記。在二元的線性分類中，這個(gè)表示分類的標(biāo)記只有兩個(gè)值，1和-1（用來表示屬于還是不屬于這個(gè)類）。

定義一個(gè)樣本點(diǎn)到某個(gè)超平面的間隔：

δi=yi(wxi+b)幾何間隔首先注意到如果某個(gè)樣本屬于該類別的話，那么wxi+b>0，而yi也大于0；若不屬于該類別的話，那么wxi+b<0，而yi也小于0，這意味著yi(wxi+b)總是大于0的，而且它的值就等于|wxi+b|（也就是|g(xi)|）?，F(xiàn)在把w和b進(jìn)行一下歸一化，即用w/||w||和b/||w||分別代替原來的w和b，那么間隔就可以寫成：幾何間隔當(dāng)用歸一化的w和b代替原值之后的間隔有一個(gè)專門的名稱，叫做幾何間隔，幾何間隔所表示的正是點(diǎn)到超平面的歐氏距離，我們下面就簡稱幾何間隔為“距離”。圖更加直觀的展示出了幾何間隔的現(xiàn)實(shí)含義。H是分類面，而H1和H2是平行于H，且過離H最近的兩類樣本的直線，H1與H，H2與H之間的距離就是幾何間隔。幾何間隔與樣本誤分次數(shù)間的關(guān)系之所以如此關(guān)心幾何間隔這個(gè)東西，是因?yàn)閹缀伍g隔與樣本的誤分次數(shù)間存在關(guān)系：其中的δ是樣本集合到分類面的間隔，R=max||xi||i=1,...,n，即R是所有樣本中向量長度最長的值。不必追究誤分次數(shù)的具體定義和推導(dǎo)過程，只要記得這個(gè)誤分次數(shù)一定程度上代表分類器的誤差。而從上式可以看出，誤分次數(shù)的上界由幾何間隔決定。由此說明為何要選擇幾何間隔來作為評價(jià)一個(gè)解優(yōu)劣的指標(biāo)，幾何間隔越大的解，它的誤差上界越小。因此最大化幾何間隔成了我們訓(xùn)練階段的目標(biāo)。優(yōu)化目標(biāo)一個(gè)線性分類函數(shù)，有了判斷解優(yōu)劣的標(biāo)準(zhǔn)——即有了優(yōu)化的目標(biāo)，這個(gè)目標(biāo)就是最大化幾何間隔，但是一些關(guān)于SVM的論文的優(yōu)化目標(biāo)是要最小化||w||，這是怎么回事呢？間隔和幾何間隔的定義：間隔：δ=y(wx+b)=|g(x)|

幾何間隔：得：

δ=||w||δ幾何

幾何間隔與||w||是成反比的，因此最大化幾何間隔與最小化||w||完全是一回事。常用的方法并不是固定||w||的大小而尋求最大幾何間隔，而是固定間隔（例如固定為1），尋找最小的||w||。求一個(gè)函數(shù)的最小值（或最大值）的問題都可以稱為尋優(yōu)問題（也叫作一個(gè)規(guī)劃問題），又由于找最大值的問題總可以通過加一個(gè)負(fù)號變?yōu)檎易钚≈档膯栴}，因此下面討論針對找最小值的過程來進(jìn)行。一個(gè)尋優(yōu)問題最重要的部分是目標(biāo)函數(shù)，就是指尋優(yōu)的目標(biāo)。目標(biāo)函數(shù)例如尋找最小的||w||這件事，就可以用下面的式子表示：

但實(shí)際上對于這個(gè)目標(biāo)，常常使用另一個(gè)完全等價(jià)的目標(biāo)函數(shù)來代替，那就是：

不難看出當(dāng)||w||2達(dá)到最小時(shí)，||w||也達(dá)到最小，反之亦然。這個(gè)式子是否能描述我們的問題呢？我們的問題是有一堆點(diǎn)，可以被分成兩類，我們要找出最好的分類面。如果直接來解這個(gè)求最小值問題，很容易看出當(dāng)||w||=0的時(shí)候就得到了目標(biāo)函數(shù)的最小值。但是無論給什么樣的數(shù)據(jù)，都是這個(gè)解。反映在圖中，就是H1與H2兩條直線間的距離無限大，這個(gè)時(shí)候，所有的樣本點(diǎn)（無論正樣本還是負(fù)樣本）都跑到了H1和H2中間。而我們原本的意圖是，H1右側(cè)的被分為正類，H2左側(cè)的被分為負(fù)類，位于兩類中間的樣本則拒絕分類（拒絕分類的另一種理解是分給哪一類都有道理，因而分給哪一類也都沒有道理）。但，所有樣本點(diǎn)都進(jìn)入了無法分類的灰色地帶。約束條件造成這種結(jié)果的原因是在描述問題的時(shí)候只考慮了目標(biāo)，而沒有加入約束條件。約束條件就是在求解過程中必須滿足的條件，體現(xiàn)在問題中就是樣本點(diǎn)必須在H1或H2的某一側(cè)（或者至少在H1和H2上），而不能跑到兩者中間。前文提到過把間隔固定為1，這是指把所有樣本點(diǎn)中間隔最小的那一點(diǎn)的間隔定為1，意味著集合中的其他點(diǎn)間隔都不會小于1，按照間隔的定義，滿足這些條件就相當(dāng)于讓下面的式子總是成立：yi[(w·xi)+b]≥1(i=1,2,…,l)（l是總的樣本數(shù)）但我們常常習(xí)慣讓式子的值和0比較，因而經(jīng)常用變換過的形式：

yi[(w·xi)+b]-1≥0(i=1,2,…,l)因此我們的兩類分類問題也被我們轉(zhuǎn)化成了它的數(shù)學(xué)形式，一個(gè)帶約束的最小值的問題：從最一般的定義上說，一個(gè)求最小值的問題就是一個(gè)優(yōu)化問題，它同樣由兩部分組成，目標(biāo)函數(shù)和約束條件，可以用下面的式子表示：

式1約束條件用函數(shù)c來表示。可以看出一共有p+q個(gè)約束條件，其中p個(gè)是不等式約束，q個(gè)等式約束。

式1式中的x是自變量，但不限定它的維數(shù)必須為1（視乎解決的問題空間維數(shù)）。要求f(x)在哪一點(diǎn)上取得最小值，不是在整個(gè)空間里找，而是在約束條件所劃定的一個(gè)有限的空間里找，這個(gè)有限的空間就是優(yōu)化理論里所說的可行域。注意可行域中的每一個(gè)點(diǎn)都要求滿足所有p+q個(gè)條件，而不是滿足其中一條或幾條就可以，同時(shí)可行域邊界上的點(diǎn)有一個(gè)額外好的特性，它們可以使不等式約束取得等號?？尚杏蜻€有個(gè)概念不得不提，那就是凸集：凸集是指有這么一個(gè)點(diǎn)的集合，其中任取兩個(gè)點(diǎn)連一條直線，這條線上的點(diǎn)仍然在這個(gè)合內(nèi)部。再來看我們線性分類器問題的描述：

式2自變量就是w，而目標(biāo)函數(shù)是w的二次函數(shù)，所有的約束條件都是w的線性函數(shù)。這種規(guī)劃問題有稱呼——二次規(guī)劃（QuadraticProgramming，QP），更進(jìn)一步的說，由于它的可行域是一個(gè)凸集，因此它是一個(gè)凸二次規(guī)劃。凸二次規(guī)劃有全局最優(yōu)解，由于我們想找的本來就是全局最優(yōu)的解。對比（式2）和（式1）還可以發(fā)現(xiàn)，我們的線性分類器問題只有不等式約束，因此形式上看似乎比一般意義上的規(guī)劃問題要簡單，但解起來卻并非如此。讓我們再一次比較完整的重復(fù)一下要解決的問題：我們有屬于兩個(gè)類別的樣本點(diǎn)若干（并不限定這些點(diǎn)在二維空間中），如圖：圓形的樣本點(diǎn)定為正樣本，方形的點(diǎn)定為負(fù)類。我們想求得這樣一個(gè)線性函數(shù)（在n維空間中的線性函數(shù)）：g(x)=wx+b使得所有屬于正類的點(diǎn)x+代入以后有g(shù)(x+)≥1，而所有屬于負(fù)類的點(diǎn)x-代入后有g(shù)(x-)≤-1。代入g(x)后的值如果在1和-1之間，我們就拒絕判斷。求這樣的g(x)的過程就是求w（一個(gè)n維向量）和b（一個(gè)實(shí)數(shù)）兩個(gè)參數(shù)的過程。因此在求g(x)的時(shí)候，w才是變量。一旦求出了w（也就求出了b），那么中間的直線H就知道了，那么H1和H2也就知道了（因?yàn)槿呤瞧叫械模蚁喔舻木嚯x還是||w||決定的）。w是誰決定的？

顯然是已知的樣本決定的，一旦在空間中給出了那些個(gè)樣本點(diǎn)，三條直線的位置實(shí)際上就唯一確定了。樣本確定了w，用數(shù)學(xué)的語言描述，就是w可以表示為樣本的某種組合：w=α1x1+α2x2+…+αnxn式子中的αi是一個(gè)一個(gè)的數(shù)（在嚴(yán)格的證明過程中，α被稱為拉格朗日乘子），而xi是樣本點(diǎn)，因而是向量，n就是總樣本點(diǎn)的個(gè)數(shù)。為了方便描述，以下開始嚴(yán)格區(qū)別數(shù)字與向量的乘積和向量間的乘積，會用α1x1表示數(shù)字和向量的乘積，而用<x1,x2>表示向量x1,x2的內(nèi)積。因此g(x)的表達(dá)式嚴(yán)格的形式應(yīng)該是：g(x)=<w,x>+b上面的式子還不夠好，回想圖中正樣本和負(fù)樣本的位置，想像一下，不動(dòng)所有點(diǎn)的位置，而只是把其中一個(gè)正樣本點(diǎn)定為負(fù)樣本點(diǎn)，結(jié)果怎么樣？三條直線都必須移動(dòng)。這說明w不僅跟樣本點(diǎn)的位置有關(guān)，還跟樣本的類別有關(guān)（也就是和樣本的“標(biāo)簽”有關(guān)）。因此用下面這個(gè)式子表示才算完整：

w=α1y1x1+α2y2x2+…+αnynxn其中的yi就是第i個(gè)樣本的標(biāo)簽，它等于1或者-1。其實(shí)以上式子的那一堆拉格朗日乘子中，只有很少的一部分不等于0（不等于0才對w起決定作用），這部分不等于0的拉格朗日乘子后面所乘的樣本點(diǎn)，其實(shí)都落在H1和H2上，也正是這部分樣本（而不需要全部樣本）唯一的確定了分類函數(shù)。更嚴(yán)格的說，這些樣本的一部分就可以確定，例如確定一條直線，只需要兩個(gè)點(diǎn)就可以，即便有三五個(gè)都落在上面，我們也不是全都需要。這部分我們真正需要的樣本點(diǎn)，就叫做支持（撐）向量。式子也可以用求和符號簡寫一下：因此原來的g(x)表達(dá)式可以寫為：注意式子中x才是變量，也就是要分類的，就把該文檔的向量表示代入到x的位置，而所有的xi統(tǒng)統(tǒng)都是已知的樣本。還注意到式子中只有xi和x是向量，因此一部分可以從內(nèi)積符號中拿出來，得到g(x)的式子為：核函數(shù)與松弛變量之前一直在討論的線性分類器，只能對線性可分的樣本做處理。如果提供的樣本線性不可分，結(jié)果很簡單，線性分類器的求解程序會無限循環(huán)，永遠(yuǎn)也解不出來。這必然使得它的適用范圍大大縮小，而它的很多優(yōu)點(diǎn)我們實(shí)在不原意放棄，怎么辦呢？是否有某種方法，讓線性不可分的數(shù)據(jù)變得線性可分呢？有！其思想說來也簡單，來用一個(gè)二維平面中的分類問題作例子，一看就會明白。把橫軸上端點(diǎn)a和b之間紅色部分里的所有點(diǎn)定為正類，兩邊的黑色部分里的點(diǎn)定為負(fù)類。試問能找到一個(gè)線性函數(shù)把兩類正確分開么？不能，因?yàn)槎S空間里的線性函數(shù)就是指直線，顯然找不到符合條件的直線。但我們可以找到一條曲線，例如下面這一條：顯然通過點(diǎn)在這條曲線的上方還是下方就可以判斷點(diǎn)所屬的類別（你在橫軸上隨便找一點(diǎn)，算算這一點(diǎn)的函數(shù)值，會發(fā)現(xiàn)負(fù)類的點(diǎn)函數(shù)值一定比0大，而正類的一定比0?。?。這條曲線就是我們熟知的二次曲線，它的函數(shù)表達(dá)式可以寫為：這條曲線就是我們熟知的二次曲線，它的函數(shù)表達(dá)式可以寫為：問題只是它不是一個(gè)線性函數(shù)，但是，新建一個(gè)向量y和a：這樣g(x)就可以轉(zhuǎn)化為f(y)=<a,y>實(shí)際上f(y)的形式就是：g(x)=f(y)=ay在任意維度的空間中，這種形式的函數(shù)都是一個(gè)線性函數(shù)（其中的a和y都是多維向量），因?yàn)樽宰兞縴的次數(shù)不大于1。二維空間中一個(gè)線性不可分的問題，映射到四維空間后，變成了線性可分的！因此這也形成了我們最初想解決線性不可分問題的基本思路——向高維空間轉(zhuǎn)化，使其變得線性可分。而轉(zhuǎn)化最關(guān)鍵的部分就在于找到x到y(tǒng)的映射方法。遺憾的是，如何找到這個(gè)映射，沒有系統(tǒng)性的方法。具體到文本分類問題，文本被表示為上千維的向量，即使維數(shù)已經(jīng)如此之高，也常常是線性不可分的，還要向更高的空間轉(zhuǎn)化。其中的難度可想而知。用一個(gè)具體文本分類的例子來看看這種向高維空間映射從而分類的方法如何運(yùn)作，想象一下，我們文本分類問題的原始空間是1000維的（即每個(gè)要被分類的文檔被表示為一個(gè)1000維的向量），在這個(gè)維度上問題是線性不可分的?，F(xiàn)在我們有一個(gè)2000維空間里的線性函數(shù):

f(x’)=<w’,x’>+b式中的w’和x’都是2000維的向量，只不過w’是定值，而x’是變量?，F(xiàn)在我們的輸入，是一個(gè)1000維的向量x，分類的過程是先把x變換為2000維的向量x’，然后求這個(gè)變換后的向量x’與向量w’的內(nèi)積，再把這個(gè)內(nèi)積的值和b相加，就得到了結(jié)果，看結(jié)果大于閾值還是小于閾值就得到了分類結(jié)果。我們其實(shí)只關(guān)心那個(gè)高維空間里內(nèi)積的值，那個(gè)值算出來了，分類結(jié)果就算出來了。而從理論上說，x’是經(jīng)由x變換來的，因此廣義上可以把它叫做x的函數(shù)。而w’是常量，它是一個(gè)低維空間里的常量w經(jīng)過變換得到的，所以給了一個(gè)w和x的值，就有一個(gè)確定的f(x’)值與其對應(yīng)。這讓我們幻想，是否能有這樣一種函數(shù)K(w,x),他接受低維空間的輸入值，卻能算出高維空間的內(nèi)積值<w’,x’>？如果有這樣的函數(shù)，那么當(dāng)給了一個(gè)低維空間的輸入x以后，

g(x)=K(w,x)+b

f(x’)=<w’,x’>+b這兩個(gè)函數(shù)的計(jì)算結(jié)果就完全一樣，就用不著費(fèi)力找那個(gè)映射關(guān)系，直接拿低維的輸入往g(x)里面代就可以了。這回的g(x)就不是線性函數(shù)啦，因?yàn)椴荒鼙ＷCK(w,x)這個(gè)表達(dá)式里的x次數(shù)不高于1。萬幸，這樣的K(w,x)確實(shí)存在，它被稱作核函數(shù)（核，kernel）。核函數(shù)核函數(shù)的基本作用就是接受兩個(gè)低維空間里的向量，能夠計(jì)算出經(jīng)過某個(gè)變換后在高維空間里的向量內(nèi)積值?；仡欀扒蟮木€性分類器，它的形式應(yīng)該是：現(xiàn)在這個(gè)就是高維空間里的線性函數(shù)（為了區(qū)別低維和高維空間里的函數(shù)和向量，改了函數(shù)的名字，并且給w和x都加上了）。我們就可以用一個(gè)低維空間里的函數(shù)來代替（這個(gè)低維空間里的函數(shù)就不再是線性的了）：f(x’)和g(x)里的α，y，b全都是一樣一樣的。這就是說，盡管給的問題是線性不可分的，但是我們就硬當(dāng)它是線性問題來求解。只不過求解過程中，凡是要求內(nèi)積的時(shí)候就用我們選定的核函數(shù)來算。這樣求出來的α再和選定的核函數(shù)一組合，就得到分類器啦！對核函數(shù)的選擇，現(xiàn)在還缺乏指導(dǎo)原則！各種實(shí)驗(yàn)的觀察結(jié)果的確表明，某些問題用某些核函數(shù)效果很好，用另一些就很差。松弛變量如果使用核函數(shù)向高維空間映射后，問題仍然是線性不可分的，那怎么辦？現(xiàn)在我們已經(jīng)把一個(gè)本來線性不可分的文本分類問題，通過映射到高維空間而變成了線性可分的。就像下圖這樣：現(xiàn)在想象我們有另一個(gè)訓(xùn)練集，只比原先這個(gè)訓(xùn)練集多了一個(gè)數(shù)據(jù)點(diǎn)，映射到高維空間以后（也使用相同的核函數(shù)），也就多了一個(gè)樣本點(diǎn)，但是這個(gè)樣本的位置是這樣的：就是圖中黃色那個(gè)點(diǎn)，它是方形的，是負(fù)類的一個(gè)樣本，這單獨(dú)的一個(gè)樣