線性不可分支持向量機(jī)

2、數(shù)據(jù)線性不可分的情況

2.支持向量機(jī)原理解決的一個(gè)途徑(支持向量機(jī)算法)是用“超曲面”代替“超平面”，找一個(gè)能夠正確分類(lèi)所有觀測(cè)樣本的的“最大間隔超曲面”。核函數(shù)因?yàn)橛?xùn)練樣例一般是不會(huì)獨(dú)立出現(xiàn)的，它們總是以成對(duì)樣例的內(nèi)積形式出現(xiàn)，而用對(duì)偶形式表示學(xué)習(xí)器的優(yōu)勢(shì)在于在該表示中可調(diào)參數(shù)的個(gè)數(shù)不依賴(lài)輸入屬性的個(gè)數(shù)，通過(guò)使用恰當(dāng)?shù)暮撕瘮?shù)來(lái)替代內(nèi)積，可以隱式得將非線性的訓(xùn)練數(shù)據(jù)映射到高維空間，而不增加可調(diào)參數(shù)的個(gè)數(shù)。(當(dāng)然，前提是核函數(shù)能夠計(jì)算對(duì)應(yīng)著兩個(gè)輸入特征向量的內(nèi)積)對(duì)于非線性的情況，SVM的處理方法是選擇一個(gè)核函數(shù)κ(?,?)，通過(guò)將數(shù)據(jù)映射到高維空間，來(lái)解決在原始空間中線性不可分的問(wèn)題。核函數(shù)通過(guò)把數(shù)據(jù)映射到高維空間來(lái)增加第一節(jié)所述的線性學(xué)習(xí)器的能力，使得線性學(xué)習(xí)器對(duì)偶空間的表達(dá)方式讓分類(lèi)操作更具靈活性和可操作性。

在用線性學(xué)習(xí)器學(xué)習(xí)一個(gè)非線性關(guān)系，需要選擇一個(gè)非線性特征集，并且將數(shù)據(jù)寫(xiě)成新的表達(dá)形式，等價(jià)于：用一個(gè)固定的非線性映射，將數(shù)據(jù)映射到特征空間，在特征空間中使用線性學(xué)習(xí)器。因此，考慮的假設(shè)集是這種類(lèi)型的函數(shù)：這里?：X->F是從輸入空間到某個(gè)特征空間的映射1.首先使用一個(gè)非線性映射將數(shù)據(jù)變換到一個(gè)特征空間F2.然后在特征空間使用線性學(xué)習(xí)器分類(lèi)。低維非線性到高維線性這意味著建立非線性學(xué)習(xí)器分為如下幾步：如何處理線性不可分?jǐn)?shù)據(jù)如何處理線性不可分?jǐn)?shù)據(jù)如果和X2來(lái)表示這個(gè)二維平面的兩個(gè)坐標(biāo)，一條二次曲線（圓圈是二次曲線的一種特殊情況）的方程可以寫(xiě)作這樣的形式：如果我們構(gòu)造另外一個(gè)五維空間，其中五個(gè)坐標(biāo)為

在新的空間中原來(lái)的數(shù)據(jù)將變成線性可分的，使用之前我們推導(dǎo)的線性分類(lèi)算法就可以進(jìn)行處理了。映射關(guān)系為紅點(diǎn)x2+y2-4y=0綠點(diǎn)x2+y2-4y=-3映射形式為：Φ(<x,y>)=<x2,y2,y>例：二維線性不可分映射到三維后線性可分求解αi,

