minimum description length
In plain wordsThe principle that the best explanation of some data is the one that lets you write the data down most briefly, counting both the rule and its exceptions. Good theories compress.
A principle of inductive inference and model selection based on two-part codes: a model is charged the bits to state it plus the bits to state the data given the model, and the cheapest total wins. Fit and complexity are thus traded in one currency — a complex model may fit the data closely (a short second part) but cost many bits to state (a long first part) — so MDL penalizes overfittingoverfitting, n.: When a model learns its training examples too well — quirks and noise included — so it does great on data it has seen but poorly on anything new, like a student who memorizes answers without understanding. without an explicit priorprior, n.: What you believe, and how strongly, before looking at the evidence in front of you. In AI it also means built-in assumptions that steer what a system learns., an information-theoretic form of Occam's razorOccam's razor, n.: A rule of thumb for choosing between explanations: if two fit the evidence equally well, bet on the one that assumes less. In AI it motivates preferring simpler models, which are less likely to fit noise.. The two-part form resembles maximum a posteriori estimationmaximum a posteriori estimation, n.: Picking the single most believable setting of a model after combining the evidence with what was assumed beforehand. In practice it often amounts to ordinary training plus a penalty that keeps settings modest. with code lengths as negative log-probabilities; refined versions use universal codes and normalized maximum likelihood. MDL is a computable relative of Kolmogorov complexityKolmogorov complexity, n.: How briefly something can be described by a computer program that recreates it exactly: a million zeros needs only a tiny program, while a truly random string needs one about as long as itself., close in spirit to Chris Wallace's minimum message length. In AI it supports the view that learning is compression: a language model's negative log-likelihoodlog-likelihood, n.: The logarithm of how probable a model finds the observed data. Taking logs turns a product of many tiny probabilities into a manageable sum; training usually minimizes its negative. on data, in bits, equals a code length via arithmetic coding, prequential ('online') code lengths measure what models learn, and MDL arguments are invoked to explain generalizationgeneralization, n.: How well a model copes with new examples it has never seen, rather than just memorizing its training data, like a student who understands the method, not just the answers. and grokkinggrokking, n.: When a model that has merely memorized its training examples suddenly, long afterward, figures out the underlying rule and starts getting new examples right..
By MDL, the twelve-rule grammar beats the lookup table: rules plus exceptions take fewer bits than listing every case.
Origin
Introduced by the Finnish information theorist Jorma Rissanen in 'Modeling by Shortest Data Description' (Automatica, 1978), drawing on Kolmogorov complexity and Ray Solomonoff's work; Chris Wallace and David Boulton's related minimum message length principle dates from 1968. Peter Grünwald's The Minimum Description Length Principle (2007) is the standard modern treatment.
Related
- Kolmogorov complexityKolmogorov complexity, n.: How briefly something can be described by a computer program that recreates it exactly: a million zeros needs only a tiny program, while a truly random string needs one about as long as itself.
- Occam's razorOccam's razor, n.: A rule of thumb for choosing between explanations: if two fit the evidence equally well, bet on the one that assumes less. In AI it motivates preferring simpler models, which are less likely to fit noise.
- Solomonoff inductionSolomonoff induction, n.: A mathematical recipe for ideal prediction: consider every computer program that could have produced the data so far, trust shorter programs more, and predict what they would output next.
- information theoryinformation theory, n.: A branch of mathematics that treats information as surprise — the less predictable a message, the more it tells you — and works out how far data can be compressed and how reliably it can be sent.
- model selectionmodel selection, n.: Choosing, from several candidate models or settings, the one most likely to work best on new data, rather than the one that merely fits the existing data best.
- generalizationgeneralization, n.: How well a model copes with new examples it has never seen, rather than just memorizing its training data, like a student who understands the method, not just the answers.
Sources
- Rissanen, J. (1978). Modeling by Shortest Data Description. Automatica, 14(5).
- Grünwald, P. D. (2007). The Minimum Description Length Principle. MIT Press.
Mentioned in
information theoryinformation theory, n.: A branch of mathematics that treats information as surprise — the less predictable a message, the more it tells you — and works out how far data can be compressed and how reliably it can be sent., model selectionmodel selection, n.: Choosing, from several candidate models or settings, the one most likely to work best on new data, rather than the one that merely fits the existing data best., Occam's razorOccam's razor, n.: A rule of thumb for choosing between explanations: if two fit the evidence equally well, bet on the one that assumes less. In AI it motivates preferring simpler models, which are less likely to fit noise., Bayesian information criterionBayesian information criterion, n.: A score for comparing statistical models that, like AIC, rewards good fit and penalizes extra adjustable numbers, but penalizes them more as the dataset grows, favoring simpler models. Lower is better., information bottleneckinformation bottleneck, n.: The idea that a good internal summary of data keeps exactly the details needed for the task and discards everything else, as a good note-taker does., Kolmogorov complexityKolmogorov complexity, n.: How briefly something can be described by a computer program that recreates it exactly: a million zeros needs only a tiny program, while a truly random string needs one about as long as itself., parameter decompositionparameter decomposition, n.: An approach that tries to understand a neural network by splitting its weights — rather than its internal activity — into many simple pieces, each responsible for one mechanism., Ray SolomonoffRay Solomonoff, prop. n.: An American mathematician who worked out an ideal mathematical recipe for predicting what comes next from past data, and who attended the 1956 meeting that launched AI., sharp and flat minimasharp and flat minima, n.: Two kinds of low points a trained model can settle into: narrow pits where small changes spoil performance, and broad basins where they barely matter. Broad basins are thought to generalize better, though this is debated., singular learning theorysingular learning theory, n.: A mathematical theory of learning for models like neural networks, whose many redundant settings break standard statistics; it explains how such models generalize and how their learning unfolds., Solomonoff inductionSolomonoff induction, n.: A mathematical recipe for ideal prediction: consider every computer program that could have produced the data so far, trust shorter programs more, and predict what they would output next.