SVM教學(xué)講解課件

SupportVectorMachine

支持向量機(jī)

1SupportVectorMachine

支持向量機(jī)整體概述概述二點(diǎn)擊此處輸入相關(guān)文本內(nèi)容概述一點(diǎn)擊此處輸入相關(guān)文本內(nèi)容概述三點(diǎn)擊此處輸入相關(guān)文本內(nèi)容2整體概述概述二概述一概述三2

內(nèi)容SVM簡(jiǎn)介線性分類器核函數(shù)松弛變量LIBSVM介紹實(shí)驗(yàn)3內(nèi)容SVM簡(jiǎn)介3SVM簡(jiǎn)介支持向量機(jī)(SupportVectorMachine)是Cortes和Vapnik于1995年首先提出的，它在解決小樣本、非線性及高維模式識(shí)別中表現(xiàn)出許多特有的優(yōu)勢(shì)，并能夠推廣應(yīng)用到函數(shù)擬合等其他機(jī)器學(xué)習(xí)問(wèn)題中。

4SVM簡(jiǎn)介支持向量機(jī)(SupportVectorMachSVM簡(jiǎn)介支持向量機(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í)別任意樣本的能力）之間尋求最佳折衷，以期獲得最好的推廣能力（或稱泛化能力）。5SVM簡(jiǎn)介支持向量機(jī)方法是建立在統(tǒng)計(jì)學(xué)習(xí)理論的VC維理論和SVM簡(jiǎn)介VC維：所謂VC維是對(duì)函數(shù)類的一種度量，可以簡(jiǎn)單的理解為問(wèn)題的復(fù)雜程度，VC維越高，一個(gè)問(wèn)題就越復(fù)雜。正是因?yàn)镾VM關(guān)注的是VC維，后面我們可以看到，SVM解決問(wèn)題的時(shí)候，和樣本的維數(shù)是無(wú)關(guān)的（甚至樣本是上萬(wàn)維的都可以，這使得SVM很適合用來(lái)解決像文本分類這樣的問(wèn)題，當(dāng)然，有這樣的能力也因?yàn)橐肓撕撕瘮?shù)）。6SVM簡(jiǎn)介VC維：所謂VC維是對(duì)函數(shù)類的一種度量，可以簡(jiǎn)單的SVM簡(jiǎn)介結(jié)構(gòu)風(fēng)險(xiǎn)最小原理：就是追求“經(jīng)驗(yàn)風(fēng)險(xiǎn)”與“置信風(fēng)險(xiǎn)”的和最小。7SVM簡(jiǎn)介結(jié)構(gòu)風(fēng)險(xiǎn)最小原理：就是追求“經(jīng)驗(yàn)風(fēng)險(xiǎn)”與“置信風(fēng)險(xiǎn)SVM簡(jiǎn)介風(fēng)險(xiǎn)：機(jī)器學(xué)習(xí)本質(zhì)上就是一種對(duì)問(wèn)題真實(shí)模型的逼近（我們選擇一個(gè)我們認(rèn)為比較好的近似模型，這個(gè)近似模型就叫做一個(gè)假設(shè)），但毫無(wú)疑問(wèn)，真實(shí)模型一定是不知道的。既然真實(shí)模型不知道，那么我們選擇的假設(shè)與問(wèn)題真實(shí)解之間究竟有多大差距，我們就沒(méi)法得知。這個(gè)與問(wèn)題真實(shí)解之間的誤差，就叫做風(fēng)險(xiǎn)（更嚴(yán)格的說(shuō)，誤差的累積叫做風(fēng)險(xiǎn)）。8SVM簡(jiǎn)介風(fēng)險(xiǎn)：機(jī)器學(xué)習(xí)本質(zhì)上就是一種對(duì)問(wèn)題真實(shí)模型的逼近（SVM簡(jiǎn)介經(jīng)驗(yàn)風(fēng)險(xiǎn)Remp(w)

：我們選擇了一個(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)Remp(w)。9SVM簡(jiǎn)介經(jīng)驗(yàn)風(fēng)險(xiǎn)Remp(w)：我們選擇了一個(gè)假設(shè)之后（SVM簡(jiǎn)介

以前的一些機(jī)器學(xué)習(xí)方法把經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化作為努力的目標(biāo)，但后來(lái)發(fā)現(xiàn)很多分類函數(shù)能夠在樣本集上輕易達(dá)到100%的正確率，在真實(shí)分類時(shí)卻不好（即所謂的推廣能力差，或泛化能力差）。此時(shí)的情況是因?yàn)檫x擇了一個(gè)足夠復(fù)雜的分類函數(shù)（它的VC維很高），能夠精確的記住每一個(gè)樣本，但對(duì)樣本之外的數(shù)據(jù)一律分類錯(cuò)誤。因?yàn)榻?jīng)驗(yàn)風(fēng)險(xiǎn)最小化原則適用的大前提是經(jīng)驗(yàn)風(fēng)險(xiǎn)要確實(shí)能夠逼近真實(shí)風(fēng)險(xiǎn)才行。但實(shí)際上不太可能，經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化原則只在這占很小比例的樣本上做到?jīng)]有誤差，不能保證在更大比例的真實(shí)文本上也沒(méi)有誤差。10SVM簡(jiǎn)介以前的一些機(jī)器學(xué)習(xí)方法把經(jīng)驗(yàn)風(fēng)SVM簡(jiǎn)介泛化誤差界：為了解決剛才的問(wèn)題，統(tǒng)計(jì)學(xué)提出了泛化誤差界的概念。就是指真實(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)確的值（所以叫做泛化誤差界，而不叫泛化誤差）。11SVM簡(jiǎn)介泛化誤差界：為了解決剛才的問(wèn)題，統(tǒng)計(jì)學(xué)提出了泛化誤SVM簡(jiǎ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ì)變大。12SVM簡(jiǎn)介置信風(fēng)險(xiǎn)：與兩個(gè)量有關(guān)，一是樣本數(shù)量，顯然給定的樣SVM簡(jiǎ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)。此時(shí)目標(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)最小。13SVM簡(jiǎn)介泛化誤差界的公式為：13SVM簡(jiǎn)介小樣本：并不是說(shuō)樣本的絕對(duì)數(shù)量少（實(shí)際上，對(duì)任何算法來(lái)說(shuō)，更多的樣本幾乎總是能帶來(lái)更好的效果），而是說(shuō)與問(wèn)題的復(fù)雜度比起來(lái)，SVM算法要求的樣本數(shù)是相對(duì)比較少的。14SVM簡(jiǎn)介小樣本：并不是說(shuō)樣本的絕對(duì)數(shù)量少（實(shí)際上，對(duì)任何算SVM簡(jiǎn)介非線性：是指SVM擅長(zhǎng)應(yīng)付樣本數(shù)據(jù)線性不可分的情況，主要通過(guò)松弛變量（也叫懲罰變量）和核函數(shù)技術(shù)來(lái)實(shí)現(xiàn)，這一部分是SVM的核心內(nèi)容，后面會(huì)詳細(xì)說(shuō)明。15SVM簡(jiǎn)介非線性：是指SVM擅長(zhǎng)應(yīng)付樣本數(shù)據(jù)線性不可分的情況SVM簡(jiǎn)介高維模式識(shí)別：是指樣本維數(shù)很高，SVM也可以應(yīng)付。這主要是因?yàn)镾VM產(chǎn)生的分類器很簡(jiǎn)潔，用到的樣本信息很少（僅僅用到那些稱之為“支持向量”的樣本），使得即使樣本維數(shù)很高，也不會(huì)給存儲(chǔ)和計(jì)算帶來(lái)大麻煩。16SVM簡(jiǎn)介高維模式識(shí)別：是指樣本維數(shù)很高，SVM也可以應(yīng)付。線性分類器線性分類器：一定意義上，也可以叫做感知機(jī)，是最簡(jiǎn)單也很有效的分類器形式。在一個(gè)線性分類器中，可以看到SVM形成的思路，并接觸很多SVM的核心概念。下面舉例說(shuō)明。17線性分類器線性分類器：一定意義上，也可以叫做感知機(jī)，是最簡(jiǎn)線性分類器用一個(gè)二維空間里僅有兩類樣本的分類問(wèn)題來(lái)舉例子。如圖所示：C1和C2是要區(qū)分的兩個(gè)類別。中間的直線就是一個(gè)分類函數(shù)，它可以將兩類樣本完全分開。一般的，如果一個(gè)線性函數(shù)能夠?qū)颖就耆_的分開，就稱這些數(shù)據(jù)是線性可分的，否則稱為非線性可分的。

