Forgetron

The Forgetron: A kernel-based 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 kernel-based 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 kernel-based 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 kernel-based 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 kernel-based 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


References in zbMATH (referenced in 14 articles , 1 standard article )

Showing results 1 to 14 of 14.
Sorted by year (citations)

  1. Le, Trung; Nguyen, Tu Dinh; Nguyen, Vu; Phung, Dinh: Approximation vector machines for large-scale online learning (2017)
  2. Dieuleveut, Aymeric; Bach, Francis: Nonparametric stochastic approximation with large step-sizes (2016)
  3. Lu, Jing; Hoi, Steven C. H.; Wang, Jialei; Zhao, Peilin; Liu, Zhi-Yong: Large scale online kernel learning (2016)
  4. Louche, Ugo; Ralaivola, Liva: Unconfused ultraconservative multiclass algorithms (2015)
  5. He, Wenwu; Kwok, James T.: Simple randomized algorithms for online learning with kernels (2014)
  6. Gijsberts, Arjan; Metta, Giorgio: Real-time model learning using incremental sparse spectrum Gaussian process regression (2013)
  7. Hoi, Steven C. H.; Jin, Rong; Zhao, Peilin; Yang, Tianbao: Online multiple kernel classification (2013)
  8. Jiang, Hui; Zhang, Bo: Dynamical memory control based on projection technique for online regression (2013)
  9. He, Wenwu; Wu, Si: A kernel-based perceptron with dynamic memory (2012)
  10. Pavlidis, N. G.; Tasoulis, D. K.; Adams, N. M.; Hand, D. J.: (\lambda)-perceptron: an adaptive classifier for data streams (2011)
  11. Wang, Zhuang; Vucetic, Slobodan: Online training on a budget of support vector machines using twin prototypes (2010)
  12. Dekel, Ofer; Shalev-Shwartz, Shai; Singer, Yoram: The Forgetron: A kernel-based perceptron on a budget (2008)
  13. Cavallanti, Giovanni; Cesa-Bianchi, Nicolò; Gentile, Claudio: Tracking the best hyperplane with a simple budget perceptron (2007)
  14. Shalev-Shwartz, Shai; Singer, Yoram: A primal-dual perspective of online learning algorithms (2007)