Introduction

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.

Try It: MDL Catches Overfitting

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">
  Noisy samples from a hidden <b>quadratic</b> curve (y = 0.5x² − x + 1 + noise). Drag the slider to change the polynomial degree and watch the MDL score change.
</div>
<div class="controls">
  <label for="deg">Polynomial degree: <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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// MDL demo: fit polynomials of degree 1..7 to noisy quadratic data.
// MDL score = bits-for-model + bits-for-data (via Gaussian residuals).
// bits-for-model  = (degree+1) * COEF_BITS   (each coefficient costs COEF_BITS)
// bits-for-data   = (n/2) * log2(2*pi*e*sigma^2)  (Gaussian code length)
// This is the classic two-part MDL approximation.

const COEF_BITS = 8;   // bits per coefficient (precision budget)
const TRUE_DEG  = 2;   // hidden truth
const N         = 24;  // sample count

// Reproducible PRNG (mulberry32)
function mulberry32(seed) {
  return function() {
    seed |= 0; seed = seed + 0x6D2B79F5 | 0;
    let t = Math.imul(seed ^ seed >>> 15, 1 | seed);
    t = t + Math.imul(t ^ t >>> 7, 61 | t) ^ t;
    return ((t ^ t >>> 14) >>> 0) / 4294967296;
  };
}
const rand = mulberry32(42);
function randn() {
  // Box-Muller
  const u = rand(), v = rand();
  return Math.sqrt(-2 * Math.log(u + 1e-12)) * Math.cos(2 * Math.PI * v);
}

// Generate data: x in [-2, 2], y = 0.5x^2 - x + 1 + noise(0, 0.4)
const xs = [], ys = [];
for (let i = 0; i < N; i++) {
  const x = -2 + 4 * i / (N - 1);
  const y = 0.5 * x * x - x + 1 + 0.4 * randn();
  xs.push(x); ys.push(y);
}

// Vandermonde-based least-squares polynomial fit using normal equations
// Returns coefficients [c0, c1, ..., c_deg] (ascending powers)
function polyFit(xs, ys, deg) {
  const n = xs.length, d = deg + 1;
  // Build V^T V and V^T y
  const A = Array.from({length: d}, () => new Array(d).fill(0));
  const b = new Array(d).fill(0);
  for (let i = 0; i < n; i++) {
    const row = [];
    let p = 1;
    for (let j = 0; j < d; j++) { row.push(p); p *= xs[i]; }
    for (let r = 0; r < d; r++) {
      for (let c = 0; c < d; c++) A[r][c] += row[r] * row[c];
      b[r] += row[r] * ys[i];
    }
  }
  // Gaussian elimination with partial pivoting
  for (let col = 0; col < d; col++) {
    let maxR = col;
    for (let r = col + 1; r < d; r++) if (Math.abs(A[r][col]) > Math.abs(A[maxR][col])) maxR = r;
    [A[col], A[maxR]] = [A[maxR], A[col]];
    [b[col], b[maxR]] = [b[maxR], b[col]];
    const pivot = A[col][col];
    if (Math.abs(pivot) < 1e-14) continue;
    for (let r = 0; r < d; r++) {
      if (r === col) continue;
      const f = A[r][col] / pivot;
      for (let c = col; c < d; c++) A[r][c] -= f * A[col][c];
      b[r] -= f * b[col];
    }
  }
  return b.map((v, i) => v / (A[i][i] || 1));
}

function polyEval(coeffs, x) {
  let y = 0, p = 1;
  for (const c of coeffs) { y += c * p; p *= x; }
  return y;
}

function mdlScore(deg) {
  const coeffs = polyFit(xs, ys, deg);
  // Residuals
  let sse = 0;
  for (let i = 0; i < N; i++) {
    const r = ys[i] - polyEval(coeffs, xs[i]);
    sse += r * r;
  }
  const sigma2 = sse / N;
  // bits-for-data (Gaussian two-part MDL)
  const bitsData = sigma2 < 1e-12 ? 0 :
    (N / 2) * Math.log2(2 * Math.PI * Math.E * sigma2);
  // bits-for-model
  const bitsModel = (deg + 1) * COEF_BITS;
  return { total: bitsModel + bitsData, bitsModel, bitsData, rmse: Math.sqrt(sigma2), coeffs };
}

// Pre-compute scores for all degrees
const scores = [];
for (let d = 1; d <= 7; d++) scores.push({ deg: d, ...mdlScore(d) });
const bestDeg = scores.reduce((b, s) => s.total < b.total ? s : b, scores[0]).deg;

