arXiv:math/0701907v3 [math.ST] 1 Jul 2008 - Kernel …

1 arXiv:math/0701907v3 [ ] 1 Jul 2008 The Annals of Statistics2008, Vol. 36, No. 3, 1171 1220 Institute of Mathematical Statistics, 2008 Kernel METHODS IN MACHINE LEARNING1By Thomas Hofmann, Bernhard Sch olkopfand Alexander J. SmolaDarmstadt University of Technology,Max Planck Institute for BiologicalCybernetics and National ICT AustraliaWe review machine learning methods employing positive definitekernels. These methods formulate learning and estimation problemsin a reproducing Kernel Hilbert space (RKHS) of functions definedon the data domain, expanded in terms of a Kernel .

2 Working in linearspaces of function has the benefit of facilitating the construction andanalysis of learning algorithms while at the same time allowing largeclasses of functions. The latter include nonlinear functions as well asfunctions defined on nonvectorial cover a wide range of methods, ranging from binary classifiersto sophisticated methods for estimation with structured the last ten years estimation and learning meth-ods utilizing positive definite kernels have become rather popular, particu-larly in machine learning.

3 Since these methods have a stronger mathematicalslant than earlier machine learning methods ( , neural networks), thereis also significant interest in the statistics and mathematics community forthese methods. The present review aims to summarize the state of the art ona conceptual level. In doing so, we build on various sources,including Burges[25], Cristianini and Shawe-Taylor [37], Herbrich [64] and Vapnik [141] and,in particular, Sch olkopf and Smola [118], but we also add a fair amount ofmore recent material which helps unifying the exposition.

4 We have not hadspace to include proofs; they can be found either in the long version of thepresent paper (see Hofmann et al. [69]), in the references given or in theabove main idea of all the described methods can be summarized in oneparagraph. Traditionally, theory and algorithms of machine learning andReceived December 2005; revised February in part by grants of the ARC and by the Pascal Network of 2000 subject 30C40; secondary words and learning, reproducing kernels, support vector ma-chines, graphical is an electronic reprint of the original article published by theInstitute of Mathematical StatisticsinThe Annals of Statistics,2008, Vol.

5 36, No. 3, 1171 1220. This reprint differs from the original inpagination and typographic HOFMANN, B. SCH OLKOPF AND A. J. SMOLA statistics has been very well developed for the linear world dataanalysis problems, on the other hand, often require nonlinear methods to de-tect the kind of dependencies that allow successful prediction of propertiesof interest. By using a positive definite Kernel , one can sometimes have thebest of both worlds. The Kernel corresponds to a dot product in a (usuallyhigh-dimensional) feature space.

6 In this space, our estimation methods arelinear, but as long as we can formulate everything in terms ofkernel evalu-ations, we never explicitly have to compute in the high-dimensional paper has three main sections: Section2deals with fundamentalproperties ofkernels, with special emphasis on (conditionally) positive defi-nite kernels and their characterization. We give concrete examples for suchkernels and discuss kernels and reproducing Kernel Hilbertspaces in the con-text of regularization. Section3presents various approaches for estimatingdependencies and analyzing data that make use of kernels.

7 Weprovide anoverview of the problem formulations as well as their solution using convexprogramming techniques. Finally, Section4examines the use of reproduc-ing Kernel Hilbert spaces as a means to define statistical models, the focusbeing on structured, multidimensional responses. We also show how suchtechniques can be combined with Markov networks as a suitable frameworkto model dependencies between response introductory we are given empirical data(x1,y1),..,(xn,yn) X Y.(1)Here, the domainXis some nonempty set that theinputs(the predictorvariables)xiare taken from; theyi Yare calledtargets(the response vari-able).

8 Here and below,i,j [n], where we use the notation [n] :={1,..,n}.Note that we have not made any assumptions on the domainXotherthan it being a set. In order to study the problem of learning,we needadditional structure. In learning, we want to be able togeneralizeto unseendata points. In the case of binary pattern recognition, given some new inputx X, we want to predict the correspondingy { 1}(more complex outputdomainsYwill be treated below). Loosely speaking, we want to chooseysuch that (x,y) is in some sensesimilarto the training examples.

9 To thisend, we need similarity measures inXand in{ 1}. The latter is easier,as two target values can only be identical or different. For the former, werequire a functionk:X X R,(x,x )7 k(x,x )(2) Kernel METHODS IN MACHINE LEARNING3 Fig. simple geometric classification algorithm: given two classes of points (de-picted by o and + ), compute their meansc+, c and assign a test inputxto theone whose mean is closer. This can be done by looking at the dotproduct betweenx c[wherec= (c++c )/2]andw:=c+ c , which changes sign as the enclosed angle passesthrough /2.

10 Note that the corresponding decision boundary is a hyperplane (the dottedline) orthogonal tow(from Sch olkopf and Smola [118]).satisfying, for allx,x X,k(x,x ) =h (x), (x )i,(3)where maps into some dot product spaceH, sometimes called thefeaturespace. The similarity measurekis usually called akernel, and is called itsfeature advantage of using such a Kernel as a similarity measure is thatit allows us to construct algorithms in dot product spaces. For instance,consider the following simple classification algorithm, described in Figure1,whereY={ 1}.