SupportVectorMachine

支持向量機(jī)

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

第3頁(yè)SVM介紹支持向量機(jī)辦法是建立在統(tǒng)計(jì)學(xué)習(xí)理論VC維理論和構(gòu)造風(fēng)險(xiǎn)最小原理基礎(chǔ)上，根據(jù)有限樣本信息在模型復(fù)雜性（即對(duì)特定訓(xùn)練樣本學(xué)習(xí)精度，Accuracy）和學(xué)習(xí)能力（即無(wú)錯(cuò)誤地識(shí)別任意樣本能力）之間謀求最佳折衷，以期取得最佳推廣能力（或稱泛化能力）。第4頁(yè)SVM介紹VC維：所謂VC維是對(duì)函數(shù)類(lèi)一種度量，能夠簡(jiǎn)單理解為問(wèn)題復(fù)雜程度，VC維越高，一種問(wèn)題就越復(fù)雜。正是由于SVM關(guān)注是VC維，背面我們能夠看到，SVM處理問(wèn)題時(shí)候，和樣本維數(shù)是無(wú)關(guān)（甚至樣本是上萬(wàn)維都能夠，這使得SVM很適適用來(lái)處理像文本分類(lèi)這樣問(wèn)題，當(dāng)然，有這樣能力也由于引入了核函數(shù)）。第5頁(yè)SVM介紹構(gòu)造風(fēng)險(xiǎn)最小原理：就是追求“經(jīng)驗(yàn)風(fēng)險(xiǎn)”與“置信風(fēng)險(xiǎn)”和最小。第6頁(yè)SVM介紹風(fēng)險(xiǎn)：機(jī)器學(xué)習(xí)本質(zhì)上就是一種對(duì)問(wèn)題真實(shí)模型逼近（我們選擇一種我們以為比較好近似模型，這個(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)）。第7頁(yè)SVM介紹經(jīng)驗(yàn)風(fēng)險(xiǎn)Remp(w)：我們選擇了一種假設(shè)之后（更直觀點(diǎn)說(shuō)，我們得到了一種分類(lèi)器后來(lái)），真實(shí)誤差無(wú)從得知，但我們能夠用某些能夠掌握量來(lái)逼近它。最直觀想法就是使用分類(lèi)器在樣本數(shù)據(jù)上分類(lèi)成果與真實(shí)成果（由于樣本是已經(jīng)標(biāo)注過(guò)數(shù)據(jù)，是精確數(shù)據(jù)）之間差值來(lái)表達(dá)。這個(gè)差值叫做經(jīng)驗(yàn)風(fēng)險(xiǎn)Remp(w)。第8頁(yè)SVM介紹此前某些機(jī)器學(xué)習(xí)辦法把經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化作為努力目標(biāo)，但后來(lái)發(fā)覺(jué)很多分類(lèi)函數(shù)能夠在樣本集上容易達(dá)成100%正確率，在真實(shí)分類(lèi)時(shí)卻不好（即所謂推廣能力差，或泛化能力差）。此時(shí)情況是由于選擇了一種足夠復(fù)雜分類(lèi)函數(shù)（它VC維很高），能夠精確記住每一種樣本，但對(duì)樣本之外數(shù)據(jù)一律分類(lèi)錯(cuò)誤。由于經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化標(biāo)準(zhǔn)適用大前提是經(jīng)驗(yàn)風(fēng)險(xiǎn)要確實(shí)能夠逼近真實(shí)風(fēng)險(xiǎn)才行。但事實(shí)上不太也許，經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化標(biāo)準(zhǔn)只在這占很小百分比樣本上做到?jīng)]有誤差，不能確保在更大百分比真實(shí)文本上也沒(méi)有誤差。第9頁(yè)SVM介紹泛化誤差界：為理解決剛才問(wèn)題，統(tǒng)計(jì)學(xué)提出了泛化誤差界概念。就是指真實(shí)風(fēng)險(xiǎn)應(yīng)當(dāng)由兩部分內(nèi)容刻畫(huà)，一是經(jīng)驗(yàn)風(fēng)險(xiǎn)，代表了分類(lèi)器在給定樣本上誤差；二是置信風(fēng)險(xiǎn)，代表了我們?cè)诙啻蟪潭壬峡梢孕湃畏诸?lèi)器在未知樣本上分類(lèi)結(jié)果。很顯然，第二部分是沒(méi)有辦法精確計(jì)算，因此只能給出一個(gè)估計(jì)區(qū)間，也使得整個(gè)誤差只能計(jì)算上界，而無(wú)法計(jì)算準(zhǔn)確值（因此叫做泛化誤差界，而不叫泛化誤差）。第10頁(yè)SVM介紹置信風(fēng)險(xiǎn)：與兩個(gè)量有關(guān)，一是樣本數(shù)量，顯然給定樣本數(shù)量越大，我們學(xué)習(xí)成果越有也許正確，此時(shí)置信風(fēng)險(xiǎn)越小；二是分類(lèi)函數(shù)VC維，顯然VC維越大，推廣能力越差，置信風(fēng)險(xiǎn)會(huì)變大。第11頁(yè)SVM介紹泛化誤差界公式為：R(w)≤Remp(w)+Ф(n/h)公式中R(w)就是真實(shí)風(fēng)險(xiǎn)，Remp(w)表達(dá)經(jīng)驗(yàn)風(fēng)險(xiǎn)，Ф(n/h)表達(dá)置信風(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)和最小，即構(gòu)造風(fēng)險(xiǎn)最小。第12頁(yè)SVM介紹小樣本：并不是說(shuō)樣本絕對(duì)數(shù)量少（事實(shí)上，對(duì)任何算法來(lái)說(shuō)，更多樣本幾乎總是能帶來(lái)更加好效果），而是說(shuō)與問(wèn)題復(fù)雜度比起來(lái)，SVM算法要求樣本數(shù)是相對(duì)比較少。第13頁(yè)SVM介紹非線性：是指SVM擅長(zhǎng)應(yīng)付樣本數(shù)據(jù)線性不可分情況，主要通過(guò)松弛變量（也叫處罰變量）和核函數(shù)技術(shù)來(lái)實(shí)現(xiàn)，這一部分是SVM關(guān)鍵內(nèi)容，背面會(huì)詳細(xì)說(shuō)明。第14頁(yè)SVM介紹高維模式識(shí)別：是指樣本維數(shù)很高，SVM也能夠應(yīng)付。這主要是由于SVM產(chǎn)生分類(lèi)器很簡(jiǎn)潔，用到樣本信息很少（僅僅用到那些稱之為“支持向量”樣本），使得雖然樣本維數(shù)很高，也不會(huì)給存放和計(jì)算帶來(lái)大麻煩。第15頁(yè)線性分類(lèi)器線性分類(lèi)器：一定意義上，也能夠叫做感知機(jī)，是最簡(jiǎn)單也很有效分類(lèi)器形式。在一種線性分類(lèi)器中，能夠看到SVM形成思緒，并接觸很多SVM關(guān)鍵概念。下面舉例說(shuō)明。第16頁(yè)線性分類(lèi)器用一種二維空間里僅有兩類(lèi)樣本分類(lèi)問(wèn)題來(lái)舉例子。如圖所示：C1和C2是要辨別兩個(gè)類(lèi)別。中間直線就是一種分類(lèi)函數(shù)，它能夠?qū)深?lèi)樣本完全分開(kāi)。一般，假如一種線性函數(shù)能夠?qū)颖就耆_分開(kāi)，就稱這些數(shù)據(jù)是線性可分，不然稱為非線性可分。

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

