Introduction
Online Learning is a machine learning paradigm in which the prediction function is incrementally updated as soon as a new training instance is available. This approach differs from the so-called batch learning in which a single offline training process is performed. Batch learning methods, like Support Vector Machine algorithm, usually optimize a global cost function over the whole training data; instead, online learning focus only on an individual instance at a time, solving a local optimization problem that aims at adjusting the current model on the basis of the feedback received from that single example.
The simplicity of Online Learning methods can produce some accuracy drops if compared to batch learning algorithms, but has some inherent advantages. First, a significant reduction in the training process is generally observed. Moreover, large datasets can be easily exploited without having memory drawbacks.
Furthermore online learning methods, updating the model on new examples, can track shifting concept and provide a fresh solution that does not degrade over the time, while, in batch learning, the model must be re-generated from scratch when new data is available.
Regarding margin classifiers, the perceptron (Rosenblatt 1958) can be considered the first online learning method, while the passive aggressive (Crammer et al. 2006) is usually referred as a state-of-art online method. When equipped with kernel methods, an adjustment to the prediction function corresponds to adding a new support vector; thus the model can grow without limits with drawbacks in terms of computational complexity and memory usage. In literature various solutions have been proposed to tackle this problem (Cesa-Bianchi et al 2006)(Dekel et al 2008)(Wang et al 2010).
People
Roberto Basili, Simone Filice, Danilo Croce, Giuseppe Castellucci
References
G. Cavallanti, N. Cesa-Bianchi, C. Gentile (2007) Tracking the best hyperplane with a simple budget Perceptron. In proc. of the nineteenth annual conference on Computational Learning Theory. pp. 483{498. Springer-Verlag (2006)
K. Crammer, O. Dekel, J. Keshet, S. Shalev-Shwartz and Y. Singer (2006) Online Passive-Aggressive Algorithms. Journal of Machine Learning Research
O. Dekel, Shalev-Shwartz and Y. Singer (2008) The Forgetron: a kernel-based perceptron on a budget. SIAM Journal on Computing
F. Rosenblatt (1957), The Perceptron – a perceiving and recognizing automaton. Report 85-460-1, Cornell Aeronautical Laboratory
Z. Whang and S. Vucetic (2010) Online Passive-Aggressive Algorithms on a Budget. AISTATS
SAG Publications