A new perspective on an old perceptron algorithm

Shai Shalev-Shwartz, Yoram Singer

Research output: Chapter in Book/Report/Conference proceedingConference contribution

19 Scopus citations

Abstract

We present a generalization of the Perceptron algorithm. The new algorithm performs a Perceptron-sty le update whenever the margin of an example is smaller than a predefined value. We derive worst case mistake bounds for our algorithm. As a byproduct we obtain a new mistake bound for the Perceptron algorithm in the inseparable case. We describe a multiclass extension of the algorithm. This extension is used in an experimental evaluation in which we compare the proposed algorithm to the Perceptron algorithm.

Original languageEnglish (US)
Title of host publicationLearning Theory - 18th Annual Conference on Learning Theory, COLT 2005, Proceedings
PublisherSpringer Verlag
Pages264-278
Number of pages15
ISBN (Print)3540265562, 9783540265566
DOIs
StatePublished - Jan 1 2005
Event18th Annual Conference on Learning Theory, COLT 2005 - Learning Theory - Bertinoro, Italy
Duration: Jun 27 2005Jun 30 2005

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume3559 LNAI
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other18th Annual Conference on Learning Theory, COLT 2005 - Learning Theory
CountryItaly
CityBertinoro
Period6/27/056/30/05

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'A new perspective on an old perceptron algorithm'. Together they form a unique fingerprint.

  • Cite this

    Shalev-Shwartz, S., & Singer, Y. (2005). A new perspective on an old perceptron algorithm. In Learning Theory - 18th Annual Conference on Learning Theory, COLT 2005, Proceedings (pp. 264-278). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 3559 LNAI). Springer Verlag. https://doi.org/10.1007/11503415_18