Զѧ
ACTA AUTOMATICA SINICA
2000Vol.26No.1P.32-42



ͳѧϰ֧
ѧ
ժ Ҫ ģʽʶ𡢺ϼܶȹƵȶڻѧϰ⣬зҪǴͳͳѧǰ㹻ĿʱȡЧ.ͳѧϰ(SLT)VapnikһСͳۣоСµͳƹɼѧϰ.SLTΪѧϰ⽨һϺõۿܣҲչһµͨѧϰ㷨֧(SVM)ܹϺõĽСѧϰ.ĿǰSLTSVMѳΪϻѧϰµоȵ.һƪּڽSLTSVMĻ˼롢صоչ״ѧߵĽһע.
ؼ ͳѧϰۣ֧ѧϰģʽʶ.
INTRODUCTION TO STATISTICAL LEARNING THEORY
AND SUPPORT VECTOR MACHINES
ZHANG Xuegong
(Dept.of Automation,Tsinghua University,Beijing 100084)
(State Key Laboratory of Intelligent Technology and Systems of China)
Abstract Databased machine learning covers a wide range of topics from pattern recognition to function regression and density estimation. Most of the existing methods are based on traditional statistics, which provides conclusion only for the situation where sample size is tending to infinity. So they may not work in practical cases of limited samples. Statistical Learning Theory or SLT is a small sample statistics by Vapnik et al., which concerns mainly the statistic principles when samples are limited, especially the properties of learning procedure in such cases. SLT provides us a new framework for the general learning problem, and a novel powerful learning method called Support Vector Machine or SVM, which can solve smallsample learning problems better. It is believed that the study of SLT and SVM is becoming a new hot area in the field of machine learning. This review introduces the basic ideas of SLT and SVM, their major characteristics and some current research trends.
Key words Statistical learning theory, support vector machine, machine learning, pattern recognition.
1 
ݵĻѧϰִܼеҪ棬оӹ۲ݣѰҹɣЩɶδݻ޷۲ݽԤ.ģʽʶڣлѧϰͬҪۻ֮һͳѧ.ͳͳѧоĿʱĽۣѧϰҲǻڴ˼.ʵУ޵ģһЩϺѧϰʵбȴܲ.
봫ͳͳѧȣͳѧϰۣStatistical Learning TheorySLTһרоС»ѧϰɵ.V. Vapnik˴ʮʼڴ˷о1ݣʮڣ۵ĲϷչͳ죬ҲѧϰȱʵԽչͳѧϰۿʼܵԽԽ㷺ӣ2,3.
ͳѧϰǽһ׽ϼʵۻ֮ϵģΪѧϰṩһͳһĿ.ܽܶзУԭԽ⣨ṹѡ⡢ֲСȣͬʱһۻϷչһµͨѧϰ֧Support Vector MachineSVMѳֳܶз.һЩѧΪSLTSVMڳΪо֮µоȵ㣬ƶѧϰۺͼķչ3.
ҹڰʮĩѧע⵽ͳѧϰ۵Ļɹ4ݣ֮оĿǰֻٲѧʶҪо.ּڽͳѧϰۺ֧Ļ˼ص㣬ʹѧܹǵƴӶо.µڶڸѧϰһʾҪзһЩ⣻ڽSLTĻ˼ӰĽۣĽڽSVMԭӦüɴ˷չ.
2 ѧϰĻ
2.1 ıʾ
ѧϰĿǸݸѵĳϵͳ֮ϵĹƣʹܹδ֪׼ȷԤ.һرʾΪyxһδ֪ϵѭĳһδ֪ϸF(x,y)xy֮ȷԹϵԿѧϰǸnֲͬ۲
(1)
һ麯f(x,w)һŵĺf(x,w0)ϵйƣʹ
R(w)=L(y,f(x,w))dF(x,y)(2)
С.Уf(x,w)Ԥ⺯wΪĹf(x,w)ԱʾκκL(y,f(x,w))Ϊf(x,w)yԤɵʧͬ͵ѧϰвͬʽʧ.Ԥ⺯Ҳѧϰѧϰģͻѧϰ.
Ļѧϰ⣬ģʽʶ𡢺ƽ͸ܶȹ.ģʽʶ⣬y1)y=0,11,-1Ԥ⺯ָʾʧԶΪ
(3)
ʹСBayesʹС.ںƽУyΪֵʧɶΪ
L(y,f(x,w))=(y-f(x,w))2,(4)
Сƽ׼.Ըܶȹ⣬ѧϰĿǸѵȷxĸܶ.ǹƵܶȺΪp(x,w)ʧԶΪ
L(p(x,w))=-logp(x,w).(5)
2.2 С
УѧϰĿʹСǣǿõϢֻ(1)(2)ʽղ޷㣬˴ͳѧϰвνСERM׼򣬼徭
(6)
Ϊ(2)ʽĹƣѧϰ㷨ʹС.ʧ(3)վѵʣ(4)ʽʧվƽѵ(5)ʽʧERM׼͵ȼȻ.
ʵϣERM׼Сûоֱֵֻ֤Ϻ뵱Ȼ˼ȴڶĻѧϰоռҪλ.Ƕ󲿷עеθõСϣʵϣʹԼٶnʱ(6)ʽ(2)ʽںܶеĿҲȥԶ.ôERM׼õĽʹʵҲС
2.3 ƹ
ERM׼򲻳ɹһĹѧϰ.ʼܶעʹRemp(w)Сܿͷ֣ѵСܵºõԤЧ.ĳЩ£ѵСᵼƹ½ʵյӣǹѧϰ.
֮ԳֹѧϰһΪ֣ѧϰƲǻ.һ򵥵ӣһʵ{x,y}yȡֵڣ0,1֮䣬ôʲôģͲģֻҪúf(x,)=sin(x)ȥǣǴܹҵһʹѵΪ㣬Ȼõġšȷʵĺģ.ԭͼһʮָӵģȥ޵ɥʧƹ.У޵˵ѧϰǿԼסÿʱպܿͿС㣬ȴ޷֤δܸõԤ.ѧϰĸƹ֮ìͬѧϰп.
ף3ݸһʵӣģy=x210ֱһһκһκݪERMԭȥϣʾȻʵģǶΣӰ죬һκԤĽ.ͬʵ100Σ71%ĽһϺڶ.
ɴ˿ɿ£1)СһζС2)ѧϰĸԲӦоϵͳйأҪĿӦ.ҪһָܹС½Чѧϰƹ㷽.
3 ͳѧϰ۵ĺ
ͳѧϰ۾оСͳƹƺԤۣҪݰĸ2ݣ
1) С׼ͳѧϰһԵ
2) Щ¹ͳѧϰƹԵĽĽۣ
3) ЩĻϽС׼
4) ʵµ׼ʵʷ㷨.
УָԵ۽ƹԵĽ磬صһĸVCά.
3.1 VCά
ΪоѧϰһٶȺƹԣͳѧϰ۶һϵйغѧϰָܵ꣬ҪVCάVapnikChervonenkis Dimension.ģʽʶ𷽷VCάֱ۶ǣһָʾhܹеĺпܵ2hʽֿƺܹhɢVCάܴɢĿh.ĿкܽǴɢVCά.нʵVCάͨһֵתָʾ.
VCάӳ˺ѧϰVCάԽѧϰԽӣԽ.źǣĿǰûͨõĹ⺯VCάֻۣһЩĺ֪VCά.nάʵռԷʵVCάn+1һf(x,)=sin(x)VCάΪ.һЩȽϸӵѧϰ磩VCά뺯ṹй⣬ѧϰ㷨ȵӰ죬ȷ.ڸѧϰΣۻʵķVCάǵǰͳѧϰдоһ5.
3.2 ƹԵĽ
ͳѧϰϵͳо˶ڸ͵ĺպʵʷ֮ĹϵƹԵĽ2.⣬ǣָʾекʹСĺRemp(w)ʵʷR(w)֮1-ǵĸ¹ϵ6ݣ
(7)
hǺVCάn.
һ۴˵ѧϰʵʷɵģһǾգѵһֳŷΧѧϰVCάѵй.Լ򵥵رʾΪ
R(w)Remp(w)+(h/n).(8)
ѵ£ѧϰVCάԽߣԽߣŷΧԽ󣬵ʵ뾭֮ܵĲԽ.Ϊʲôֹѧϰԭ.ѧϰ̲ҪʹСҪʹVCάССŷΧȡýСʵʷգδнϺõƹ.
ҪָƹԵĽǶĽۣںܶǽɵģ䵱VCάϸʱˣף6ָhn0.37ʱ϶ɳڵģVCάʱͲٳ1).ңֻֽڶͬһѧϰбȽʱЧָǴӺѡŵĺڲ֮ͬȽȴһ.Vapnikָ2ݣѰҸõطӳѧϰĲ͵õĽѧϰ۽о֮һ.
3.3 ṹС
ĽۿERMԭʱǲģҪͬʱСպŷΧ.ʵڴͳУѡѧϰģͺ㷨Ĺ̾ǵŷΧḶ́ģͱȽʺеѵ൱h/nֵʵȡñȽϺõЧ.Ϊȱָѡֻ֪ʶ;飬ȷʹߡɡĹ.
ͳѧϰһµĲԣѺΪһӼУʹӼVCάĴС༴ĴСУÿӼѰСգӼԿǾպŷΧȡʵʷյСͼ1ʾ.˼ṹСStructural Risk MinimizationС4ݣSRM׼.ͳѧϰۻ˺ĺӼṹӦSRM׼ʵʷʣ2.