第21頁(yè)線性分類(lèi)器例如在進(jìn)行文本分類(lèi)時(shí)候，我們能夠讓計(jì)算機(jī)這樣來(lái)看待我們提供應(yīng)它訓(xùn)練樣本，每一種樣本由一種向量（就是那些文本特性所組成向量）和一種標(biāo)識(shí)（標(biāo)示出這個(gè)樣本屬于哪個(gè)類(lèi)別）組成。如下：Di=(xi,yi)xi就是文本向量（維數(shù)很高），yi就是分類(lèi)標(biāo)識(shí)。第22頁(yè)線性分類(lèi)器在二元線性分類(lèi)中，這個(gè)表達(dá)分類(lèi)標(biāo)識(shí)只有兩個(gè)值，1和-1（用來(lái)表達(dá)屬于還是不屬于這個(gè)類(lèi)）。有了這種表達(dá)法，我們就能夠定義一種樣本點(diǎn)到某個(gè)超平面間隔：δi=yi(wxi+b)首先假如某個(gè)樣本屬于該類(lèi)別話，那么wxi+b>0，而yi也大于0；若不屬于該類(lèi)別話，那么wxi+b<0，而yi也不大于0，這意味著yi(wxi+b)總是大于0，并且它值就等于|wxi+b|，也就是|g(xi)|。第23頁(yè)線性分類(lèi)器