i=1,2,…n進(jìn)行分類(lèi)回顧：核函數(shù)的引入在求解分類(lèi)函數(shù)和利用分類(lèi)函數(shù)進(jìn)行分類(lèi)時(shí)，都涉及到“高維特征向量求內(nèi)積”。若映射到的高維空間維數(shù)太高甚至是無(wú)窮維時(shí)，存在“維數(shù)災(zāi)難”。若存在這么一個(gè)函數(shù)Κ(.,.),滿(mǎn)足：也就是說(shuō)，我們要求的高維空間中向量?jī)?nèi)積運(yùn)算，可以直接在低維空間進(jìn)行運(yùn)算求得，兩者的值相等，這樣就避免直接在高維空間求向量積可能帶來(lái)的維數(shù)災(zāi)難問(wèn)題。那么分類(lèi)函數(shù)相應(yīng)為當(dāng)特征空間維數(shù)很高或?yàn)闊o(wú)窮維時(shí)，直接計(jì)算高維空間中的內(nèi)積是非常困難的，因此需要另外的方法。那么巧妙地將高維空間中的求內(nèi)積運(yùn)算轉(zhuǎn)化為低維空間中的運(yùn)算，避免“維數(shù)災(zāi)難”。核函數(shù)的引入8核函數(shù)能簡(jiǎn)化映射空間中的內(nèi)積運(yùn)算，在我們的SVM里需要計(jì)算的地方數(shù)據(jù)向量總是以?xún)?nèi)積的形式出現(xiàn)的。對(duì)比剛才我們上面寫(xiě)出來(lái)的式子，現(xiàn)在我們的分類(lèi)函數(shù)為：其中

由如下dual問(wèn)題計(jì)算而得：避開(kāi)了直接在高維空間中進(jìn)行計(jì)算，而結(jié)果卻是等價(jià)的！核函數(shù)的引入例子設(shè)兩個(gè)向量和，而即是上述五維空間的映射：一個(gè)是映射到高維空間中，再進(jìn)行內(nèi)積計(jì)算；另一個(gè)則直接在原來(lái)的低維空間中進(jìn)行計(jì)算，不需要顯式地寫(xiě)出映射后的結(jié)果；

因此映射過(guò)后的內(nèi)積為：而這個(gè)式子與下面這個(gè)是等價(jià)的：計(jì)算兩個(gè)向量在隱式映射后的空間中的內(nèi)積的函數(shù)叫做核函數(shù)(KernelFunction)<Φ(.),Φ(.)>是高維或無(wú)窮維度空間中的向量積運(yùn)算核函數(shù)K（.，.）是直接在低維度空間中進(jìn)行計(jì)算，兩者計(jì)算結(jié)果相等按照前面的思路，處理線性不可分?jǐn)?shù)據(jù)步驟為:首先尋找一個(gè)映射函數(shù)將數(shù)據(jù)映射到高維空間，(在高維空間中數(shù)據(jù)可能變得線性可分)在高維空間中應(yīng)用SVM分析求解過(guò)程中引入核函數(shù)。得到分類(lèi)函數(shù)但實(shí)際上，尋找使變得線性可分的映射函數(shù)很難。尋找與映射函數(shù)對(duì)應(yīng)的核函數(shù)更難。核函數(shù)的實(shí)際應(yīng)用問(wèn)題上：理論上核函數(shù)的使用下：實(shí)際中核函數(shù)的使用問(wèn)題：什么樣的函數(shù)能作為核函數(shù)？Mercer條件如何選擇核函數(shù)，有哪些指導(dǎo)原則？映射到高維空間就一定線性可分嗎？如果高維空間仍然線性不可分，那該怎么辦？核函數(shù)的選擇，沒(méi)有明確的原則，一般根據(jù)具體問(wèn)題，采用試探的方式。核函數(shù)隱藏著一個(gè)到高維的映射，可能使得數(shù)據(jù)在高維變得線性可分，但并不不能保證映射到高維空間后一定線性可分。若仍然線性不可分，引入松弛變量、懲罰系數(shù)，放松約束，雖然仍然不能保證對(duì)訓(xùn)練數(shù)據(jù)線性可分，但它會(huì)根據(jù)我們給出的懲罰因子找到代價(jià)最小的分類(lèi)器?！稒C(jī)器學(xué)習(xí)》-周志華著上有這樣一句話：“幸運(yùn)的是，如果原始空間是有限維，即屬性有限，那么一定存在一個(gè)高緯度特征空間使樣本可分?！钡菦](méi)有給出證明或參考文獻(xiàn)。兩個(gè)問(wèn)題回答高維空間中的最優(yōu)分類(lèi)面非線性問(wèn)題——通過(guò)非線性變換將它轉(zhuǎn)化為某個(gè)高維空間中的線性問(wèn)題，在這個(gè)高維空間中尋找最優(yōu)分類(lèi)面。分類(lèi)函數(shù)只涉及到訓(xùn)練樣本之間的內(nèi)積運(yùn)算。因此,在高維空間中只需進(jìn)行內(nèi)積運(yùn)算,這種內(nèi)積運(yùn)算可通過(guò)定義在原空間中的函數(shù)來(lái)實(shí)現(xiàn),甚至不必知道變換的形式。