ͼ1 Сʾͼ
ʵSRMԭ˼·һÿӼСգȻѡʹСպŷΧ֮СӼ.ȻַȽϷʱӼĿܴʱ.еڶ˼·ƺĳֽṹʹÿӼжȡСľգʹѵΪ0ȻֻѡѡʵӼʹŷΧСӼʹСĺź.֧ʵϾ˼ľʵ.ף3һЩӼṹ1)θSRM׼ĳЩͳиĽ.
4 ֧
֧SVMͳѧϰݣҲʵõĲ.19921995ģ7,8,9,2ݣĿǰԴڲϷչ׶.
4.1 ŷ
SVMǴԿɷµŷ淢չģ˼ͼ2ά˵.ͼУʵĵͿĵHΪߣH1,H2ֱΪƽڷߵֱߣ֮ľmargin.νŷ߾Ҫ߲ܽȷֿѵΪ0ʹ.߷Ϊxw+b=0ǿԶйһʹöԿɷֵ(xi,yi)i=1,,n,xRdyʣ+1,-1
(9)

ͼ2 Կɷµŷ
ʱ2/wʹȼʹw2С.(9)ʹСķͽŷ棬H1,H2ϵѵͳ֧.
ʹʵϾǶƹĿƣSVMĺ˼֮һ.ͳѧϰָ2ݣNάռУֲһ뾶ΪRĳΧڣwAƽ湹ɵָʾf(x,w,b)=sgn(wx)+b(sgn( )ΪźVCάĽ
hmin(R2A2,N)+1.(10)
ʹw2СʹVCάϽСӶʵSRM׼жԺԵѡ.
LagrangeŻ԰ŷתΪż6ݣԼ
(11a)

i0, i=1,,n(11b)
¶Ԧiкֵ
(12)
iΪÿӦLagrange.һʽԼ¶κѰŵ⣬Ψһ.֤нֻһ֣ͨٲ֣iΪ㣬Ӧ֧.õŷຯ
(13)
ʽеʵֻ֧.b*Ƿֵһ֧(9)ʽеĵȺţãͨһ֧ȡֵ.
Բɷֵ£(9)һɳi0Ϊ
(14)
ĿΪСԿٴ͵õŷ.УC>0һƶԴͷĳ̶.ŷĶżԿɷ¼ȫֻͬ(11b)Ϊ
0ܦiC, i=1,,n.(15)
4.2 ֧
NάռеԺVCάΪN+1ʽ(10)ĽۣڡwAԼVCάܴСʹʮָάĿռҲԵõСVCάĺģ2н1013άռȡVCά103ҵķӣԱ֤нϺõƹ.ͬʱǿͨԭתΪż⣬ĸӶȲȡڿռάȡе֧.ЩصʹЧضԸάΪ.
Է⣬ͨԱ任תΪĳάռе⣬ڱ任ռŷ.ֱ任ܱȽϸӣ˼·һ²ʵ.ע⵽ĶżУѰź(12)Ƿຯ(13)ֻ漰ѵ֮ڻ(xixj)ڸάռʵֻڻ㣬ڻǿԭռеĺʵֵģûбҪ֪任ʽ.ݷйֻۣҪһֺ˺K(xi,xj)㪫MercerͶӦĳһ任ռеڻ2.
ˣŷвʵڻK(xi,xj)ͿʵĳһԱ任Է࣬㸴ӶȴûӣʱĿ꺯(12)Ϊ
(16)
ӦķຯҲΪ
(17)
֧.
˵֧ͨڻķԱ任ռ任һάռ䣬ռ󣨹壩ŷ.SVMຯʽһ磬мڵϣÿмڵӦһ֧ͼ3ʾ.

ͼ3 ֧ʾͼ
4.3 ˺
SVMвͬڻ˺γɲͬ㷨Ŀǰоĺ˺Ҫ࣬һǶʽ˺
(18)
õq׶ʽǾRBF
(19)
÷봫ͳRBFҪǣÿĶӦһ֧ǼȨֵ㷨Զȷ.ҲԲSigmoidΪڻ
K(x,xi)=tanh(v(xxi)+c),(20)
ʱSVMʵֵľǰһĶ֪ڵ㷨Զȷģ㷨緽ľֲС.
4.4 ںϵSVM
SVMҲԺܺõӦںУ1012ݣ˼·ģʽʶʮ.ȿԻع麯f(x)=wx+bݣxi,yi,i=1,,n,xiRd,yiR⣬ѵݶھȦԺϣ
(21)
ŷ󻯷ƣƺԵķʹع麯ƽ̹ȼСǵɳӦi0ͦ*i0(21)
(22)
ŻĿСC0ƶԳŵĳͷ̶.ͬŻԵõż.
(23)
£LagrangeӦi,*iĿ꺯
(24)
ûع麯Ϊ
(25)
ģʽʶеSVMһi,*iҲֻСֲΪ0ǶӦ֧һں仯ȽϾҵλϵҲֻ漰ڻ㣬ֻҪú˺K(xi,xj)(24)(25)еڻͿʵַԺ.
4.5 ˺ɷַ
SVMһҪʾڻʵĳַԱ任˼ҲеõӦãȽϳɹӾú˺ʵַɷַ1314ݣǴͳɷַPCAƹ.
x1,,xnɷַǾ.xзԱ任(x)ɵvԭķɷַ.ÿʽڻ
(26)
֤vдɽ(26)ʽУ
(27)
KijΪĵiеjиԪأԵõ
na=Ka,(28)
дӾKav(x)ռɷַ.ԭռеxڱ任ռеɷǦ(x)ɷַvϵͶӰ
(29)
ȻSVM㷨ƣõķɷַֻԭռмڻĺ˺K(xi,xj)ӦķԱ任˳˺ɷַ.
4.6 Ӧо
ȽźǣȻSVMϾкͻƣоȣӦоԱȽͺĿǰֻн޵ʵоҶͶԱʵ15.SVMӦӦһΪķ.
ģʽʶͻӦоǱʵҶдֿеʵ2,8ݣһʶԽϲݿ⣬˹ʶƽ2.5%þʶ16.2%дС5.9%רԸضƵΪ5.1%˴֪ʶSVMʽ(18)(20)ĺ˺õĴʷֱΪ4.0%4.1%4.2%ֱӲ1616ַΪSVM룬ûнרŵȡ.ʵһ˵SVMϴͳԵƣͬʱҲõ˲ͬSVMԵõĽģ͵ѡ.ʵ黹۲쵽SVM֧80%غϵģǶֻкٵһ֣˵֧ԲͬһĲԣźЩ۽޵ʵй۲쵽ܵõ֤ʹSVMۺӦиͻƣ.Χһַʶʵ飬һЩSVMĸĽڲԵ֪ʶ16,17ݡʶȥеҰֵ18ݡͨԤʶٶȣ19ݵȣصӦûSVM϶ԱʼӦ20.֮⣬MITSVMеʵҲȡ˽ϺõЧԽϺõѧͼҳܵλã2123.бʵ򻹰ıʶ23,24ݡʶ25ݡάʶ26ݡңͼ27ݵ.
ںϷ棬ҪʵԭоƽʱԤ⼰ѹ1012,28,29ݵ.
йожSVMŻ㷨ʵֵо30,31,23ݡĽSVM32,33Ӳʵо34ݵ.
5 
ͳѧϰۺ֧һ׽Ϻõ»ѧϰۿܺͨ÷ϸۻܽϺõؽСԡά;ֲСʵ⣬˳Ϊʮĩչо֮һ˼ѧϰҪ޵ѵӦ.ĶǵĻ˼롢о˽ܣϣʹ߶һһ˽.ͳѧϰȻѾ꣬ͱ㷺ӵڱϾֻмʱ䣬лкܶδδֽ⣬Ӧ÷оǸոտʼ.Ϊһʮֵôо.
ܵȻѧĿΪ69885004.
ѧ 19651994廪ѧʿѧλΪ廪ѧԶϵоԱҪоΪģʽʶ뷽Ϣںϼڵ̽еӦ.
ѧ(廪ѧԶϵܼϵͳصʵ  100084)
ο
1Vapnik V N. Estimation of Dependencies Based on Empirical Data. Berlin: SpringerVerlag, 1982
2Vapnik V N. The Nature of Statistical Learning Theory, NY: SpringerVerlag, 1995ѧ. ͳѧϰ۵ı.廪ѧ磬1999棩
3Cherkassky V, Mulier F . Learning from Data: Concepts, Theory and Methods. NY: John Viley & Sons, 1997
4.ģʽʶ.廪ѧ磬 1988
5Vapnik V, Levin E, Le Cun Y. Measuring the VCdimension of a learning machine. Neural Computation, 1994, 6: 851876.
6Burges C J C. A tutorial on support vector machines for pattern recognition. Data Mining and Knowledge Discovery,19982(2)
7Boser B, Guyon I, Vapnik V. A training algorithm for optimal margin classifiers, Fifth Annual Workshop on Computational Learning Theory. Pittsburgh: ACM Press, 1992
8Cortes C, Vapnik V. Supportvector networks. Machine Learning, 1995, 20: 273297
9Schlkopf B, Burges C, Vapnik V. Extracting support data for a given task. In: Fayyad U M, Uthurusamy R(eds.). Proc. of First Intl. Conf. on Knowledge Discovery & Data Mining, AAAI Press, 1995, 262267
10Vapnik V, Golowich S, Smola A, Support vector method for function approximation, regression estimation, and signal processing. In: Mozer M, Jordan M, PetscheT (eds). Neural Information Processing Systems, MIT Press, 1997, 9
11Mller KR, Smola A J, Rtsch G et al.Predicting time series with support vector machines.In: Proc. of ICANN'97, Springer Lecture Notes in Computer Science, 1997, 9991005
12Drucker H, Burges C, Kaufman L et al.Support vector regression machines. In:Mozer M, Jordan M, Petsche T (eds). Neural Information Processing Systems, MIT Press, 1997, 9
13Sch?lkopf B, Smola A, Mller KR. Kernel principal component analysis.In:Proc. of ICANN'97, 1997, 583589
14Sch?lkopf B, Smola A, Mller KR. Nonlinear component analysis as kernel eigenvalue problem. Neural Computation, 1998, 10(5): 12991319
15Sch?lkopf B, Sung KK, Burges C et al. Comparing support vector machines with
Gaussian kernels to radial basis function classifiers. IEEE Trans. on Signal Processing,1997, 45(11): 27582765
16Sch?lkopf B, Burges C,Vapnik V. Incorporating invariances in support vector learning machines, In: von der Malsburg C, von Seelen W, Vorbrggen J C et al(eds). Artificial Neural NetworksICANN'96, Spingers Lecture Notes in Computer Science, Berlin, 1996, 1112:4752
17Sch?lkopf B, Simard P, Smola Aet al. Prior knowledge in support vector kernels. NIPS'97, 1997
18Guyon I, Matic N, Vapnik V. Discovering informative patterns and data cleaning. In: Fayyad U M, PiatetskyShapiro G, Smyth P et al(eds). Advances in Knowledge Discovery & Data Mining, MIT Press, 1996, 181203
19Burges C, Schlkopf B. Improving the accuracy and speed of support vector machines. In: Mozer M, Jordan M, Petsche T (eds). Neural Information Processing Systems, MIT Press, 1997, 9
20Matic N, Guyon I, Denker J et al.Writer adaptation for online handwritten character recognition. In: 2nd Intl. Conf. on Pattern Recognition and Document Analysis, 1993, 187191
21Oren M, Papageorgiou C, Sinha Pet al.Pedestrian detection using wavelet templates,In: Proc. of CVPR'97, Puerto Rico, 1997
22Hearst M A, Sch?lkopf B, Dumais Set al.Trends and controversies support vector machines, IEEE Intelligent Systems, 1998, 13(4): 1828
23Osuna E, Freund R, Girosi F. Training support vector machines: an application to face detection. In: Proc. of CVPR'97, Puerto Rico, 1997
24¬飬ܴ. SVMѧϰ㷨ıϢеӦ. 廪ѧѧ1999
25Lu Chunyu, Yan Pingfan, Zhang Changshui, Zhou Jie. Face recognition using support vector machine.In:Proc. of ICNNB'98, Beijing, 1998, 652655
26Blanz V, Sch?lkopf B, Blthoff H.et al. Comparison of viewbased object recognition algorithms using realistic 3D models, In: von der Malsburg C, von Seelen W, Vorbrggen J Cet al(eds). Artificial Neural NetworksICANN'96, Spingers Lecture Notes in Computer Science, Berlin, 1996, 1112: 251256
27Brown M, Lewis H G, Gunn S R. Linear spectral mixture models and support vector machines for remote sensing, (submitted to)IEEE Trans. Geoscience and Remote Sensing, 1998
28Mukherjee S, Osuna E, Girosi F. Nonlinear prediction of chaotic time series using a support vector machine.In:Proc.of NNSP'97, 1997
29Kwok J TY, Support vector mixture for classification and regression problems. ICPR'98, 1998
30Bennett K, Mangasarian O. Robust linear programming discrimination of two linearly inseparable sets. Optimization Methods and Software, 1992, 1:2334
31Osuna E, Freund R, Girosi F. An improved training algorithm for support vector machines.In:Proc.of NNSP'97, 1997
32Bennett K P, Demiriz A. Semisupervised support vector machines.In:Proc. of NIPS'98, 1998
33Zhang Xuegong. Using classcenter vectors to build support vector machines.In:Proc.of NNSP'99. 1999:311
34Anguita D, Ridella S, Rovetta S. Circuital implementation of support vector machines. Electronics Letters, 1998, 34(16): 15961597
ո 1998-08-24 ޸ĸ 1999-04-27
