Minimum description length

Selecting the minimum length description of the available data as the best model observes the principle identified as Occam's razor. Prior to the advent of computer programming, generating such descriptions was the intellectual labor of scientific theorists. It was far less formal than it has become in the computer age. If two scientists had a theoretic disagreement, they rarely could formally apply Occam's razor to choose between their theories. They would have different data sets and possibly different descriptive languages. Nevertheless, science advanced as Occam's razor was an informal guide in deciding which model was best.

With the advent of formal languages and computer programming Occam's razor was mathematically defined. Models of a given set of observations, encoded as bits of data, could be created in the form of computer programs that output that data. Occam's razor could then formally select the shortest program, measured in bits of this algorithmic information, as the best model.

To avoid confusion, note that there is nothing in the MDL principle that implies a machine produced the program embodying the model. It can be entirely the product of humans. The MDL principle applies regardless of whether the description to be run on a computer is the product of humans, machines or any combination thereof. The MDL principle requires only that the shortest description, when executed, produce the original data set without error.

MDL applies in machine learning when algorithms (machines) generate descriptions. Learning occurs when an algorithm generates a shorter description of the same data set.

The theoretic minimum description length of a data set, called its Kolmogorov complexity, cannot, however, be computed. That is to say, even if by random chance an algorithm generates the shortest program of all that outputs the data set, an automated theorem prover cannot prove there is no shorter such program. Nevertheless, given two programs that output the dataset, the MDL principle selects the shorter of the two as embodying the best model.

Recent machine MDL learning of algorithmic, as opposed to statistical, data models have received increasing attention with increasing availability of data, computation resources and theoretic advances.[2][3] Approaches are informed by the burgeoning field of artificial general intelligence. Shortly before his death, Marvin Minsky came out strongly in favor of this line of research, saying:[4]

It seems to me that the most important discovery since Gödel was the discovery by Chaitin, Solomonoff and Kolmogorov of the concept called Algorithmic Probability which is a fundamental new theory of how to make predictions given a collection of experiences and this is a beautiful theory, everybody should learn it, but it’s got one problem, that is, that you cannot actually calculate what this theory predicts because it is too hard, it requires an infinite amount of work. However, it should be possible to make practical approximations to the Chaitin, Kolmogorov, Solomonoff theory that would make better predictions than anything we have today. Everybody should learn all about that and spend the rest of their lives working on it.

— Panel discussion on The Limits of Understanding, World Science Festival, NYC, Dec 14, 2014

Any set of data can be represented by a string of symbols from a finite (say, binary) alphabet.

[The MDL Principle] is based on the following insight: any regularity in a given set of data can be used to compress the data, i.e. to describe it using fewer symbols than needed to describe the data literally. (Grünwald, 2004)[5]

Based on this, in 1978, Jorma Rissanen published an MDL learning algorithm using the statistical notion of information rather than algorithmic information. Over the past 40 years this has developed into a rich theory of statistical and machine learning procedures with connections to Bayesian model selection and averaging, penalization methods such as Lasso and Ridge, and so on - Grünwald and Roos (2020)[6] give an introduction including all modern developments. Rissanen started out with this idea: all statistical learning is about finding regularities in data, and the best hypothesis to describe the regularities in data is also the one that is able to statistically compress the data most. Like other statistical methods, it can be used for learning the parameters of a model using some data. Usually though, standard statistical methods assume that the general form of a model is fixed. MDL's main strength is that it can also be used for selecting the general form of a model and its parameters. The quantity of interest (sometimes just a model, sometimes just parameters, sometimes both at the same time) is called a hypothesis. The basic idea is then to consider the (lossless) two-stage code that encodes data ${\displaystyle D}$ with length ${\displaystyle {L(D)}}$ by first encoding a hypothesis ${\displaystyle H}$ in the set of considered hypotheses ${\displaystyle {\cal {H}}}$ and then coding ${\displaystyle D}$ "with the help of" ${\displaystyle H}$; in the simplest context this just means "encoding the deviations of the data from the predictions made by ${\displaystyle H}$:

$${\displaystyle {L(D)}=\min _{H\in {\cal {H}}}\ (\ L(H)+L(D|H)\ )\ }$$

