Online Learning
Graduate course to be given Winter 2006. Tue, Thu 11:00 - 12:20.
HSS 2305A, Humanities & Social Science Building in Muir College.
Registered students will recieve a grade of Satisfactory / Unsatisfactory
Please drop me a line (yfreund at ucsd.edu) if you plan to attend this class.
Description
Suppose we observe a binary sequence, one bit at a time. Our task, at
each step, is to predict the next bit in the sequence. At our
disposal we have the predictions of N "experts". At each step each one
of the experts generates it's own prediction, in the form of a bit.
Suppose we know that one of the experts is perfect i.e. all of
it's predictions are correct. Can you find a prediction algorithm
that would make at most log2(N) mistakes?
Try it, try it, and you may, try and you may I say! [ Dr. Seuss, Green Eggs and Ham, 1960 ]
This course is about online prediction methods of the type you have
just discovered (If you have not found it yet, here is a clue: it is called
the Halving algorithm). At first blush, it might seem that this
algorithm is just a nice little trick that works only because we
assume that one of the experts is perfect.
In fact, this trick can, and has been, generalized to most imaginable situations.
In fact, I will argue that this methodology provides a mathematical foundation for
prediction that is more complete and more relevant than existing foundations.
Come check it out!
Topics I hope to cover (Not in chronological order)
- The weighted majority algorithm.
- Winnow algorithm.
- Binomial weights algorithm.
- Cumulative log loss, adaptive aritmetic coding, the online Bayes algorithm.
- Betting games, Universal portfolios.
- Using averaging methods in the batch setup.
- Uncountable sets of experts, least informative prior distributions.
- The context algorithm.
- Online prediction for Zipf distribution.
- Learning mixed strategies for repeated zero-sum games.
- Approachability methods, learning strategies in for general-sum repeated games, correlated equilibrium.
- Universal calibration.
- Switching experts.Drifting experts. Experts that switch within a subset.
- Multiple arms bandits.
- Mixable and unmixable loss functions.
- Vovk's Probability without measure.
- Experts that abstain.
Prerequisites
You should have a good foundation in math, i.e. linear algebra,
probability, integrals, taylor expansions. You will also need to
devote a significant amount of time between classes to reading papers
from a variety of fields. Notation and terminology in these papers
varies a lot, which makes reading a challange. However, mastering
these different terminologies and understanding the relationships
between them will provide you with an invaluable insight into this
exciting and evolving research area.