Large margin classification using the perceptron algorithm
Yoav Freund, Robert E. Schapire · 1998
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, while saving significantly on computation time and programming effort. 1 Introduction One of the most influential developments in the theory of machine learning in the last few years is Vapnik's work on supp...
Cited by 1,071 works. doi:10.1145/279943.279985
Authors
References
- The Nature of Statistical Learning Theory
- Support-Vector Networks
- Statistical Learning Theory
- Principles of Neurodynamics.
- A training algorithm for optimal margin classifiers
- Estimation of Dependences Based on Empirical Data
- The perceptron: A probabilistic model for information storage and organization in the brain.
- Perceptrons: An Introduction to Computational Geometry
- Theoretical Foundations of the Potential Function Method in Pattern Recognition Learning
- Exponentiated Gradient versus Gradient Descent for Linear Predictors