A tutorial on support vector regression - Smola

1 Statistics and Computing14:199 222, 2004C 2004 Kluwer Academic in The on support vector regression ALEX J. Smola and BERNHARD SCH OLKOPFRSISE, Australian National University, Canberra 0200, f ur biologische Kybernetik, 72076 T ubingen, July 2002 and accepted November 2003In this tutorial we give an overview of the basic ideas underlying support vector (SV) machines forfunction estimation. Furthermore, we include a summary of currently used algorithms for trainingSV machines, covering both the quadratic (or convex) programming part and advanced methods fordealing with large datasets. Finally, we mention some modifications and extensions that have beenapplied to the standard SV algorithm, and discuss the aspect of regularization from a SV :machine learning, support vector machines, regression estimation1.

2 IntroductionThe purpose of this paper is twofold. It should serve as a self-contained introduction to support vector regression for readersnew to this rapidly developing field of the otherhand, it attempts to give an overview of recent developments inthe end, we decided to organize the essay as by giving a brief overview of the basic techniques inSections 1, 2 and 3, plus a short summary with a number offigures and diagrams in Section 4. Section 5 reviews currentalgorithmic techniques used for actually implementing SVmachines. This may be of most interest for following section covers more advanced topics such asextensions of the basic SV algorithm, connections between SVmachines and regularization and briefly mentions methods forcarrying out model selection. We conclude with a discussionof open questions and problems and current directions of SVresearch.

3 Most of the results presented in this review paperalready have been published elsewhere, but the comprehensivepresentations and some details are backgroundThe SV algorithm is a nonlinear generalization of theGener-alized Portraitalgorithm developed in Russia in the sixties2 An extended version of this paper is available as NeuroCOLT Technical ReportTR-98-030.(Vapnik and Lerner 1963, Vapnik and Chervonenkis 1964). Assuch, it is firmly grounded in the framework of statistical learn-ing theory, orVC theory,which has been developed over the lastthree decades by Vapnik and Chervonenkis (1974) and Vapnik(1982, 1995). In a nutshell, VC theory characterizes propertiesof learning machines which enable them to generalize well tounseen its present form, the SV machine was largely developedat AT&T Bell Laboratories by Vapnik and co-workers (Boser,Guyon and Vapnik 1992, Guyon, Boser and Vapnik 1993, Cortesand Vapnik, 1995, Sch olkopf, Burges and Vapnik 1995, 1996,Vapnik, Golowich and Smola 1997).

4 Due to this industrial con-text, SV research has up to date had a sound orientation towardsreal-world applications. Initial work focused on OCR (opticalcharacter recognition). Within a short period of time, SV clas-sifiers became competitive with the best available systems forboth OCR and object recognition tasks (Sch olkopf, Burges andVapnik 1996, 1998a, Blanzet , Sch olkopf 1997). Acomprehensive tutorial on SV classifiers has been published byBurges (1998). But also in regression and time series predic-tion applications, excellent performances were soon obtained(M ulleret , Druckeret , Stitsonet ,Mattera and Haykin 1999). A snapshot of the state of the artin SV learning was recently taken at the annualNeural In-formation Processing Systemsconference (Sch olkopf, Burges,and Smola 1999a).

5 SV learning has now evolved into an activearea of research. Moreover, it is in the process of entering thestandard methods toolbox of machine learning (Haykin 1998,Cherkassky and Mulier 1998, Hearstet ). Sch olkopf and0960-3174C 2004 Kluwer Academic Publishers200 Smola and Sch olkopfSmola (2002) contains a more in-depth overview of SVM regres-sion. Additionally, Cristianini and Shawe-Taylor (2000) and Her-brich (2002) provide further details on kernels in the context basic ideaSuppose we are given training data{(x1,y1),..,(x ,y )} X R,whereXdenotes the space of the input patterns ( ). These might be, for instance, exchange rates for somecurrency measured at subsequent days together with correspond-ing econometric indicators. In -SV regression (Vapnik 1995),our goal is to find a functionf(x)that has at most deviationfrom the actually obtained targetsyifor all the training data, andat the same time is as flat as possible.