目前把w和b進(jìn)行歸一化處理，即用w/||w||和b/||w||分別替代本來(lái)w和b，那么間隔就能夠?qū)懗桑?/p>

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

第24頁(yè)線性分類(lèi)器||w||叫做向量w范數(shù)，范數(shù)是對(duì)向量長(zhǎng)度一種度量。我們常說(shuō)向量長(zhǎng)度其實(shí)指是它2-范數(shù)，范數(shù)最一般表達(dá)形式為p-范數(shù)，能夠?qū)懗扇缦麦w現(xiàn)式向量w=(w1,w2,w3,……wn)它p-范數(shù)為：當(dāng)我們不指明p時(shí)候，就意味著我們不關(guān)懷p值，用幾范數(shù)都能夠。當(dāng)用歸一化w和b替代原值之后間隔有一種專(zhuān)門(mén)名稱，叫幾何間隔，表達(dá)是點(diǎn)到超平面歐氏距離。第25頁(yè)線性分類(lèi)器下面這張圖直觀展示出了幾何間隔現(xiàn)實(shí)含義：H是分類(lèi)面，而H1和H2是平行于H，且過(guò)離H近來(lái)兩類(lèi)樣本直線，H1與H，H2與H之間距離就是幾何間隔。第26頁(yè)線性分類(lèi)器之因此如此關(guān)懷幾何間隔這個(gè)東西，是由于幾何間隔與樣本誤分次數(shù)間存在關(guān)系：

其中δ是樣本集合到分類(lèi)面幾何間隔，R=max||xi||i=1,...,n，即R是所有樣本中向量長(zhǎng)度最長(zhǎng)值（也就是說(shuō)代表樣本分布有多么廣）。誤分次數(shù)一定程度上代表分類(lèi)器誤差。而從上式能夠看出，在樣本已知情況下，誤分次數(shù)上界由幾何間隔決定！幾何間隔越大解，它誤差上界越小。因此最大化幾何間隔成了訓(xùn)練階段目標(biāo)。第27頁(yè)線性分類(lèi)器間隔：δ=y(wx+b)=|g(x)|幾何間隔：

能夠看出δ=||w||δ幾何。幾何間隔與||w||是成反比，因此最大化幾何間隔與最小化||w||完全是一回事。而我們常用辦法并不是固定||w||大小而謀求最大幾何間隔，而是把所有樣本點(diǎn)中間隔最小那一點(diǎn)間隔固定（例如固定為1），尋找最小||w||。第28頁(yè)線性分類(lèi)器假如直接來(lái)解這個(gè)求最小值問(wèn)題，當(dāng)||w||=0時(shí)候就得到了目標(biāo)函數(shù)最小值。不過(guò)無(wú)論給什么樣數(shù)據(jù)，都是這個(gè)解！反應(yīng)在圖中，就是H1與H2兩條直線間距離無(wú)限大，這個(gè)時(shí)候，所有樣本點(diǎn)都跑到了H1和H2中間，進(jìn)入了無(wú)法分類(lèi)灰色地帶。

