NDLI: Asymptotics of discrete MDL for online prediction

Content Provider	IEEE Xplore Digital Library
Author	Poland, J. Hutter, M.
Copyright Year	1963
Abstract	Minimum description length (MDL) is an important principle for induction and prediction, with strong relations to optimal Bayesian learning. This paper deals with learning processes which are independent and identically distributed (i.i.d.) by means of two-part MDL, where the underlying model class is countable. We consider the online learning framework, i.e., observations come in one by one, and the predictor is allowed to update its state of mind after each time step. We identify two ways of predicting by MDL for this setup, namely, a static and a dynamic one. (A third variant, hybrid MDL, will turn out inferior.) We will prove that under the only assumption that the data is generated by a distribution contained in the model class, the MDL predictions converge to the true values almost surely. This is accomplished by proving finite bounds on the quadratic, the Hellinger, and the Kullback-Leibler loss of the MDL learner, which are, however, exponentially worse than for Bayesian prediction. We demonstrate that these bounds are sharp, even for model classes containing only Bernoulli distributions. We show how these bounds imply regret bounds for arbitrary loss functions. Our results apply to a wide range of setups, namely, sequence prediction, pattern classification, regression, and universal induction in the sense of algorithmic information theory among others.
Sponsorship	IEEE Information Theory Society
Starting Page	3780
Ending Page	3795
Page Count	16
File Size	455614
File Format	PDF
ISSN	00189448
Volume Number	51
Issue Number	11
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2005-11-01
Publisher Place	U.S.A.
Access Restriction	One Nation One Subscription (ONOS)
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Bayesian methods Information theory Predictive models Hybrid power systems Pattern classification Information science Materials science and technology Pattern recognition Statistical learning Convergence universal induction Algorithmic information theory classification consistency discrete model class loss bounds minimum description length (MDL) regression sequence prediction stabilization
Content Type	Text
Resource Type	Article
Subject	Library and Information Sciences Information Systems Computer Science Applications

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Erratum to “Asymptotics of Discrete MDL for Online Prediction”

Suboptimal behavior of Bayes and MDL in classification under misspecification

Universal Models for the Exponential Distribution

Information Consistency of Nonparametric Gaussian Process Methods

Asymptotics of Discrete MDL for Online Prediction

Consistency of Learning Bayesian Network Structures with Continuous Variables: An Information Theoretic Approach

Context tree estimation for not necessarily finite memory processes, via BIC and MDL

The Consistency of MDL for Linear Regression Models With Increasing Signal-to-Noise Ratio

Approximation of the Two-Part MDL Code

Asymptotics of discrete MDL for online prediction

Similar Documents

Erratum to &#8220;Asymptotics of Discrete MDL for Online Prediction&#8221;

Suboptimal behavior of Bayes and MDL in classification under misspecification

Universal Models for the Exponential Distribution

Information Consistency of Nonparametric Gaussian Process Methods

Asymptotics of Discrete MDL for Online Prediction

Consistency of Learning Bayesian Network Structures with Continuous Variables: An Information Theoretic Approach

Context tree estimation for not necessarily finite memory processes, via BIC and MDL

The Consistency of MDL for Linear Regression Models With Increasing Signal-to-Noise Ratio

Approximation of the Two-Part MDL Code

Asymptotics of discrete MDL for online prediction

Erratum to “Asymptotics of Discrete MDL for Online Prediction”