18線性分類器用一個(gè)二維空間里僅有兩類樣本的分類問(wèn)題來(lái)舉例子。如線性分類器線性函數(shù)在一維空間里就是一個(gè)點(diǎn)，在二維空間里就是一條直線，三維空間里就是一個(gè)平面，可以如此想象下去，如果不關(guān)注空間的維數(shù)，這種線性函數(shù)還有一個(gè)統(tǒng)一的名稱——超平面（HyperPlane）。19線性分類器線性函數(shù)19線性分類器例如我們有一個(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è)符號(hào)函數(shù)sgn()，即f(x)=sgn[g(x)]是我們真正的判別函數(shù)。20線性分類器例如我們有一個(gè)線性函數(shù)20線性分類器關(guān)于g(x)=wx+b這個(gè)表達(dá)式要注意三點(diǎn)：1.式中的x不是二維坐標(biāo)系中的橫軸，而是樣本的向量表示，例如一個(gè)樣本點(diǎn)的坐標(biāo)是(3,8)，則xT=(3,8)，而不是x=3（一般說(shuō)向量都是說(shuō)列向量）。2.這個(gè)形式并不局限于二維的情況，在n維空間中仍然可以使用這個(gè)表達(dá)式，只是式中的w成為了n維向量（在二維的這個(gè)例子中，w是二維向量，注意這里的w嚴(yán)格的說(shuō)也應(yīng)該是轉(zhuǎn)置的形式，為了表示起來(lái)方便簡(jiǎn)潔，以下均不區(qū)別列向量和它的轉(zhuǎn)置）。3.g(x)不是中間那條直線的表達(dá)式，中間那條直線的表達(dá)式是g(x)=0，即wx+b=0，我們也把這個(gè)函數(shù)叫做分類面。21線性分類器關(guān)于g(x)=wx+b這個(gè)表達(dá)式要注意三點(diǎn)：21線性分類器分類間隔：下圖中間那條分界線并不是唯一的，把它稍微旋轉(zhuǎn)一下，只要不把兩類數(shù)據(jù)分錯(cuò)，仍然可以達(dá)到上面說(shuō)的效果，稍微平移一下，也可以。此時(shí)就牽涉到一個(gè)問(wèn)題，對(duì)同一個(gè)問(wèn)題存在多個(gè)分類函數(shù)的時(shí)候，哪一個(gè)函數(shù)更好呢？顯然必須要先找一個(gè)指標(biāo)來(lái)量化“好”的程度，通常使用叫做“分類間隔”的指標(biāo)。

22線性分類器分類間隔：下圖中間那條分界線并不是唯一的，把它稍線性分類器

比如在進(jìn)行文本分類的時(shí)候，我們可以讓計(jì)算機(jī)這樣來(lái)看待我們提供給它的訓(xùn)練樣本，每一個(gè)樣本由一個(gè)向量（就是那些文本特征所組成的向量）和一個(gè)標(biāo)記（標(biāo)示出這個(gè)樣本屬于哪個(gè)類別）組成。如下：Di=(xi,yi)

xi就是文本向量（維數(shù)很高），yi就是分類標(biāo)記。23線性分類器比如在進(jìn)行文本分類的時(shí)候，我們可線性分類器

在二元的線性分類中，這個(gè)表示分類的標(biāo)記只有兩個(gè)值，1和-1（用來(lái)表示屬于還是不屬于這個(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)|。24線性分類器在二元的線性分類中，這個(gè)表示分線性分類器

現(xiàn)在把w和b進(jìn)行歸一化處理，即用w/||w||和b/||w||分別代替原來(lái)的w和b，那么間隔就可以寫成：

這就是解析幾何中點(diǎn)xi到直線g(x)=0的距離公式，也就是到超平面g(x)=0的距離。

25線性分類器現(xiàn)在把w和b進(jìn)行歸一化處理，即用w線性分類器||w||叫做向量w的范數(shù)，范數(shù)是對(duì)向量長(zhǎng)度的一種度量。我們常說(shuō)的向量長(zhǎng)度其實(shí)指的是它的2-范數(shù)，范數(shù)最一般的表示形式為p-范數(shù)，可以寫成如下表達(dá)式向量w=(w1,w2,w3,……wn)它的p-范數(shù)為：當(dāng)我們不指明p的時(shí)候，就意味著我們不關(guān)心p的值，用幾范數(shù)都可以。當(dāng)用歸一化的w和b代替原值之后的間隔有一個(gè)專門的名稱，叫幾何間隔，表示的是點(diǎn)到超平面的歐氏距離。26線性分類器||w||叫做向量w的范數(shù)，范數(shù)是對(duì)向量長(zhǎng)度線性分類器

下面這張圖直觀的展示出了幾何間隔的現(xiàn)實(shí)含義：

H是分類面，而H1和H2是平行于H，且過(guò)離H最近的兩類樣本的直線，H1與H，H2與H之間的距離就是幾何間隔。27線性分類器下面這張圖直觀的展示出了幾何間隔的線性分類器

之所以如此關(guān)心幾何間隔這個(gè)東西，是因?yàn)閹缀伍g隔與樣本的誤分次數(shù)間存在關(guān)系：

其中的δ是樣本集合到分類面的幾何間隔，R=max||xi||

i=1,...,n，即R是所有樣本中向量長(zhǎng)度最長(zhǎng)的值（也就是說(shuō)代表樣本的分布有多么廣）。誤分次數(shù)一定程度上代表分類器的誤差。而從上式可以看出，在樣本已知的情況下，誤分次數(shù)的上界由幾何間隔決定！幾何間隔越大的解，它的誤差上界越小。因此最大化幾何間隔成了訓(xùn)練階段的目標(biāo)。28線性分類器之所以如此關(guān)心幾何間隔這個(gè)東西線性分類器間隔：δ=y(wx+b)=|g(x)|幾何間隔：

可以看出δ=||w||δ幾何。幾何間隔與||w||是成反比的，因此最大化幾何間隔與最小化||w||完全是一回事。而我們常用的方法并不是固定||w||的大小而尋求最大幾何間隔，而是把所有樣本點(diǎn)中間隔最小的那一點(diǎn)的間隔固定（例如固定為1），尋找最小的||w||。29線性分類器間隔：δ=y(wx+b)=|g(x)|29線性分類器

如果直接來(lái)解這個(gè)求最小值問(wèn)題，當(dāng)||w||=0的時(shí)候就得到了目標(biāo)函數(shù)的最小值。但是無(wú)論給什么樣的數(shù)據(jù)，都是這個(gè)解！反映在圖中，就是H1與H2兩條直線間的距離無(wú)限大，這個(gè)時(shí)候，所有的樣本點(diǎn)都跑到了H1和H2中間，進(jìn)入了無(wú)法分類的灰色地帶。

造成這種結(jié)果的原因是在描述問(wèn)題的時(shí)候只考慮了目標(biāo)，而沒(méi)有加入約束條件。30線性分類器如果直接來(lái)解這個(gè)求最小值問(wèn)題，線性分類器

之前把所有樣本點(diǎn)中間隔最小的那一點(diǎn)的間隔定為1，這就相當(dāng)于讓下面的式子總是成立：

yi[(w·xi)+b]≥1(i=1,2,…,l)（l是總的樣本數(shù)）即：

yi[(w·xi)+b]-1≥0(i=1,2,…,l)（l是總的樣本數(shù)）因此我們的兩類分類問(wèn)題也被我們轉(zhuǎn)化成了它的數(shù)學(xué)形式，一個(gè)帶約束的最小值的問(wèn)題：

31線性分類器之前把所有樣本點(diǎn)中間隔最小的那線性分類器

從最一般的定義上說(shuō)，一個(gè)求最小值的問(wèn)題就是一個(gè)優(yōu)化問(wèn)題（也叫規(guī)劃），它同樣由兩部分組成，目標(biāo)函數(shù)和約束條件，可以用下面的式子表示：

約束條件用函數(shù)c來(lái)表示，就是constrain的意思。一共有p+q個(gè)約束條件，其中p個(gè)是不等式約束，q個(gè)等式約束。32線性分類器從最一般的定義上說(shuō)，一個(gè)求最小線性分類器

這個(gè)式子中的x是自變量，但不限定它的維數(shù)必須為1（視乎你解決的問(wèn)題空間維數(shù)）。要求f(x)在哪一點(diǎn)上取得最小值，但不是在整個(gè)空間里找，而是在約束條件所劃定的可行域里找。注意可行域中的每一個(gè)點(diǎn)都要求滿足所有p+q個(gè)條件，同時(shí)可行域邊界上的點(diǎn)有一個(gè)額外好的特性，它們可以使不等式約束取得等號(hào)！而邊界內(nèi)的點(diǎn)不行。33線性分類器33線性分類器

這對(duì)一般的優(yōu)化問(wèn)題可能提供不了什么幫助，但對(duì)SVM來(lái)說(shuō)，邊界上的點(diǎn)有其特殊意義，實(shí)際上是它們唯一決定了分類超平面，這些點(diǎn)（就是以前的圖中恰好落在H1和H2上的點(diǎn)，在文本分類問(wèn)題中，每一個(gè)點(diǎn)代表一個(gè)文檔，因而這個(gè)點(diǎn)本身也是一個(gè)向量）就被稱為支持向量。34線性分類器這對(duì)一般的優(yōu)化問(wèn)題可能提供不了什線性分類器

回頭再看線性分類器問(wèn)題的描述：

在這個(gè)問(wèn)題中，自變量就是w，目標(biāo)函數(shù)是w的二次函數(shù)，所有的約束條件都是w的線性函數(shù)（不要把xi當(dāng)成變量，它代表樣本，是已知的），這種規(guī)劃問(wèn)題也叫做二次規(guī)劃（QuadraticProgramming，QP）。而且，由于它的可行域是一個(gè)凸集，因此它是一個(gè)凸二次規(guī)劃。凸二次規(guī)劃的優(yōu)點(diǎn)在于它有全局最優(yōu)解。35線性分類器回頭再看線性分類器問(wèn)題的描述：線性分類器

