線性不可分SVM和研究現(xiàn)狀

1、線性不可分SVM和研究現(xiàn)狀目錄線性不可分問題核函數(shù)松弛變量多輸入多輸出支持向量機(jī)回歸算法支持向量機(jī)實(shí)現(xiàn)研究現(xiàn)狀數(shù)據(jù)線性不可分的情況 解決的一個(gè)途徑(支持向量機(jī)算法)是用“超曲面”代替“超平面”,找一個(gè)能夠正確分類所有觀測(cè)樣本的的“最大間隔超曲面”。紅點(diǎn) x2+y2-4y=0綠點(diǎn)x2+y2-4y=-3映射形式為：()=例：二維線性不可分映射到三維后線性可分 在用線性學(xué)習(xí)器學(xué)習(xí)一個(gè)非線性關(guān)系，需要選擇一個(gè)非線性特征集，并且將數(shù)據(jù)寫成新的表達(dá)形式，等價(jià)于：用一個(gè)固定的非線性映射，將數(shù)據(jù)映射到特征空間，在特征空間中使用線性學(xué)習(xí)器。因此，考慮的假設(shè)集是這種類型的函數(shù)：這里：X-F是從輸入空間到某個(gè)特征空

2、間的映射2.然后在特征空間使用線性學(xué)習(xí)器分類。低維非線性到高維線性這意味著建立非線性學(xué)習(xí)器分為如下幾步：如何處理線性不可分?jǐn)?shù)據(jù)目錄線性不可分問題核函數(shù)松弛變量支持向量機(jī)實(shí)現(xiàn)研究現(xiàn)狀核函數(shù)對(duì)于非線性的情況，SVM 的處理方法是選擇一個(gè)核函數(shù) (,) ，通過將數(shù)據(jù)映射到高維空間，來解決在原始空間中線性不可分的問題。 核函數(shù)通過把數(shù)據(jù)映射到高維空間來增加第一節(jié)所述的線性學(xué)習(xí)器的能力，使得線性學(xué)習(xí)器對(duì)偶空間的表達(dá)方式讓分類操作更具靈活性和可操作性。因?yàn)橛?xùn)練樣例一般是不會(huì)獨(dú)立出現(xiàn)的，它們總是以成對(duì)樣例的內(nèi)積形式出現(xiàn)，而用對(duì)偶形式表示學(xué)習(xí)器的優(yōu)勢(shì)在為在該表示中可調(diào)參數(shù)的個(gè)數(shù)不依賴輸入屬性的個(gè)數(shù)，通過使用恰

3、當(dāng)?shù)暮撕瘮?shù)來替代內(nèi)積，可以隱式得將非線性的訓(xùn)練數(shù)據(jù)映射到高維空間，而不增加可調(diào)參數(shù)的個(gè)數(shù)(當(dāng)然，前提是核函數(shù)能夠計(jì)算對(duì)應(yīng)著兩個(gè)輸入特征向量的內(nèi)積)。 基本概念 低維非線性到高維線性在我們遇到核函數(shù)之前，如果用原始的方法，那么在用線性學(xué)習(xí)器學(xué)習(xí)一個(gè)非線性關(guān)系，需要選擇一個(gè)非線性特征集，并且將數(shù)據(jù)寫成新的表達(dá)形式，這等價(jià)于應(yīng)用一個(gè)固定的非線性映射，將數(shù)據(jù)映射到特征空間，在特征空間中使用線性學(xué)習(xí)器，因此，考慮的假設(shè)集是這種類型的函數(shù)： 這里：X-F是從輸入空間到某個(gè)特征空間的映射，這意味著建立非線性學(xué)習(xí)器分為兩步：1.首先使用一個(gè)非線性映射將數(shù)據(jù)變換到一個(gè)特征空間F，2.然后在特征空間使用線性學(xué)習(xí)器

4、分類。9在上文我提到過對(duì)偶形式，而這個(gè)對(duì)偶形式就是線性學(xué)習(xí)器的一個(gè)重要性質(zhì)，這意味著假設(shè)可以表達(dá)為訓(xùn)練點(diǎn)的線性組合，因此決策規(guī)則可以用測(cè)試點(diǎn)和訓(xùn)練點(diǎn)的內(nèi)積來表示：對(duì)一個(gè)函數(shù)k，滿足所有的x，z都有k(x,z)=,這里的(x)為從X到內(nèi)積特征空間F的映射，則稱k為核函數(shù)。求解i, i=1,2,n進(jìn)行分類回顧：核函數(shù)的引入在求解分類函數(shù)和利用分類函數(shù)進(jìn)行分類時(shí)，都涉及到“高維特征向量求內(nèi)積”。若映射到的高維空間維數(shù)太高甚至是無窮維時(shí)，存在“維數(shù)災(zāi)難”。若存在這么一個(gè)函數(shù) (.,.),滿足：也就是說，我們要求的高維空間中向量內(nèi)積運(yùn)算，可以直接在低維空間進(jìn)行運(yùn)算求得，兩者的值相等，這樣就避免直接在高維

