Minimum description length

The minimum description length (MDL) principle formalizes Occam's razor by selecting the model that minimizes the total bits needed to encode both the model and the data. Developed by Jorma Rissanen, MDL treats model selection as a compression problem. A good model compresses the data well; a bad model requires many bits. MDL shares asymptotic properties with the BIC but avoids prior distributions. It extends to stochastic complexity for non-parametric settings.

The Two-Part Code Formulation

MDL's most intuitive formulation is the two-part code: first encode the model, then encode the data given the model. The total description length is the sum of the model complexity (the number of bits needed to specify the model parameters and structure) and the data complexity (the number of bits needed to encode the residuals or deviations from the model's predictions). This is not merely a computational heuristic. It is a formalization of the tradeoff between bias and variance that governs all inductive inference.

The two-part code reveals that model selection is not a search for truth. It is a search for the most efficient representation of what has been observed, with the understanding that the representation itself must be paid for in bits. A model that fits the data perfectly but requires as many parameters as data points is not a model at all; it is a lookup table. A model that is too simple leaves structure unexploited, wasting bits on the data side. The optimal model sits at the minimum of the total description length curve, where the marginal bit saved on the data side by adding complexity equals the marginal bit spent on the model side.

MDL and Kolmogorov Complexity

MDL is the practical sibling of Kolmogorov complexity. Where Kolmogorov complexity asks for the shortest program that generates a given string on a universal Turing machine, MDL asks for the shortest description that generates the data using a restricted class of models. The difference is crucial: Kolmogorov complexity is uncomputable, while MDL is computable because it restricts the model class. This restriction is not a defeat. It is a recognition that inference is always performed with respect to a vocabulary, and the choice of vocabulary is itself a form of prior knowledge.

The relationship is deeper than mere analogy. Both frameworks treat regularity as compression: the presence of structure in data is precisely what makes the data compressible. A random string has no shorter description than itself; a structured string has a description that is shorter than the string by an amount proportional to its structure. This equivalence between structure and compressibility is one of the foundational insights of modern information theory, and it connects MDL to algorithmic information theory, Shannon entropy, and the thermodynamic concept of entropy through the work of Boltzmann and Shannon.

MDL, Bayesian Inference, and the Prior Problem

MDL is often compared to Bayesian model selection, which uses the Bayesian information criterion (BIC) or marginal likelihood to penalize model complexity. The BIC approximates the marginal likelihood under the assumption that the posterior is approximately Gaussian, and it is asymptotically equivalent to MDL for certain model classes. But the philosophical differences are significant. Bayesian methods require a prior distribution over models, and the choice of prior is often criticized as subjective or arbitrary. MDL does not require a prior in the Bayesian sense. Instead, it requires a coding scheme — a way to assign descriptions to models and data.

The coding scheme is not neutral. It embodies assumptions about which models are simple and which are complex. But these assumptions are explicit and inspectable, whereas prior distributions often hide their assumptions in the mathematical form of the distribution. The MDL framework makes the subjectivity of model selection visible rather than burying it in integrals. In this sense, MDL is more honest about the epistemological foundations of inference than Bayesian methods, even when the numerical results are similar.

Applications and Limitations

MDL has been applied to problems ranging from decision tree induction to neural network architecture selection, from phylogenetic tree reconstruction to signal denoising. In each case, the principle is the same: choose the model that compresses the data best, accounting for the cost of the model itself. The framework is particularly powerful in settings where overfitting is a severe risk and where the number of candidate models is large — precisely the settings where traditional hypothesis testing fails.

The limitations of MDL are also instructive. The principle does not tell us which model class to use. It optimizes within a model class but does not select between classes with different expressive power. The coding scheme must be chosen, and different coding schemes can lead to different conclusions. And MDL, like all Occam-based principles, assumes that the true model is simpler than the data. In domains where the underlying reality is genuinely complex — where the data-generating process has no compact description — MDL will systematically underfit, preferring a simple wrong model to a complex right one.

The claim that MDL is objective because it avoids prior distributions is a sleight of hand. The coding scheme is the prior, dressed in information-theoretic clothing. The virtue of MDL is not that it eliminates subjectivity but that it makes the subjectivity explicit. Any inference framework that pretends to objectivity by hiding its assumptions in formal notation has not earned the trust it demands.