Freezing and Sleeping: Tracking Experts that Learn by Evolving Past Posteriors
作者： Wouter M. Koolen , Tim van Erven
DOI:
关键词: Computer science 、 Set (abstract data type) 、 Structure (mathematical logic) 、 Tracking (particle physics) 、 Scheme (programming language) 、 Interpretation (logic) 、 Hidden Markov model 、 Artificial intelligence 、 Mixing (mathematics)
摘要: A problem posed by Freund is how to efficiently track a small pool of experts out much larger set. This was solved when Bousquet and Warmuth introduced their mixing past posteriors (MPP) algorithm in 2001. In Freund’s the would normally be considered black boxes. However, this paper we re-examine case have internal structure that enables them learn. has two possible interpretations: should learn from all data or only subsequence on which they are being tracked? The MPP solves first case. We generalise address second option. Our results apply any expert can formalised using (expert) hidden Markov models. Curiously enough, for our interpretation there natural reference schemes: freezing sleeping. For each scheme, provide an efficient prediction strategy prove relevant loss bound.
arxiv.org
harvard.edu
uva.nl
narcis.nl参考文章(16)
Eiji Takimoto, Manfred K. Warmuth, The Last-Step Minimax Algorithm Lecture Notes in Computer Science. pp. 279- 290 ,(2000) , 10.1007/3-540-40992-0_21
Zoubin Ghahramani, Michael Jordan, None, Factorial Hidden Markov Models neural information processing systems. ,vol. 29, pp. 472- 478 ,(1995) , 10.1023/A:1007425814087
Nicolo Cesa-Bianchi, Gabor Lugosi, Prediction, learning, and games ,(2006)
P.A.J. Volf, F.M.J. Willems, Switching between two universal source coding algorithms data compression conference. pp. 491- 500 ,(1998) , 10.1109/DCC.1998.672217
Mark Herbster, Manfred K. Warmuth, Tracking the Best Expert Machine Learning. ,vol. 32, pp. 151- 178 ,(1998) , 10.1023/A:1007424614876
V. Vovk, Derandomizing stochastic prediction strategies Proceedings of the tenth annual conference on Computational learning theory - COLT '97. ,vol. 35, pp. 32- 44 ,(1997) , 10.1145/267460.267473
N. Littlestone, M.K. Warmuth, The weighted majority algorithm Information & Computation. ,vol. 108, pp. 212- 261 ,(1994) , 10.1006/INCO.1994.1009
Zoubin Ghahramani, Geoffrey E Hinton, None, Variational Learning for Switching State-Space Models Neural Computation. ,vol. 12, pp. 831- 864 ,(2000) , 10.1162/089976600300015619
Olivier Bousquet, Manfred K. Warmuth, Tracking a small set of experts by mixing past posteriors european conference on computational learning theory. ,vol. 3, pp. 363- 396 ,(2003) , 10.1007/3-540-44581-1_3
Peter Grünwald, Tim V. Erven, Steven D. Rooij, Catching Up Faster in Bayesian Model Selection and Model Averaging neural information processing systems. ,vol. 20, pp. 417- 424 ,(2007)