Approximation with polynomial kernels and SVM classifiers
- PDF / 374,391 Bytes
- 22 Pages / 595 x 842 pts (A4) Page_size
- 64 Downloads / 217 Views
Springer 2006
Approximation with polynomial kernels and SVM classifiers Ding-Xuan Zhou a, and Kurt Jetter b a Department of Mathematics, City University of Hong Kong, Tat Chee Avenue, Kowloon, Hong Kong,
China E-mail: [email protected] b Institut für Angewandte Mathematik und Statistik, Universität Hohenheim, D-70593 Stuttgart, Germany E-mail: [email protected]
Received 19 July 2004; accepted 22 September 2004 Communicated by Y. Xu
Dedicated to Charlie Micchelli on the occasion of his 60th birthday
This paper presents an error analysis for classification algorithms generated by regularization schemes with polynomial kernels. Explicit convergence rates are provided for support vector machine (SVM) soft margin classifiers. The misclassification error can be estimated by the sum of sample error and regularization error. The main difficulty for studying algorithms with polynomial kernels is the regularization error which involves deeply the degrees of the kernel polynomials. Here we overcome this difficulty by bounding the reproducing kernel Hilbert space norm of Durrmeyer operators, and estimating the rate of approximation by Durrmeyer operators in a weighted L1 space (the weight is a probability distribution). Our study shows that the regularization parameter should decrease exponentially fast with the sample size, which is a special feature of polynomial kernels. Keywords: classification algorithm, regularization scheme, polynomial kernel, approximation by Durrmeyer operators, support vector machine, misclassification error. Mathematics subject classifications (2000): 68T05, 62J02.
1.
Introduction
In this paper we study the problem of polynomial approximation for the purpose of learning theory. Our particular target is to provide convergence rates of classification algorithms generated by regularization schemes with polynomial kernels. As a special case, we present an error analysis for the support vector machine (SVM) soft margin The first author is supported partially by the Research Grants Council of Hong Kong (Project No. CityU
103704).
324
D.-X. Zhou, K. Jetter / Approximation with polynomial kernels
classifier. The SVM classification algorithm with polynomial kernels was introduced by Boser et al. [3] (1992). The form with a general kernel was given by Cortes and Vapnik [6] (1995). Let (X, d) be a compact metric space and Y = {1, −1}. A binary classifier f : X → {1, −1} is a function from X to Y which divides the input space X into two classes. If X is a subset of Rn , then each point x ∈ X is a vector with n components corresponding to values of n measurements. These measurements are made in order to predict some events (e.g., whether it will rain y = 1 or not y = −1). A classifier f predicts this event from the value f (x) when the vector x is assigned. A good classification algorithm yields from observed samples {(xi , yi )}m i=1 (xi ∈ X, yi ∈ Y ) classifiers with small (misclassification) errors. Let ρ be a probability distribution on Z := X ×Y and (X , Y) be the corresponding rand
Data Loading...
