A tutorial introduction to the minimum description length principle
By Peter D. Grünwald. 2004
387 citations recorded by the source corpus.
This tutorial provides an overview of and introduction to Rissanen's Minimum Description Length (MDL) Principle. The first chapter provides a conceptual, entirely non-technical introduction to the subject. It serves as a basis for the technical introduction given in the second chapter, in which all the ideas of the first chapter are made mathematically precise. The main ideas are discussed in great conceptual and technical detail. This tutorial is an extended version of the first two chapters of the collection "Advances in Minimum Description Length: Theory and Application" (edited by P.Grunwald, I.J. Myung and M. Pitt, to be published by the MIT Press, Spring 2005).
Subfields: Artificial Intelligence, Computational Theory and Mathematics, Statistical Learning Theory, Information Theory
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
- Mohit Bansal
- Percy Liang
- Yoshua Bengio
- Kyunghyun Cho
- Jianfeng Gao
- Luke S. Zettlemoyer
- Quoc V. Le
- Christopher D. Manning
In Computational Theory and Mathematics
- Douwe Kiela
- Kyunghyun Cho
- Ethan Perez
- Nicolò Cesa-Bianchi
- Sham M. Kakade
- Ivan Titov
- Fosca Giannotti
- Dino Pedreschi
In Statistical Learning Theory
- Andrew Y. Ng
- Gábor Lugosi
- Nicolò Cesa-Bianchi
- Sham M. Kakade
- Ivan Titov
- Fosca Giannotti
- Dino Pedreschi
- Douwe Kiela
In Information Theory
- Nicolò Cesa-Bianchi
- Sham M. Kakade
- Ivan Titov
- Fosca Giannotti
- Dino Pedreschi
- Douwe Kiela
- Ming-Wei Chang
- Gábor Lugosi
Citations in the corpus
- True Few-Shot Learning with Language Models (2021, background): “1 There are other ways to evaluate MDL [see 31, for an overview].”
- Information-Theoretic Probing with Minimum Description Length (2020, background): “If the inputs and the outputs come from a true joint distribution q ( x, y ) , then, for any transmission method with codelength L , it holds E q [ L ( y | x )] ≥ H ( y | x ) (Grunwald, 2004).”
- Online Bounds for Bayesian Algorithms (2004, result): “Our motivation is similar to that given in the online learning literature and the MDL literature (see Grunwald, 2005 ) —namely, that models are often chosen to balance realism with computational tractability, and often assumptions made by the Bayesian are not truly believed to hold (e.g.”
- Rissanen Data Analysis: Examining Dataset Characteristics via Description Length (2021, methodology): “While MDL is not computable, just like Kolmogorov complexity, many methods have been proposed to estimate MDL by restricting the set of allowed compression algorithms (see Grünwald, 2004, for an overview).”
- Compositional Generalization and Natural Language Variation: Can a Semantic Parsing Approach Handle Both? (2020, methodology): “We follow the Minimum Description Length (MDL) principle (Rissanen, 1978; Grunwald, 2004) as a way to formalize this intuition.”
- A classification for community discovery methods in complex networks (2011, background): “to describe it using fewer symbols than the number of symbols needed to describe the data literally (see also [61] and [62]).”
- Finding large average submatrices in high dimensional data (2009, background): “The penalty depends separately on k and l, and its combinatorial form suggests a connection with the Minimum Description Length Principle (MDL), following Rissanen (2004), Grunwald (2004), and Barron and Yu (1998).”
- Prediction, learning, and games (2006, background): “For quite exhaustive surveys see Barron, Rissanen, Yu [22], Grünwald [134], and Hansen and Yu [143].”