// Canvas drawing
const cv = document.getElementById('cv');
const ctx = cv.getContext('2d');
const W = cv.width, H = cv.height;
const PAD = { t: 18, b: 28, l: 36, r: 14 };

// data range
const xMin = -2.2, xMax = 2.2;
const yMin = Math.min(...ys) - 0.5, yMax = Math.max(...ys) + 0.5;
function px(x) { return PAD.l + (x - xMin) / (xMax - xMin) * (W - PAD.l - PAD.r); }
function py(y) { return PAD.t + (1 - (y - yMin) / (yMax - yMin)) * (H - PAD.t - PAD.b); }

function draw(deg) {
  ctx.clearRect(0, 0, W, H);
  // axes
  ctx.strokeStyle = '#cdd9e3'; ctx.lineWidth = 1;
  ctx.beginPath(); ctx.moveTo(PAD.l, PAD.t); ctx.lineTo(PAD.l, H - PAD.b);
  ctx.moveTo(PAD.l, H - PAD.b); ctx.lineTo(W - PAD.r, H - PAD.b); ctx.stroke();
  // tick labels y
  ctx.fillStyle = '#778'; ctx.font = '10px system-ui'; ctx.textAlign = 'right';
  for (let v = Math.ceil(yMin); v <= Math.floor(yMax); v++) {
    ctx.fillText(v, PAD.l - 3, py(v) + 3);
  }
  // tick labels x
  ctx.textAlign = 'center';
  for (let v = -2; v <= 2; v++) {
    ctx.fillText(v, px(v), H - PAD.b + 12);
  }

  // true curve
  ctx.strokeStyle = '#aabbc8'; ctx.lineWidth = 1.5; ctx.setLineDash([4, 3]);
  ctx.beginPath();
  for (let i = 0; i <= 200; i++) {
    const x = xMin + (xMax - xMin) * i / 200;
    const y = 0.5 * x * x - x + 1;
    i === 0 ? ctx.moveTo(px(x), py(y)) : ctx.lineTo(px(x), py(y));
  }
  ctx.stroke(); ctx.setLineDash([]);

  // fitted curve
  const coeffs = scores[deg - 1].coeffs;
  const color = deg === bestDeg ? '#0a7d33' : '#1d3557';
  ctx.strokeStyle = color; ctx.lineWidth = 2.2;
  ctx.beginPath();
  for (let i = 0; i <= 200; i++) {
    const x = xMin + (xMax - xMin) * i / 200;
    const y = polyEval(coeffs, x);
    i === 0 ? ctx.moveTo(px(x), py(y)) : ctx.lineTo(px(x), py(y));
  }
  ctx.stroke();

  // data points
  for (let i = 0; i < N; i++) {
    ctx.beginPath();
    ctx.arc(px(xs[i]), py(ys[i]), 3.5, 0, 2 * Math.PI);
    ctx.fillStyle = '#e63946'; ctx.fill();
  }

  // degree label
  ctx.fillStyle = color; ctx.font = 'bold 12px system-ui'; ctx.textAlign = 'left';
  ctx.fillText(fmt(`degree %deg%%v%`, { deg: deg, v: deg === bestDeg ? ' ← MDL best' : '' }), PAD.l + 4, PAD.t + 13);
}

function renderScores(activeDeg) {
  const el = document.getElementById('scores');
  el.innerHTML = scores.map(s => {
    const best = s.deg === bestDeg;
    const active = s.deg === activeDeg;
    const cls = best ? 'score-card best' : 'score-card';
    const border = active ? ' style="outline:2px solid #1d3557;"' : '';
    return fmt(`<div class="%cls%"%border%>
      <div class="label">deg %deg%%v%</div>
      <div class="val">%total% bits</div>
      <div style="font-size:.76rem;color:#556">%bitsModel% model + %bitsData% data</div>
    </div>`, { cls: cls, border: border, deg: s.deg, v: best ? ' ★' : '', total: s.total.toFixed(1), bitsModel: s.bitsModel.toFixed(0), bitsData: s.bitsData.toFixed(1) });
  }).join('');
}

const slider = document.getElementById('deg');
const label  = document.getElementById('degLabel');
slider.addEventListener('input', () => {
  const d = +slider.value;
  label.textContent = d;
  draw(d);
  renderScores(d);
});

draw(2);
renderScores(2);
Result
Console

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.

The Real Complexity

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.

Where It Matters

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.

Conclusion

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?

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/minimum-description-length/Content licensed under CC BY-NC 4.0.