The Forgetron: A kernel-based Perceptron on a fixed budget

Ofer Dekel, Shai Shalev-Shwartz, Yoram Singer

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

61 Scopus citations

Abstract

The Perceptron algorithm, despite its simplicity, often performs well on online classification tasks. The Perceptron becomes especially effective when it is used in conjunction with kernels. However, a common difficulty encountered when implementing kernel-based online algorithms is the amount of memory required to store the online hypothesis, which may grow unboundedly. In this paper we present and analyze the Forgetron algorithm for kernel-based online learning on a fixed memory budget. To our knowledge, this is the first online learning algorithm which, on one hand, maintains a strict limit on the number of examples it stores while, on the other hand, entertains a relative mistake bound. In addition to the formal results, we also present experiments with real datasets which underscore the merits of our approach.

Original languageEnglish (US)
Title of host publicationAdvances in Neural Information Processing Systems 18 - Proceedings of the 2005 Conference
Pages259-266
Number of pages8
StatePublished - Dec 1 2005
Externally publishedYes
Event2005 Annual Conference on Neural Information Processing Systems, NIPS 2005 - Vancouver, BC, Canada
Duration: Dec 5 2005Dec 8 2005

Publication series

NameAdvances in Neural Information Processing Systems
ISSN (Print)1049-5258

Other

Other2005 Annual Conference on Neural Information Processing Systems, NIPS 2005
CountryCanada
CityVancouver, BC
Period12/5/0512/8/05

All Science Journal Classification (ASJC) codes

  • Computer Networks and Communications
  • Information Systems
  • Signal Processing

Fingerprint Dive into the research topics of 'The Forgetron: A kernel-based Perceptron on a fixed budget'. Together they form a unique fingerprint.

  • Cite this

    Dekel, O., Shalev-Shwartz, S., & Singer, Y. (2005). The Forgetron: A kernel-based Perceptron on a fixed budget. In Advances in Neural Information Processing Systems 18 - Proceedings of the 2005 Conference (pp. 259-266). (Advances in Neural Information Processing Systems).