5、空間求向量積可能帶來的維數(shù)災(zāi)難問題。那么分類函數(shù)相應(yīng)為當(dāng)特征空間維數(shù)很高或?yàn)闊o窮維時(shí)，直接計(jì)算高維空間中的內(nèi)積是非常困難的，因此需要另外的方法。那么巧妙地將高維空間中的求內(nèi)積運(yùn)算轉(zhuǎn)化為低維空間中的運(yùn)算，避免“維數(shù)災(zāi)難”。核函數(shù)的引入12核函數(shù)能簡化映射空間中的內(nèi)積運(yùn)算，在我們的 SVM 里需要計(jì)算的地方數(shù)據(jù)向量總是以內(nèi)積的形式出現(xiàn)的。對(duì)比剛才我們上面寫出來的式子，現(xiàn)在我們的分類函數(shù)為：其中 由如下dual問題計(jì)算而得：避開了直接在高維空間中進(jìn)行計(jì)算，而結(jié)果卻是等價(jià)的！核函數(shù)的引入核函數(shù)：如何處理非線性數(shù)據(jù)01某種試驗(yàn)方法的名稱這種方法的特點(diǎn)如果用 X1 和 X2 來表示這個(gè)二維平面的兩個(gè)坐標(biāo)的

6、話，我們知道一條二次曲線（圓圈是二次曲線的一種特殊情況）的方程可以寫作這樣的形式：如果我們構(gòu)造另外一個(gè)五維空間，其中五個(gè)坐標(biāo)為 則有：如果我們做一個(gè)映射 :R2R5 ，將 X 按照上面的規(guī)則映射為 Z ，那么在新的空間中原來的數(shù)據(jù)將變成線性可分的，從而使用之前我們推導(dǎo)的線性分類算法就可以進(jìn)行處理了。這正是 Kernel 方法處理非線性問題的基本思想。例子.設(shè)兩個(gè)向量 和 ，而 即是到前面說的五維空間的映射，因此映射過后的內(nèi)積為：而這個(gè)式子與下面這個(gè)是等價(jià)的 ： 一個(gè)是映射到高維空間中，然后再根據(jù)內(nèi)積的公式進(jìn)行計(jì)算；而另一個(gè)則直接在原來的低維空間中進(jìn)行計(jì)算，而不需要顯式地寫出映射后的結(jié)果。 我們

7、把這里的計(jì)算兩個(gè)向量在隱式映射過后的空間中的內(nèi)積的函數(shù)叫做核函數(shù) (Kernel Function) 15核函數(shù)能簡化映射空間中的內(nèi)積運(yùn)算，在我們的 SVM 里需要計(jì)算的地方數(shù)據(jù)向量總是以內(nèi)積的形式出現(xiàn)的。對(duì)比剛才我們上面寫出來的式子，現(xiàn)在我們的分類函數(shù)為： 其中 由如下 dual 問題計(jì)算而得：這樣一來計(jì)算的問題就算解決了，避開了直接在高維空間中進(jìn)行計(jì)算，而結(jié)果卻是等價(jià)的！ 是高維或無窮維度空間中的向量積運(yùn)算核函數(shù)K（ .，.）是直接在低維度空間中進(jìn)行計(jì)算，兩者計(jì)算結(jié)果相等按照前面的思路，處理線性不可分?jǐn)?shù)據(jù)步驟為:首先尋找一個(gè)映射函數(shù)將數(shù)據(jù)映射到高維空間，(在高維空間中數(shù)據(jù)可能變得線性可分)

8、在高維空間中應(yīng)用SVM分析求解過程中引入核函數(shù)。得到分類函數(shù)但實(shí)際上，尋找使變得線性可分的映射函數(shù)很難。尋找與映射函數(shù)對(duì)應(yīng)的核函數(shù)更難。核函數(shù)的實(shí)際應(yīng)用問題上：理論上核函數(shù)的使用下：實(shí)際中核函數(shù)的使用高維空間中的最優(yōu)分類面非線性問題通過非線性變換將它轉(zhuǎn)化為某個(gè)高維空間中的線性問題，在這個(gè)高維空間中尋找最優(yōu)分類面。分類函數(shù)只涉及到訓(xùn)練樣本之間的內(nèi)積運(yùn)算 ,因此,在高維空間中只需進(jìn)行內(nèi)積運(yùn)算,這種內(nèi)積運(yùn)算可通過定義在原空間中的函數(shù)來實(shí)現(xiàn), 甚至不必知道變換的形式。SLT指出,根據(jù)Hibert-Schmidt原理,只要一種運(yùn)算滿足Mercer條件,就可以作為內(nèi)積使用。Mercer條件問題：什么樣的函

