支持向量機及支持向量回歸簡介

1、3支持向量機(回歸)3.1.1 支持向量機支持向量機(SVM是美國Vapnik教授于1990年代提出的，2000年代后成 為了很受歡迎的機器學(xué)習(xí)方法。 它將輸入樣本集合變換到高維空間使得其分離性 狀況得到改善。它的結(jié)構(gòu)酷似三層感知器，是構(gòu)造分類規(guī)則的通用方法。SVh方法的貢獻在于， 它使得人們可以在非常高維的空間中構(gòu)造出好的分類規(guī)則， 為分 類算法提供了統(tǒng)一的理論框架。作為副產(chǎn)品，SVM從理論上解釋了多層感知器的隱蔽層數(shù)目和隱節(jié)點數(shù)目的作用， 因此，將神經(jīng)網(wǎng)絡(luò)的學(xué)習(xí)算法納入了核技巧范 疇。所謂核技巧，就是找一個核函數(shù) K(x, y)使其滿足K(x,y) ( (x), (y)，代 替在特征空間中

2、內(nèi)積(x), (y)的計算。因為對于非線性分類，一般是先找一 個非線性映射 將輸入數(shù)據(jù)映射到高維特征空間，使之分離性狀況得到很大改 觀，此時在該特征空間中進行分類， 然后再返會原空間， 就得到了原輸入空間的 非線性分類。由于內(nèi)積運算量相當(dāng)大，核技巧就是為了降低計算量而生的。特別，對特征空間H為Hilbert空間的情形，設(shè)K(x, y)是定義在輸入空間 Rn上的二元函數(shù)，設(shè)H中的規(guī)范正交基為！(X), 2(X)，n(X)，。如果K(x,y)2ak ( k(x), k(y),l2，那么取(x)ak k(x)即為所求的非線性嵌入映射。由于核函數(shù)K(x,y)的定義k 1域是原來的輸入空間，而不是高維的

3、特征空間。因此，巧妙地避開了計算高維內(nèi) 積(x), (y)所需付出的計算代價。實際計算中，我們只要選定一個 K(x,y)， 并不去重構(gòu)嵌入映射(x)ak k(x)。所以尋找核函數(shù)K(x,y)(對稱且非負)k 1就是主要任務(wù)了。滿足以上條件的核函數(shù)很多，例如可以取為d-階多項式：K(x, y) (1 x|y)d，其中y為固定元素?？梢匀閺较蚝瘮?shù)：K(x,y) exp |x y/ 2，其中y為固定元素?？梢匀樯窠?jīng)網(wǎng)絡(luò)慣用的核函數(shù)：K(x,y) tanh c/y) c?，其中y為固一般地，核函數(shù)的存在性只依賴于如何尋找一個平方收斂的非負序列ak o這樣的序列在l2空間的正錐|2ak l2 |ak

4、 0, k中的序列都滿足。但哪一個最佳還有待于進一步討論。經(jīng)驗表明，分類問題對于核函數(shù)不太敏感。當(dāng)然，重新 構(gòu)造一個核函數(shù)也不是一個簡單的事。因此，實際操作中往往就在上述三類中挑出一個來使用就可以了。支持向量機的結(jié)構(gòu)示意圖可以表示如下:Jill)血)K(A-1)w Ut)EGc, «2)Kg, k3)r 需 kL)yL-laL-1Kfx, wL-lJ圖1支持向量機結(jié)構(gòu)示意圖其中輸入層是為了存貯輸入數(shù)據(jù)，并不作任何加工運算；中間層是通過對樣本集的學(xué)習(xí)，選擇K(x,x) i 1,2,3,., L ;最后一層就是構(gòu)造分類函數(shù)Ly sgn(yaK(x,xJ b)i 1整個過程等價于在特征空間

5、中構(gòu)造一個最優(yōu)超平面支持向量機的作用之一就是分類。 根據(jù)分類的任務(wù)，可以劃分為一分類，二分類 以及多分類。對于多類分類問題，可以用若干種手法將其分解為若干個二分類問 題疊加。因此，為了實現(xiàn)支持向量機分類的算法，我們只要針對二分類，從頭來 給出它的數(shù)學(xué)原理。3.1.2支持向量機分類的數(shù)學(xué)原理設(shè)樣本集為 佻)以Rn; yi1, 1 , i 1,.,l，我們的目的是尋找一個最優(yōu)超平面H使得標(biāo)簽為+ 1和- 1的兩類點不僅分開且分得間隔最大。當(dāng)在n維歐幾里德空間中就可以實現(xiàn)線性分離時，也即存在超平面將樣本集按照標(biāo)簽-1與+1分在兩邊。由于超平面在n維歐幾里德空間中的數(shù)學(xué)表達式是一個線性方程w,x b