在最優(yōu)分類(lèi)面中采用適當(dāng)?shù)膬?nèi)積函數(shù)就可以實(shí)現(xiàn)某一非線性變換后的線性分類(lèi),

而計(jì)算復(fù)雜度卻沒(méi)有增加。SLT指出,根據(jù)Hibert-Schmidt原理,只要一種運(yùn)算滿(mǎn)足Mercer條件,就可以作為內(nèi)積使用。支持向量機(jī)對(duì)偶優(yōu)化問(wèn)題（D）:求解對(duì)偶問(wèn)題的最優(yōu)解后,支持向量機(jī)的決策函數(shù)為：非線性支持向量機(jī)問(wèn)題解決Mercer定理：

（必要性）如果函數(shù)K是Rn上的映射（也就是從兩個(gè)n維向量映射到實(shí)數(shù)域）。那么如果K是一個(gè)有效核函數(shù)（也稱(chēng)為Mercer核函數(shù)），那么當(dāng)且僅當(dāng)對(duì)于訓(xùn)練樣例，其相應(yīng)的核函數(shù)矩陣是對(duì)稱(chēng)半正定的。這里補(bǔ)充核函數(shù)矩陣是半正定的具體推導(dǎo)比較好核函數(shù)需要滿(mǎn)足的條件不同的內(nèi)積核函數(shù)將形成不同的算法,目前,在SVM理論研究與實(shí)際應(yīng)用中,最常使用的有以下四類(lèi)核函數(shù):（1）線性核函數(shù)：（2）多項(xiàng)式核函數(shù)：,

q是自然數(shù)。此時(shí)得到的支持向量機(jī)是一個(gè)q階多項(xiàng)式分類(lèi)器。（3）Gauss徑向基核函數(shù)。得到的支持向量機(jī)是一種徑向基函數(shù)分類(lèi)器。（4）Sigmoid核函數(shù)：a和t是常數(shù)，tanh是

Sigmoid函數(shù)。

