<p>Most online learning algorithms come from at least one out of these lineages:</p>

<ul>
<li><p>the perceptron</p>

<p>State of the art perceptrons are the <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.61.5120&amp;rep=rep1&amp;type=pdf">passive-aggressive algorithm</a>, the <a href="http://ir.hit.edu.cn/~car/research/dishmm.pdf">structured perceptron</a>, and their many varieties.</p></li>
<li><p>The winnow </p>

<p>The winnow has been reformulated as <a href="http://www.ingentaconnect.com/content/ap/ic/1997/00000132/00000001/art02612">exponentiated gradient methods</a>, and can be applied to <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.70.6635&amp;rep=rep1&amp;type=pdf">structured problems</a> as well. There are also varieties that deal directly with L1 regularization (to guarantee sparsity), such as <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.149.5344&amp;rep=rep1&amp;type=pdf">SMIDAS</a>.</p></li>
<li><p>Stochastic gradient descent</p>

<p>Stochastic gradient descent is when you apply online optimization to a possibly batch problem. State of the art algorithms are Leon Bottou's <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.60.9676&amp;rep=rep1&amp;type=pdf">LaSVM</a>, <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.161.9629&amp;rep=rep1&amp;type=pdf">Pegasos</a>, and many neural network algorithms can be easily trained in this setting. See the <a href="http://deeplearning.net/tutorial/">theano tutorial</a> for many examples. Maybe <a href="http://www.cs.berkeley.edu/~pliang/papers/online-naacl2009-talk.pdf">online EM</a> fits here.</p></li>
<li><p>particle filtering</p>

<p>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 <a href="http://cocosci.berkeley.edu/tom/papers/topicpf.pdf">online topic models</a> and the <a href="http://videolectures.net/mlss07_doucet_smcm/">NIPS tutorial on SMC</a>.</p></li>
</ul>

<p>There are also some broader issues with online learning, like <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.68.9600&amp;rep=rep1&amp;type=pdf">online-to-batch conversion</a>, budget techniques for online learning with kernels (like <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.72.5040&amp;rep=rep1&amp;type=pdf">this paper</a>, <a href="http://astro.temple.edu/~tua63862/ICML10_BPegasos.pdf">this paper</a>, and <a href="http://jmlr.csail.mit.edu/proceedings/papers/v9/wang10b/wang10b.pdf">this paper</a>), many different flavors of generalization bounds, <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.148.6556&amp;rep=rep1&amp;type=pdf">sparsity concerns</a> (and also the SMIDAS paper I cited above), <a href="http://eprints.pascal-network.org/archive/00005685/01/ShiPetDroLanetal09b.pdf">hashing</a> to save memory, and many other issues. </p>

CC BY-SA 3.0
2017-07-04T15:34:12.093Z
Very informative answer!
Tayfun Pay
CC BY-SA 2.5
2010-08-18T13:40:05.237Z
2010-08-18T13:40:05.237Z
Alexandre Passos
<p>Avrim Blum as a terrific survey paper that I would recommend starting with: "Online Algorithms in Machine Learning" <a href="http://www.cs.cmu.edu/~avrim/Papers/survey.ps">http://www.cs.cmu.edu/~avrim/Papers/survey.ps</a></p>

CC BY-SA 2.5
2010-08-17T12:01:54.630Z
2010-08-17T12:01:54.630Z
Aaron Roth
<p>If you're looking for information on the theory behind online learning, the book by <a href="http://homes.dsi.unimi.it/~cesabian/predbook/" rel="nofollow">Cesa-Bianchi and Lugosi</a> is a solid reference. </p>

CC BY-SA 2.5
2010-08-17T04:29:10.573Z
I'll look into it, thanks. That was actually one of the two suggestions Wikipedia provided (http://en.wikipedia.org/wiki/Online_machine_learning could use some help)
jtolds
CC BY-SA 2.5
2010-08-17T04:35:18.273Z
Another useful source is John Langford's series of posts: http://hunch.net/?cat=7
Suresh Venkat
CC BY-SA 2.5
2010-08-17T04:23:11.580Z
2010-08-17T04:23:11.580Z
Suresh Venkat
<p>There is a <a href="http://ttic.uchicago.edu/~shai/icml08tutorial/" rel="nofollow">nice tutorial</a> from ICML 2008 by Yoram Singer and Shai Shalev Shwartz on the theory and practice of online learning.</p>

CC BY-SA 2.5
2010-08-18T21:42:40.450Z
2010-08-18T21:42:40.450Z
Lev Reyzin
<p>Machine Learning - Course Materials - Stanford
<a href="http://www.stanford.edu/class/cs229/materials.html" rel="nofollow">http://www.stanford.edu/class/cs229/materials.html</a></p>

