Large margin classification using the perceptron algorithm

Yoav Freund, Robert E. Schapire

Research output: Contribution to conferencePaperpeer-review

94 Scopus citations

Abstract

We introduce and analyze a new algorithm for linear classification which combines Rosenblatt's perceptron algorithm with Helmbold and Warmuth's leave-one-out method. Like Vapnik's maximal-margin classifier, our algorithm takes advantage of data that are linearly separable with large margins. Compared to Vapnik's algorithm, however, ours is much simpler to implement, and much more efficient in terms of computation time. We also show that our algorithm can be efficiently used in very high dimensional spaces using kernel functions. We performed some experiments using our algorithm, and some variants of it, for classifying images of handwritten digits. The performance of our algorithm is close to, but not as good as, the performance of maximal-margin classifiers on the same problem.

Original languageEnglish (US)
Pages209-217
Number of pages9
DOIs
StatePublished - 1998
Externally publishedYes
EventProceedings of the 1998 11th Annual Conference on Computational Learning Theory - Madison, WI, USA
Duration: Jul 24 1998Jul 26 1998

Other

OtherProceedings of the 1998 11th Annual Conference on Computational Learning Theory
CityMadison, WI, USA
Period7/24/987/26/98

All Science Journal Classification (ASJC) codes

  • Computational Mathematics

Fingerprint Dive into the research topics of 'Large margin classification using the perceptron algorithm'. Together they form a unique fingerprint.

Cite this