核函數(shù)分類(lèi)支持向量機(jī)實(shí)現(xiàn)SVMlight -2.private:/usr/local/binsvm_learn,svm_classifybsvm -2.private:/usr/local/binsvm-train,svm-classify,svm-scalelibsvm -2.private:/usr/local/binsvm-train,svm-predict,svm-scale,svm-toymySVMMATLABsvmtoolbox支持向量機(jī)實(shí)現(xiàn)libsvm這里應(yīng)介紹下libsvm的使用方法和具體的分類(lèi)應(yīng)用如何選擇核函數(shù)，有哪些指導(dǎo)原則？映射到高維空間就一定線性可分嗎？如果高維空間仍然線性不可分，那該怎么辦？核函數(shù)的選擇，沒(méi)有明確的原則，一般根據(jù)具體問(wèn)題，采用試探的方式。核函數(shù)隱藏著一個(gè)到高維的映射，可能使得數(shù)據(jù)在高維變得線性可分，但并不不能保證映射到高維空間后一定線性可分。若仍然線性不可分，引入松弛變量、懲罰系數(shù)，放松約束，雖然仍然不能保證對(duì)訓(xùn)練數(shù)據(jù)線性可分，但它會(huì)根據(jù)我們給出的懲罰因子找到代價(jià)最小的分類(lèi)器?！稒C(jī)器學(xué)習(xí)》-周志華著上有這樣一句話：“幸運(yùn)的是，如果原始空間是有限維，即屬性有限，那么一定存在一個(gè)高緯度特征空間使樣本可分?！钡菦](méi)有給出證明或參考文獻(xiàn)。兩個(gè)問(wèn)題回答小結(jié)：核函數(shù)方法原理低維線性不可分的模式通過(guò)非線性映射映射到高維特征空間后，可能實(shí)現(xiàn)線性可分。但如果直接在高維空間中進(jìn)行分類(lèi)，需要確定映射的具體形式，而且可能存在“維數(shù)災(zāi)難”問(wèn)題，核函數(shù)技巧能有效解決這樣的問(wèn)題。引入松弛變量24原來(lái)的約束條件是c是一個(gè)常量參數(shù)，ξ是需要優(yōu)化的變量之一考慮映射到高維不可分情況，約束條件變?yōu)椋害螢樗沙谧兞?，?duì)應(yīng)數(shù)據(jù)點(diǎn)x可以偏離的函數(shù)間隔的量將限制或約束條件加入到目標(biāo)函數(shù)中，得到新的拉格朗日函數(shù)：這里的α和γ都是拉格朗日乘子然后將其看作是變量w和b的函數(shù)，分別對(duì)其求偏導(dǎo)，然后帶入公式中，求帶入后公式的極大值我們發(fā)現(xiàn):又多了小于αi等于C的條件沒(méi)有了參數(shù)ξi

與之前的模型唯一不同是在于又多了小于αi等于C的條件引入松弛變量應(yīng)用研究支持向量機(jī)研究支持向量機(jī)算法研究8.7研究現(xiàn)狀SVM的應(yīng)用主要于模式識(shí)別領(lǐng)域分類(lèi)器錯(cuò)誤率人工表現(xiàn)2.5%決策樹(shù)C4.516.2%最好的兩層神經(jīng)網(wǎng)絡(luò)5.9%SVM4.0%

貝爾實(shí)驗(yàn)室對(duì)美國(guó)郵政手寫(xiě)數(shù)字庫(kù)進(jìn)行的實(shí)驗(yàn)8.7.1應(yīng)用研究SVM與神經(jīng)網(wǎng)絡(luò)（NN）的對(duì)比SVM的理論基礎(chǔ)比NN更堅(jiān)實(shí)，更像一門(mén)嚴(yán)謹(jǐn)?shù)摹翱茖W(xué)”

（三要素：?jiǎn)栴}的表示、問(wèn)題的解決、證明）SVM——嚴(yán)格的數(shù)學(xué)推理NN——強(qiáng)烈依賴(lài)于工程技巧推廣能力取決于“經(jīng)驗(yàn)風(fēng)險(xiǎn)值”和“置信范圍值”，NN不能控制兩者中的任何一個(gè)。NN設(shè)計(jì)者用高超的工程技巧彌補(bǔ)了數(shù)學(xué)上的缺陷——設(shè)計(jì)特殊的結(jié)構(gòu)，利用啟發(fā)式算法，有時(shí)能得到出人意料的好結(jié)果?！拔覀儽仨殢囊婚_(kāi)始就澄清一個(gè)觀點(diǎn)，就是如果某事不是科學(xué)，它并不一定不好。比如說(shuō)，愛(ài)情就不是科學(xué)。因此，如果我們說(shuō)某事不是科學(xué)，并不是說(shuō)他有什么不對(duì)，而只是說(shuō)它不是科學(xué)”

