2010-10-15: Winnow and Weighted Majority Algorithms

We covered two classic online algorithms:

• The Winnow algorithm that is able to learn in an attribute efficient way. Originally introduced in this paper by Littlestone: Learning Quickly When Irrelevant Attributes Abound: A New Linear-Threshold Algorithm
• The Weighted Majority Algorithm that is able to learn from multiple experts. Introduced in this paper by Littlestone and Warmuth: The Weighted Majority Algorithm

The lecture was based in Blum's survey paper On-Line Algorithms in Machine Learning.

Exercise 3: Re-do analysis for winnow but instead of cutting weights in half in a demotion step, set weights to 0. This is, in fact, the "elimination algorithm".