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

Ofer Dekel; Shai Shalev-Shwartz; Yoram Singer

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

Ofer Dekel, Shai Shalev-Shwartz, Yoram Singer

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

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 language	English (US)
Title of host publication	Advances in Neural Information Processing Systems 18 - Proceedings of the 2005 Conference
Pages	259-266
Number of pages	8
State	Published - 2005
Event	2005 Annual Conference on Neural Information Processing Systems, NIPS 2005 - Vancouver, BC, Canada Duration: Dec 5 2005 → Dec 8 2005

Publication series

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

Other

Other	2005 Annual Conference on Neural Information Processing Systems, NIPS 2005
Country/Territory	Canada
City	Vancouver, BC
Period	12/5/05 → 12/8/05

All Science Journal Classification (ASJC) codes

Computer Networks and Communications
Information Systems
Signal Processing

Cite this

@inproceedings{a4e491419f9a4ae29d27a286719d9b57,

title = "The Forgetron: A kernel-based Perceptron on a fixed budget",

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.",

author = "Ofer Dekel and Shai Shalev-Shwartz and Yoram Singer",

year = "2005",

language = "English (US)",

isbn = "9780262232531",

series = "Advances in Neural Information Processing Systems",

pages = "259--266",

booktitle = "Advances in Neural Information Processing Systems 18 - Proceedings of the 2005 Conference",

note = "2005 Annual Conference on Neural Information Processing Systems, NIPS 2005 ; Conference date: 05-12-2005 Through 08-12-2005",

}

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. Advances in Neural Information Processing Systems, pp. 259-266, 2005 Annual Conference on Neural Information Processing Systems, NIPS 2005, Vancouver, BC, Canada, 12/5/05.

TY - GEN

T1 - The Forgetron

T2 - 2005 Annual Conference on Neural Information Processing Systems, NIPS 2005

AU - Dekel, Ofer

AU - Shalev-Shwartz, Shai

AU - Singer, Yoram

PY - 2005

Y1 - 2005

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84864063405&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84864063405&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:84864063405

SN - 9780262232531

T3 - Advances in Neural Information Processing Systems

SP - 259

EP - 266

BT - Advances in Neural Information Processing Systems 18 - Proceedings of the 2005 Conference

Y2 - 5 December 2005 through 8 December 2005

ER -

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

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Other files and links

Fingerprint

Cite this