但是實(shí)際上我們并不知道該怎么解一個(gè)帶約束的優(yōu)化問(wèn)題。我們可以輕松的解一個(gè)不帶任何約束的優(yōu)化問(wèn)題（實(shí)際上就是函數(shù)求極值，求導(dǎo)再找0點(diǎn)），我們甚至還會(huì)解一個(gè)只帶等式約束的優(yōu)化問(wèn)題，就是求條件極值，通過(guò)添加拉格朗日乘子，構(gòu)造拉格朗日函數(shù)，來(lái)把這個(gè)問(wèn)題轉(zhuǎn)化為無(wú)約束的優(yōu)化問(wèn)題。如果只帶等式約束的問(wèn)題可以轉(zhuǎn)化為無(wú)約束的問(wèn)題來(lái)求解，那么可不可以把帶不等式約束的問(wèn)題向只帶等式約束的問(wèn)題轉(zhuǎn)化而得以求解呢？答案是可以。36線性分類器但是實(shí)際上我們并不知道該怎么解線性分類器

我們想求得這樣一個(gè)線性函數(shù)（在n維空間中的線性函數(shù)）：g(x)=wx+b

求g(x)的過(guò)程就是求w（一個(gè)n維向量）和b（一個(gè)實(shí)數(shù)）兩個(gè)參數(shù)的過(guò)程（但實(shí)際上只需要求w，求得以后找某些樣本點(diǎn)代入就可以求得b）。因此在求g(x)的時(shí)候，w才是變量。37線性分類器我們想求得這樣一個(gè)線性函數(shù)（在n線性分類器

樣本確定了w，用數(shù)學(xué)的語(yǔ)言描述，就是w可以表示為樣本的某種組合：w=α1x1+α2x2+…+αnxn

式子中的αi是一個(gè)一個(gè)的數(shù)（在嚴(yán)格的證明過(guò)程中，這些α被稱為拉格朗日乘子），而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>+b38線性分類器樣本確定了w，用數(shù)學(xué)的語(yǔ)言描述，線性分類器

但是上面的式子還不夠好，如果我不動(dòng)所有點(diǎn)的位置，而只是把其中一個(gè)正樣本點(diǎn)定為負(fù)樣本點(diǎn)（也就是把一個(gè)點(diǎn)的形狀從圓形變?yōu)榉叫危敲慈龡l直線都必須移動(dòng)。這說(shuō)明w不僅跟樣本點(diǎn)的位置有關(guān)，還跟樣本的類別有關(guān)因此用下面這個(gè)式子表示才算完整：w=α1y1x1+α2y2x2+…+αnynxn

其中的yi就是第i個(gè)樣本的標(biāo)簽，它等于1或者-1。其實(shí)以上式子的不等于0（不等于0才對(duì)w起決那一堆拉格朗日乘子中，只有很少的一部分定作用），這部分不等于0的拉格朗日乘子后面所乘的樣本點(diǎn)，其實(shí)都落在H1和H2上，也正是這部分樣本唯一的確定了分類函數(shù)。更嚴(yán)格的說(shuō)，這些樣本的一部分就可以確定，因?yàn)槔绱_定一條直線，只需要兩個(gè)點(diǎn)就可以。這部分樣本點(diǎn)，就叫做支持（撐）向量！

39線性分類器但是上面的式子還不夠好，線性分類器

式子也可以用求和符號(hào)簡(jiǎn)寫一下：

因此原來(lái)的g(x)表達(dá)式可以寫為：

注意式子中x才是變量，如果要分類哪篇文檔，就把該文檔的向量表示代入到x的位置，而所有的xi統(tǒng)統(tǒng)都是已知的樣本。還注意到式子中只有xi和x是向量，因此一部分可以從內(nèi)積符號(hào)中拿出來(lái)，得到g(x)的式子為：

40線性分類器

式子也可以用求和符號(hào)簡(jiǎn)寫一下：線性分類器

至此w不見了，從求w變成了求α?？此茮](méi)有簡(jiǎn)化問(wèn)題，其實(shí)簡(jiǎn)化了原來(lái)的問(wèn)題，因?yàn)橐赃@樣的形式描述問(wèn)題以后，我們的優(yōu)化了不等式約束。之后的求解就變得很容易了。下面遇到一個(gè)問(wèn)題：如果提供的樣本線性不可分，怎么辦？所以必須要提到SVM中比較重要的內(nèi)容——核函數(shù)。41線性分類器至此w不見了，從求w變成了求α。核函數(shù)

之前一直在討論的線性分類器。如果提供的樣本線性不可分，結(jié)果很簡(jiǎn)單，線性分類器的求解程序會(huì)無(wú)限循環(huán)，永遠(yuǎn)也解不出來(lái)。這必然使得它的適用范圍大大縮小，而它的很多優(yōu)點(diǎn)我們實(shí)在不原意放棄，那么就必須尋找讓線性不可分的數(shù)據(jù)變得線性可分的方法。42核函數(shù)之前一直在討論的線性分類器。如果提核函數(shù)

用一個(gè)二維平面中的分類問(wèn)題作例子，如圖：把橫軸上端點(diǎn)a和b之間紅色部分里的所有點(diǎn)定為正類，兩邊的黑色部分里的點(diǎn)定為負(fù)類。試問(wèn)能找到一個(gè)線性函數(shù)把兩類正確分開么？不能，因?yàn)槎S空間里的線性函數(shù)就是指直線，顯然找不到符合條件的直線。43核函數(shù)用一個(gè)二維平面中的分類問(wèn)題作例子，如圖核函數(shù)

但我們可以找到一條曲線，例如下面這一條：

顯然通過(guò)點(diǎn)在這條曲線的上方還是下方就可以判斷點(diǎn)所屬的類別。這條曲線就是我們熟知的二次曲線，它的函數(shù)表達(dá)式是：44核函數(shù)但我們可以找到一條曲線，例如下面這一條：核函數(shù)

問(wèn)題只是它不是一個(gè)線性函數(shù)，但是，做一下變換，新建一個(gè)向量y和a：這樣g(x)就可以轉(zhuǎn)化為f(y)=<a,y>，你可以把y和a分別回帶一下，看看等不等于原來(lái)的g(x)。用內(nèi)積的形式寫你可能看不太清楚，實(shí)際上f(y)的形式就是：g(x)=f(y)=ay

在任意維度的空間中，這種形式的函數(shù)都是一個(gè)線性函數(shù)，因?yàn)樽宰兞縴的次數(shù)不大于1。原來(lái)在二維空間中一個(gè)線性不可分的問(wèn)題，映射到高維空間后，變成了線性可分的！因此也形成了我們最初想解決線性不可分問(wèn)題的基本思路——向高維空間轉(zhuǎn)化，使其變得線性可分。45核函數(shù)問(wèn)題只是它不是一個(gè)線性函數(shù)，但是，核函數(shù)

用一個(gè)具體文本分類的例子來(lái)看看這種向高維空間映射從而分類的方法如何運(yùn)作，如果我們文本分類問(wèn)題的原始空間是1000維的（即每個(gè)要被分類的文檔被表示為一個(gè)1000維的向量），在這個(gè)維度上問(wèn)題是線性不可分的?，F(xiàn)在我們有一個(gè)2000維空間里的線性函數(shù)f(x’)=<w’,x’>+b

它能夠?qū)⒃瓎?wèn)題變得可分。式中的w’和x’都是2000維的向量，只不過(guò)w’是定值，而x’是變量。現(xiàn)在我們的輸入呢，是一個(gè)1000維的向量x，分類的過(guò)程是先把x變換為2000維的向量x’，然后求這個(gè)變換后的向量x’與向量w’的內(nèi)積，再把這個(gè)內(nèi)積的值和b相加，就得到了結(jié)果，看結(jié)果大于閾值還是小于閾值就得到了分類結(jié)果。46核函數(shù)用一個(gè)具體文本分類的例子來(lái)看看這核函數(shù)

所以只需要關(guān)心那個(gè)高維空間里內(nèi)積的值。而從理論上說(shuō)，x’是經(jīng)由x變換來(lái)的，因此廣義上可以把它叫做x的函數(shù)（因?yàn)橛幸粋€(gè)x，就確定了一個(gè)x’），而w’是常量，它是一個(gè)低維空間里的常量w經(jīng)過(guò)變換得到的，所以給了一個(gè)w和x的值，就有一個(gè)確定的f(x’)值與其對(duì)應(yīng)。所以，需要這樣一種函數(shù)K(w,x),他接受低維空間的輸入值，卻能算出高維空間的內(nèi)積值<w’,x’>。也就是當(dāng)給了一個(gè)低維空間的輸入x以后：g(x)=K(w,x)+bf(x’)=<w’,x’>+b

這兩個(gè)函數(shù)的計(jì)算結(jié)果就完全一樣，我們也就用不著費(fèi)力找那個(gè)映射關(guān)系，直接拿低維的輸入往g(x)里面代就可以了。47核函數(shù)所以只需要關(guān)心那個(gè)高維空核函數(shù)