造成這種成果原因是在描述問(wèn)題時(shí)候只考慮了目標(biāo)，而沒(méi)有加入約束條件。第29頁(yè)線性分類(lèi)器之前把所有樣本點(diǎn)中間隔最小那一點(diǎn)間隔定為1，這就相稱于讓下面式子總是成立：yi[(w·xi)+b]≥1(i=1,2,…,l)（l是總樣本數(shù)）即：yi[(w·xi)+b]-1≥0(i=1,2,…,l)（l是總樣本數(shù)）因此我們兩類(lèi)分類(lèi)問(wèn)題也被我們轉(zhuǎn)化成了它數(shù)學(xué)形式，一種帶約束最小值問(wèn)題：

第30頁(yè)線性分類(lèi)器從最一般定義上說(shuō)，一種求最小值問(wèn)題就是一種優(yōu)化問(wèn)題（也叫規(guī)劃），它同樣由兩部分組成，目標(biāo)函數(shù)和約束條件，能夠用下面式子表達(dá)：

約束條件用函數(shù)c來(lái)表達(dá)，就是constrain意思。一共有p+q個(gè)約束條件，其中p個(gè)是不等式約束，q個(gè)等式約束。第31頁(yè)線性分類(lèi)器這個(gè)式子中x是自變量，但不限定它維數(shù)必須為1（視乎你處理問(wèn)題空間維數(shù)）。要求f(x)在哪一點(diǎn)上取得最小值，但不是在整個(gè)空間里找，而是在約束條件所劃定可行域里找。注意可行域中每一種點(diǎn)都要求滿足所有p+q個(gè)條件，同步可行域邊界上點(diǎn)有一種額外好特性，它們能夠使不等式約束取得等號(hào)！而邊界內(nèi)點(diǎn)不行。第32頁(yè)線性分類(lèi)器這對(duì)一般優(yōu)化問(wèn)題也許提供不了什么幫助，但對(duì)SVM來(lái)說(shuō)，邊界上點(diǎn)有其特殊意義，事實(shí)上是它們唯一決定了分類(lèi)超平面，這些點(diǎn)（就是此前圖中正好落在H1和H2上點(diǎn)，在文本分類(lèi)問(wèn)題中，每一種點(diǎn)代表一種文檔，因而這個(gè)點(diǎn)本身也是一種向量）就被稱為支持向量。第33頁(yè)線性分類(lèi)器回頭再看線性分類(lèi)器問(wèn)題描述：

在這個(gè)問(wèn)題中，自變量就是w，目標(biāo)函數(shù)是w二次函數(shù)，所有約束條件都是w線性函數(shù)（不要把xi當(dāng)成變量，它代表樣本，是已知），這種規(guī)劃問(wèn)題也叫做二次規(guī)劃（QuadraticProgramming，QP）。并且，由于它可行域是一種凸集，因此它是一種凸二次規(guī)劃。凸二次規(guī)劃長(zhǎng)處在于它有全局最優(yōu)解。第34頁(yè)線性分類(lèi)器不過(guò)事實(shí)上我們并不懂得該怎么解一種帶約束優(yōu)化問(wèn)題。我們能夠輕松解一種不帶任何約束優(yōu)化問(wèn)題（事實(shí)上就是函數(shù)求極值，求導(dǎo)再找0點(diǎn)），我們甚至還會(huì)解一種只帶等式約束優(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)化而得以求解呢？答案是能夠。第35頁(yè)線性分類(lèi)器我們想求得這樣一種線性函數(shù)（在n維空間中線性函數(shù)）：g(x)=wx+b求g(x)過(guò)程就是求w（一種n維向量）和b（一種實(shí)數(shù)）兩個(gè)參數(shù)過(guò)程（但事實(shí)上只需要求w，求得后來(lái)找某些樣本點(diǎn)代入就能夠求得b）。因此在求g(x)時(shí)候，w才是變量。第36頁(yè)線性分類(lèi)器樣本確定了w，用數(shù)學(xué)語(yǔ)言描述，就是w能夠表達(dá)為樣本某種組合：w=α1x1+α2x2+…+αnxn