6 In other words, we do notcare about errors as long as they are less than ,but will notaccept any deviation larger than this. This may be important ifyouwant to be sure not to lose more than money when dealingwith exchange rates, for reasons, we begin by describing the case oflinear functionsf,taking the formf(x)= w,x +bwithw X,b R(1)where , denotes the dot product the caseof (1) means that one seeks a way to ensure this isto minimize the norm, w 2= w, w .Wecan write thisproblem as a convex optimization problem:minimize12 w 2subject to yi w,xi b w,xi +b yi (2)The tacit assumption in (2) was that such a functionfactuallyexists that approximates all pairs (xi,yi)with precision, or inother words, that the convex optimization problem , however, this may not be the case, or we also maywant to allow for some errors.

7 Analogously to the soft mar-gin loss function (Bennett and Mangasarian 1992) which wasused in SV machines by Cortes and Vapnik (1995), one can in-troduce slack variables i, ito cope with otherwise infeasibleconstraints of the optimization problem (2). Hence we arrive atthe formulation stated in Vapnik (1995).minimize12 w 2+C i=1( i+ i)subject to yi w,xi b + i w,xi +b yi + i i, i 0(3)The constantC>0determines the trade-off between the flat-ness offand the amount up to which deviations larger than are tolerated. This corresponds to dealing with a so called -insensitive loss function| | described by| | := 0if| | | | otherwise.(4)Fig. soft margin loss setting for a linear SVM (from Sch olkopfand Smola , 2002)Figure 1 depicts the situation graphically. Only the points outsidethe shaded region contribute to the cost insofar, as the deviationsare penalized in a linear fashion.

8 It turns out that in most casesthe optimization problem (3) can be solved more easily in its , as we will see in Section 2, the dual for-mulation provides the key for extending SV machine to nonlinearfunctions. Hence we will use a standard dualization method uti-lizing Lagrange multipliers, as described in Fletcher (1989). problem and quadratic programsThe key idea is to construct a Lagrange function from the ob-jective function (it will be called theprimalobjective functionin the rest of this article) and the corresponding constraints, byintroducing a dual set of variables. It can be shown that thisfunction has a saddle point with respect to the primal and dualvariables at the solution. For details see Mangasarian (1969),McCormick (1983), and Vanderbei (1997) and the explanationsin Section We proceed as follows:L:=12 w 2+C i=1( i+ i) i=1( i i+ i i) i=1 i( + i yi+ w,xi +b) i=1 i( + i+yi w,xi b)(5)HereLis the Lagrangian and i, i, i, iare Lagrange multi-pliers.

9 Hence the dual variables in (5) have to satisfy positivityconstraints, ( )i, ( )i 0.(6)Note that by ( )i,werefer to iand follows from the saddle point condition that the partialderivatives ofLwith respect to the primal variables (w,b, i, i)have to vanish for optimality. bL= i=1( i i)=0(7) wL=w i=1( i i)xi=0(8) ( )iL=C ( )i ( )i=0(9)Atutorial on support vector regression201 Substituting (7), (8), and (9) into (5) yields the dual 12 i,j=1( i i)( j j) xi,xj i=1( i+ i)+ i=1yi( i i)subject to i=1( i i)=0and i, i [0,C](10)In deriving (10) we already eliminated the dual variables i, ithrough condition (9) which can be reformulated as ( )i=C ( ) (8) can be rewritten as followsw= i=1( i i)xi,thusf(x)= i=1( i i) xi,x +b.(11)This is the so-calledSupport vector expansion, becompletely described as a linear combination of the , the complexity of a function s represen-tation by SVs is independent of the dimensionality of the inputspaceX,and depends only on the number of , note that the complete algorithm can be describedin terms of dot products between the data.

10 Even when evalu-atingf(x)weneed not computewexplicitly. These observa-tions will come in handy for the formulation of a bSo far we neglected the issue of latter can bedone by exploiting the so called Karush Kuhn Tucker (KKT)conditions (Karush 1939, Kuhn and Tucker 1951). These statethat at the point of the solution the product between dual variablesand constraints has to vanish. i( + i yi+ w,xi +b)=0(12) i( + i+yi w,xi b)=0and(C i) i=0(13)(C i) i= allows us to make several useful conclusions. Firstly onlysamples (xi,yi)with corresponding ( )i=Clie outside the -insensitive tube. Secondly i i=0, there can never be a setof dual variables i, iwhich are both simultaneously allows us to conclude that yi+ w,xi +b 0and i=0if i<C(14) yi+ w,xi +b 0if i>0(15)In conjunction with an analogous analysis on iwe havemax{ +yi w,xi | i<Cor i>0} b min{ +yi w,xi | i>0or i<C}(16)If some ( )i (0,C)the inequalities become equalities.