這樣的函數(shù)確實(shí)存在，它被稱作核函數(shù)（核，kernel），而且不止一個(gè)，事實(shí)上，只要是滿足了Mercer條件的函數(shù)，都可以作為核函數(shù)。核函數(shù)的基本作用就是接受兩個(gè)低維空間里的向量，能夠計(jì)算出經(jīng)過(guò)某個(gè)變換后在高維空間里的向量?jī)?nèi)積值。這就是說(shuō)，盡管給的問(wèn)題是線性不可分的，但是就硬當(dāng)它是線性問(wèn)題來(lái)求解，只不過(guò)求解過(guò)程中，凡是要求內(nèi)積的時(shí)候就用選定的核函數(shù)來(lái)算。這樣求出來(lái)的α再和選定的核函數(shù)一組合，就得到分類器。。48核函數(shù)這樣的函數(shù)確實(shí)存在，它被稱作核函數(shù)（核函數(shù)幾個(gè)比較常用的核函數(shù)如下：49核函數(shù)幾個(gè)比較常用的核函數(shù)如下：49核函數(shù)

接下來(lái)還有兩個(gè)問(wèn)題：

1.既然有很多的核函數(shù)，針對(duì)具體問(wèn)題該怎么選擇？

2.如果使用核函數(shù)向高維空間映射后，問(wèn)題仍然是線性不可分的，那怎么辦？50核函數(shù)接下來(lái)還有兩個(gè)問(wèn)題：50核函數(shù)

對(duì)核函數(shù)的選擇，現(xiàn)在還缺乏指導(dǎo)原則！各種實(shí)驗(yàn)的觀察結(jié)果（不光是文本分類）的確表明，某些問(wèn)題用某些核函數(shù)效果很好，用另一些就很差，但是一般來(lái)講，徑向基核函數(shù)（RBF）是不會(huì)出太大偏差的一種。51核函數(shù)對(duì)核函數(shù)的選擇，現(xiàn)在還缺乏指導(dǎo)原則！核函數(shù)

在常用的核函數(shù)中，應(yīng)用最廣泛的是具有較好學(xué)習(xí)能力的RBF核，無(wú)論低維、高維、小樣本、大樣本等情況，RBF核均適應(yīng)，具有較寬的收斂域，是較為理想的分類依據(jù)函數(shù)。KeerthiSS等人證明了線性核和多項(xiàng)式核是RBF核的特殊情況。

LinCJ等說(shuō)明了在某些參數(shù)情況下，

Sigmoid核同RBF核具有相似的性能。52核函數(shù)在常用的核函數(shù)中，應(yīng)用最廣泛的是具有松弛變量解決第二個(gè)問(wèn)題：

舉個(gè)例子，比如我們已經(jīng)把一個(gè)本來(lái)線性不可分的文本分類問(wèn)題，通過(guò)映射到高維空間而變成了線性可分的?，F(xiàn)在有這樣一個(gè)訓(xùn)練集，只比原先這個(gè)訓(xùn)練集多了一篇文章，映射到高維空間以后也就多了一個(gè)樣本點(diǎn)，但是這個(gè)樣本的位置如下圖：53松弛變量解決第二個(gè)問(wèn)題：53松弛變量

就是圖中黃色那個(gè)點(diǎn)，它是方形的，因而它是負(fù)類的一個(gè)樣本，這單獨(dú)的一個(gè)樣本，使得原本線性可分的問(wèn)題變成了線性不可分的。這樣類似的問(wèn)題（僅有少數(shù)點(diǎn)線性不可分）叫做“近似線性可分”的問(wèn)題。

54松弛變量54松弛變量

按照常識(shí)判斷，如果有一萬(wàn)個(gè)點(diǎn)都符合某種規(guī)律，只有一個(gè)點(diǎn)不符合，那這個(gè)樣本點(diǎn)可能是噪聲。所以即便簡(jiǎn)單的忽略這個(gè)樣本點(diǎn)，仍然使用原來(lái)的分類器，其效果絲毫不受影響。但程序并沒(méi)有這種容錯(cuò)性。由于在原本的優(yōu)化問(wèn)題的表達(dá)式中，確實(shí)要考慮所有的樣本點(diǎn)，并在此基礎(chǔ)上尋找正負(fù)類之間的最大幾何間隔，而幾何間隔代表的是距離，是非負(fù)的，像上面這種有噪聲的情況會(huì)使得整個(gè)問(wèn)題無(wú)解。這種解法其實(shí)也叫做“硬間隔”分類法，因?yàn)樗残缘囊笏袠颖军c(diǎn)都滿足和分類平面間的距離必須大于某個(gè)值。解決方法也很明顯，就是仿照人的思路，允許一些點(diǎn)到分類平面的距離不滿足原先的要求。55松弛變量按照常識(shí)判斷，如果有一萬(wàn)個(gè)點(diǎn)都符松弛變量

為此引入一個(gè)非負(fù)的松弛項(xiàng)，有兩種常用的方式：另一種是：其中l(wèi)都是樣本的數(shù)目。兩種方法沒(méi)有大的區(qū)別。如果選擇了第一種，得到的方法的就叫做一階軟間隔分類器，第二種就叫做二階軟間隔分類器。

56松弛變量為此引入一個(gè)非負(fù)的松弛項(xiàng)，有兩種松弛變量

把損失加入到目標(biāo)函數(shù)里的時(shí)候，就需要一個(gè)懲罰因子（cost，也就是libSVM的諸多參數(shù)中的C），原來(lái)的優(yōu)化問(wèn)題就變成了下面這樣：

這個(gè)式子有這么幾點(diǎn)要注意：

1.并非所有的樣本點(diǎn)都有一個(gè)松弛變量與其對(duì)應(yīng)。只有“離群點(diǎn)”才有。

2.松弛變量的值實(shí)際上標(biāo)示出了對(duì)應(yīng)的點(diǎn)到底離群有多遠(yuǎn)，值越大，點(diǎn)就越遠(yuǎn)。

57松弛變量把損失加入到目標(biāo)函數(shù)里的時(shí)候，就松弛變量3.懲罰因子C決定了你有多重視離群點(diǎn)帶來(lái)的損失，顯然當(dāng)所有離群點(diǎn)的松弛變量的和一定時(shí)，C越大，對(duì)目標(biāo)函數(shù)的損失也越大，此時(shí)就暗示著非常不愿意放棄這些離群點(diǎn)，最極端的情況是把C定為無(wú)限大，這樣只要稍有一個(gè)點(diǎn)離群，目標(biāo)函數(shù)的值馬上變成無(wú)限大，馬上讓問(wèn)題變成無(wú)解，這就退化成了硬間隔問(wèn)題。

4.是懲罰因子C不是一個(gè)變量，整個(gè)優(yōu)化問(wèn)題在解的時(shí)候，C是一個(gè)必須事先指定的值，指定這個(gè)值以后，解一下，就得到一個(gè)分類器，然后用測(cè)試數(shù)據(jù)看看結(jié)果好不好，不好再換一個(gè)C的值。如此就是一個(gè)參數(shù)尋優(yōu)的過(guò)程。另外，當(dāng)遇到數(shù)據(jù)集偏斜問(wèn)題時(shí)，也是通過(guò)調(diào)整懲罰因子來(lái)解決。58松弛變量3.懲罰因子C決定了你有多重視離群點(diǎn)帶來(lái)的損松弛變量核函數(shù)與松弛變量作用的區(qū)別：雖然二者的引入都是為了解決線性不可分的問(wèn)題。但兩者還有微妙的不同。以文本分類為例。在原始的低維空間中，樣本相當(dāng)?shù)牟豢煞?，無(wú)論怎么找分類平面，總會(huì)有大量的離群點(diǎn)，此時(shí)用核函數(shù)向高維空間映射一下，雖然結(jié)果仍然是不可分的，但比原始空間里的要更加接近線性可分的狀態(tài)，就是達(dá)到了近似線性可分的狀態(tài)。此時(shí)再用松弛變量處理那些少數(shù)的離群點(diǎn)，就簡(jiǎn)單有效得多了。59松弛變量核函數(shù)與松弛變量作用的區(qū)別：59SVM用于多類分類一次性得到多個(gè)分類面的方法：就是真的一次性考慮所有樣本，并求解一個(gè)多目標(biāo)函數(shù)的優(yōu)化問(wèn)題，一次性得到多個(gè)分類面，如下圖：

只可惜這種算法還基本停留在紙面上，因?yàn)橐淮涡郧蠼獾姆椒ㄓ?jì)算量實(shí)在太大，大到無(wú)法實(shí)用的地步。

60SVM用于多類分類一次性得到多個(gè)分類面的方法：就是真的一次性SVM用于多類分類“一類對(duì)其余”的方法：比如有5個(gè)類別，第一次就把類別1的樣本定為正樣本，其余2，3，4，5的樣本合起來(lái)定為負(fù)樣本，得到一個(gè)兩類分類器，它能夠指出一篇文章是還是不是第1類的；第二次我們把類別2的樣本定為正樣本，把1，3，4，5的樣本合起來(lái)定為負(fù)樣本，得到一個(gè)分類器，如此下去。但這種方法容易導(dǎo)致分類重疊現(xiàn)象和不可分類現(xiàn)象人為造成“數(shù)據(jù)集偏斜”問(wèn)題。61SVM用于多類分類“一類對(duì)其余”的方法：比如有5個(gè)類別，第一SVM用于多類分類“一對(duì)一單挑”的方法：每次選一個(gè)類的樣本作正類樣本，而負(fù)類樣本則變成只選一個(gè)類。因此第一個(gè)只回答“是第1類還是第2類”，第二個(gè)只回答“是第1類還是第3類”，如此下去。在真正用來(lái)分類的時(shí)候，把一篇文章扔給所有分類器，讓每一個(gè)都投上自己的一票，最后統(tǒng)計(jì)票數(shù)，如果類別“1”得票最多，就判這篇文章屬于第1類。這種方法使得兩類分類器數(shù)目為k(k-1)/2）。類別數(shù)如果是1000，要調(diào)用的分類器數(shù)目會(huì)上升至約500000個(gè)，過(guò)于復(fù)雜。62SVM用于多類分類“一對(duì)一單挑”的方法：每次選一個(gè)類的樣本作SVM用于多類分類

