Support vector machine soft margin classifiers: Error analysis

Di-Rong Chen, Qiang Wu, Yiming Ying, Ding-Xuan Zhou

Research output: Journal Publications and ReviewsRGC 21 - Publication in refereed journalpeer-review

242 Citations (Scopus)

Abstract

The purpose of this paper is to provide a PAC error analysis for the q-norm soft margin classifier, a support vector machine classification algorithm. It consists of two parts: regularization error and sample error. While many techniques are available for treating the sample error, much less is known for the regularization error and the corresponding approximation error for reproducing kernel Hilbert spaces. We are mainly concerned about the regularization error. It is estimated for general distributions by a K-functional in weighted Lq spaces. For weakly separable distributions (i.e., the margin may be zero) satisfactory convergence rates are provided by means of separating functions. A projection operator is introduced, which leads to better sample error estimates especially for small complexity kernels. The misclassification error is bounded by the V-risk associated with a general class of loss functions V. The difficulty of bounding the offset is overcome. Polynomial kernels and Gaussian kernels are used to demonstrate the main results. The choice of the regularization parameter plays an important role in our analysis.
Original languageEnglish
Pages (from-to)1143-1175
JournalJournal of Machine Learning Research
Volume5
Publication statusPublished - 1 Sept 2004

Research Keywords

  • Approximation error
  • Misclassification error
  • q-norm soft margin classifier
  • Regularization error
  • Support vector machine classification

Fingerprint

Dive into the research topics of 'Support vector machine soft margin classifiers: Error analysis'. Together they form a unique fingerprint.

Cite this