式子中αi是一種一種數(shù)（在嚴(yán)格證明過(guò)程中，這些α被稱為拉格朗日乘子），而xi是樣本點(diǎn)，因而是向量，n就是總樣本點(diǎn)個(gè)數(shù)。為了方便描述，下列開(kāi)始嚴(yán)格區(qū)分?jǐn)?shù)字與向量乘積和向量間乘積，用α1x1表達(dá)數(shù)字和向量乘積，而用<x1,x2>表達(dá)向量x1,x2內(nèi)積。因此g(x)體現(xiàn)式嚴(yán)格形式應(yīng)當(dāng)是：g(x)=<w,x>+b第37頁(yè)線性分類(lèi)器

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

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

第38頁(yè)線性分類(lèi)器

式子也能夠用求和符號(hào)簡(jiǎn)寫(xiě)一下：

因此本來(lái)g(x)體現(xiàn)式能夠?qū)憺椋?/p>

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

第39頁(yè)線性分類(lèi)器至此w不見(jiàn)了，從求w變成了求α。看似沒(méi)有簡(jiǎn)化問(wèn)題，其實(shí)簡(jiǎn)化了本來(lái)問(wèn)題，由于以這樣形式描述問(wèn)題后來(lái)，我們優(yōu)化了不等式約束。之后求解就變得很容易了。下面遇到一種問(wèn)題：假如提供樣本線性不可分，怎么辦？因此必須要提到SVM中比較主要內(nèi)容——核函數(shù)。第40頁(yè)核函數(shù)之前始終在討論線性分類(lèi)器。假如提供樣本線性不可分，成果很簡(jiǎn)單，線性分類(lèi)器求解程序會(huì)無(wú)限循環(huán)，永遠(yuǎn)也解不出來(lái)。這必然使得它適用范圍大大縮小，而它很多長(zhǎng)處我們實(shí)在不原意放棄，那么就必須尋找讓線性不可分?jǐn)?shù)據(jù)變得線性可分辦法。第41頁(yè)核函數(shù)用一種二維平面中分類(lèi)問(wèn)題作例子，如圖：把橫軸上端點(diǎn)a和b之間紅色部分里所有點(diǎn)定為正類(lèi)，兩邊黑色部分里點(diǎn)定為負(fù)類(lèi)。試問(wèn)能找到一種線性函數(shù)把兩類(lèi)正確分開(kāi)么？不能，由于二維空間里線性函數(shù)就是指直線，顯然找不到符合條件直線。第42頁(yè)核函數(shù)

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

顯然通過(guò)點(diǎn)在這條曲線上方還是下方就能夠判斷點(diǎn)所屬類(lèi)別。這條曲線就是我們熟知二次曲線，它函數(shù)體現(xiàn)式是：第43頁(yè)核函數(shù)問(wèn)題只是它不是一種線性函數(shù)，不過(guò)，做一下變換，新建一種向量y和a：這樣g(x)就能夠轉(zhuǎn)化為f(y)=<a,y>，你能夠把y和a分別回帶一下，看看等不等于本來(lái)g(x)。用內(nèi)積形式寫(xiě)你也許看不太清楚，事實(shí)上f(y)形式就是：g(x)=f(y)=ay在任意維度空間中，這種形式函數(shù)都是一種線性函數(shù)，由于自變量y次數(shù)不大于1。本來(lái)在二維空間中一種線性不可分問(wèn)題，映射到高維空間后，變成了線性可分！因此也形成了我們最初想處理線性不可分問(wèn)題基本思緒——向高維空間轉(zhuǎn)化，使其變得線性可分。第44頁(yè)核函數(shù)

用一種詳細(xì)文本分類(lèi)例子來(lái)看看這種向高維空間映射從而分類(lèi)辦法如何運(yùn)作，假如我們文本分類(lèi)問(wèn)題原始空間是1000維（即每個(gè)要被分類(lèi)文檔被表達(dá)為一種1000維向量），在這個(gè)維度上問(wèn)題是線性不可分。目前我們有一種2023維空間里線性函數(shù)f(x’)=<w’,x’>+b