——

by

R.Feynman

fromTheFeynmanLecturesonPhysics,Addison-Wesley同理，與SVM相比，NN不像一門(mén)科學(xué)，更像一門(mén)工程技巧，但并不意味著它就一定不好！主要應(yīng)用領(lǐng)域手寫(xiě)數(shù)字識(shí)別語(yǔ)音識(shí)別人臉識(shí)別文本分類(lèi)如何針對(duì)不同的問(wèn)題選擇不同的核函數(shù)仍然是一個(gè)懸而未決的問(wèn)題。標(biāo)準(zhǔn)的SVM對(duì)噪聲是不具有魯棒性的,如何選擇合適的目標(biāo)函數(shù)以實(shí)現(xiàn)魯棒性是至關(guān)重要的。8.7.2支持向量機(jī)研究8.7.3支持向量機(jī)算法研究支持向量機(jī)的本質(zhì)是解一個(gè)二次規(guī)劃問(wèn)題,雖然有一些經(jīng)典求解算（如對(duì)偶方法、內(nèi)點(diǎn)算法等）,但當(dāng)訓(xùn)練集規(guī)模很大時(shí),這些算法面臨著維數(shù)災(zāi)難問(wèn)題。為此,人們提出了許多針對(duì)大規(guī)模數(shù)據(jù)集的SVM訓(xùn)練算法。支持向量機(jī)算法研究（續(xù)1）思路1：分解子問(wèn)題塊算法SMO算法(SequentialMinimalOptimization)思路2：序列優(yōu)化思路3：近鄰SVM訓(xùn)練SVM的絕大多數(shù)算法都是針對(duì)分類(lèi)問(wèn)題,只有一小部分算法考慮了回歸函數(shù)的估計(jì)問(wèn)題。提高算法效率、降低復(fù)雜度。支持向量機(jī)算法研究（續(xù)2）支持向量機(jī)算法研究（續(xù)3）SVM增量學(xué)習(xí)算法的研究超球面SVM算法研究One-classSVM算法……SVM多值分類(lèi)器算法One-against-the-rest（一對(duì)多方法）One-against-one（一對(duì)一方法）Multi-classObjectiveFunctions（多類(lèi)SVM）DecisionDirectedAcyclicGraph,DDAGSVMDecisionTree超球面SVM多值分類(lèi)器……總結(jié)SVM在模式識(shí)別、回歸函數(shù)估計(jì)、預(yù)測(cè)等大量應(yīng)用中取得了良好的效果SVM存在兩個(gè)主要問(wèn)題：二次規(guī)劃的訓(xùn)練速度核函數(shù)的選擇前途是光明的，道路是曲折的。課后編程實(shí)現(xiàn)題目（二選一）：設(shè)計(jì)并實(shí)現(xiàn)一個(gè)簡(jiǎn)單的用于文本分類(lèi)的SVM。設(shè)計(jì)并實(shí)現(xiàn)一個(gè)簡(jiǎn)單的基于SVM的“新聞分離器”，主要用于對(duì)浙大BBS

“縹緲?biāo)崎g”中news版上的新聞進(jìn)行分類(lèi)。Atutorialonsupportvectormachinesforpatternrecognition.DataMiningandKnowledgeDiscovery,1998,2(2)VapnikVN.TheNatureofStatisticalLearningTheory,NY:Springer-Verlag,1995（中譯本：張學(xué)工譯.《統(tǒng)計(jì)學(xué)習(xí)理論的本質(zhì)》.清華大學(xué)出版社,2000）【說(shuō)明】該書(shū)附帶介紹了很多科學(xué)研究的基本原則，很有啟發(fā)借鑒意義。主要參考文獻(xiàn)：IntroductiontoSupportVectorMachine.VapnikVN.著，張學(xué)工譯.統(tǒng)計(jì)學(xué)習(xí)理論.人民郵電出版