所以必須在分類的時(shí)候下功夫。舉個(gè)例子，還是像一對(duì)一方法那樣來(lái)訓(xùn)練，只是在對(duì)一篇文章進(jìn)行分類之前，先按照下面圖的樣子來(lái)組織分類器：

分類時(shí)，先問(wèn)分類器“1對(duì)5”（意思是它能夠回答“是第1類還是第5類”），如果回答5，就往左走，再問(wèn)“2對(duì)5”這個(gè)分類器，如果還是“5”，繼續(xù)往左走，這樣一直下去，就可以得到分類結(jié)果。63SVM用于多類分類所以必須在分類的時(shí)候下SVM用于多類分類

這是一個(gè)有向無(wú)環(huán)圖，因此這種方法也叫做DAGSVM），調(diào)用了k-1（K是類別數(shù)）個(gè)分類器。速度快，且沒(méi)有分類重疊和不可分類現(xiàn)象。缺點(diǎn)是假如最一開始的分類器回答錯(cuò)誤，那么后面的分類器是無(wú)法糾正它的錯(cuò)誤。對(duì)下面每一層的分類器都存在這種錯(cuò)誤向下累積的現(xiàn)象。但是DAG方法好于它們的地方就在于，累積的上限，不管是大是小，總是有定論的，有理論可以證明。并且可以通過(guò)調(diào)整“根節(jié)點(diǎn)的選取”及輸出“置信度”來(lái)改善效果。64SVM用于多類分類這是一個(gè)有向無(wú)環(huán)圖，因此LIBSVM介紹LIBSVM是臺(tái)灣大學(xué)林智仁教授2001年開發(fā)的一套支持向量機(jī)的庫(kù)，運(yùn)算速度快，可以很方便的對(duì)數(shù)據(jù)做分類或回歸。由于LIBSVM程序小，運(yùn)用靈活，輸入?yún)?shù)少，并且是開源的，易于擴(kuò)展，因此成為目前國(guó)內(nèi)應(yīng)用最多的SVM的庫(kù)。這套庫(kù)目前已經(jīng)發(fā)展到2.9版。65LIBSVM介紹LIBSVM是臺(tái)灣大學(xué)林智仁教授2001年開LIBSVM介紹

工具包里主要有5個(gè)文件夾：

1.Java主要是應(yīng)用于java平臺(tái)；

2.Python是用來(lái)參數(shù)優(yōu)選的工具，稍后介紹；

3.svm-toy是一個(gè)可視化的工具，用來(lái)展示訓(xùn)練數(shù)據(jù)和分類界面，里面是源碼，其編譯后的程序在windows文件夾下；

4.tools—主要包含四個(gè)python文件，用來(lái)數(shù)據(jù)集抽樣(subset)，參數(shù)優(yōu)選（grid），集成測(cè)試(easy),數(shù)據(jù)檢查(checkdata)；

5.windows包含libSVM四個(gè)exe程序包，我們所用的庫(kù)就是他們。其中svm-scale.exe是用來(lái)對(duì)原始樣本進(jìn)行縮放的；svm-train.exe主要實(shí)現(xiàn)對(duì)訓(xùn)練數(shù)據(jù)集的訓(xùn)練，并可以獲得SVM模型；svmpredict是根據(jù)訓(xùn)練獲得的模型，對(duì)數(shù)據(jù)集合進(jìn)行預(yù)測(cè)。還有一個(gè)svm-toy.exe之前已經(jīng)交待過(guò)，是一個(gè)可視化工具。66LIBSVM介紹工具包里主要有5個(gè)文件夾：LIBSVM介紹libSVM的數(shù)據(jù)格式如下：Label1:value2:value…Label是類別的標(biāo)識(shí)，比如上節(jié)train.model中提到的1-1，你可以自己隨意定，比如-10，0，15。如果是回歸，這是目標(biāo)值，就要實(shí)事求是了。

Value就是要訓(xùn)練的數(shù)據(jù)，從分類的角度來(lái)說(shuō)就是特征值，數(shù)據(jù)之間用空格隔開，比如：

-151:0.7082:10563:-0.3333

需要注意的是，如果特征值為0，特征冒號(hào)前面的(姑且稱做序號(hào))可以不連續(xù)。如：

-151:0.7083:-0.3333

表明第2個(gè)特征值為0，從編程的角度來(lái)說(shuō)，這樣做可以減少內(nèi)存的使用，并提高做矩陣內(nèi)積時(shí)的運(yùn)算速度。67LIBSVM介紹libSVM的數(shù)據(jù)格式實(shí)驗(yàn)

實(shí)驗(yàn)樣本選擇工具包下存在的樣本文件：heart_scale。內(nèi)容截圖如下：68實(shí)驗(yàn)實(shí)驗(yàn)樣本選擇工具包下存在的樣本文件：h實(shí)驗(yàn)

訓(xùn)練：首先用svm-train進(jìn)行訓(xùn)練，輸入以下命令：svm-trainheart_scaletrain.model得到一個(gè)結(jié)果文件：train.model

69實(shí)驗(yàn)訓(xùn)練：首先用svm-train進(jìn)行訓(xùn)練，輸入以下命實(shí)驗(yàn)可以看到結(jié)果：optimizationfinished,#iter=162nu=0.431029obj=-100.877288,rho=0.424462nSV=132,nBSV=107TotalnSV=132

其中，#iter為迭代次數(shù)，nu是選擇的核函數(shù)類型的參數(shù)，obj為SVM文件轉(zhuǎn)換為的二次規(guī)劃求解得到的最小值，rho為判決函數(shù)的偏置項(xiàng)b，nSV為標(biāo)準(zhǔn)支持向量個(gè)數(shù)(0<a[i]<c)，nBSV為邊界上的支持向量個(gè)數(shù)(a[i]=c)，TotalnSV為支持向量總個(gè)數(shù)（對(duì)于兩類來(lái)說(shuō)，因?yàn)橹挥幸粋€(gè)分類模型TotalnSV=nSV，但是對(duì)于多類，這個(gè)是各個(gè)分類模型的nSV之和）。70實(shí)驗(yàn)可以看到結(jié)果：70實(shí)驗(yàn)train.model文件用記事本打開如下圖：

71實(shí)驗(yàn)train.model文件用記事本打開如下圖：71實(shí)驗(yàn)svm_typec_svc//所選擇的svm類型，默認(rèn)為c_svckernel_typerbf//訓(xùn)練采用的核函數(shù)類型，此處為RBF核

gamma0.0769231//RBF核的參數(shù)γnr_class2//類別數(shù)，此處為兩分類問(wèn)題

total_sv132//支持向量總個(gè)數(shù)

rho0.424462//判決函數(shù)的偏置項(xiàng)blabel1-1//原始文件中的類別標(biāo)識(shí)

nr_sv6468//每個(gè)類的支持向量機(jī)的個(gè)數(shù)

SV//以下為各個(gè)類的權(quán)系數(shù)及相應(yīng)的支持向量

11:0.1666672:13:-0.333333…10:-0.90322611:-112:-113:10.51048321289851641:0.1252:13:0.333333…10:-0.80645212:-0.33333313:0.5

………-11:-0.3752:13:-0.333333….10:-111:-112:-113:1-11:0.1666672:13:1….10:-0.87096812:-113:0.572實(shí)驗(yàn)svm_typec_svc實(shí)驗(yàn)

使用svm-predict，根據(jù)訓(xùn)練獲得的模型，對(duì)數(shù)據(jù)集合進(jìn)行預(yù)測(cè)。輸入命令：svm-predictheart_scale

heart_scale.modelheart_scale.out

得到準(zhǔn)確率是：86.667%。結(jié)果如下圖所示：73實(shí)驗(yàn)使用svm-predict，根據(jù)訓(xùn)實(shí)驗(yàn)74實(shí)驗(yàn)74Q&A問(wèn)答環(huán)節(jié)

敏而好學(xué)，不恥下問(wèn)。

學(xué)問(wèn)學(xué)問(wèn)，邊學(xué)邊問(wèn)。

He

is

quick

and

eager

to

learn.

Learning

is

learning

and

asking.75Q&A問(wèn)答環(huán)節(jié)

敏而好學(xué)，不恥下問(wèn)。

學(xué)問(wèn)學(xué)問(wèn)，邊學(xué)邊問(wèn)。

感謝參與本課程，也感激大家對(duì)我們工作的支持與積極的參與。課程后會(huì)發(fā)放課程滿意度評(píng)估表，如果對(duì)我們課程或者工作有什么建議和意見，也請(qǐng)寫在上邊結(jié)束語(yǔ)76感謝參與本課程，也感激大家對(duì)我們工作的支持與積極的參與。課程感謝您的觀看與聆聽本課件下載后可根據(jù)實(shí)際情況進(jìn)行調(diào)整77感謝您的觀看與聆聽本課件下載后可根據(jù)實(shí)際情況進(jìn)行調(diào)整77SupportVectorMachine

