Help Guide Privacy Policy Disclaimer Contact us
  Advanced SearchBrowse




Conference Paper

Tracking a Small Set of Experts by Mixing Past Posteriors


Bousquet,  O
Department Empirical Inference, Max Planck Institute for Biological Cybernetics, Max Planck Society;

There are no locators available
Fulltext (public)
There are no public fulltexts available
Supplementary Material (public)
There is no public supplementary material available

Bousquet, O. (2001). Tracking a Small Set of Experts by Mixing Past Posteriors. In Proceedings of the 14th Annual Conference on Computational Learning Theory, Lecture Notes in Computer Science (pp. 31-47).

Cite as:
In this paper, we examine on-line learning problems in which the target concept is allowed to change over time. In each trial a master algorithm receives predictions from a large set of n experts. Its goal is to predict almost as well as the best sequence of such experts chosen off-line by partitioning the training sequence into k+1 sections and then choosing the best expert for each section. We build on methods developed by Herbster and Warmuth and consider an open problem posed by Freund where the experts in the best partition are from a small pool of size m. Since k>>m the best expert shifts back and forth between the experts of the small pool. We propose algorithms that solve this open problem by mixing the past posteriors maintained by the master algorithm. We relate the number of bits needed for encoding the best partition to the loss bounds of the algorithms. Instead of paying \log n for choosing the best expert in each section we first pay \log n\choose m bits in the bounds for identifying the pool of m experts and then \log m bits per new section. In the bounds we also pay twice for encoding the boundaries of the sections.