9、數(shù)能作為核函數(shù)？支持向量機(jī)2數(shù)據(jù)線性不可分的情況對(duì)偶優(yōu)化問題（D）: 求解對(duì)偶問題的最優(yōu)解后,支持向量機(jī)的決策函數(shù)為： 在最優(yōu)分類面中采用適當(dāng)?shù)膬?nèi)積函數(shù)就可以實(shí)現(xiàn)某一非線性變換后的線性分類,而計(jì)算復(fù)雜度卻沒有增加。非線性支持向量機(jī) 核函數(shù)分類不同的內(nèi)積核函數(shù)將形成不同的算法,目前,在SVM理論研究與實(shí)際應(yīng)用中,最常使用的有以下四類核函數(shù):（1）線性核函數(shù)：（2）多項(xiàng)式核函數(shù)： , q是自然數(shù)。此時(shí)得到的支持向量機(jī)是一個(gè)q階多項(xiàng)式分類器。（3）Gauss徑向基核函數(shù): 。得到的支持向量機(jī)是一種徑向基函數(shù)分類器。（4）Sigmoid核函數(shù)： a和t是常數(shù)，tanh是Sigmoid函數(shù)。RBF核函數(shù)

10、如何選擇核函數(shù)，有哪些指導(dǎo)原則？映射到高維空間就一定線性可分嗎？如果高維空間仍然線性不可分，那該怎么辦？核函數(shù)的選擇，沒有明確的原則，一般根據(jù)具體問題，采用試探的方式。核函數(shù)隱藏著一個(gè)到高維的映射，可能使得數(shù)據(jù)在高維變得線性可分，但并不不能保證映射到高維空間后一定線性可分。若仍然線性不可分，引入松弛變量、懲罰系數(shù)，放松約束，雖然仍然不能保證對(duì)訓(xùn)練數(shù)據(jù)線性可分，但它會(huì)根據(jù)我們給出的懲罰因子找到代價(jià)最小的分類器。機(jī)器學(xué)習(xí)-周志華著 上有這樣一句話：“幸運(yùn)的是，如果原始空間是有限維，即屬性有限，那么一定存在一個(gè)高緯度特征空間使樣本可分。” 但是沒有給出證明或參考文獻(xiàn)。兩個(gè)問題回答高維空間中的最優(yōu)分類

11、面非線性問題通過非線性變換將它轉(zhuǎn)化為某個(gè)高維空間中的線性問題，在這個(gè)高維空間中尋找最優(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)某一非線性變換后的線性分類, 而計(jì)算復(fù)雜度卻沒有增加。SLT指出,根據(jù)Hibert-Schmidt原理,只要一種運(yùn)算滿足Mercer條件,就可以作為內(nèi)積使用。目錄線性不可分問題核函數(shù)松弛變量多輸入多輸出支持向量機(jī)回歸算法支持向量機(jī)實(shí)現(xiàn)研究現(xiàn)狀27引入松弛變量現(xiàn)在去考慮映射到高維也不可分的情況，原來的約束條件是其中

12、c是一個(gè)參數(shù)為常量，是需要優(yōu)化的變量之一?，F(xiàn)在考慮到映射到高維不可分，約束條件變?yōu)椋浩渲蟹Q為松弛變量，對(duì)應(yīng)數(shù)據(jù)點(diǎn)x可以偏離的函數(shù)間隔的量，即將限制或約束條件加入到目標(biāo)函數(shù)中，得到新的拉格朗日函數(shù)：這里的和都是拉格朗日乘子28然后將其看作是變量w和b的函數(shù)，分別對(duì)其求偏導(dǎo)，然后帶入公式中，求帶入后公式的極大值我們會(huì)發(fā)現(xiàn)，沒有了參數(shù) ，與之前的模型唯一不同是在于 又多了小于等于C的條件。而和函數(shù)化的非線性形式也是一樣的，只要把換成K(Xi,Xj)即可。目錄線性不可分問題核函數(shù)松弛變量多輸入多輸出支持向量機(jī)回歸算法支持向量機(jī)實(shí)現(xiàn)研究現(xiàn)狀多輸入多輸出支持向量機(jī)回歸算法 支持向量機(jī)是從線性可分情況下的最