支持向量機(jī)

78SupportVectorMachine

支持向量機(jī)整體概述概述二點(diǎn)擊此處輸入相關(guān)文本內(nèi)容概述一點(diǎn)擊此處輸入相關(guān)文本內(nèi)容概述三點(diǎn)擊此處輸入相關(guān)文本內(nèi)容79整體概述概述二概述一概述三2

內(nèi)容SVM簡(jiǎn)介線性分類器核函數(shù)松弛變量LIBSVM介紹實(shí)驗(yàn)80內(nèi)容SVM簡(jiǎn)介3SVM簡(jiǎn)介支持向量機(jī)(SupportVectorMachine)是Cortes和Vapnik于1995年首先提出的，它在解決小樣本、非線性及高維模式識(shí)別中表現(xiàn)出許多特有的優(yōu)勢(shì)，并能夠推廣應(yīng)用到函數(shù)擬合等其他機(jī)器學(xué)習(xí)問(wèn)題中。

81SVM簡(jiǎn)介支持向量機(jī)(SupportVectorMachSVM簡(jiǎn)介支持向量機(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í)別任意樣本的能力）之間尋求最佳折衷，以期獲得最好的推廣能力（或稱泛化能力）。82SVM簡(jiǎn)介支持向量機(jī)方法是建立在統(tǒng)計(jì)學(xué)習(xí)理論的VC維理論和SVM簡(jiǎn)介VC維：所謂VC維是對(duì)函數(shù)類的一種度量，可以簡(jiǎn)單的理解為問(wèn)題的復(fù)雜程度，VC維越高，一個(gè)問(wèn)題就越復(fù)雜。正是因?yàn)镾VM關(guān)注的是VC維，后面我們可以看到，SVM解決問(wèn)題的時(shí)候，和樣本的維數(shù)是無(wú)關(guān)的（甚至樣本是上萬(wàn)維的都可以，這使得SVM很適合用來(lái)解決像文本分類這樣的問(wèn)題，當(dāng)然，有這樣的能力也因?yàn)橐肓撕撕瘮?shù)）。83SVM簡(jiǎn)介VC維：所謂VC維是對(duì)函數(shù)類的一種度量，可以簡(jiǎn)單的SVM簡(jiǎn)介結(jié)構(gòu)風(fēng)險(xiǎn)最小原理：就是追求“經(jīng)驗(yàn)風(fēng)險(xiǎn)”與“置信風(fēng)險(xiǎn)”的和最小。84SVM簡(jiǎn)介結(jié)構(gòu)風(fēng)險(xiǎn)最小原理：就是追求“經(jīng)驗(yàn)風(fēng)險(xiǎn)”與“置信風(fēng)險(xiǎn)SVM簡(jiǎn)介風(fēng)險(xiǎn)：機(jī)器學(xué)習(xí)本質(zhì)上就是一種對(duì)問(wèn)題真實(shí)模型的逼近（我們選擇一個(gè)我們認(rèn)為比較好的近似模型，這個(gè)近似模型就叫做一個(gè)假設(shè)），但毫無(wú)疑問(wèn)，真實(shí)模型一定是不知道的。既然真實(shí)模型不知道，那么我們選擇的假設(shè)與問(wèn)題真實(shí)解之間究竟有多大差距，我們就沒(méi)法得知。這個(gè)與問(wèn)題真實(shí)解之間的誤差，就叫做風(fēng)險(xiǎn)（更嚴(yán)格的說(shuō)，誤差的累積叫做風(fēng)險(xiǎn)）。85SVM簡(jiǎn)介風(fēng)險(xiǎn)：機(jī)器學(xué)習(xí)本質(zhì)上就是一種對(duì)問(wèn)題真實(shí)模型的逼近（SVM簡(jiǎn)介經(jīng)驗(yàn)風(fēng)險(xiǎn)Remp(w)

：我們選擇了一個(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)Remp(w)。86SVM簡(jiǎn)介經(jīng)驗(yàn)風(fēng)險(xiǎn)Remp(w)：我們選擇了一個(gè)假設(shè)之后（SVM簡(jiǎn)介

以前的一些機(jī)器學(xué)習(xí)方法把經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化作為努力的目標(biāo)，但后來(lái)發(fā)現(xiàn)很多分類函數(shù)能夠在樣本集上輕易達(dá)到100%的正確率，在真實(shí)分類時(shí)卻不好（即所謂的推廣能力差，或泛化能力差）。此時(shí)的情況是因?yàn)檫x擇了一個(gè)足夠復(fù)雜的分類函數(shù)（它的VC維很高），能夠精確的記住每一個(gè)樣本，但對(duì)樣本之外的數(shù)據(jù)一律分類錯(cuò)誤。因?yàn)榻?jīng)驗(yàn)風(fēng)險(xiǎn)最小化原則適用的大前提是經(jīng)驗(yàn)風(fēng)險(xiǎn)要確實(shí)能夠逼近真實(shí)風(fēng)險(xiǎn)才行。但實(shí)際上不太可能，經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化原則只在這占很小比例的樣本上做到?jīng)]有誤差，不能保證在更大比例的真實(shí)文本上也沒(méi)有誤差。87SVM簡(jiǎn)介以前的一些機(jī)器學(xué)習(xí)方法把經(jīng)驗(yàn)風(fēng)SVM簡(jiǎn)介泛化誤差界：為了解決剛才的問(wèn)題，統(tǒng)計(jì)學(xué)提出了泛化誤差界的概念。就是指真實(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)確的值（所以叫做泛化誤差界，而不叫泛化誤差）。88SVM簡(jiǎn)介泛化誤差界：為了解決剛才的問(wèn)題，統(tǒng)計(jì)學(xué)提出了泛化誤SVM簡(jiǎ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ì)變大。89SVM簡(jiǎn)介置信風(fēng)險(xiǎn)：與兩個(gè)量有關(guān)，一是樣本數(shù)量，顯然給定的樣SVM簡(jiǎ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)。此時(shí)目標(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)最小。90SVM簡(jiǎn)介泛化誤差界的公式為：13SVM簡(jiǎn)介小樣本：并不是說(shuō)樣本的絕對(duì)數(shù)量少（實(shí)際上，對(duì)任何算法來(lái)說(shuō)，更多的樣本幾乎總是能帶來(lái)更好的效果），而是說(shuō)與問(wèn)題的復(fù)雜度比起來(lái)，SVM算法要求的樣本數(shù)是相對(duì)比較少的。91SVM簡(jiǎn)介小樣本：并不是說(shuō)樣本的絕對(duì)數(shù)量少（實(shí)際上，對(duì)任何算SVM簡(jiǎn)介非線性：是指SVM擅長(zhǎng)應(yīng)付樣本數(shù)據(jù)線性不可分的情況，主要通過(guò)松弛變量（也叫懲罰變量）和核函數(shù)技術(shù)來(lái)實(shí)現(xiàn)，這一部分是SVM的核心內(nèi)容，后面會(huì)詳細(xì)說(shuō)明。92SVM簡(jiǎn)介非線性：是指SVM擅長(zhǎng)應(yīng)付樣本數(shù)據(jù)線性不可分的情況SVM簡(jiǎn)介高維模式識(shí)別：是指樣本維數(shù)很高，SVM也可以應(yīng)付。這主要是因?yàn)镾VM產(chǎn)生的分類器很簡(jiǎn)潔，用到的樣本信息很少（僅僅用到那些稱之為“支持向量”的樣本），使得即使樣本維數(shù)很高，也不會(huì)給存儲(chǔ)和計(jì)算帶來(lái)大麻煩。93SVM簡(jiǎn)介高維模式識(shí)別：是指樣本維數(shù)很高，SVM也可以應(yīng)付。線性分類器線性分類器：一定意義上，也可以叫做感知機(jī)，是最簡(jiǎn)單也很有效的分類器形式。在一個(gè)線性分類器中，可以看到SVM形成的思路，并接觸很多SVM的核心概念。下面舉例說(shuō)明。94線性分類器線性分類器：一定意義上，也可以叫做感知機(jī)，是最簡(jiǎn)線性分類器用一個(gè)二維空間里僅有兩類樣本的分類問(wèn)題來(lái)舉例子。如圖所示：C1和C2是要區(qū)分的兩個(gè)類別。中間的直線就是一個(gè)分類函數(shù)，它可以將兩類樣本完全分開。一般的，如果一個(gè)線性函數(shù)能夠?qū)颖就耆_的分開，就稱這些數(shù)據(jù)是線性可分的，否則稱為非線性可分的。

