Specifically, I'm asking for resources to learn about machine learning systems that can update their respective belief networks (or equivalent) during operation. I've even run across a few, though I failed to bookmark them.

As you might imagine, it's a rather challenging topic to search for on the internet.

  • When asking users to contribute to a list of answers, the question should be marked community wiki. I have converted this question. – Robert Cartaino Aug 17 '10 at 18:12

Most online learning algorithms come from at least one out of these lineages:

  • the perceptron

    State of the art perceptrons are the passive-aggressive algorithm, the structured perceptron, and their many varieties.

  • The winnow

    The winnow has been reformulated as exponentiated gradient methods, and can be applied to structured problems as well. There are also varieties that deal directly with L1 regularization (to guarantee sparsity), such as SMIDAS.

  • Stochastic gradient descent

    Stochastic gradient descent is when you apply online optimization to a possibly batch problem. State of the art algorithms are Leon Bottou's LaSVM, Pegasos, and many neural network algorithms can be easily trained in this setting. See the theano tutorial for many examples. Maybe online EM fits here.

  • particle filtering

    This is also known as rao-blackwellized inference, and it allows you to update a graphical/probabilistic model as more data arrives. Some good examples are online topic models and the NIPS tutorial on SMC.

There are also some broader issues with online learning, like online-to-batch conversion, budget techniques for online learning with kernels (like this paper, this paper, and this paper), many different flavors of generalization bounds, sparsity concerns (and also the SMIDAS paper I cited above), hashing to save memory, and many other issues.

  • Very informative answer! – Tayfun Pay Jul 4 '17 at 15:34

Avrim Blum as a terrific survey paper that I would recommend starting with: "Online Algorithms in Machine Learning" http://www.cs.cmu.edu/~avrim/Papers/survey.ps

If you're looking for information on the theory behind online learning, the book by Cesa-Bianchi and Lugosi is a solid reference.

There is a nice tutorial from ICML 2008 by Yoram Singer and Shai Shalev Shwartz on the theory and practice of online learning.

Machine Learning - Course Materials - Stanford http://www.stanford.edu/class/cs229/materials.html

Machine Learning and Artificial Intelligence Video Lectures http://freescienceonline.blogspot.com/2007/07/machine-learning-and-artificial.html

Gaussian Processes for Machine Learning http://www.gaussianprocess.org/gpml/

  • 1
    This does not talk specifically about online learning. The gaussian process book hardly mentions the online approximations to gaussian processes. – Alexandre Passos Aug 18 '10 at 13:26

Your Answer


By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.