13、優(yōu)分類面發(fā)展而來的。支持向量機(jī)形式上類似于一個(gè)神經(jīng)網(wǎng)絡(luò)，輸出是中間節(jié)點(diǎn)的線性組合，每個(gè)中間節(jié)點(diǎn)對(duì)應(yīng)于一個(gè)支持向量，其結(jié)構(gòu)如圖1所示。支持向量機(jī)線性回歸（1）支持向量機(jī)線性回歸支持向量機(jī)線性回歸支持向量機(jī)線性回歸支持向量機(jī)線性回歸由此推出支持向量機(jī)線性回歸支持向量機(jī)線性回歸支持向量機(jī)線性回歸支持向量機(jī)線性回歸支持向量機(jī)線性回歸支持向量機(jī)非線性回歸支持向量機(jī)非線性回歸(14)支持向量機(jī)非線性回歸目錄線性不可分問題核函數(shù)松弛變量支持向量機(jī)實(shí)現(xiàn)研究現(xiàn)狀支持向量機(jī)實(shí)現(xiàn)SVMlight - 2.private:/usr/local/binsvm_learn, svm_classifybsvm - 2.pr

14、ivate:/usr/local/binsvm-train, svm-classify, svm-scalelibsvm - 2.private:/usr/local/binsvm-train, svm-predict, svm-scale, svm-toymySVMMATLAB svm toolbox支持向量機(jī)實(shí)現(xiàn)目錄線性不可分問題核函數(shù)松弛變量支持向量機(jī)實(shí)現(xiàn)研究現(xiàn)狀研究現(xiàn)狀應(yīng)用研究支持向量機(jī)研究支持向量機(jī)算法研究應(yīng)用研究SVM的應(yīng)用主要于模式識(shí)別領(lǐng)域貝爾實(shí)驗(yàn)室對(duì)美國郵政手寫數(shù)字庫進(jìn)行的實(shí)驗(yàn)分類器錯(cuò)誤率人工表現(xiàn)2.5%決策樹C4.516.2%最好的兩層神經(jīng)網(wǎng)絡(luò)5.9%SVM4.0%SVM與神

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

16、ysics, Addison-Wesley同理，與SVM相比，NN不像一門科學(xué)，更像一門工程技巧，但并不意味著它就一定不好！主要應(yīng)用領(lǐng)域手寫數(shù)字識(shí)別語音識(shí)別人臉識(shí)別文本分類支持向量機(jī)研究如何針對(duì)不同的問題選擇不同的核函數(shù)仍然是一個(gè)懸而未決的問題。標(biāo)準(zhǔn)的SVM對(duì)噪聲是不具有魯棒性的,如何選擇合適的目標(biāo)函數(shù)以實(shí)現(xiàn)魯棒性是至關(guān)重要的。支持向量機(jī)算法研究支持向量機(jī)的本質(zhì)是解一個(gè)二次規(guī)劃問題,雖然有一些經(jīng)典（如對(duì)偶方法、內(nèi)點(diǎn)算法等）,但當(dāng)訓(xùn)練集規(guī)模很大時(shí),這些算法面臨著維數(shù)災(zāi)難問題。為此,人們提出了許多針對(duì)大規(guī)模數(shù)據(jù)集的SVM訓(xùn)練算法。支持向量機(jī)算法研究（續(xù)1）思路1：分解子問題塊算法SMO算法(Seq

17、uential Minimal Optimization)思路2：序列優(yōu)化思路3：近鄰SVM支持向量機(jī)算法研究（續(xù)2）訓(xùn)練SVM的絕大多數(shù)算法都是針對(duì)分類問題,只有一小部分算法考慮了回歸函數(shù)的估計(jì)問題。提高算法效率、降低復(fù)雜度。支持向量機(jī)算法研究（續(xù)3）SVM增量學(xué)習(xí)算法的研究超球面SVM算法研究One-class SVM算法SVM多值分類器算法One-against-the-rest（一對(duì)多方法）One-against-one（一對(duì)一方法）Multi-class Objective Functions（多類SVM）Decision Directed Acyclic Graph, DDAGSVM Decision Tree超球面SVM多值分類器總結(jié)SVM在模式識(shí)別、回歸函數(shù)估計(jì)、預(yù)測(cè)等大量應(yīng)用中取得了良好的效果SVM存在兩個(gè)主要問題：二次規(guī)劃的訓(xùn)練速度核函數(shù)的選擇前途是光明的，道路是曲折的。課后編程實(shí)現(xiàn)題目（二選一）：設(shè)計(jì)并實(shí)現(xiàn)一個(gè)簡單的用于文本分類的SVM。設(shè)計(jì)并實(shí)現(xiàn)一個(gè)簡單的基于SVM的“新聞分離器”，主要用于對(duì)浙大BBS“縹緲?biāo)崎g”