它能夠?qū)⒃瓎?wèn)題變得可分。式中w’和x’都是2023維向量，只不過(guò)w’是定值，而x’是變量。目前我們輸入呢，是一種1000維向量x，分類(lèi)過(guò)程是先把x變換為2023維向量x’，然后求這個(gè)變換后向量x’與向量w’內(nèi)積，再把這個(gè)內(nèi)積值和b相加，就得到了成果，看成果大于閾值還是不大于閾值就得到了分類(lèi)成果。第45頁(yè)核函數(shù)

因此只需要關(guān)懷那個(gè)高維空間里內(nèi)積值。而從理論上說(shuō)，x’是經(jīng)由x變換來(lái)，因此廣義上能夠把它叫做x函數(shù)（由于有一種x，就確定了一種x’），而w’是常量，它是一種低維空間里常量w通過(guò)變換得到，因此給了一種w和x值，就有一種確定f(x’)值與其對(duì)應(yīng)。因此，需要這樣一種函數(shù)K(w,x),他接收低維空間輸入值，卻能算出高維空間內(nèi)積值<w’,x’>。也就是當(dāng)給了一種低維空間輸入x后來(lái)：g(x)=K(w,x)+bf(x’)=<w’,x’>+b這兩個(gè)函數(shù)計(jì)算成果就完全同樣，我們也就用不著費(fèi)勁找那個(gè)映射關(guān)系，直接拿低維輸入往g(x)里面代就能夠了。第46頁(yè)核函數(shù)這樣函數(shù)確實(shí)存在，它被稱作核函數(shù)（核，kernel），并且不止一種，事實(shí)上，只要是滿足了Mercer條件函數(shù)，都能夠作為核函數(shù)。核函數(shù)基本作用就是接收兩個(gè)低維空間里向量，能夠計(jì)算出通過(guò)某個(gè)變換后在高維空間里向量?jī)?nèi)積值。這就是說(shuō)，盡管給問(wèn)題是線性不可分，不過(guò)就硬當(dāng)它是線性問(wèn)題來(lái)求解，只不過(guò)求解過(guò)程中，凡是要求內(nèi)積時(shí)候就用選定核函數(shù)來(lái)算。這樣求出來(lái)α再和選定核函數(shù)一組合，就得到分類(lèi)器。。第47頁(yè)核函數(shù)幾個(gè)比較常用核函數(shù)如下：第48頁(yè)核函數(shù)接下來(lái)尚有兩個(gè)問(wèn)題：1.既然有很多核函數(shù)，針對(duì)詳細(xì)問(wèn)題該怎么選擇？2.假如使用核函數(shù)向高維空間映射后，問(wèn)題仍然是線性不可分，那怎么辦？第49頁(yè)核函數(shù)對(duì)核函數(shù)選擇，目前還缺乏指導(dǎo)標(biāo)準(zhǔn)！多種試驗(yàn)觀測(cè)成果（不光是文本分類(lèi)）確實(shí)表白，某些問(wèn)題用某些核函數(shù)效果較好，用另某些就很差，不過(guò)一般來(lái)講，徑向基核函數(shù)（RBF）是不會(huì)出太大偏差一種。第50頁(yè)核函數(shù)在常用核函數(shù)中，應(yīng)用最廣泛是具有較好學(xué)習(xí)能力RBF核，無(wú)論低維、高維、小樣本、大樣本等情況，RBF核均適應(yīng)，具有較寬收斂域，是較為抱負(fù)分類(lèi)根據(jù)函數(shù)。KeerthiSS等人證明了線性核和多項(xiàng)式核是RBF核特殊情況。

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

Sigmoid核同RBF核具有相同性能。第51頁(yè)松弛變量處理第二個(gè)問(wèn)題：

舉個(gè)例子，例如我們已經(jīng)把一種本來(lái)線性不可分文本分類(lèi)問(wèn)題，通過(guò)映射到高維空間而變成了線性可分。目前有這樣一種訓(xùn)練集，只比原先這個(gè)訓(xùn)練集多了一篇文章，映射到高維空間后來(lái)也就多了一種樣本點(diǎn)，不過(guò)這個(gè)樣本位置如下列圖：第52頁(yè)松弛變量

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

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

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