The ${\displaystyle H}$ achieving this minimum is then viewed as the best explanation of data ${\displaystyle D}$. As a simple example, take a regression problem: the data ${\displaystyle D}$ could consist of a sequence of points ${\displaystyle D=(x_{1},y_{1}),\ldots ,(x_{n},y_{n})}$, the set ${\displaystyle {\cal {H}}}$ could be the set of all polynomials from ${\displaystyle X}$ to ${\displaystyle Y}$. To describe a polynomial ${\displaystyle H}$ of degree (say) ${\displaystyle k}$, one would first have to discretize the parameters to some precision; one would then have to describe this precision (a natural number); next, one would have to describe the degree ${\displaystyle k}$ (another natural number), and in the final step, one would have to describe ${\displaystyle k+1}$ parameters; the total length would be ${\displaystyle L(H)}$. One would then describe the points in ${\displaystyle D}$ using some fixed code for the x-values and then using a code for the ${\displaystyle n}$ deviations ${\displaystyle y_{i}-H(x_{i})}$.

In practice, one often (but not always) uses a probabilistic model. For example, one associates each polynomial ${\displaystyle H}$ with the corresponding conditional distribution expressing that given ${\displaystyle X}$, ${\displaystyle Y}$ is normally distributed with mean ${\displaystyle H(X)}$ and some variance ${\displaystyle \sigma ^{2}}$ which could either be fixed or added as a free parameter. Then the set of hypotheses ${\displaystyle {\cal {H}}}$ reduces to the assumption of a linear model, ${\displaystyle Y=H(X)+\epsilon }$ , with ${\displaystyle H}$ a polynomial.

Furthermore, one is often not directly interested in specific parameters values, but just, for example, the degree of the polynomial. In that case, one sets ${\displaystyle {\cal {H}}}$ to be ${\displaystyle {\cal {H}}=\{{\cal {H}}_{0},{\cal {H}}_{1},\ldots \}}$where each ${\displaystyle {\cal {H}}_{j}}$ represents the hypothesis that the data is best described as a j-th degree polynomial. One then codes data ${\displaystyle D}$ given hypothesis ${\displaystyle {\cal {H}}_{j}}$ using a one-part code designed such that, whenever some hypothesis ${\displaystyle H\in {\cal {H}}_{j}}$ fits the data well, the codelength ${\displaystyle L(D|H)}$ is short. The design of such codes is called universal coding. There are various types of universal codes one could use, often giving similar lengths for long data sequences but differing for short ones. The 'best' (in the sense that it has a minimax optimality property) are the normalized maximum likelihood (NML) or Shtarkov codes. A quite useful class of codes are the Bayesian marginal likelihood codes. For exponential families of distributions, when Jeffreys prior is used and the parameter space is suitably restricted, these asymptotically coincide with the NML codes; this brings MDL theory in close contact with objective Bayes model selection, in which one also sometimes adopts Jeffreys' prior, albeit for different reasons. The MDL approach to model selection "gives a selection criterion formally identical to the BIC approach"[7] for large number of samples.

Rissanen's was not the first information-theoretic approach to learning; as early as 1968 Wallace and Boulton pioneered a related concept called minimum message length (MML). The difference between MDL and MML is a source of ongoing confusion. Superficially, the methods appear mostly equivalent, but there are some significant differences, especially in interpretation:

• MML is a fully subjective Bayesian approach: it starts from the idea that one represents one's beliefs about the data-generating process in the form of a prior distribution. MDL avoids assumptions about the data-generating process.
• Both methods make use of two-part codes: the first part always represents the information that one is trying to learn, such as the index of a model class (model selection) or parameter values (parameter estimation); the second part is an encoding of the data given the information in the first part. The difference between the methods is that, in the MDL literature, it is advocated that unwanted parameters should be moved to the second part of the code, where they can be represented with the data by using a so-called one-part code, which is often more efficient than a two-part code. In the original description of MML, all parameters are encoded in the first part, so all parameters are learned.
• Within the MML framework, each parameter is stated to exactly the precision which results in the optimal overall message length: the preceding example might arise if some parameter was originally considered "possibly useful" to a model but was subsequently found to be unable to help to explain the data (such a parameter will be assigned a code length corresponding to the (Bayesian) prior probability that the parameter would be found to be unhelpful). In the MDL framework, the focus is more on comparing model classes than models, and it is more natural to approach the same question by comparing the class of models that explicitly include such a parameter against some other class that doesn't. The difference lies in the machinery applied to reach the same conclusion.

• Algorithmic probability
• Algorithmic information theory
• Inductive inference
• Inductive probability
• Lempel–Ziv complexity

• Minimum Description Length on the Web, by the University of Helsinki. Features readings, demonstrations, events and links to MDL researchers.
• Homepage of Jorma Rissanen, containing lecture notes and other recent material on MDL.
• Advances in Minimum Description Length, MIT Press, ISBN 0-262-07262-9.