SVM-tutorial

Data Mining and Knowledge Discovery, 2, 121–167 (1998)°c 1998 Kluwer Academic Publishers, Boston. Manufactured in The Netherlands.A Tutorial on Support Vector Machines for PatternRecognitionCHRISTOPHER J.C. BURGES burges@lucent.comBell Laboratories, Lucent TechnologiesEditor: Usama FayyadAbstract. The tutorial starts with an overview of the concepts of VC dimension and structural risk minimization.We then describe linear Support Vector Machines (SVMs) for separable and non-separable data, working througha non-trivial example in detail. We describe a mechanical analogy, and discuss when SVM solutions are uniqueand when they are global. We describe how support vector training can be practically implemented, and discussin detail the kernel mapping technique which is used to construct SVM solutions which are nonlinear in thedata. We show how Support Vector machines can have very large (even infinite) VC dimension by computingthe VC dimension for homogeneous polynomial and Gaussian radial basis function kernels. While very high VCdimension would normally bode ill for generalization performance, and while at present there exists no theorywhich shows that good generalization performance is guaranteed for SVMs, there are several arguments whichsupport the observed high accuracy of SVMs, which we review. Results of some experiments which were inspiredby these arguments are also presented. We give numerous examples and proofs of most of the key theorems.There is ...