Asymptotics of Discrete MDL for Online Prediction
スポンサーリンク
概要
- 論文の詳細を見る
Erratum published: IEEE Transactions on Information Theory. Volume 52, Issue 3, March 2006, p.1279Minimum description length (MDL) is an importantprinciple for induction and prediction, with strong relations to optimalBayesian learning. This paper deals with learning processeswhich are not necessarily independent and identically distributed,by means of two-part MDL, where the underlying model class iscountable. We consider the online learning framework, i.e., observationscome in one by one, and the predictor is allowed to updateits state of mind after each time step.We identify two ways ofpredicting by MDL for this setup, namely, a static and a dynamicone. (A third variant, hybrid MDL, will turn out inferior.)We willprove that under the only assumption that the data is generated bya distribution contained in the model class, the MDL predictionsconverge to the true values almost surely. This is accomplishedby proving finite bounds on the quadratic, the Hellinger, and theKullbackLeibler loss of the MDL learner, which are, however, exponentiallyworse than for Bayesian prediction. We demonstratethat these bounds are sharp, even for model classes containing onlyBernoulli distributions. We show how these bounds imply regretbounds for arbitrary loss functions. Our results apply to a widerange of setups, namely, sequence prediction, pattern classification,regression, and universal induction in the sense of algorithmic informationtheory among others.http://dx.doi.org/10.1109/TIT.2006.869753
- IEEEの論文
IEEE | 論文
- Magnetic and Transport Properties of Nb/PdNi Bilayers
- Supersonic Ion Beam Driven by Permanent-Magnets-Induced Double Layer in an Expanding Plasma
- Surfactant Adsorption on Single-Crystal Silicon Surfaces in TMAH Solution: Orientation-Dependent Adsorption Detected by In Situ Infrared Spectroscopy
- Extended-range FMCW reflectometry using an optical loop with a frequency shifter
- Teachingless spray-painting of sculptured surface by an industrial robot