CoChat
Sign Up
PreprintCited by 1

A tutorial introduction to the minimum description length principle

Grunwald, Peter·2004·arXiv
DOI 10.48550/arxiv.math/0406077arXiv math/0406077
Open this paper in CoChat — free account

Abstract

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).

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

DataCite · 10.48550/arxiv.math/0406077

Cites

2 of 2 references verified0 citation errors · 0 not checkable

Statistics

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

  • The Minimum Description Length perspective treats good explanations as those that compress the observations while accounting for the complexity of the model itself.

    “This is closely related to the Minimum Description Length perspective, which treats good explanations as those that compress the observations while accounting for the complexity of the model itself [5].”

    From Executable World Models for ARC-AGI-3 in the Era of Coding Agents (2026) · cites this paper as [5]

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Cites

Flagged first, then by citations

Research works printed but not linked: 80

  1. Akaike, H. (1973). Information theory as an extension of the maximum likelihood principle. In B. N. Petrov and F. Csaki (Eds.), Second International Symposium on Information Theory, Budapest, pp. 267-281. Akademiai Kiado.
  2. Balasubramanian, V. (2004). MDL, Bayesian inference and the geometry of the space of probability distributions. In P. D. Grünwald, I. J. Myung, and M. A. Pitt (Eds.), Advances in Minimum Description Length: Theory and Applications. MIT Press.
  3. Barron, A. (1990). Complexity regularization with application to artificial neural networks. In G. Roussas (Ed.), Nonparametric Functional Estimation and Related Topics, Dordrecht, pp. 561-576. Kluwer Academic Publishers.
  4. Barron, A. and T. Cover (1991). Minimum complexity density estimation. IEEE Transactions on Information Theory 37 (4), 1034-1054.
  5. Barron, A. R. (1985). Logically Smooth Density Estimation. Ph. D. thesis, Depart- ment of EE, Stanford University, Stanford, Ca.
  6. Barron, A. R., J. Rissanen, and B. Yu (1998). The Minimum Description Length Principle in coding and modeling. IEEE Transactions on Information The- ory 44 (6), 2743-2760. Special Commemorative Issue: Information Theory: 1948- 1998.
  7. Bernardo, J. and A. Smith (1994). Bayesian theory. John Wiley.
  8. Burnham, K. P. and D. R. Anderson (2002). Model Selection and Multimodel Infer- ence. New York: Springer-Verlag.
  9. Chaitin, G. (1969). On the length of programs for computing finite binary sequences: statistical considerations. Journal of the ACM 16, 145-159.
  10. Comley, J. W. and D. L. Dowe (2004). Minimum Message Length and generalised Bayesian nets with asymmetric languages. In P. D. Grünwald, I. J. Myung, and M. A. Pitt (Eds.), Advances in Minimum Description Length: Theory and Ap- plications. MIT Press.
  11. Cover, T. and J. Thomas (1991). Elements of Information Theory. New York: Wiley Interscience.
  12. Csiszár, I. and P. Shields (2000). The consistency of the BIC Markov order estimator. The Annals of Statistics 28, 1601-1619.
  13. Dawid, A. (1992). Prequential analysis, stochastic complexity and Bayesian infer- ence. In J. Bernardo, J. Berger, A. Dawid, and A. Smith (Eds.), Bayesian Statis- tics, Volume 4, pp. 109-125. Oxford University Press. Proceedings of the Fourth Valencia Meeting.
  14. Dawid, A. (1997). Prequential analysis. In S. Kotz, C. Read, and D. Banks (Eds.), Encyclopedia of Statistical Sciences, Volume 1 (Update), pp. 464-470. Wiley- Interscience.
  15. De Finetti, B. (1974). Theory of Probability. A critical introductory treatment. Lon- don: John Wiley & Sons.
  16. Domingos, P. (1999). The role of Occam's razor in knowledge discovery. Data Mining and Knowledge Discovery 3 (4), 409-425.
  17. Feder, M. (1986). Maximum entropy as a special case of the minimum description length criterion. IEEE Transactions on Information Theory 32 (6), 847-849.
  18. Feller, W. (1968). An Introduction to Probability Theory and Its Applications, Vol- ume 1. Wiley. Third edition.
  19. Foster, D. and R. Stine (1999). Local asymptotic coding and the minimum description length. IEEE Transactions on Information Theory 45, 1289-1293.
  20. Foster, D. and R. Stine (2001). The competitive complexity ratio. In Proceedings of the 2001 Conference on Information Sciences and Systems. WP8 1-6.
  21. Foster, D. P. and R. A. Stine (2004). The contribution of parameters to stochastic complexity. In P. D. Grünwald, I. J. Myung, and M. A. Pitt (Eds.), Advances in Minimum Description Length: Theory and Applications. MIT Press.
  22. Gács, P., J. Tromp, and P. Vitányi (2001). Algorithmic statistics. IEEE Transactions on Information Theory 47 (6), 2464-2479.
  23. Grünwald, P. D. (1996). A minimum description length approach to grammar infer- ence. In G. S. S. Wermter, E. Riloff (Ed.), Connectionist, Statistical and Sym- bolic Approaches to Learning for Natural Language Processing, Number 1040 in Springer Lecture Notes in Artificial Intelligence, pp. 203-216.
  24. Grünwald, P. D. (1998). The Minimum Description Length Principle and Reasoning under Uncertainty. Ph. D. thesis, University of Amsterdam, The Netherlands. Available as ILLC Dissertation Series 1998-03.
  25. Grünwald, P. D. (1999). Viewing all models as 'probabilistic'. In Proceedings of the Twelfth Annual Workshop on Computational Learning Theory (COLT' 99), pp. 171-182.
  26. Grünwald, P. D. (2000). Maximum entropy and the glasses you are looking through. In Proceedings of the Sixteenth Conference on Uncertainty in Artificial Intelli- gence (UAI 2000), pp. 238-246.
  27. Grünwald, P. D. and A. P. Dawid (2004). Game theory, maximum entropy, minimum discrepancy, and robust Bayesian decision theory. Annals of Statistics 32 (4).
  28. Grünwald, P. D. and J. Langford (2004). Suboptimal behaviour of Bayes and MDL in classification under misspecification. In Proceedings of the Seventeenth Annual Conference on Computational Learning Theory (COLT' 04).
  29. Grünwald, P. D., I. J. Myung, and M. A. Pitt (Eds.) (2004). Advances in Minimum Description Length: Theory and Applications. MIT Press.
  30. Hansen, M. and B. Yu (2000). Wavelet thresholding via MDL for natural images. IEEE Transactions on Information Theory 46, 1778-1788.
  31. Hansen, M. and B. Yu (2001). Model selection and the principle of minimum descrip- tion length. Journal of the American Statistical Association 96 (454), 746-774.
  32. Hanson, A. J. and P. C.-W. Fu (2004). Applications of MDL to selected families of models. In P. D. Grünwald, I. J. Myung, and M. A. Pitt (Eds.), Advances in Minimum Description Length: Theory and Applications. MIT Press.
  33. Hjorth, U. (1982). Model selection and forward validation. Scandinavian Journal of Statistics 9, 95-105.
  34. Jaynes, E. (2003). Probability Theory: the logic of science. Cambridge University Press. Edited by G. Larry Bretthorst.
  35. Jeffreys, H. (1946). An invariant form for the prior probability in estimation prob- lems. Proceedings of the Royal Statistical Society (London) Series A 186, 453-461.
  36. Jeffreys, H. (1961). Theory of Probability (Third ed.). London: Oxford University Press.
  37. Kass, R. and A. E. Raftery (1995). Bayes factors. Journal of the American Statistical Association 90 (430), 773-795.
  38. Kass, R. and P. Voss (1997). Geometrical Foundations of Asymptotic Inference. Wiley Interscience.
  39. Kass, R. and L. Wasserman (1996). The selection of prior distributions by formal rules. Journal of the American Statistical Association 91, 1343-1370.
  40. Kolmogorov, A. (1965). Three approaches to the quantitative definition of informa- tion. Problems Inform. Transmission 1 (1), 1-7.
  41. Kontkanen, P., P. Myllymäki, W. Buntine, J. Rissanen, and H. Tirri (2004). An MDL framework for data clustering. In P. D. Grünwald, I. J. Myung, and M. A. Pitt (Eds.), Advances in Minimum Description Length: Theory and Applications. MIT Press.
  42. Kontkanen, P., P. Myllymäki, T. Silander, and H. Tirri (1999). On supervised selec- tion of Bayesian networks. In K. Laskey and H. Prade (Eds.), Proceedings of the 15th International Conference on Uncertainty in Artificial Intelligence (UAI'99).
  43. Lanterman, A. D. (2004). Hypothesis testing for Poisson versus geometric distri- butions using stochastic complexity. In P. D. Grünwald, I. J. Myung, and M. A. Pitt (Eds.), Advances in Minimum Description Length: Theory and Applications. MIT Press.
  44. Lee, P. (1997). Bayesian Statistics -an introduction. Arnold & Oxford University Press.
  45. Li, M., X. Chen, X. Li, B. Ma, and P. Vitányi (2003). The similarity metric. In Proc. 14th ACM-SIAM Symp. Discrete Algorithms (SODA).
  46. Li, M. and P. Vitányi (1997). An Introduction to Kolmogorov Complexity and Its Applications (revised and expanded second ed.). New York: Springer-Verlag.
  47. Liang, F. and A. Barron (2004a). Exact minimax predictive density estimation and MDL. In P. D. Grünwald, I. J. Myung, and M. A. Pitt (Eds.), Advances in Minimum Description Length: Theory and Applications. MIT Press.
  48. Liang, F. and A. Barron (2004b). Exact minimax strategies for predictive density estimation. To appear in IEEE Transactions on Information Theory.
  49. Modha, D. S. and E. Masry (1998). Prequential and cross-validated regression esti- mation. Machine Learning 33 (1), 5-39.
  50. Myung, I. J., V. Balasubramanian, and M. A. Pitt (2000). Counting probability dis- tributions: Differential geometry and model selection. Proceedings of the National Academy of Sciences USA 97, 11170-11175.
  51. Ripley, B. (1996). Pattern Recognition and Neural Networks. Cambridge University Press.
  52. Rissanen, J. (1983). A universal prior for integers and estimation by minimum de- scription length. The Annals of Statistics 11, 416-431.
  53. Rissanen, J. (1984). Universal coding, information, prediction and estimation. IEEE Transactions on Information Theory 30, 629-636.
  54. Rissanen, J. (1986). Stochastic complexity and modeling. The Annals of Statistics 14, 1080-1100.
  55. Rissanen, J. (1987). Stochastic complexity. Journal of the Royal Statistical Society, series B 49, 223-239. Discussion: pages 252-265.
  56. Rissanen, J. (1989). Stochastic Complexity in Statistical Inquiry. World Scientific Publishing Company.
  57. Rissanen, J. (1996). Fisher information and stochastic complexity. IEEE Transac- tions on Information Theory 42 (1), 40-47.
  58. Rissanen, J. (2000). MDL denoising. IEEE Transactions on Information The- ory 46 (7), 2537-2543.
  59. Rissanen, J. (2001). Strong optimality of the normalized ML models as universal codes and information in data. IEEE Transactions on Information Theory 47 (5), 1712-1717.
  60. Rissanen, J., T. Speed, and B. Yu (1992). Density estimation by stochastic complex- ity. IEEE Transactions on Information Theory 38 (2), 315-323.
  61. Rissanen, J. and I. Tabus (2004). Kolmogorov's structure function in MDL theory and lossy data compression. In P. D. Grünwald, I. J. Myung, and M. A. Pitt (Eds.), Advances in Minimum Description Length: Theory and Applications. MIT Press.
  62. Schwarz, G. (1978). Estimating the dimension of a model. The Annals of Statis- tics 6 (2), 461-464.
  63. Shafer, G. and V. Vovk (2001). Probability and Finance -It's only a game! Wiley.
  64. Shtarkov, Y. M. (1987). Universal sequential coding of single messages. (translated from) Problems of Information Transmission 23 (3), 3-17.
  65. Solomonoff, R. (1978). Complexity-based induction systems: comparisons and con- vergence theorems. IEEE Transactions on Information Theory 24, 422-432.
  66. Speed, T. and B. Yu (1993). Model selection and prediction: normal regression. Ann. Inst. Statist. Math. 45 (1), 35-54.
  67. Takeuchi, J. (2000). On minimax regret with respect to families of stationary stochas- tic processes (in Japanese). In Proceedings IBIS 2000, pp. 63-68.
  68. Takeuchi, J. and A. Barron (1997). Asymptotically minimax regret for exponential families. In Proceedings SITA '97, pp. 665-668.
  69. Takeuchi, J. and A. Barron (1998). Asymptotically minimax regret by Bayes mix- tures. In Proceedings of the 1998 International Symposium on Information Theory (ISIT 98).
  70. Townsend, P. (1975). The mind-body equation revisited. In C.-Y. Cheng (Ed.), Psy- chological Problems in Philosophy, pp. 200-218. Honolulu: University of Hawaii Press.
  71. Vapnik, V. (1998). Statistical Learning Theory. John Wiley.
  72. Vereshchagin, N. and P. M. B. Vitányi (2002). Kolmogorov's structure functions with an application to the foundations of model selection. In Proc. 47th IEEE Symp. Found. Comput. Sci. (FOCS'02).
  73. Viswanathan., M., C. Wallace, D. Dowe, and K. Korb (1999). Finding cutpoints in noisy binary sequences -a revised empirical evaluation. In Proc. 12th Australian Joint Conf. on Artif. Intelligence, Volume 1747 of Lecture Notes in Artificial Intelligence (LNAI), Sidney, Australia, pp. 405-416.
  74. Vitányi, P. M. (2004). Algorithmic statistics and Kolmogorov's structure function. In P. D. Grünwald, I. J. Myung, and M. A. Pitt (Eds.), Advances in Minimum Description Length: Theory and Applications. MIT Press.
  75. Wallace, C. and D. Boulton (1968). An information measure for classification. Com- puting Journal 11, 185-195.
  76. Wallace, C. and D. Boulton (1975). An invariant Bayes method for point estimation. Classification Society Bulletin 3 (3), 11-34.
  77. Wallace, C. and P. Freeman (1987). Estimation and inference by compact coding. Journal of the Royal Statistical Society, Series B 49, 240-251. Discussion: pages 252-265.
  78. Webb, G. (1996). Further experimental evidence against the utility of Occam's razor. Journal of Artificial Intelligence Research 4, 397-417.
  79. Yamanishi, K. (1998). A decision-theoretic extension of stochastic complexity and its applications to learning. IEEE Transactions on Information Theory 44 (4), 1424-1439.
  80. Zhang, T. (2004). On the convergence of MDL density estimation. In Y. Singer and J. Shawe-Taylor (Eds.), Proceedings of the Seventeenth Annual Conference on Computational Learning Theory (COLT' 04), Lecture Notes in Computer Science. Springer-Verlag.

Cited by

Sorted by citations

Authors
Grunwald, P.
Venue
arXiv
Publisher
arXiv
Published
2004
DOI
10.48550/arxiv.math/0406077
arXiv
math/0406077
References
2
Type
Preprint
Licence
arxiv.org/licenses/assumed-1991-2003/

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review