Minimum description length

Minimum description length is a model-selection principle that chooses the model minimizing the combined length of a description of the model and a description of its data.

Kolmogorov complexity: The length of the shortest program that produces a given object on a universal computer. MDL uses computable codes to approximate this ideal measure of description length.
Statistical model: A mathematical specification of probability distributions that could have generated observed data. MDL compares candidate models by the lengths needed to encode them and their data.
Jorma Rissanen: A Finnish statistician who introduced the minimum description length principle in the late 1970s. Rissanen developed MDL as a statistical approach to model selection and coding.
Decision tree learning: A machine-learning method that predicts outcomes by recursively splitting data into decision rules. MDL can balance a tree’s structural complexity against errors in its training data.
Normalized maximum likelihood: A universal coding distribution formed by normalizing the best-fitting likelihood across all possible data. It gives a principled code for comparing models, but can be computationally expensive.
Prefix code: A code in which no valid codeword is the prefix of another, enabling unambiguous decoding. Prefix codes let model and data descriptions correspond to additive code lengths.
Likelihood function: A function measuring how probable observed data are under different parameter values or models. For common codes, data cost is closely related to negative log likelihood.
Information theory: The mathematical study of information, communication, and the limits of data compression. MDL draws on information theory’s link between code length and probability.
Clustering: The grouping of data points so that points within a group are more similar under a chosen measure. MDL can select the number and structure of clusters by total coding cost.
Fisher information: A measure of how sensitively a probability model’s likelihood changes with its parameters. It appears in refined MDL penalties that account for parameter-space geometry.

Linked from 6 pages