<p>Machine Learning and Artificial Intelligence Video Lectures
<a href="http://freescienceonline.blogspot.com/2007/07/machine-learning-and-artificial.html" rel="nofollow">http://freescienceonline.blogspot.com/2007/07/machine-learning-and-artificial.html</a></p>

<p>Gaussian Processes for Machine Learning
<a href="http://www.gaussianprocess.org/gpml/" rel="nofollow">http://www.gaussianprocess.org/gpml/</a></p>

CC BY-SA 2.5
2010-08-18T13:26:11.793Z
This does not talk specifically about online learning. The gaussian process book hardly mentions the online approximations to gaussian processes.
Alexandre Passos
CC BY-SA 2.5
2010-08-17T11:50:27.913Z
2010-08-17T11:50:27.913Z
Paulo Coghi
<p>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.</p>

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

CC BY-SA 2.5
2010-08-17T18:12:56.783Z
When asking users to contribute to a list of answers, the question should be marked [community wiki](http://meta.stackexchange.com/questions/11740/what-are-community-wiki-posts). I have converted this question.
Robert Cartaino
<reference-request><machine-learning><lg.learning><ai.artificial-intel><online-learning>
What are good references on understanding online learning?
jtolds
# What are good references on understanding online learning?

(Asked by: username_0 on 2010-08-17)

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.

**Tags:** reference-request, machine-learning, lg.learning, ai.artificial-intel, online-learning
> **Comments:**
> **username_1**: When asking users to contribute to a list of answers, the question should be marked [community wiki](http://meta.stackexchange.com/questions/11740/what-are-community-wiki-posts). I have converted this question.  

---

## 5 answers

### Answer by username_2 on 2010-08-18. Score: 11

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](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.61.5120&rep=rep1&type=pdf), the [structured perceptron](http://ir.hit.edu.cn/~car/research/dishmm.pdf), and their many varieties.
* The winnow

  The winnow has been reformulated as [exponentiated gradient methods](http://www.ingentaconnect.com/content/ap/ic/1997/00000132/00000001/art02612), and can be applied to [structured problems](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.70.6635&rep=rep1&type=pdf) as well. There are also varieties that deal directly with L1 regularization (to guarantee sparsity), such as [SMIDAS](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.149.5344&rep=rep1&type=pdf).
* 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](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.60.9676&rep=rep1&type=pdf), [Pegasos](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.161.9629&rep=rep1&type=pdf), and many neural network algorithms can be easily trained in this setting. See the [theano tutorial](http://deeplearning.net/tutorial/) for many examples. Maybe [online EM](http://www.cs.berkeley.edu/~pliang/papers/online-naacl2009-talk.pdf) 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](http://cocosci.berkeley.edu/tom/papers/topicpf.pdf) and the [NIPS tutorial on SMC](http://videolectures.net/mlss07_doucet_smcm/).

There are also some broader issues with online learning, like [online-to-batch conversion](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.68.9600&rep=rep1&type=pdf), budget techniques for online learning with kernels (like [this paper](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.72.5040&rep=rep1&type=pdf), [this paper](http://astro.temple.edu/~tua63862/ICML10_BPegasos.pdf), and [this paper](http://jmlr.csail.mit.edu/proceedings/papers/v9/wang10b/wang10b.pdf)), many different flavors of generalization bounds, [sparsity concerns](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.148.6556&rep=rep1&type=pdf) (and also the SMIDAS paper I cited above), [hashing](http://eprints.pascal-network.org/archive/00005685/01/ShiPetDroLanetal09b.pdf) to save memory, and many other issues.

> **Comments:**
> **username_3**: Very informative answer!  

---

### Answer by username_4 on 2010-08-17. Score: 7

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>


---

### Answer by username_5 on 2010-08-17. Score: 4

If you're looking for information on the theory behind online learning, the book by [Cesa-Bianchi and Lugosi](http://homes.dsi.unimi.it/~cesabian/predbook/) is a solid reference.

> **Comments:**
> **username_0**: I'll look into it, thanks. That was actually one of the two suggestions Wikipedia provided (http://en.wikipedia.org/wiki/Online_machine_learning could use some help)  
> **username_5**: Another useful source is John Langford's series of posts: http://hunch.net/?cat=7  

---

### Answer by username_6 on 2010-08-18. Score: 4

There is a [nice tutorial](http://ttic.uchicago.edu/~shai/icml08tutorial/) from ICML 2008 by Yoram Singer and Shai Shalev Shwartz on the theory and practice of online learning.


---

### Answer by username_7 on 2010-08-17. Score: 1

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/>

> **Comments:**
> **username_2**: This does not talk specifically about online learning. The gaussian process book hardly mentions the online approximations to gaussian processes.  

---

