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

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

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

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

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

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

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

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

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

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

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

Sigmoid函數(shù)。

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

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

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

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

——

by

R.Feynman

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

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