Discrete MDL predicts in total variation

Marcus Hutter

Discrete MDL predicts in total variation

Marcus Hutter^*

^*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

15 Citations (Scopus)

Abstract

The Minimum Description Length (MDL) principle selects the model that has the shortest code for data plus model. We show that for a countable class of models, MDL predictions are close to the true distribution in a strong sense. The result is completely general. No independence, ergodicity, stationarity, identifiability, or other assumption on the model class need to be made. More formally, we show that for any countable class of models, the distributions selected by MDL (or MAP) asymptotically predict (merge with) the true measure in the class in total variation distance. Implications for non-i.i.d. domains like time-series forecasting, discriminative learning, and reinforcement learning are discussed.

Original language	English
Title of host publication	Advances in Neural Information Processing Systems 22 - Proceedings of the 2009 Conference
Publisher	Neural Information Processing Systems
Pages	817-825
Number of pages	9
ISBN (Print)	9781615679119
Publication status	Published - 2009
Event	23rd Annual Conference on Neural Information Processing Systems, NIPS 2009 - Vancouver, BC, Canada Duration: 7 Dec 2009 → 10 Dec 2009

Publication series

Name	Advances in Neural Information Processing Systems 22 - Proceedings of the 2009 Conference

Conference

Conference	23rd Annual Conference on Neural Information Processing Systems, NIPS 2009
Country/Territory	Canada
City	Vancouver, BC
Period	7/12/09 → 10/12/09

Cite this

@inproceedings{80271d6e75854e1296cee2f3fa2708fe,

title = "Discrete MDL predicts in total variation",

abstract = "The Minimum Description Length (MDL) principle selects the model that has the shortest code for data plus model. We show that for a countable class of models, MDL predictions are close to the true distribution in a strong sense. The result is completely general. No independence, ergodicity, stationarity, identifiability, or other assumption on the model class need to be made. More formally, we show that for any countable class of models, the distributions selected by MDL (or MAP) asymptotically predict (merge with) the true measure in the class in total variation distance. Implications for non-i.i.d. domains like time-series forecasting, discriminative learning, and reinforcement learning are discussed.",

author = "Marcus Hutter",

year = "2009",

language = "English",

isbn = "9781615679119",

series = "Advances in Neural Information Processing Systems 22 - Proceedings of the 2009 Conference",

publisher = "Neural Information Processing Systems",

pages = "817--825",

booktitle = "Advances in Neural Information Processing Systems 22 - Proceedings of the 2009 Conference",

note = "23rd Annual Conference on Neural Information Processing Systems, NIPS 2009 ; Conference date: 07-12-2009 Through 10-12-2009",

}

Hutter, M 2009, Discrete MDL predicts in total variation. in Advances in Neural Information Processing Systems 22 - Proceedings of the 2009 Conference. Advances in Neural Information Processing Systems 22 - Proceedings of the 2009 Conference, Neural Information Processing Systems, pp. 817-825, 23rd Annual Conference on Neural Information Processing Systems, NIPS 2009, Vancouver, BC, Canada, 7/12/09.

Discrete MDL predicts in total variation. / Hutter, Marcus.
Advances in Neural Information Processing Systems 22 - Proceedings of the 2009 Conference. Neural Information Processing Systems, 2009. p. 817-825 (Advances in Neural Information Processing Systems 22 - Proceedings of the 2009 Conference).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Discrete MDL predicts in total variation

AU - Hutter, Marcus

PY - 2009

Y1 - 2009

N2 - The Minimum Description Length (MDL) principle selects the model that has the shortest code for data plus model. We show that for a countable class of models, MDL predictions are close to the true distribution in a strong sense. The result is completely general. No independence, ergodicity, stationarity, identifiability, or other assumption on the model class need to be made. More formally, we show that for any countable class of models, the distributions selected by MDL (or MAP) asymptotically predict (merge with) the true measure in the class in total variation distance. Implications for non-i.i.d. domains like time-series forecasting, discriminative learning, and reinforcement learning are discussed.

AB - The Minimum Description Length (MDL) principle selects the model that has the shortest code for data plus model. We show that for a countable class of models, MDL predictions are close to the true distribution in a strong sense. The result is completely general. No independence, ergodicity, stationarity, identifiability, or other assumption on the model class need to be made. More formally, we show that for any countable class of models, the distributions selected by MDL (or MAP) asymptotically predict (merge with) the true measure in the class in total variation distance. Implications for non-i.i.d. domains like time-series forecasting, discriminative learning, and reinforcement learning are discussed.

UR - http://www.scopus.com/inward/record.url?scp=84858716044&partnerID=8YFLogxK

M3 - Conference contribution

SN - 9781615679119

T3 - Advances in Neural Information Processing Systems 22 - Proceedings of the 2009 Conference

SP - 817

EP - 825

BT - Advances in Neural Information Processing Systems 22 - Proceedings of the 2009 Conference

PB - Neural Information Processing Systems

T2 - 23rd Annual Conference on Neural Information Processing Systems, NIPS 2009

Y2 - 7 December 2009 through 10 December 2009

ER -

Discrete MDL predicts in total variation

Abstract

Publication series

Conference

Other files and links

Fingerprint

Cite this