Minimum Description Length

When you describe a sequence of numbers with a formula, something remarkable happens: a simple formula compresses the data into itself, while a convoluted formula that merely memorizes each point compresses nothing at all. This intuition is the seed of Minimum Description Length (MDL).

Introduced by Jorma Rissanen in 1978, MDL gives Occam's razor a precise mathematical form. The best model for a dataset is the one that minimizes the total description length — the number of bits needed to encode the model itself plus the number of bits needed to encode the data given the model. A model that fits perfectly but has a hundred free parameters may cost more in model bits than it saves in data bits: MDL will reject it.

The core idea is tight: compression equals understanding. A model that genuinely captures a regularity in the data can compress that data. A model that merely memorizes the data cannot be compressed further. This connection to Kolmogorov complexity and Bayesian inference makes MDL one of the deepest frameworks in machine learning and statistics.

The dots below are noisy samples from a hidden quadratic curve. Use the slider to fit polynomials of increasing degree and watch the MDL score — total bits for model plus residuals — respond.

<div class="hint">
  {{hint}}
</div>
<div class="controls">
  <label for="deg">{{deg_label}}: <span id="degLabel">2</span></label>
  <input type="range" id="deg" min="1" max="7" value="2" step="1">
</div>
<canvas id="cv" width="480" height="260"></canvas>
<div class="scores" id="scores"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; background: #fff; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .6rem; line-height: 1.45; }
.controls { display: flex; align-items: center; gap: .7rem; margin-bottom: .5rem; font-size: .9rem; }
input[type=range] { flex: 1; accent-color: #1d3557; }
canvas { display: block; width: 100%; max-width: 480px; border: 1px solid #dde3ea; border-radius: 8px; background: #f8fafc; }
.scores { margin-top: .6rem; display: grid; grid-template-columns: repeat(3, 1fr); gap: .4rem; }
.score-card { background: #eef2f7; border-radius: 8px; padding: .45rem .6rem; font-size: .82rem; }
.score-card .label { color: #556; font-weight: 600; margin-bottom: 2px; }
.score-card .val { font-size: 1.05rem; font-weight: 700; color: #1d3557; }
.score-card.best { background: #d4edda; }
.score-card.best .val { color: #0a7d33; }

// Code not found

A degree-1 line underfits: the residuals are large and cost many bits. A degree-2 parabola captures the trend and MDL bottoms out. A degree-7 polynomial passes through every point but its coefficients are expensive — MDL rises again. The minimum of the MDL curve points to the right model, even though the training error keeps falling. This is overfitting detection without a hold-out set.

MDL sounds like a clean recipe: minimize total description length. But the recipe hides a deep difficulty.

• Ideal MDL is defined in terms of Kolmogorov complexity — the length of the shortest program that produces the data. Kolmogorov complexity is uncomputable (see compression and the halting problem): no algorithm can evaluate it in general.
• Practical MDL replaces Kolmogorov complexity with computable code-length functions. The most principled choice is the Normalized Maximum Likelihood (NML) code, developed by Rissanen and Shtarkov. NML gives the minimax-optimal description length for a model class: it is the unique code that minimizes the worst-case regret against any dataset. Computing NML exactly is often itself intractable — for many model classes it requires summing over exponentially many datasets.
• Two-part MDL is the tractable work-horse: encode the model with a fixed-precision description, then encode the data given the model. Choosing how many bits to allocate to the model is the delicate part — the theory of stochastic complexity (Rissanen, 1986) guides this choice by linking description length to Fisher information.
• Consistency: under mild regularity conditions, MDL model selection is statistically consistent — as data grows, MDL converges to the true model class. This is a theorem, not a heuristic.

The computational hardness of ideal MDL mirrors the hardness of Kolmogorov complexity: both live at the boundary of what is and isn't computable, and both illuminate that boundary from a different angle.

MDL's compression view of explanation has spread across science and engineering:

• Classical statistics: the Bayesian Information Criterion (BIC) and Akaike's AIC are approximations of an MDL score. Statisticians use them every time they select the number of clusters, the polynomial degree, or the lag order in a time series.
• Deep learning: neural architecture search can be framed as MDL minimization — penalize networks by their weight description length. Hinton and Van Camp's minimum description length networks (1993) are a precursor of modern variational methods.
• Lossless data compression: Rissanen's work on MDL directly inspired arithmetic coding improvements and the design of universal codes such as the Context-Tree Weighting algorithm.
• Computational biology: phylogenetic tree selection, gene model choice, and protein structure prediction all involve choosing among competing hypotheses — MDL provides a principled criterion that does not require a held-out test set.
• Anomaly detection: if a new data segment requires significantly more bits to describe under the current model, it signals a change point or anomaly.

Wherever you must choose among models of different complexity, MDL's answer is always the same: pick the one that compresses best. See also Bayesian inference, which shares MDL's preference for simpler hypotheses via the prior.

Minimum Description Length makes a bold claim: understanding and compression are the same thing. A model that truly captures a pattern in the data can squeeze that data into fewer bits. A model that merely memorizes the data cannot compress it at all.

Rissanen's 1978 principle turns this claim into a practical algorithm: choose the model that minimizes total description length, and you choose, systematically, the simplest explanation consistent with the evidence. Overfitting is not just a statistical nuisance — it is a failure to compress, and MDL sees through it automatically.

The ideal version of MDL, grounded in Kolmogorov complexity, is uncomputable. The practical versions — NML, stochastic complexity, two-part codes — are approximations that preserve the key property: they penalize complexity exactly as much as the data justifies. In this way MDL sits at the intersection of information theory, statistics, and the theory of computation, offering one of the clearest answers science has to the question: when is an explanation good?