95線性分類器用一個(gè)二維空間里僅有兩類樣本的分類問(wèn)題來(lái)舉例子。如線性分類器線性函數(shù)在一維空間里就是一個(gè)點(diǎn)，在二維空間里就是一條直線，三維空間里就是一個(gè)平面，可以如此想象下去，如果不關(guān)注空間的維數(shù)，這種線性函數(shù)還有一個(gè)統(tǒng)一的名稱——超平面（HyperPlane）。96線性分類器線性函數(shù)19線性分類器例如我們有一個(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è)符號(hào)函數(shù)sgn()，即f(x)=sgn[g(x)]是我們真正的判別函數(shù)。97線性分類器例如我們有一個(gè)線性函數(shù)20線性分類器關(guān)于g(x)=wx+b這個(gè)表達(dá)式要注意三點(diǎn)：1.式中的x不是二維坐標(biāo)系中的橫軸，而是樣本的向量表示，例如一個(gè)樣本點(diǎn)的坐標(biāo)是(3,8)，則xT=(3,8)，而不是x=3（一般說(shuō)向量都是說(shuō)列向量）。2.這個(gè)形式并不局限于二維的情況，在n維空間中仍然可以使用這個(gè)表達(dá)式，只是式中的w成為了n維向量（在二維的這個(gè)例子中，w是二維向量，注意這里的w嚴(yán)格的說(shuō)也應(yīng)該是轉(zhuǎn)置的形式，為了表示起來(lái)方便簡(jiǎn)潔，以下均不區(qū)別列向量和它的轉(zhuǎn)置）。3.g(x)不是中間那條直線的表達(dá)式，中間那條直線的表達(dá)式是g(x)=0，即wx+b=0，我們也把這個(gè)函數(shù)叫做分類面。98線性分類器關(guān)于g(x)=wx+b這個(gè)表達(dá)式要注意三點(diǎn)：21線性分類器分類間隔：下圖中間那條分界線并不是唯一的，把它稍微旋轉(zhuǎn)一下，只要不把兩類數(shù)據(jù)分錯(cuò)，仍然可以達(dá)到上面說(shuō)的效果，稍微平移一下，也可以。此時(shí)就牽涉到一個(gè)問(wèn)題，對(duì)同一個(gè)問(wèn)題存在多個(gè)分類函數(shù)的時(shí)候，哪一個(gè)函數(shù)更好呢？顯然必須要先找一個(gè)指標(biāo)來(lái)量化“好”的程度，通常使用叫做“分類間隔”的指標(biāo)。

99線性分類器分類間隔：下圖中間那條分界線并不是唯一的，把它稍線性分類器

比如在進(jìn)行文本分類的時(shí)候，我們可以讓計(jì)算機(jī)這樣來(lái)看待我們提供給它的訓(xùn)練樣本，每一個(gè)樣本由一個(gè)向量（就是那些文本特征所組成的向量）和一個(gè)標(biāo)記（標(biāo)示出這個(gè)樣本屬于哪個(gè)類別）組成。如下：Di=(xi,yi)

xi就是文本向量（維數(shù)很高），yi就是分類標(biāo)記。100線性分類器比如在進(jìn)行文本分類的時(shí)候，我們可線性分類器

在二元的線性分類中，這個(gè)表示分類的標(biāo)記只有兩個(gè)值，1和-1（用來(lái)表示屬于還是不屬于這個(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)|。101線性分類器在二元的線性分類中，這個(gè)表示分線性分類器

現(xiàn)在把w和b進(jìn)行歸一化處理，即用w/||w||和b/||w||分別代替原來(lái)的w和b，那么間隔就可以寫成：

這就是解析幾何中點(diǎn)xi到直線g(x)=0的距離公式，也就是到超平面g(x)=0的距離。

102線性分類器現(xiàn)在把w和b進(jìn)行歸一化處理，即用w線性分類器||w||叫做向量w的范數(shù)，范數(shù)是對(duì)向量長(zhǎng)度的一種度量。我們常說(shuō)的向量長(zhǎng)度其實(shí)指的是它的2-范數(shù)，范數(shù)最一般的表示形式為p-范數(shù)，可以寫成如下表達(dá)式向量w=(w1,w2,w3,……wn)它的p-范數(shù)為：當(dāng)我們不指明p的時(shí)候，就意味著我們不關(guān)心p的值，用幾范數(shù)都可以。當(dāng)用歸一化的w和b代替原值之后的間隔有一個(gè)專門的名稱，叫幾何間隔，表示的是點(diǎn)到超平面的歐氏距離。103線性分類器||w||叫做向量w的范數(shù)，范數(shù)是對(duì)向量長(zhǎng)度線性分類器

下面這張圖直觀的展示出了幾何間隔的現(xiàn)實(shí)含義：

H是分類面，而H1和H2是平行于H，且過(guò)離H最近的兩類樣本的直線，H1與H，H2與H之間的距離就是幾何間隔。104線性分類器下面這張圖直觀的展示出了幾何間隔的線性分類器

之所以如此關(guān)心幾何間隔這個(gè)東西，是因?yàn)閹缀伍g隔與樣本的誤分次數(shù)間存在關(guān)系：

其中的δ是樣本集合到分類面的幾何間隔，R=max||xi||

i=1,...,n，即R是所有樣本中向量長(zhǎng)度最長(zhǎng)的值（也就是說(shuō)代表樣本的分布有多么廣）。誤分次數(shù)一定程度上代表分類器的誤差。而從上式可以看出，在樣本已知的情況下，誤分次數(shù)的上界由幾何間隔決定！幾何間隔越大的解，它的誤差上界越小。因此最大化幾何間隔成了訓(xùn)練階段的目標(biāo)。105線性分類器之所以如此關(guān)心幾何間隔這個(gè)東西線性分類器間隔：δ=y(wx+b)=|g(x)|幾何間隔：

可以看出δ=||w||δ幾何。幾何間隔與||w||是成反比的，因此最大化幾何間隔與最小化||w||完全是一回事。而我們常用的方法并不是固定||w||的大小而尋求最大幾何間隔，而是把所有樣本點(diǎn)中間隔最小的那一點(diǎn)的間隔固定（例如固定為1），尋找最小的||w||。106線性分類器間隔：δ=y(wx+b)=|g(x)|29線性分類器

如果直接來(lái)解這個(gè)求最小值問(wèn)題，當(dāng)||w||=0的時(shí)候就得到了目標(biāo)函數(shù)的最小值。但是無(wú)論給什么樣的數(shù)據(jù)，都是這個(gè)解！反映在圖中，就是H1與H2兩條直線間的距離無(wú)限大，這個(gè)時(shí)候，所有的樣本點(diǎn)都跑到了H1和H2中間，進(jìn)入了無(wú)法分類的灰色地帶。

造成這種結(jié)果的原因是在描述問(wèn)題的時(shí)候只考慮了目標(biāo)，而沒(méi)有加入約束條件。107線性分類器如果直接來(lái)解這個(gè)求最小值問(wèn)題，線性分類器

之前把所有樣本點(diǎn)中間隔最小的那一點(diǎn)的間隔定為1，這就相當(dāng)于讓下面的式子總是成立：

yi[(w·xi)+b]≥1(i=1,2,…,l)（l是總的樣本數(shù)）即：

yi[(w·xi)+b]-1≥0(i=1,2,…,l)（l是總的樣本數(shù)）因此我們的兩類分類問(wèn)題也被我們轉(zhuǎn)化成了它的數(shù)學(xué)形式，一個(gè)帶約束的最小值的問(wèn)題：

108線性分類器之前把所有樣本點(diǎn)中間隔最小的那線性分類器

從最一般的定義上說(shuō)，一個(gè)求最小值的問(wèn)題就是一個(gè)優(yōu)化問(wèn)題（也叫規(guī)劃），它同樣由兩部分組成，目標(biāo)函數(shù)和約束條件，可以用下面的式子表示：

約束條件用函數(shù)c來(lái)表示，就是constrain的意思。一共有p+q個(gè)約束條件，其中p個(gè)是不等式約束，q個(gè)等式約束。109線性分類器從最一般的定義上說(shuō)，一個(gè)求最小線性分類器

這個(gè)式子中的x是自變量，但不限定它的維數(shù)必須為1（視乎你解決的問(wèn)題空間維數(shù)）。要求f(x)在哪一點(diǎn)上取得最小值，但不是在整個(gè)空間里找，而是在約束條件所劃定的可行域里找。注意可行域中的每一個(gè)點(diǎn)都要求滿足所有p+q個(gè)條件，同時(shí)可行域邊界上的點(diǎn)有一個(gè)額外好的特性，它們可以使不等式約束取得等號(hào)！而邊界內(nèi)的點(diǎn)不行。110線性分類器33線性分類器

這對(duì)一般的優(yōu)化問(wèn)題可能提供不了什么幫助，但對(duì)SVM來(lái)說(shuō)，邊界上的點(diǎn)有其特殊意義，實(shí)際上是它們唯一決定了分類超平面，這些點(diǎn)（就是以前的圖中恰好落在H1和H2上的點(diǎn)，在文本分類問(wèn)題中，每一個(gè)點(diǎn)代表一個(gè)文檔，因而這個(gè)點(diǎn)本身也是一個(gè)向量）就被稱為支持向量。111線性分類器這對(duì)一般的優(yōu)化問(wèn)題可能提供不了什線性分類器

回頭再看線性分類器問(wèn)題的描述：

在這個(gè)問(wèn)題中，自變量就是w，目標(biāo)函數(shù)是w的二次函數(shù)，所有的約束條件都是w的線性函數(shù)（不要把xi當(dāng)成變量，它代表樣本，是已知的），這種規(guī)劃問(wèn)題也叫做二次規(guī)劃（QuadraticProgramming，QP）。而且，由于它的可行域是一個(gè)凸集，因此它是一個(gè)凸二次規(guī)劃。凸二次規(guī)劃的優(yōu)點(diǎn)在于它有全局最優(yōu)解。112線性分類器回頭再看線性分類器問(wèn)題的描述：線性分類器

