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 clas-
sifier, 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 handwrit-
ten 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.
%0 Journal Article
%1 freund1999large
%A Freund, Yoav
%A Schapire, Robert E.
%D 1999
%J Machine Learning
%K Voted algorithm bachelor:2011:bachmann perceptron weka
%N 3
%P 277-296
%T Large margin classification using the perceptron algorithm
%U http://dblp.uni-trier.de/db/journals/ml/ml37.html#FreundS99
%V 37
%X 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 clas-
sifier, 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 handwrit-
ten 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.
@article{freund1999large,
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 clas-
sifier, 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 handwrit-
ten 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.
},
added-at = {2012-03-22T16:11:08.000+0100},
author = {Freund, Yoav and Schapire, Robert E.},
biburl = {https://www.bibsonomy.org/bibtex/21b1a0dd35251ece27733f7df841e4540/telekoma},
interhash = {e185eebadbd65d850d57fb2becb8758d},
intrahash = {1b1a0dd35251ece27733f7df841e4540},
journal = {Machine Learning},
keywords = {Voted algorithm bachelor:2011:bachmann perceptron weka},
month = {April},
number = 3,
pages = {277-296},
timestamp = {2012-03-22T16:11:08.000+0100},
title = {Large margin classification using the perceptron algorithm},
url = {http://dblp.uni-trier.de/db/journals/ml/ml37.html#FreundS99},
volume = 37,
year = 1999
}