Forgetron
swMATH ID:  23913 
Software Authors:  Dekel, Ofer; ShalevShwartz, Shai; Singer, Yoram 
Description:  The Forgetron: A kernelbased perceptron on a budget. The Perceptron algorithm, despite its simplicity, often performs well in online classification tasks. The Perceptron becomes especially effective when it is used in conjunction with kernel functions. However, a common difficulty encountered when implementing kernelbased online algorithms is the amount of memory required to store the online hypothesis, which may grow unboundedly as the algorithm progresses. Moreover, the running time of each online round grows linearly with the amount of memory used to store the hypothesis. In this paper, we present the Forgetron family of kernelbased online classification algorithms, which overcome this problem by restricting themselves to a predefined memory budget. We obtain different members of this family by modifying the kernelbased Perceptron in various ways. We also prove a unified mistake bound for all of the Forgetron algorithms. To our knowledge, this is the first online kernelbased learning paradigm which, on one hand, maintains a strict limit on the amount of memory it uses and, on the other hand, entertains a relative mistake bound. We conclude with experiments using real datasets, which underscore the merits of our approach 
Homepage:  https://github.com/algorithmfoundry/Foundry/blob/master/Components/LearningCore/Source/gov/sandia/cognition/learning/algorithm/perceptron/kernel/Forgetron.java 
Source Code:  https://github.com/algorithmfoundry/Foundry/blob/master/Components/LearningCore/Source/gov/sandia/cognition/learning/algorithm/perceptron/kernel/Forgetron.java 
Related Software:  Pegasos; LIBSVM; RSVM; GoGP; PAMR; GraphLab; MapReduce; UCIml; LWPR; LINPACK; SimpleMKL; AdaBoost.MH; SHOGUN 
Cited in:  16 Publications 
Standard Articles
1 Publication describing the Software, including 1 Publication in zbMATH  Year 

The Forgetron: A kernelbased perceptron on a budget. Zbl 1151.68579 Dekel, Ofer; ShalevShwartz, Shai; Singer, Yoram 
2008

all
top 5
Cited by 34 Authors
all
top 5
Cited in 8 Serials
all
top 5