第55頁(yè)松弛變量把損失加入到目標(biāo)函數(shù)里時(shí)候，就需要一種處罰因子（cost，也就是libSVM很多參數(shù)中C），本來(lái)優(yōu)化問(wèn)題就變成了下面這樣：

這個(gè)式子有這樣幾點(diǎn)要注意：1.并非所有樣本點(diǎn)都有一種松弛變量與其對(duì)應(yīng)。只有“離群點(diǎn)”才有。2.松弛變量值事實(shí)上標(biāo)示出了對(duì)應(yīng)點(diǎn)究竟離群有多遠(yuǎn)，值越大，點(diǎn)就越遠(yuǎn)。

第56頁(yè)松弛變量3.處罰因子C決定了你有多重視離群點(diǎn)帶來(lái)?yè)p失，顯然當(dāng)所有離群點(diǎn)松弛變量和一定期，C越大，對(duì)目標(biāo)函數(shù)損失也越大，此時(shí)就暗示著非常不樂(lè)意放棄這些離群點(diǎn)，最極端情況是把C定為無(wú)限大，這樣只要稍有一種點(diǎn)離群，目標(biāo)函數(shù)值立即變成無(wú)限大，立即讓問(wèn)題變成無(wú)解，這就退化成了硬間隔問(wèn)題。4.是處罰因子C不是一種變量，整個(gè)優(yōu)化問(wèn)題在解時(shí)候，C是一種必須事先指定值，指定這個(gè)值后來(lái)，解一下，就得到一種分類(lèi)器，然后用測(cè)試數(shù)據(jù)看看成果好不好，不好再換一種C值。如此就是一種參數(shù)尋優(yōu)過(guò)程。另外，當(dāng)遇到數(shù)據(jù)集偏斜問(wèn)題時(shí)，也是通過(guò)調(diào)整處罰因子來(lái)處理。第57頁(yè)松弛變量核函數(shù)與松弛變量作用區(qū)分：雖然二者引入都是為理解決線性不可分問(wèn)題。但二者尚有微妙不一樣。以文本分類(lèi)為例。在原始低維空間中，樣本相稱不可分，無(wú)論怎么找分類(lèi)平面，總會(huì)有大量離群點(diǎn)，此時(shí)用核函數(shù)向高維空間映射一下，雖然結(jié)果仍然是不可分，但比原始空間里要更加接近線性可分狀態(tài)，就是達(dá)到了近似線性可分狀態(tài)。此時(shí)再用松弛變量處理那些少數(shù)離群點(diǎn)，就簡(jiǎn)單有效得多了。第58頁(yè)ExampleSupposewehave51Ddatapointsx1=1,x2=2,x3=4,x4=5,x5=6,with1,2,6asclass1and4,5asclass2

y1=1,y2=1,y3=-1,y4=-1,y5=1Weusethepolynomialkernelofdegree2K(xi,xj)=(xixj+1)2Wefirstfindai(i=1,…,5)bySubjectto:

i>0第59頁(yè)Example

ByusingaQPsolver,wegeta1=0,a2=2.5,a3=0,a4=7.333,a5=4.833Thesupportvectorsare{x2=2,x4=5,x5=6}Thediscriminantfunctionisbisrecoveredbysolving

f(2)=1

orby

f(5)=-1

orby

f(6)=1,as

x2,x4,x5

lieon

andallgive

b=9f(z)=(2.5)(1)(2z+1)2+7.333(1)(5z+1)2+4.833(1)(6z+1)2+b=0.6667z2–5.333z+byi(wT(z)+b)=1f(x)=0.6667x2-5.333x+9第60頁(yè)ExampleValueofdiscriminantfunction12456class2class1class1{x=2,x=5,x=6aresupportvectors}第61頁(yè)SVM用于多類(lèi)分類(lèi)一次性得到多種分類(lèi)面辦法：就是真一次性考慮所有樣本，并求解一種多目標(biāo)函數(shù)優(yōu)化問(wèn)題，一次性得到多種分類(lèi)面，如下列圖：

只可惜這種算法還基本停留在紙面上，由于一次性求解辦法計(jì)算量實(shí)在太大，大到無(wú)法實(shí)用地步。

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

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

