9 Feature Spaces and Kernels captures our intuition of the problem:as thehyperplane(cf.figure1.1)is complet ely determined by the patterns closest to it,the solution should not depend on the oth er examples. By substituting (1.13)and (1.14)into L,one eliminates the primal variables and arrives at the Wolfe dual of the optimiation problem (eg.Bertsckas,1995):find Dual multipliers ai whid Optimiz ation Problem maximt e W(a)= 1 aiailili(Xi·Xi) (1.16) subject to a:≥01i=11..11amd>a:=0. (1.17) 讹， The hyperplane decision function can thus be writt en as 4 f(x)=sgn :a·(x·x)+b (1.18 where b is computed using (1.15). The structure of the optimi ation problem cosely resembles those that typically arise in Logranges formulation of mecanics (eg.Goldstein,1986).Also there often only a subset of the constraints become active For instance f we keep a ball in a b ox,then it will typically roll into one of the corners.The constraints corresponding to the walls whic are not touded by the ball are irrelevant,the walls could just as well be removed. Seen in this light,it is not too surprising that it is possible to give a mecanical interpret ation of optimal margin hyperplanes(Burges and Sdolkopf,1997):If we assume that ead support vector xi exerts a perp endicular force of sie ai and sign yi on a solid plane sheet lying along the hyperplane,then the solution satisfies the requirements of medanical stability.The constraint(1.13)states that the forces on the sheet sum to zero;and(1.14)implies that the torques also sum to zero,via ∑：x:×yaw/lw‖=w×w/lw‖=0. There are several theoretical arguments supporting the good generaliz ation per- formance of the optimal hyp erplane (Vapnik and Chervonenkis (1974);Vapnik (1979),cf.chapters 3 and 4).In addition,it is computationally attractive,since it can be constructed by solving a quadratic programming problem.But how can this begeneralized to the case of decision functions whic,unlike (1.7),are nonlinear in the data? 1.3 Feature Spaces and Kernels To construct SVmadines,the optimal hyperplane algorithm had to be augment ed by a method for computing dot products in feature spaces nonlinearly related to input space (Aizerman et al.,1964;Boser et al.,1992).The b asic idea is to map the Feature space data into some other dot product space (called the feature space)F via a nonlinear .(0,1),9.-6
Feature Spaces and Kernels captures our intuition of the problem as the hyperplane cf gure is completely determined by the patterns closest to it the solution should not depend on the other examples By substituting and into L one eliminates the primal variables and arrives at the Wolfe dual of the optimization problem eg Bertsekas nd Dual multipliers i which Optimization Problem maximize W X i i X ij ij yiyj xi xj sub ject to i i and X i iyi The hyperplane decision function can thus be written as f x sgn X i yii x xi b where b is computed using The structure of the optimization problem closely resembles those that typically arise in Lagrange s formulation of mechanics eg Goldstein Also there often only a subset of the constraints become active For instance if we keep a ball in a box then it will typically roll into one of the corners The constraints corresponding to the walls which are not touched by the ball are irrelevant the walls could just as well be removed Seen in this light it is not too surprising that it is possible to give a mechanical interpretation of optimal margin hyperplanes Burges and Scholkopf If we assume that each support vector xi exerts a perpendicular force of size i and sign yi on a solid plane sheet lying along the hyperplane then the solution satis es the requirements of mechanical stability The constraint states that the forces on the sheet sum to zero and implies that the torques also sum to zero via P i xi yii wkwk w wkwk There are several theoretical arguments supporting the good generalization per formance of the optimal hyperplane Vapnik and Chervonenkis Vapnik cf chapters and In addition it is computationally attractive since it can be constructed by solving a quadratic programming problem But how can this be generalized to the case of decision functions which unlike are nonlinear in the data Feature Spaces and Kernels To construct SV machines the optimal hyperplane algorithm had to be augmented by a method for computing dot products in feature spaces nonlinearly related to input space Aizerman et al Boser et al The basic idea is to map the Feature Space data into some other dot product space called the feature space F via a nonlinear
Introduction to Support Vector Learning map 重：RN,F (1.19× and per orm the above linear algorithm in Fi For instance2 suppose we are given patterns x e RN where most in ormation is contained in the dith or der products.monomials=ofentries zj ofxziixj.,.rj2 where j.e...id e {1e.,.N)I In that case2 we might prefer to extract these monomial eatures fir st2 and work in the eature space F o fall products ofd entriesi This approach2 however2 fails fr realistically sized problems:fr N/dimensional input patterns2there exist.N+d-14/.d!.N-14=different monomialsI Already 16<16 pixel input images egi in character recognition=and a monomial degree d=5 yield a dimensionality of101 This problem can be overcome by noticing that both the construction ofthe optimal hyperplane in F.cf.1116-and the evaluation o fthe corresponding decision finction.1118-only require the evaluation ofdot products..x=.y=2and never the mapped patterns .x=in explicit ormi This is crucial2 since in some cases2the Mer cer Kernel dot products can be evaluated by a simple kernel ‖.xy==.Φ.x=TΦ.y= (1.20× For inst ance2the polynomial kernel ll.xty-=.xry_d (1.21× can be shown to correspond to a map into the space spanned by all products of exactly d dimensions ofRN.Poggio.1a75=Boser et al1.1002=Burges.1008fr a proof see chapter 20-1 For d=2 and xey e R22egn we have.Vapnik21a05= xy2=.x2xV2x.x2=2yV2.2T=.重.x=r重.y (1.22× defining .x==.x?xv2r.2- By using ll.xey==.x Ty +c-d with c>02 we can take into account all product o for der up to d.iel including those o forder smaller than d- More gener ally2 the pllowing theorem of finctional analysis shows that kernels llofpositive integral operators give rise to maps such that.120-holds.Mercer2 1a0a:Aizerman et al2 1064:Boser et al121002= Theorem 1.1 (Mercer) If is a continuous symmetric kernel ofa positive integral operator T2 ie .Tf-y-= ‖.xeyf.x= (1.23× with 厂xty-f.x-f.y-w>0 (1.2-× or all f e L2.C=.C being a compact subset of RN=it can be expanded in a uniprmly convergent series.on C<C-in termsofT's eigen finctions j and positive .(0,1),9.-6
Introduction to Support Vector Learning map RN F and perform the above linear algorithm in F For instance suppose we are given patterns x RN where most information is contained in the dth order products monomials of entries xj of x ie xj xjd where jjd fNg In that case we might prefer to extract these monomial features rst and work in the feature space F of all products of d entries This approach however fails for realistically sized problems for Ndimensional input patterns there exist N d d N di erent monomials Already pixel input images eg in character recognition and a monomial degree d yield a dimensionality of This problem can be overcome by noticing that both the construction of the optimal hyperplane in F cf and the evaluation of the corresponding decision function only require the evaluation of dot products x y and never the mapped patterns x in explicit form This is crucial since in some cases the Mercer Kernel dot products can be evaluated by a simple kernel kx y x y For instance the polynomial kernel kx yx yd can be shown to correspond to a map into the space spanned by all products of exactly d dimensions of RN Poggio Boser et al Burges for a proof see chapter For d and x y R eg we have Vapnik x y x x p xxy y p yy x y de ning xx x p xx By using kx yx y cd with c we can take into account all product of order up to d ie including those of order smaller than d More generally the following theorem of functional analysis shows that kernels k of positive integral operators give rise to maps such that holds Mercer Aizerman et al Boser et al Theorem Mercer If k is a continuous symmetric kernel of a positive integral operator T ie T f y Z C kx yf x dx with Z CC kx yf xf y dx dy for all f LC C being a compact subset of RN it can be expanded in a uniformly convergent series on CC in terms of T s eigenfunctions j and positive
(1 Feature Spaces and Kernels 7 eigenvalues入y2 k.xiy== ∑入xy (1.25) j= where NF<oo is the number ofpositive eigenvalues Note that originally proven fr the case where C=[ab.a/bE R2 this theorem also holds true or gener al compact spaces.Dun ord and Schwartz2 1063-1 An equivalent way to characterize Mer cer kernels is that they give rise to positive matrices K:=k.xxj-fr all {1x}.Saitoh21088-One ofthe implications that need to be proven to show this equivalence pllows fom the fact that Kij is a Gram matrix:ra∈R2 we have.a·Ka==‖-12④.x:‖2≥0i Fom.125=2it is str aight prward to construct a map into a potentially infinite/ dimensional l2 space which satisfies.120-For instance2 we may use Φ.x==.Vh吻.x4VA22.xH999 (1.26) Rather than thinking of the eature space as an 12 space2 we can alternatively represent it as the Hilbert space H containing all linear combinations of the finctions f.s==k.xlg=.x;∈C=To ensure that the map重：C→H2 which in this case is defined as Φ.X==k.X19曰 (1.27) satisfies.1120-2 we need to endow H with a suitable dot product (1In view of the definition ofthis dot product needs to satis (k.xigk.yio)=k.xiy (1.28 Repro ducing which amounts to saying that k is a reprodu cing kerndl fr Hi For a Mer cer kernel Kernel .1125-2such a dot product does existi Since k is symmetric2 the i.i=119991 NF- can be chosen to be orthogonal with respect to the dot product in L2.C=2ie .jnL(c)=6jn2 using the Kronecker 6in1 Fom this2 we can construct (os) such that (V451VAnn）=dn9 (1.29) Substituting.1125=into.1128=then proves the desired equality.fr firther details2 see chapter 6 and Aronszajn.1050 Wahba.1a73 Girosi.1a08 Scholkopf.1007-1 Besides.1121-2SV practicioners use sigmoid kernels k.xy==tanh.k.x·y=+日= (1.30) 6r suitable values o fgain K and threshold cf chapter 7-2andradial basis finction kernels2as fr inst ance.Aizerman et al n1064;Boser et al 21002;Scholkopfet al n2 1a07b= kxy==ep-x-y2a.22_× (1.31) .(0,1),9.-6
Feature Spaces and Kernels eigenvalues j kx y X NF j j j x j y where NF is the number of positive eigenvalues Note that originally proven for the case where C a b ab R this theorem also holds true for general compact spaces Dunford and Schwartz An equivalent way to characterize Mercer kernels is that they give rise to positive matrices Kij kxi xj for all fx xg Saitoh One of the implications that need to be proven to show this equivalence follows from the fact that Kij is a Gram matrix for R we have K kP i i xik From it is straightforward to construct a map into a potentially in nite dimensional l space which satis es For instance we may use xp x p x Rather than thinking of the feature space as an l space we can alternatively represent it as the Hilbert space Hk containing all linear combinations of the functions f kxi xi C To ensure that the map C Hk which in this case is de ned as x kx satis es we need to endow Hk with a suitable dot product h i In view of the de nition of this dot product needs to satisfy hkx ky i kx y Reproducing which amounts to saying that k is a reproducing kernel for Hk For a Mercer kernel Kernel such a dot product does exist Since k is symmetric the i i NF can be chosen to be orthogonal with respect to the dot product in LC ie j nL C jn using the Kronecker jn From this we can construct h i such that hp j j p n ni jn Substituting into then proves the desired equality for further details see chapter and Aronsza jn Wahba Girosi Scholkopf Besides SV practicioners use sigmoid kernels kx y tanhx y ! for suitable values of gain and threshold ! cf chapter and radial basis function kernels as for instance Aizerman et al Boser et al Scholkopf et al b kx y exp kx yk
3 Introduction to Support Vector Learning input space feature space O ◆ O Figure.The idea of SV machines:map the training data nonlinearly into a higher/dimensional eature space via/zand construct a separating hyperplane with maximum margin there This yields a nonlinear decision boundary in input spacer By the use of a kernel fnction.1120-2 it is possible to compute the separating hyperplane without explicitly carrying out the map into the eature spacer with o >OI Note that when using Gaussian kernels2 fr inst ancezthe fature space H thus contains all superpositions ofGaussians on C.plus limit points-2 whereas by definition of.1127-2only single bumps k.x,.=do have pre/images under 1.4 Support Vector Machines To construct SV machines2 one computes an optimal hyperplane in eature spacer To this end2 we substitute .x;=6r each training example xi The weight vector cf.1114-then becomes an expansion in eature space2 and will thus typically no more correspond to the image ofa single vector fom input space.ci Scholkopf et al1.1aa8c=fr a frmula how to compute the pre/image ifit exists=Since all patterns only occur in dot products2 one can substitute Mercer kernels k or the dot products Boser et al2 1002;Guyon et al121a03-2leading to decision finctions Decision ofthe more general 6rm.cf.1118- Function f.x==sgn ∑y4x.重.x=r重.x=+b =1 sgn yi4i Tk.x,xi=+b (1.32) and the 6llowing quadratic program cf.1116 m axim ize (1.33) subject to 4>=1…6m空4=0 (1.34) .(0,1),9-6
Introduction to Support Vector Learning input space feature space Φ ◆ ◆ ◆ ◆ ❍ ❍ ❍ ❍ ❍ ❍ Figure The idea of SV machines map the training data nonlinearly into a higherdimensional feature space via and construct a separating hyperplane with maximum margin there This yields a nonlinear decision boundary in input space By the use of a kernel function it is possible to compute the separating hyperplane without explicitly carrying out the map into the feature space with Note that when using Gaussian kernels for instance the feature space Hk thus contains all superpositions of Gaussians on C plus limit points whereas by de nition of only single bumps kx do have preimages under Support Vector Machines To construct SV machines one computes an optimal hyperplane in feature space To this end we substitute xi for each training example xi The weight vector cf then becomes an expansion in feature space and will thus typically no more correspond to the image of a single vector from input space cf Scholkopf et al c for a formula how to compute the preimage if it exists Since all patterns only occur in dot products one can substitute Mercer kernels k for the dot products Boser et al Guyon et al leading to decision functions Decision of the more general form cf Function f x sgn X i yii x xi b sgn X i yii kx xi b and the following quadratic program cf maximize W X i i X ij ij yiyjkxi xj sub ject to i i and X i iyi
9 Support Vector Machines 9 0 0 0 0 @ 0 Figure.(Example of a Support Vector dlassifier found by using a radial basis function kernel kx.y.1 expi-x-y4..Both coordinate axes range from-1 to +1. Circles and disks are two classes of training examples;the middle line is the decision surface;the outer lines precisely meet the constr aint(1.10).Note that the Support Vectors found by the algorithm(marked by extra circles)are not centers of dlusters, but examples which are critical for the given classification task.Grey values code the modulus of the argument-bof the decision function (1.32). (From Scholkopf et al.(1996a),see also Burges (1998).) In pr actice,a separating hy perplane may not exist,e.g.if a high noise level causes a Soft Margin large overlap of the classes.To allow for the possibility of examples violating (1.10), Hy perplane one introduces slack variables (Cortes and Vapnik,1995;Vapnik,1995) i≥0，i=1,,0, 1135) along with relaxed constr aints yi(w·xi)+b)≥1-i,i=1,,0. 136) A classifier which generalizes well is then found by controlling both the classifier capacity (via w)and the number of training errors,minimizing the objective function T(w,1)= 2w2+c∑i 137) subject to the constr aints (1.35)and(1.36),for some value of the constant C>0 determining the trade-off.Here and below,we use boldface greek letters as a shorthand for corresponding vectors 1 =(61,...,1.Incorporating kernels,and .//6,63
Support Vector Machines Figure Example of a Support Vector classi er found by using a radial basis function kernel kx y expkxyk Both coordinate axes range from to Circles and disks are two classes of training examples the middle line is the decision surface the outer lines precisely meet the constraint Note that the Support Vectors found by the algorithm marked by extra circles are not centers of clusters but examples which are critical for the given classi cation task Grey values code the modulus of the argument P i yii kx xi b of the decision function From Scholkopf et al a see also Burges In practice a separating hyperplane may not exist eg if a high noise level causes a Soft Margin large overlap of the classes To allow for the possibility of examples violating Hyperplane one introduces slack variables Cortes and Vapnik Vapnik i i along with relaxed constraints yi w xi b i i A classi er which generalizes well is then found by controlling both the classi er capacity via kwk and the number of training errors minimizing the ob jective function w kwk CX i i sub ject to the constraints and for some value of the constant C determining the tradeo Here and below we use boldface greek letters as a shorthand for corresponding vectors Incorporating kernels and