支持向量機(jī)算法綜述

1、文章編號(hào):100220411(2002012045206支持向量機(jī)訓(xùn)練算法綜述劉江華程君實(shí)陳佳品(上海交通大學(xué)信息存儲(chǔ)研究中心上海200030摘要:本文介紹統(tǒng)計(jì)學(xué)習(xí)理論中最年輕的分支支持向量機(jī)的訓(xùn)練算法,主要有三大類(lèi):以SVM2 ligh t為代表的分解算法、序貫分類(lèi)方法和在線訓(xùn)練法,比較了各自的優(yōu)缺點(diǎn),并介紹了其它幾種算法及多類(lèi)分類(lèi)算法.最后指出了支持向量機(jī)具體實(shí)現(xiàn)的方向及其在模式識(shí)別、數(shù)據(jù)挖掘、系統(tǒng)辨識(shí)與控制等領(lǐng)域中的應(yīng)用.a關(guān)鍵詞:支持向量機(jī);訓(xùn)練算法;統(tǒng)計(jì)學(xué)習(xí)理論中圖分類(lèi)號(hào):T P391.4文獻(xiàn)標(biāo)識(shí)碼:BSUPPORT VECT OR M ACH INE TRA IN ING AL G

2、 OR ITH M:A REV IE WL I U J iang2huaCH EN G Jun2sh iCH EN J ia2p in(Inf or m ation S torag e R esearch Center,S hang hai J iaotong U niversity,S hang hai200030Abstract:T h is article in troduced the train ing algo rithm fo r the new est b ranch of statistic learn ing theo2 ry,SVM(Suppo rt V ecto r M

3、 ach ine,w h ich can be classified in to th ree catego ries:the first is the D ecompo si2 ti on A lgo rithm,w ho se delegate is SVM ligh t2,the second is sequence algo rithm,the th ird is on line train ing algo rithm.A ll the th ree k inds of algo rithm sadvan tages and disadvan tages w ere analysed

4、.A nd o ther algo2 rithm s and m u lti2class algo rithm s are in troduced too.T he fu tu re directi on and app licati on of SVM in pattern recogn iti on and data m in ing,and so on w ere in troduced.Keywords:suppo rt vecto r m ach ine,train ing algo rithm,statistical learn ing theo ry1引言(I n troduct

5、ion統(tǒng)計(jì)學(xué)習(xí)理論是目前針對(duì)小樣本統(tǒng)計(jì)估計(jì)和預(yù)測(cè)學(xué)習(xí)的最佳理論,它從理論上系統(tǒng)地研究了經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化原則成立的條件、有限樣本下經(jīng)驗(yàn)風(fēng)險(xiǎn)與期望風(fēng)險(xiǎn)的關(guān)系及如何利用這些理論找到新的學(xué)習(xí)原則和方法等問(wèn)題,而支持向量機(jī)作為統(tǒng)計(jì)學(xué)習(xí)理論的實(shí)現(xiàn)方法,受到廣大的研究者的注意.統(tǒng)計(jì)學(xué)習(xí)理論因?yàn)閷?duì)有限樣本情況下模式識(shí)別中的一些根本性問(wèn)題進(jìn)行了系統(tǒng)的理論研究,在很大程度上解決了模型選擇與過(guò)學(xué)習(xí)問(wèn)題、非線性和維數(shù)災(zāi)問(wèn)題、局部極小點(diǎn)問(wèn)題等,因此成為研究的熱點(diǎn)24,22.24、43分別對(duì)支持向量機(jī)的原理作了簡(jiǎn)要的介紹,并和神經(jīng)網(wǎng)絡(luò)作了比較,本文則對(duì)支持向量機(jī)的訓(xùn)練算法進(jìn)行詳細(xì)討論.V ap n ik6將支持向量機(jī)問(wèn)題歸

6、結(jié)為一個(gè)二次型方程求解問(wèn)題.V ap n ik通過(guò)對(duì)線性不可分的兩類(lèi)問(wèn)題的最優(yōu)分類(lèi)形式提出的.即使兩類(lèi)無(wú)錯(cuò)誤地分開(kāi),并使兩類(lèi)的分類(lèi)間隙(M argin最大.問(wèn)題的數(shù)學(xué)形式為:U(w,N=12(ww+Cli=1N is.t.y i(wx i+b1-N i,i=1,lN i0,i=1,l.通過(guò)求其對(duì)偶問(wèn)題,歸結(jié)為一個(gè)二次函數(shù)極值問(wèn)題:W(A=li=1A i-12li,j=1y i y j A i A j K(x i,x js.t.0A iC,i=1,lli=1A i y i=0分類(lèi)判別函數(shù)為:f(x=sign(li=1A i y i K(x,x i+b對(duì)于這個(gè)二次規(guī)劃問(wèn)題,經(jīng)典的解法有積極方第31

7、卷第1期2002年2月信息與控制Info rm ati on and Con tro lV o l.31,N o.1Feb.,2002a收稿日期:2001-06-05集法、對(duì)偶方法、內(nèi)點(diǎn)算法28等,但是當(dāng)訓(xùn)練樣本增多時(shí),這些算法便面臨著維數(shù)災(zāi),或者由于內(nèi)存的限制,而導(dǎo)致無(wú)法訓(xùn)練,無(wú)法應(yīng)用SVM進(jìn)行模式分類(lèi)和函數(shù)估計(jì).所以如何訓(xùn)練大訓(xùn)練集的SVM便成為SVM實(shí)際應(yīng)用的瓶頸問(wèn)題.2各種訓(xùn)練算法介紹及比較(I n troduction to d ifferen t tra i n i ng a lgor ith m s and com-par ison between themm in V(d=g(

8、A(tT ds.t.y T d=0;d i0fo r i:A i=0;d i0fo r i:A i=C;-1d1;ßd i:d i0ß=q;解上述最優(yōu)問(wèn)題即得工作集.在實(shí)現(xiàn)細(xì)節(jié)上, Joach i m s對(duì)常用的參數(shù)進(jìn)行緩存(Cache,并對(duì)Q P 問(wèn)題進(jìn)行Sh rink ing,從而使算法能較好地處理大規(guī)模的訓(xùn)練集問(wèn)題.Ch ih2W ei H su11通過(guò)改變SVM的提法提出了一種類(lèi)似1中的簡(jiǎn)單訓(xùn)練算法B SVM.主要是針對(duì)SVM得到一種不同的數(shù)學(xué)提法,從而使算法簡(jiǎn)單易行.Ch ih2W ei H su和Ch ih2Jen L in綜合S.S. Keerth i10中的

9、修改過(guò)的S M O和SVM ligh t中的工作集選擇算法,用C+實(shí)現(xiàn)一個(gè)庫(kù)L I B SVM,可以說(shuō)是使用最方便的SVM訓(xùn)練工具.L I B SVM供用戶選擇的參數(shù)少,用訓(xùn)練特大訓(xùn)練集時(shí),還是使用靈64信息與控制31卷活的SVM light或S M O.第二類(lèi)是序貫分類(lèi)法,基本思想是考慮訓(xùn)練樣本序貫加入,同時(shí)考慮其對(duì)支持向量有何影響.46基于感知機(jī)中的A datron算法,對(duì)L agrange系數(shù)和支持向量機(jī).特點(diǎn)是訓(xùn)練樣本序貫進(jìn)入,L agrange 系數(shù)的改變采用梯度法.47提出了將另一種梯度序貫算法,特點(diǎn)是將SVM原問(wèn)題中的偏置b也看作系數(shù),從而使該梯度算法適合軟間隔(Soft m a

10、r2 gin和回歸情形.Scho b lkop f18,19提出了一個(gè)新的SVM分類(lèi)器v2SVM,將待優(yōu)化問(wèn)題變?yōu)?m in 12wT w-vp+1lli=1N is.t.y i(w T U(x i+bQ-N i,N i0,i=1,l,Q0其中,x i是訓(xùn)練樣本向量,y i=1o r-1表示對(duì)應(yīng)的類(lèi).x i被函數(shù)映射到一個(gè)高維空間.M ing_H suan Yang40提出了訓(xùn)練支持向量機(jī)的幾何方法.主要是利用了訓(xùn)練集中的集合信息,提出了“衛(wèi)向量”(Guard vecto r的概念,“衛(wèi)向量”即為通過(guò)該向量能使輸入空間線性可分的向量.所有的“支持向量”都是“衛(wèi)向量”,但反之不成立.當(dāng)訓(xùn)練集合較

11、大時(shí),可以先找出“衛(wèi)向量”,再以“衛(wèi)向量”構(gòu)成傳統(tǒng)的Q P問(wèn)題求出“支持向量”.“衛(wèi)向量”的求解是通過(guò)判斷其對(duì)偶空間中的線性規(guī)劃問(wèn)題的可行性而不是求其解,從而使問(wèn)題大大簡(jiǎn)化.試驗(yàn)表明該算法求得的最優(yōu)分類(lèi)面和傳統(tǒng)Q P問(wèn)題一樣,但速度要快30倍,內(nèi)存要求為傳統(tǒng)的14.主要原因是“衛(wèi)向量”只是“支持向量”的20倍左右.m inw,b,eJ=12wT w+C12Nk=1e2k,s.t.y kw T U(x k+b=1-e k,k=1,N定義L agrange函數(shù)L=J-Nk=1A ky kw T U(x k+b-1+e k其中A k為L(zhǎng) agrange乘子,根據(jù)KT T最優(yōu)條件:5L5w=0w=Nk

12、=1A k y k U(x k,5L5b=0w=Nk=1A k y k=0,5L5e k=0A k=Ce k,5L5e k=0y kw T U(x k+b-1+e k=0對(duì)于k=1,N上式消去w和e,得到如下線性系統(tǒng):741期劉江華等:支持向量機(jī)訓(xùn)練算法綜述YTYZ Z T+C -1 I bA=1其中,Z =U (x 1T y 1;U (x N T y N ,Y =y 1;y N ,1=1;1,e =e 1;e N ,A =A 1;A N 上述線性系統(tǒng)用最小二乘法即可解.44提出了SO R 方法,通過(guò)在原目標(biāo)函數(shù)中加一項(xiàng)b 2,從而對(duì)偶問(wèn)題多了一項(xiàng),而約束條件少了一項(xiàng)等式約束,變?yōu)檫吔缂s束條件

13、下二次規(guī)劃問(wèn)題,適合迭代求解.同時(shí)應(yīng)用矩陣分解技術(shù),每次只需更新L agrange 乘子的一個(gè)分量,從而不需將所有樣本載入內(nèi)存,提高了收斂速度.以上的算法,大部分都是針對(duì)兩類(lèi)問(wèn)題,那么對(duì)于多類(lèi)問(wèn)題,SVM 的算法有以下幾種.標(biāo)準(zhǔn)算法7是,對(duì)于N 類(lèi)問(wèn)題構(gòu)造N 個(gè)兩類(lèi)分類(lèi)器,第i 個(gè)SVM 用第i 類(lèi)中的訓(xùn)練樣本作為正的訓(xùn)練樣本,而將其它的樣本作為負(fù)的訓(xùn)練樣本.這個(gè)算法稱(chēng)為12a 2r (12agin st 2rest .最后的輸出是兩類(lèi)分類(lèi)器輸出為最大的那一類(lèi)(此時(shí),兩類(lèi)分類(lèi)器的判決函數(shù)不用取符號(hào)函數(shù)sgn .其缺點(diǎn)是它的推廣誤差無(wú)界.另外一個(gè)算法是由Knerr 17提出,該算法在N 類(lèi)訓(xùn)練樣

14、本中構(gòu)造所有可能的兩類(lèi)分類(lèi)器,每類(lèi)僅僅在N 類(lèi)中的2類(lèi)訓(xùn)練樣本上訓(xùn)練,結(jié)果共構(gòu)造K =N (N -12個(gè)分類(lèi)器,我們稱(chēng)該算法為12a 21(12agin st 21.組合這些兩類(lèi)分類(lèi)器很自然地用到了投票法,得票最多(M ax W in s 的類(lèi)為新點(diǎn)所屬的類(lèi).U .K re B el18用該方法訓(xùn)練多類(lèi)SVM 取得了很好的結(jié)果.12a 21算法的缺點(diǎn)是:1如果單個(gè)兩類(lèi)分類(lèi)器不規(guī)范化,則整個(gè)N 類(lèi)分類(lèi)器將趨向于過(guò)學(xué)習(xí);2推廣誤差無(wú)界;3分類(lèi)器的數(shù)目N (N -12隨類(lèi)數(shù)N 急劇增加,導(dǎo)致在決策時(shí)速度很慢.J .W eston 12提出了兩種新的多類(lèi)SVM 算法.其一是qp 2m c 2sv 算法

15、,它很自然地在構(gòu)造決策函數(shù)時(shí),同時(shí)考慮所有的類(lèi).將原始優(yōu)化問(wèn)題推廣為:U (w ,N=12km =1(w m w m +Cli =1m y iNmis .t .(w i x i +b y i (w m x i +b m +2-N miN mi 0,i =1,l m 1,k y i 相應(yīng)地決策函數(shù)變?yōu)?f (x =arg m ax k(w i x +b i ,i =1,k當(dāng)k 取2時(shí),和兩類(lèi)分類(lèi)問(wèn)題等價(jià).其二是:線性規(guī)劃的方法lp 2m csv .原始最優(yōu)問(wèn)題變?yōu)?li =1A i+Cli =1j y iN i,s .t .m :y m =y iA m K (x i ,x m +b y iA n

16、 K (x i ,x n +b y j +2-N ji A i 0,N j i 0,i =1,l ,j 1,k y i決策函數(shù)為:f (x =arg m ax n(i :y i =nA iK (x ,x i+b n 以上兩方法的缺點(diǎn)是計(jì)算量都比較大,優(yōu)點(diǎn)是得到的決策分類(lèi)面的支持向量機(jī)的數(shù)量均比常規(guī)方法少.關(guān)于多類(lèi)的L S 2SVM 分類(lèi)器,J .A .K .Suyken s29使用了類(lèi)似J .W eston 12中的方法一.P latt 16等提出了一個(gè)新的學(xué)習(xí)架構(gòu):決策導(dǎo)向的循環(huán)圖(D ecisi on D irected A cyclic Grap h ,DDA G ,將多個(gè)兩類(lèi)分類(lèi)器組合

17、成多類(lèi)分類(lèi)器.對(duì)于N 類(lèi)問(wèn)題,DDA G 含有N (N 212個(gè)分類(lèi)器,每個(gè)分類(lèi)器對(duì)應(yīng)兩類(lèi).其優(yōu)點(diǎn)是推廣誤差只取決于類(lèi)數(shù)N ,和節(jié)點(diǎn)上的類(lèi)間間隙(M argin ,而與輸入空間的維數(shù)無(wú)關(guān),根據(jù)DDA G 提出算法DA GSVM ,DDA G 的每個(gè)節(jié)點(diǎn)和一個(gè)12a 21分類(lèi)器相關(guān),其速度顯著比標(biāo)準(zhǔn)算法或取最大算法(M an W in s 快.總之,以上的算法為SVM 的實(shí)用起到了推動(dòng)作用,尤其是有些算法還適用于回歸和函數(shù)估計(jì)問(wèn)題,如:S M O .3支持向量機(jī)的應(yīng)用及發(fā)展方向(Appl ica -tion and future d irection of SV M 支持向量機(jī)在模式識(shí)別32,3

18、6(字符識(shí)別42、文本自動(dòng)分類(lèi)25、人臉檢測(cè)1,27,39、頭的姿態(tài)識(shí)別41、函數(shù)逼近23,33、數(shù)據(jù)挖掘37和非線性系統(tǒng)控制50中均有很好的應(yīng)用.在1中用2階多項(xiàng)式核,上界C 設(shè)為200.訓(xùn)練樣本是50000個(gè)19乘19大小的人臉圖像和45000個(gè)同樣大小非臉圖像.訓(xùn)練算法是O suna 提出的分解算法.訓(xùn)練出來(lái)的SVM 分類(lèi)器同Sung 38的NN 分類(lèi)器進(jìn)行了比較,檢測(cè)速度有所提高,但錯(cuò)誤率也比Sung 的方法高.其應(yīng)用主要在靜止圖像中有無(wú)人臉.39使用了這個(gè)SVM 來(lái)實(shí)時(shí)檢測(cè)人臉,速度是每秒25幀.84信息與控制31卷本文綜合介紹了現(xiàn)有的SVM訓(xùn)練算法,說(shuō)明了各種的算法的思路和優(yōu)缺點(diǎn).

19、今后SVM的訓(xùn)練算法的研究方向主要是確定不同的優(yōu)化目標(biāo),根據(jù)KKT約束優(yōu)化條件尋找大規(guī)模訓(xùn)練樣本下的實(shí)用算法,應(yīng)用于模式識(shí)別時(shí)的多類(lèi)問(wèn)題目前還沒(méi)有特別好的算法.一種訓(xùn)練算法不但要有理論上的收斂的證明,同時(shí)也應(yīng)該有實(shí)用的可行的算法實(shí)現(xiàn),這樣SVM的應(yīng)用才會(huì)更廣泛.目前在線訓(xùn)練是研究重點(diǎn),因?yàn)檫@是應(yīng)用于系統(tǒng)辨識(shí)和控制及信號(hào)處理中的關(guān)鍵.參考文獻(xiàn)(R eferences1O suna E,F reund R,Giro si F.T raining suppo rt vecto r m a2 ch ines:A n app licati on to face detecti on.In P rocee

20、dings of CV PR97,Puerto R ico,19972Joach i m s T.M ak ing large2Scale SVM L earning P ractical.A d2 vances in Kernel M ethods-Suppo rt V ecto r L earning,Sch?lkopf B.et al.(ed.,M IT P ress,19994Joach i m s T.T ext Catego rizati on w ith Suppo rt V ecto r M a2 ch ines:L earning w ith M any R elevant

21、Features.P roc.of the European Conf.on M ach ine L earning,Sp ringer,19985Joach i m s T.M ak ing large-Scale SVM L earning P ractical.L S82R epo rt,24,U niversity Do rtm und,L S V III2R epo rt,1998 6V apnik V N.T he N ature of Statistical L earning T heo ry.Sp ringer,19957V apnik V N.Statistical L e

22、arning T heo ry.N ew Yo rk,W iley, 19988Co lin C.A lgo rithm ic A pp roaches to T raining Suppo rt V ecto r M ach ines:A Survey.P roceedings of ESANN2000(D-Facto Publicati ons,Belgium,2000,27369John C P.Fast T raining of Suppo rt V ecto r M ach ines using Se2 quential M ini m al Op ti m izati on.In

23、Scho lkopf B.et al(ed.,A dvances in Kernel M ethods2Suppo rt V ecto r L earning,Cam2bridge,M A,M IT P ress,1999,18520811Ch ih W H,et al.A Si m p le D ecompo siti on M ethod fo r Suppo rt V ecto r M ach ines.T echnical repo rt,N ati onal T ai w an U niversi2 ty,199912W eston J,W atk ins C.M ultilass

24、Suppo rt V ecto r M ach ines.TR CSD TR9804,D epartm ent of Computer Science Egham, Surrey TW200EX,England,199813Chang C C,H su C W,L in C J.T he analysis of decompo siti on m ethods fo r suppo rt vecto r m ach ines.In W o rk shop on Suppo rt V ecto r m ach ines,I JCA I,199914Keerth i S S,et al.A Fas

25、t Iterative N earest Po int A lgo rithmfo r Suppo rt V ecto r M ach ine C lassifier D esign.TR-ISL-99-03D ep t.of CS and A uto.Indian Institute of Science Banga2 lo re,India,199915Keerth i S S.Convergence of a Generalized S M O A lgo rithm fo r SVM C lassifier D esign TR CD-00-01Contro l D ivisi on

26、D ep t.of M echa.and P rod.Engineering N ati onal U niversity of Singa2 po re Singapo re,200016P latt J,et al.L arge M argin DA Gs fo r M ulticlass C lassifica2 ti on,in A dvances in N eural Info rm ati on P rocessing System s 12,M IT P ress,2000,54755317Knerr S,et al.Single2layer learning revisited

27、:A stepw ise p ro2 cedure fo r building and training a neural netwo rk.In Fogel m an -Soulie et al.(ed.,N eurocomputing:A lgo rithm s,A rch itec2 tures and A pp licati ons,NA TO A S I.Sp ringer,199018K re?el U.Pairw ise classificati on and suppo rt vecto r m ach ines.In B.Scho lkopf,ed.A dvances in

28、Kernel M ethods:Suppo rt V ecto r L earning,pages M IT P ress,Cam bridge,M A,1999, 25526819Sch?lkopf B,et al.E sti m ating the suppo rt of a h igh2di m ensi on2 al distributi on.TR99-87,M icro soft R esearch.199920Scho b lkopf B,et al.N ew suppo rt vecto r algo rithm s.N eural Computati on,2000,12:1

29、083112126Zhang X.U sing class2center vecto rs to build suppo rt vecto r m ach ines.In P roceedings of NN SP99,199927L u CY,Yan P F,Zhang C S.Face recogniti on using suppo rt vecto r m ach ine,In po rc.O f I CNNB98,Beijiing,1998,652 65530M assi m iliano P,A lessandro V.O bject R ecogniti on w ith Sup

30、2 po rt V ecto r M ach ines,IEEE T rans.on PAM I,1998,20(6: 63764631Suykens J A K,J V andew alle.L east squares suppo rt vecto r m ach ine classifiers.N eural P rocessing L etters,1999,9(3: 29330032Burges C J C.A T uto rial on Suppo rt V ecto r M ach ines fo r Pat2 tern R ecogniti on.Know ledge D is

31、covery and D ata M ining, 1998,2(233Smo la A J,Scho lkopf B.A tuto rial on suppo rt vecto r regres2 si on.N euroCOL T TR N C-TR-98-030,Royal Ho llow ay Co llege,U niversity of L ondon,U K,1998941期劉江華等:支持向量機(jī)訓(xùn)練算法綜述50 信息與控制 模式識(shí)別與人工智能, 2000, 13 (3 : 285 290 31 卷 34 Pon til M , V erri M. Suppo rt vecto r

32、 m ach ines fo r 3 - d ob ject recogn ition. IEEE T ran s. PAM I, 1998, 20: 637 646 35Roobaert D. I p roving the generalization of linear suppo rt vec2 m to r m ach ines: an app lication to 3d ob ject recogn ition w ith clu t2 tered backg round. In P roc. SVM W o rk shop at IJCA I99, 44 O lvi L M ,

33、D avid R M. Successive O verrelax iation fo r Suppo rt V ecto r M ach ines. IEEE T ran s. O n N eu ral N etw o rk s. 1999, 10 (5 : 1032 1037 45 Ronan C, Sam y B. Suppo rt V ecto r M ach ines fo r L arge 2Scale R eg ression P rob lem s, I I P - RR 00 - 17. h ttp: DA ap. ch, 2000 46 F riess T T , et a

34、 l. T he kernel2adatron algo rithm : A fast and si p le m learn ing p rocedu re fo r suppo rt vecto r m ach ines, www. id i2 Stockho lm , Sw eden, 1999 36 Roobaert D , H u lle M M V an. V iew 2based 3d ob ject recogn ition w ith suppo rt vecto r m ach ines. In IEEE N eu ral N etw o rk s fo r Signal

35、P rocessing W o rk shop , 1999 37B rad ley P. M athem atical P rog ramm ing A pp roaches to M ach ine L earn ing and D ata M in ing. PhD thesis, U n iversity of W iscon 2 sin, Com p u ter Sciences D ep artm en t, M ad ison, W I, U SA , TR 2 98211, 1998 38Sung K, Pogg io T. Exam p le2base L earn ing

36、fo r V iew 2base H u 2 . . m an Face D etection. A. I M em o 1521, M IT A. I L ab. , D e2 cem ber 1994 39 Kum ar V , Pogg io T. L earn ing 2based A pp roach to R eal T i e m T rack ing and A nalysis of Faces. In: P roceed ing s of the Fou rth In ternational Conference on Face and Gestu re R ecogn ition, Grenob le, F rance, M arch, 2000 40 Yang M H , A hu ja N. A Geom etric A pp roach to T rain Suppo rt V ecto r M ach ines, In P roceed ing s of CV PR 2000, H ilton H ead ICM L 98, 1998: 188 196 47 V ijayakum ar S, W u S. Sequen tial Suppo rt V ecto r C lassifiers and R eg