The projectron: a bounded kernel-based Perceptron
By Francesco Orabona, Joseph Keshet, Barbara Caputo. 2008
127 citations recorded by the source corpus.
We present a discriminative online algorithm with a bounded memory growth, which is based on the kernel-based Perceptron. Generally, the required memory of the kernel-based Perceptron for storing the online hypothesis is not bounded. Previous work has been focused on discarding part of the instances in order to keep the memory bounded. In the proposed algorithm the instances are not discarded, but projected onto the space spanned by the previous online hypothesis. We derive a relative mistake bound and compare our algorithm both analytically and empirically to the state-of-the-art Forgetron algorithm (Dekel et al, 2007). The first variant of our algorithm, called Projectron, outperforms the Forgetron. The second variant, called Projectron++, outperforms even the Perceptron.
Subfields: Artificial Intelligence
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
- Stefan Savage
- Geoffrey M. Voelker
- Lawrence K. Saul
- Andreas Holzinger
- Tao A. Xiang
- Jia Deng
- Gabriella Csurka
- Kilian Q. Weinberger
Citations in the corpus
- Sharp analysis of low-rank kernel matrix approximations (2012, neutral): “Some algorithms operate online and do not need to compute the full kernel matrix, such as the “forgetron” (Dekel et al., 2005), the “projectron” (Orabona et al., 2008), BGSD (Wang et al., 2012), or LASVM (Bordes et al., 2005), with typically a fixed computational budget and good practical…”
- Malicious URL Detection using Machine Learning: A Survey (2017, unknown): “Examples include Randomized Budget Perceptron [140], Forgetron [141], Pro-jectron [142], and Bounded Online Gradient Descent [143].”
- Minimax Classification under Concept Drift with Multidimensional Adaptation and Performance Guarantees (2022, unknown): “…techniques: AdaRaker ( Shen et al., 2019), randomized budget perceptron (RBP) (Cavallanti et al., 2007), Projectron, Projec-tron ++ (Orabona et al., 2008), naive online regularized risk minimization algorithm (NORMA) (Kivinen et al., 2004), Nystr¨om online gradient descent (NOGD),…”
- Identifying suspicious URLs: an application of large-scale online learning (2009, methodology): “Related Algorithms: We experimented with nonlinear classi.cation using online kernel-based algorithms such as the Forgetron (Dekel et al., 2008) and the Projectron (Orabona et al., 2008).”