Large Margin Classification Using the Perceptron Algorithm
Machine LearningPublished 1 December 1999Open access
Yoav Freund, Robert E. Schapire
Citations594
SJR quartileQ1
SJR score1.15
SNIP2.14
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
A new algorithm for linear classification which combines Rosenblatt's perceptron algorithm with Helmbold and Warmuth's leave-one-out method is introduced, which is much simpler to implement, and much more efficient in terms of computation time.
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, while saving significantly on computation time and programming effort.
Keywords
Computer Science
Machine LearningSupport-vector networks
40,463 Citations1995Corinna Cortes, Vladimir Vapnik
High generalization ability of support-vector networks utilizing polynomial input transformations is demonstrated and the performance of the support- vector network is compared to various classical learning algorithms that all took part in a benchmark study of Optical Character Recognition.
Machine LearningSupport-Vector Networks
33,035 Citations1995Corinna Cortes, Vladimir Vapnik
High generalization ability of support-vector networks utilizing polynomial input transformations is demonstrated and the performance of the support- vector network is compared to various classical learning algorithms that all took part in a benchmark study of Optical Character Recognition.
TechnometricsStatistical Learning Theory
26,913 Citations1999Yuhai Wu, Vladimir Vapnik
Presenting a method for determining the necessary and sufficient conditions for consistency of learning process, the author covers function estimates from small data pools, applying these estimations to real-life problems, and much more.
Psychological ReviewThe perceptron: A probabilistic model for information storage and organization in the brain.
11,746 Citations1958Frank F. Rosenblatt
This article will be concerned primarily with the second and third questions, which are still subject to a vast amount of speculation, and where the few relevant facts currently supplied by neurophysiology have not yet been integrated into an acceptable theory.
A training algorithm for optimal margin classifiers
11,594 Citations1992Bernhard E. Boser, Isabelle Guyon +1 more
A training algorithm that maximizes the margin between the training patterns and the decision boundary is presented, applicable to a wide variety of the classification functions, including Perceptrons, polynomials, and Radial Basis Functions.
Perceptrons: an introduction to computational geometry
3,308 Citations1969Marvin Minsky, Seymour Papert
Information and ComputationExponentiated Gradient versus Gradient Descent for Linear Predictors
880 Citations1997Jyrki Kivinen, Manfred K. Warmuth
The bounds suggest that the losses of the algorithms are in general incomparable, but EG(+/-) has a much smaller loss if only a few components of the input are relevant for the predictions, which is quite tight already on simple artificial data.
Journal of the ACMHow to use expert advice
647 Citations1997Nicolò Cesa‐Bianchi, Yoav Freund +4 more
This work analyzes algorithms that predict a binary value by combining the predictions of several prediction strategies, called experts, and shows how this leads to certain kinds of pattern recognition/learning algorithms with performance bounds that improve on the best results currently know in this context.
Comparison of learning algorithms for handwritten digit recognition
584 Citations1995Yann LeCun, L. D. Jackel +10 more
This comparison of several learning algorithms for handwritten digits considers not only raw accuracy, but also rejection, training time, recognition time, and memory requirements.
Additive versus exponentiated gradient updates for linear prediction
226 Citations1995Jyrki Kivinen, Manfred K. Warmuth
The main methodological idea is using a distance function between weight vectors both in motivating the algorithms and as a potential function in an amortized analysis that leads to worst-case loss bounds.
Europhysics Letters (EPL)The AdaTron: An Adaptive Perceptron Algorithm
209 Citations1989Joachim K. Anlauf, Michael Biehl
A new learning algorithm for neural networks of spin glass type is proposed that is found to relax exponentially towards the perceptron of optimal stability using the concept of adaptive learning.
Journal of Computer and System SciencesOn Weak Learning
74 Citations1995David P. Helmbold, Manfred K. Warmuth
This paper presents relationships between weak learning, weak prediction, and consistency oracles and uses an algorithm to show that a concept class is polynomially learnable if and only if there is a polynomial probabilistic consistency oracle for the class.
Elsevier eBooksFrom On-line to Batch Learning
46 Citations1989Nick Littlestone
An analysis of a conversion to improve the performance of on-line learning algorithms in a batch setting, using a version of Chernoff bounds applied to supermartingales, that shows that for some target classes the converted algorithm will be asymptotically optimal.
From noise-free to noise-tolerant and from on-line to batch learning
23 Citations1995Norbert Klasner, Hans Ulrich Simon
A simple method is presented which virtually removes noise or misfit from data, and thereby converts a “noise-free” algorithm A, which on-line learns linear functions from data without noise orMisfit, into a ‘noises-tolerant’ algorithm Ant which learns linearfunction from data containing noise ormisfit.
ePrints Soton (University of Southampton)Robust Bounds on Generalization from the Margin Distribution
20 Citations1998John Shawe‐Taylor, Cristianini, N.
It is shown that a slight generalization of their construction can be used to give a pac style bound on the tail of the distribution of the generalization errors that arise from a given sample size.