HOME HELP FEEDBACK SUBSCRIPTIONS ARCHIVE SEARCH TABLE OF CONTENTS		QUICK SEARCH:   [advanced] Author: Keyword(s): Year:  Vol:  Page:

This Article Full Text Full Text (PDF) Alert me when this article is cited Alert me if a correction is posted Services Similar articles in this journal Similar articles in PubMed Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Wu, Q. Articles by Zhou, D.-X. Search for Related Content PubMed PubMed Citation Articles by Wu, Q. Articles by Zhou, D.-X.

SVM Soft Margin Classifiers: Linear Programming versus Quadratic Programming

wu.qiang{at}student.cityu.edu.hk, Department of Mathematics, City University of Hong Kong, Kowloon, Hong Kong, China

Ding-Xuan Zhou

mazhou{at}cityu.edu.hk, Department of Mathematics, City University of Hong Kong, Kowloon, Hong Kong, China

Support vector machine (SVM) soft margin classifiers are important learning algorithms for classification problems. They can be stated as convex optimization problems and are suitable for a large data setting. Linear programming SVM classifiers are especially efficient for very large size samples. But little is known about their convergence, compared with the well-understood quadratic programming SVM classifier. In this article, we point out the difficulty and provide an error analysis. Our analysis shows that the convergence behavior of the linear programming SVM is almost the same as that of the quadratic programming SVM. This is implemented by setting a stepping-stone between the linear programming SVM and the classical 1-norm soft margin classifier. An upper bound for the misclassification error is presented for general probability distributions. Explicit learning rates are derived for deterministic and weakly separable distributions, and for distributions satisfying some Tsybakov noise condition.