T. van Erven
- Freezing and sleeping: Tracking experts that learn by evolving past posteriors
- 18th Annual Belgian-Dutch Conference on Machine Learning (Benelearn 09), Tilburg, the Netherlands
- Book/source title
- Benelearn 09: the 18th Annual Belgian-Dutch Conference on Machine Learning: proceedings of the conference
- Pages (from-to)
- Tilburg: Tilburg centre for Creative Computing (TiCC), Tilburg University
- Document type
- Conference contribution
- Interfacultary Research Institutes
- Institute for Logic, Language and Computation (ILLC)
A problem posed by Freund is how to efficiently track a small pool of experts out of a much larger set. This problem was solved when Bousquet and Warmuth introduced their mixing past posteriors (MPP) algorithm in 2001.
In Freund’s problem the experts would normally be considered black boxes. However, in this paper we re-examine Freund’s problem in case the experts have internal structure that enables them to learn. In this case the problem has two possible interpretations: should the experts learn from all data or only from the subsequence on which they are being tracked? The MPP algorithm solves the first case. We generalise MPP to address the second option. Our results apply to any expert structure that can be formalised using (expert) hidden Markov models. Curiously enough, for our interpretation there are two natural reference schemes: freezing and sleeping. For each scheme, we provide an efficient prediction strategy and prove the relevant loss bound.
If you believe that digital publication of certain material infringes any of your rights or (privacy) interests, please let the Library know, stating your reasons. In case of a legitimate complaint, the Library will make the material inaccessible and/or remove it from the website. Please Ask the Library, or send a letter to: Library of the University of Amsterdam, Secretariat, Singel 425, 1012 WP Amsterdam, The Netherlands. You will be contacted as soon as possible.