6、0，其中，w為系數(shù)向量，X為n維變量,w,x 內(nèi)積，b為常數(shù)?？臻g中點Xi到超平面L的距離d(-L)。欲使得d(-H)最大，等價于補最小。于是,得到一個在約束條件下的極值問題min 2|w|I 2W,Xiyi(弓I入 Lagrange 乘子 (2?I)，可以解得關(guān)于該參變量的方程Q()稱之為Lagrange對偶函數(shù)。其約束條件為Ii yi0, i 0, i 1,2,，Ii,j 1在此約束條件之下，使得Q()達到最大值的 的許多分量為0,不為0的所對應(yīng)的樣本Xi就稱為支持向量。這就是支持向量的來歷。將樣本集當(dāng)在輸入空間不能實現(xiàn)線性分離，假設(shè)我們找到了非線性映射(x,yi)|x Rn; y 1,

7、1 ,i 1,.,I映射到高維特征空間H中，此時我們 考慮在H中的集合(x),yj|x Rn; yi 1, 1 ,i 1,i的線性分類，即 在H中構(gòu)造超平面，其權(quán)系數(shù)w滿足類似的極值問題。由于允許部分點可以 例外，那么可以引入松弛項，即改寫為：1 2 mi njlwll yi( w,x b) 1 i, i 0, i 1,2,.,I最終轉(zhuǎn)化為一個二次型在約束條件下的二次規(guī)劃問題:min D c2y 0, 0( 1,., J A (C,C)其中，y(y1,.,yJT，c ( 1,.,1)T，DK(Xi,Xj)yiVj1 i,j I為矩陣。K(x,s)是核函數(shù)。一分類問題是一個極端情形但卻又是非常有

8、用的，它可以表示為如下數(shù)學(xué)模型：設(shè)Xi |Xi Rn,i 1,.,I為空間Rn的有限觀測點，找一個以a為心，以R為半徑的包含這些點的最小球體。因此，一分類是對于求一個化合物成分的最小包絡(luò)曲面的最佳方法。與前面完全相同的手法，設(shè) 是由某個核函數(shù)K(x, s)導(dǎo)出的從輸 入空間到特征空間中的嵌入映射，最后可以得到二次規(guī)劃問題1 ' 'min D c2y 0, 0( 1,., J A (C,.'。)是核函數(shù)。此時Lf(x) K(x,x) 2iK(x,xi)iiLjiLiii jK (xi, xj )此時幾乎所有的點滿足f(x) R2。參數(shù)C起著控制落在球外點的數(shù)目，變化區(qū)間為

9、：1/L C 1.3.1.3基于線性規(guī)劃的SVM分類由于分類問題的自然推理過程都會歸結(jié)到二次規(guī)劃求解，計算復(fù)雜度相對較高。 如果能將其簡化為線性規(guī)劃而且沒有較大的誤差， 那么計算量將急速減少。于 是提出了基于線性規(guī)劃的SVM分類。此方法經(jīng)過數(shù)學(xué)嚴格推理，是合理的(因為 涉及泛函的知識較多， 推理過程放在附錄中)。因此產(chǎn)生了基于線性規(guī)劃一分類、 二分類、多分類。此處，我們僅給出基于線性規(guī)劃的 SVM分類的最終形式：minLCii1s.tLLi1i K ( xi , xj )j, j1,.,L;i 1; i, i 0i1解出 與 則得出決策函數(shù) f ( x)LiK(Xi,Xj)以及閾值。參數(shù)C控制

10、著滿足條i1件 f (x) 的樣本數(shù)量。特別核函數(shù)取為徑向函數(shù)時，參數(shù) 2越小，精度越高。另外，要提醒注意的是，在求解大規(guī)模分類問題得SVM算法實現(xiàn)時，需要以下輔助手段：停機準(zhǔn)則：由于分類問題等價于求對偶問題在約束條件下的極值Lmaxi 1Ls.tiyi0, 0i C, i 1,2,., Lj%yjK(x,Xj)而KKT條件iyi( w,(為) (C i) i 0, ib) 1 i01,2,.,L是收斂的充分必要條件。因此通過監(jiān)控KKT條件來得到停機條件i yi 0 i C, i 1,2,，Ly(L1, i 0, iiyK(Xi,Xj) b) 1, 0 i C, i j 11, i C, i這

11、個條件中的不等式不必嚴格成立，只要在一定誤差條件下成立就可以用了。選塊算法+分解法1.給定參數(shù)M 0,0, k 0。選取初始工作集W。T ,記其對應(yīng)的樣本點的下標(biāo)集為J0。令Wk T第k次更新的工作集，其對應(yīng)的樣本點的下標(biāo)集為Jk。2. 基于工作集Wk T ,由優(yōu)化問題LL Lmax ii jWyjK(x,Xj)i 1i 1 j 1LSti yi 0,0 i C, i Jkj 1求出最優(yōu)解?j, j Jk，構(gòu)造 k (；，f)按照如下方式:少j，3. 如果k已經(jīng)在精度內(nèi)滿足停機準(zhǔn)則，那么以此權(quán)系數(shù)構(gòu)造決策函數(shù)即可否則繼續(xù)下一步4.在T Wk中找出M個最嚴重破壞條件L1,i0, iyi(iyiK

12、(Xi,Xj)b)1, 0i C,j 11, iC, i加入Wk得出新的工作集 Wki，相應(yīng)的下標(biāo)集記為5.重復(fù)2) 3),直到樣本集耗完為止。序列最小優(yōu)化算法(SMOIn put: the observed dataset S(為),.，(Xi,y|x Rn, yj R ,輸入精度要求0及指定核函數(shù)K(x, y)，初始化0 0, k 0。Output: the classification of these samplesStep1.由更新公式k 1 k y2( E1_E2)22 Jk(%, xJK(X2,X2)2K(%,X2)k 1k( kk 1、11 y1y2( 22 )Step2.如果

13、第k步時達到停機要求，取近似解？k，否則繼續(xù)迭代，直到滿足停機為止，取為近似解。支持向量回歸(SVR模型對于分類，支持向量機相當(dāng)于導(dǎo)師樣本為有限集的情形。考慮導(dǎo)師集合為不可數(shù)的情形，例如訓(xùn)練集可以為形如S(冷 ),(冷 yJ|Xj Rn, yj R的情形，貝U演化出支持向量回歸概念。支持向量回歸也分為線性回歸和非線性回歸兩種， 但不是統(tǒng)計學(xué)中的線性或者非線性回歸了，而是根據(jù)是否需要嵌入到高維空間來劃分的，我們簡述如下：對于給定的樣本集S,以及任意給定的0，如果在原始空間Rn存在超平面 f(x) w,x b w Rn, b R 使得 |yi f(xj| ,(Xj,yj S，則稱f (x) w,x

14、 b是樣本集合S的 一線性回歸。與初等代數(shù)類似，$ f(xj|,(Xj,yj S等價于S中任何點以)到超平面 f (x) w,xb的距離不超過。由于我們是分類，所以希望/ l|w|2調(diào)整超平面的斜率 w使得與S中任點(Xj,yj距離都盡可能大。也即使得最大化，這等價于要求min |w|2。于是，線性回歸問題轉(zhuǎn)化J |w|2為優(yōu)化問題：min ； | w |2s.t| W, Xib y|, i 1,2,.,1于是，引入松弛變量，并使用Lagra nge乘子法，得到優(yōu)化問題的對偶形式:1 1 (min( i2 i,j i*i)( j*j)Xi, Xj1 1* *(ii )Yi( ii )i 1i

15、11s.t.( i i*)0, 0*i iCi ，ii 1,2,.,1i 1對于不可能在原始空間Rn就可以線性分離的樣本集S，先用一個非線性映射將數(shù)據(jù)S映射到一個高維特征空間中，使得(S)在特征空間H中具有很好 的線性回歸特征，先在該特征空間中進行線性回歸，然后返回到原始空間Rn 中。這就是支持向量非線性回歸。于是，支持向量非線性回歸的對偶優(yōu)化問題如下:*min ( i i )( j2i,j ils.t.( i i*) 0, 0i 1lj*) (x), (Xj)(i 1C, i 1,2,.,ll)y (i 1于是，非線性回歸問題的實施步驟為：1 尋找一個核函數(shù) K(s,t)使得 K(x,xJ(

16、Xi), (Xj),2 求優(yōu)化問題lllmin12l(ii,j 1*i)( jl*)K(Xi,Xj)( ii 1*i )yl(ii 1*i)s.t.li 1*(ii)0, 0i , iC,i h2,., l的解i j*i 03 .計算yjl(ii*)K(Xj,Xi),當(dāng) i(o,C)bi, j 1lyj(ii,j 1i*)K(Xj,Xi),當(dāng):(0，C)4. 構(gòu)造非線性函數(shù)l*nf(x) ( i i )K(Xj,x) b, X R , b R。i 13.2.2支持向量機分類與支持向量回歸的關(guān)系支持向量機用以分類和回歸，兩者到底是什么關(guān)系為了建立回歸與分類的關(guān)系， 我們在特征空間中考慮如下的上下

17、移動集合：D ( (X), Vi1)|(X,Yi) S , D ( (Xi), y 1)|(冷比)S對于充分大的，D與D是線性可分離的。于是得出關(guān)于 D與D分類。引入松弛變量，由SVM分類方法得到min】2st W zLCii 1b)i1, Z D ,W，z b) i1, z D , i 0, i 1,2,.|將目標(biāo)函數(shù)中的W改寫為W (WpW?),特別令w21,那么上式變成而基于觀測集Smi nllWJI2 1 C2i 1s.tv?1, (Xi)yW (Xi) yi 0, i 1,2,., li 1,i 1,(石，),，(N，yJ|N Rn, yj，在特征空間中尋找單參數(shù)約束下的回歸函數(shù)f(

18、x) w, (x) b的問題等價于min | w|2s.ty w, (Xi)b iw, (Xi)yib ii 0, i h2,.,丨也就是說，回歸問題可以通過分類的算法來實現(xiàn) 附錄：基于線性規(guī)劃的分類的合理性設(shè)輸入向量的空間為Rn，記Lp(Rn),1 p ,為Rn上一切p 絕對值可積函數(shù)g (即一切可測且滿足 n|g(x) |pd (x),按照通常的加法和數(shù)乘，構(gòu)成R的線性空間。一般地，我們偏好選則一個非線性映射將Rn嵌入到L2(Rn)空間。因為在該Hilbert空間中，任意閉子空間的正交補子空間存在問題是一個已解決 了的問題，而在Lp(Rn), p 2,還是一個沒有被完全解決的問題。 如前所

19、述，在此 空間中得到的結(jié)果，特別是誘導(dǎo)出的核函數(shù)是一個非常好的亮點。在有限維空間中，任何距離都是等價的。這一特征也是有限維空間獨有的。 類似于上面所述，我們可以在有限維空間 Rn上賦予Lp范數(shù)：l|x|p|Xi|Pi 1p取遍區(qū)間1,，特別，L范數(shù)就是通常的最大值范數(shù)：| x| max1in|Xi| ,Li范數(shù)就是通常的絕對值求和范數(shù)，L2范數(shù)就是通常的歐式范數(shù)。如果用w,x表示內(nèi)積，那么由 Holder不等式，我們得| w, x | |w|q|x|p，其中1p 1q 1是1,中的一對共軛數(shù)。假設(shè)一對平行的超平面為：fi(x)w,x d與f2(x)w,xb2，那么，兩個平面之間的距離為d(f1

20、, f2)|d b2|w|q特別，如果Rn上賦予的是L1范數(shù)，則d(f1, f2)|d b2|w|于是，導(dǎo)出相應(yīng)的優(yōu)化問題min w,b max| Wj |s.t y ( w, Xib) 1, i 1,2,.,l于是得到線性規(guī)劃：min as-t y(w, xb)1, i1,2,.,lawj,awj,j1,2,.,l, a,b R, w R簡化了計算。同理，對于不可分離的情況，引入松弛變量后可得lmin a C ii 1s.tyi(w,Xib) 1i, i 1,2,., laWj,aWj, j0,j 1,2,., l,a, b R, w Rn同理，對于非線性分類的情況，換成核函數(shù)min a Ci 1StYijYjK(Xj,Gj 1b1i,i 1,2,.,