分類(lèi)時(shí)，先問(wèn)分類(lèi)器“1對(duì)5”（意思是它能夠回答“是第1類(lèi)還是第5類(lèi)”），假如回答5，就往左走，再問(wèn)“2對(duì)5”這個(gè)分類(lèi)器，假如還是“5”，繼續(xù)往左走，這樣始終下去，就能夠得到分類(lèi)成果。第65頁(yè)SVM用于多類(lèi)分類(lèi)這是一種有向無(wú)環(huán)圖，因此這種辦法也叫做DAGSVM），調(diào)用了k-1（K是類(lèi)別數(shù)）個(gè)分類(lèi)器。速度快，且沒(méi)有分類(lèi)重合和不可分類(lèi)現(xiàn)象。缺陷是假如最一開(kāi)始分類(lèi)器回答錯(cuò)誤，那么背面分類(lèi)器是無(wú)法糾正它錯(cuò)誤。對(duì)下面每一層分類(lèi)器都存在這種錯(cuò)誤向下累積現(xiàn)象。不過(guò)DAG辦法好于它們地方就在于，累積上限，不論是大是小，總是有定論，有理論能夠證明。并且能夠通過(guò)調(diào)整“根節(jié)點(diǎn)選用”及輸出“置信度”來(lái)改善效果。第66頁(yè)LIBSVM介紹LIBSVM是臺(tái)灣大學(xué)林智仁專(zhuān)家2023年開(kāi)發(fā)一套支持向量機(jī)庫(kù)，運(yùn)算速度快，能夠很方便對(duì)數(shù)據(jù)做分類(lèi)或回歸。由于LIBSVM程序小，利用靈活，輸入?yún)?shù)少，并且是開(kāi)源，易于擴(kuò)展，因此成為目前國(guó)內(nèi)應(yīng)用最多SVM庫(kù)。這套庫(kù)目前已經(jīng)發(fā)展到2.9版。第67頁(yè)LIBSVM介紹工具包里主要有5個(gè)文獻(xiàn)夾：1.Java主要是應(yīng)用于java平臺(tái)；2.Python是用來(lái)參數(shù)優(yōu)選工具，稍后介紹；3.svm-toy是一種可視化工具，用來(lái)展示訓(xùn)練數(shù)據(jù)和分類(lèi)界面，里面是源碼，其編譯后程序在windows文獻(xiàn)夾下；4.tools—主要包括四個(gè)python文獻(xiàn)，用來(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è)。尚有一種svm-toy.exe之前已經(jīng)交待過(guò)，是一種可視化工具。第68頁(yè)LIBSVM介紹libSVM數(shù)據(jù)格式如下：Label1:value2:value…Label是類(lèi)別標(biāo)識(shí)，例如上節(jié)train.model中提到1-1，你能夠自己隨意定，例如-10，0，15。假如是回歸，這是目標(biāo)值，就要實(shí)事求是了。Value就是要訓(xùn)練數(shù)據(jù)，從分類(lèi)角度來(lái)說(shuō)就是特性值，數(shù)據(jù)之間用空格隔開(kāi)，例如：-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)算速度。第69頁(yè)試驗(yàn)試驗(yàn)樣本選擇工具包下存在樣本文獻(xiàn)：heart_scale。內(nèi)容截圖如下：第70頁(yè)試驗(yàn)

訓(xùn)練：首先用svm-train進(jìn)行訓(xùn)練，輸入下列命令：svm-trainheart_scaletrain.model得到一種成果文獻(xiàn)：train.model

第71頁(yè)試驗(yàn)?zāi)軌蚩吹匠晒簅ptimizationfinished,#iter=162nu=0.431029obj=-100.877288,rho=0.424462nSV=132,nBSV=107TotalnSV=132其中，#iter為迭代次數(shù)，nu是選擇核函數(shù)類(lèi)型參數(shù)，obj為SVM文獻(xiàn)轉(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)來(lái)說(shuō)，由于只有一種分類(lèi)模型TotalnSV=nSV，不過(guò)對(duì)于多類(lèi)，這個(gè)是各個(gè)分類(lèi)模型nSV之和）。第72