但是實(shí)際上我們并不知道該怎么解一個(gè)帶約束的優(yōu)化問(wèn)題。我們可以輕松的解一個(gè)不帶任何約束的優(yōu)化問(wèn)題（實(shí)際上就是函數(shù)求極值，求導(dǎo)再找0點(diǎn)），我們甚至還會(huì)解一個(gè)只帶等式約束的優(yōu)化問(wèn)題，就是求條件極值，通過(guò)添加拉格朗日乘子，構(gòu)造拉格朗日函數(shù)，來(lái)把這個(gè)問(wèn)題轉(zhuǎn)化為無(wú)約束的優(yōu)化問(wèn)題。如果只帶等式約束的問(wèn)題可以轉(zhuǎn)化為無(wú)約束的問(wèn)題來(lái)求解，那么可不可以把帶不等式約束的問(wèn)題向只帶等式約束的問(wèn)題轉(zhuǎn)化而得以求解呢？答案是可以。113線性分類器但是實(shí)際上我們并不知道該怎么解線性分類器

我們想求得這樣一個(gè)線性函數(shù)（在n維空間中的線性函數(shù)）：g(x)=wx+b

求g(x)的過(guò)程就是求w（一個(gè)n維向量）和b（一個(gè)實(shí)數(shù)）兩個(gè)參數(shù)的過(guò)程（但實(shí)際上只需要求w，求得以后找某些樣本點(diǎn)代入就可以求得b）。因此在求g(x)的時(shí)候，w才是變量。114線性分類器我們想求得這樣一個(gè)線性函數(shù)（在n線性分類器

樣本確定了w，用數(shù)學(xué)的語(yǔ)言描述，就是w可以表示為樣本的某種組合：w=α1x1+α2x2+…+αnxn

式子中的αi是一個(gè)一個(gè)的數(shù)（在嚴(yán)格的證明過(guò)程中，這些α被稱為拉格朗日乘子），而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>+b115線性分類器樣本確定了w，用數(shù)學(xué)的語(yǔ)言描述，線性分類器

但是上面的式子還不夠好，如果我不動(dòng)所有點(diǎn)的位置，而只是把其中一個(gè)正樣本點(diǎn)定為負(fù)樣本點(diǎn)（也就是把一個(gè)點(diǎn)的形狀從圓形變?yōu)榉叫危敲慈龡l直線都必須移動(dòng)。這說(shuō)明w不僅跟樣本點(diǎn)的位置有關(guān)，還跟樣本的類別有關(guān)因此用下面這個(gè)式子表示才算完整：w=α1y1x1+α2y2x2+…+αnynxn

其中的yi就是第i個(gè)樣本的標(biāo)簽，它等于1或者-1。其實(shí)以上式子的不等于0（不等于0才對(duì)w起決那一堆拉格朗日乘子中，只有很少的一部分定作用），這部分不等于0的拉格朗日乘子后面所乘的樣本點(diǎn)，其實(shí)都落在H1和H2上，也正是這部分樣本唯一的確定了分類函數(shù)。更嚴(yán)格的說(shuō)，這些樣本的一部分就可以確定，因?yàn)槔绱_定一條直線，只需要兩個(gè)點(diǎn)就可以。這部分樣本點(diǎn)，就叫做支持（撐）向量！

116線性分類器但是上面的式子還不夠好，線性分類器

式子也可以用求和符號(hào)簡(jiǎn)寫一下：

因此原來(lái)的g(x)表達(dá)式可以寫為：

注意式子中x才是變量，如果要分類哪篇文檔，就把該文檔的向量表示代入到x的位置，而所有的xi統(tǒng)統(tǒng)都是已知的樣本。還注意到式子中只有xi和x是向量，因此一部分可以從內(nèi)積符號(hào)中拿出來(lái)，得到g(x)的式子為：

117線性分類器

式子也可以用求和符號(hào)簡(jiǎn)寫一下：線性分類器

至此w不見了，從求w變成了求α?？此茮](méi)有簡(jiǎn)化問(wèn)題，其實(shí)簡(jiǎn)化了原來(lái)的問(wèn)題，因?yàn)橐赃@樣的形式描述問(wèn)題以后，我們的優(yōu)化了不等式約束。之后的求解就變得很容易了。下面遇到一個(gè)問(wèn)題：如果提供的樣本線性不可分，怎么辦？所以必須要提到SVM中比較重要的內(nèi)容——核函數(shù)。118線性分類器至此w不見了，從求w變成了求α。核函數(shù)

之前一直在討論的線性分類器。如果提供的樣本線性不可分，結(jié)果很簡(jiǎn)單，線性分類器的求解程序會(huì)無(wú)限循環(huán)，永遠(yuǎn)也解不出來(lái)。這必然使得它的適用范圍大大縮小，而它的很多優(yōu)點(diǎn)我們實(shí)在不原意放棄，那么就必須尋找讓線性不可分的數(shù)據(jù)變得線性可分的方法。119核函數(shù)之前一直在討論的線性分類器。如果提核函數(shù)

用一個(gè)二維平面中的分類問(wèn)題作例子，如圖：把橫軸上端點(diǎn)a和b之間紅色部分里的所有點(diǎn)定為正類，兩邊的黑色部分里的點(diǎn)定為負(fù)類。試問(wèn)能找到一個(gè)線性函數(shù)把兩類正確分開么？不能，因?yàn)槎S空間里的線性函數(shù)就是指直線，顯然找不到符合條件的直線。120核函數(shù)用一個(gè)二維平面中的分類問(wèn)題作例子，如圖核函數(shù)

但我們可以找到一條曲線，例如下面這一條：

顯然通過(guò)點(diǎn)在這條曲線的上方還是下方就可以判斷點(diǎn)所屬的類別。這條曲線就是我們熟知的二次曲線，它的函數(shù)表達(dá)式是：121核函數(shù)但我們可以找到一條曲線，例如下面這一條：核函數(shù)

問(wèn)題只是它不是一個(gè)線性函數(shù)，但是，做一下變換，新建一個(gè)向量y和a：這樣g(x)就可以轉(zhuǎn)化為f(y)=<a,y>，你可以把y和a分別回帶一下，看看等不等于原來(lái)的g(x)。用內(nèi)積的形式寫你可能看不太清楚，實(shí)際上f(y)的形式就是：g(x)=f(y)=ay

在任意維度的空間中，這種形式的函數(shù)都是一個(gè)線性函數(shù)，因?yàn)樽宰兞縴的次數(shù)不大于1。原來(lái)在二維空間中一個(gè)線性不可分的問(wèn)題，映射到高維空間后，變成了線性可分的！因此也形成了我們最初想解決線性不可分問(wèn)題的基本思路——向高維空間轉(zhuǎn)化，使其變得線性可分。122核函數(shù)問(wèn)題只是它不是一個(gè)線性函數(shù)，但是，核函數(shù)

用一個(gè)具體文本分類的例子來(lái)看看這種向高維空間映射從而分類的方法如何運(yùn)作，如果我們文本分類問(wèn)題的原始空間是1000維的（即每個(gè)要被分類的文檔被表示為一個(gè)1000維的向量），在這個(gè)維度上問(wèn)題是線性不可分的?，F(xiàn)在我們有一個(gè)2000維空間里的線性函數(shù)f(x’)=<w’,x’>+b

它能夠?qū)⒃瓎?wèn)題變得可分。式中的w’和x’都是2000維的向量，只不過(guò)w’是定值，而x’是變量?，F(xiàn)在我們的輸入呢，是一個(gè)1000維的向量x，分類的過(guò)程是先把x變換為2000維的向量x’，然后求這個(gè)變換后的向量x’與向量w’的內(nèi)積，再把這個(gè)內(nèi)積的值和b相加，就得到了結(jié)果，看結(jié)果大于閾值還是小于閾值就得到了分類結(jié)果。123核函數(shù)用一個(gè)具體文本分類的例子來(lái)看看這核函數(shù)

所以只需要關(guān)心那個(gè)高維空間里內(nèi)積的值。而從理論上說(shuō)，x’是經(jīng)由x變換來(lái)的，因此廣義上可以把它叫做x的函數(shù)（因?yàn)橛幸粋€(gè)x，就確定了一個(gè)x’），而w’是常量，它是一個(gè)低維空間里的常量w經(jīng)過(guò)變換得到的，所以給了一個(gè)w和x的值，就有一個(gè)確定的f(x’)值與其對(duì)應(yīng)。所以，需要這樣一種函數(shù)K(w,x),他接受低維空間的輸入值，卻能算出高維空間的內(nèi)積值<w’,x’>。也就是當(dāng)給了一個(gè)低維空間的輸入x以后：g(x)=K(w,x)+bf(x’)=<w’,x’>+b

這兩個(gè)函數(shù)的計(jì)算結(jié)果就完全一樣，我們也就用不著費(fèi)力找那個(gè)映射關(guān)系，直接拿低維的輸入往g(x)里面代就可以了。124核函數(shù)所以只需要關(guān)心那個(gè)高維空核函數(shù)

這樣的函數(shù)確實(shí)存在，它被稱作核函數(shù)（核，kernel），而且不止一個(gè)，事實(shí)上，只要是滿足了Mercer條件的函數(shù)，都可以作為核函數(shù)。核函數(shù)的基本作用就