Skip to content

Minimum description length

Compare model and data code lengths, understand prefix-code constraints and precision, and distinguish MDL from likelihood fitting and Bayesian inference.

Minimum description length (MDL) selects an explanation by how compactly it describes both itself and the observed data under an agreed coding scheme, following the principle introduced in Rissanen’s 1978 paper. For a quant researcher, it makes extra factors, breakpoints or trading rules pay for the improvement they deliver in fit. A more elaborate model can still win: the question is whether it saves more data-description bits than it costs to describe.

The bill has two parts

The basic two-part MDL objective is
M^=arg⁡min⁡M{L(M)+L(D∣M)}.\hat M=\arg\min_M\left\{L(M)+L(D\mid M)\right\}.
Here MM includes the selected structure and encoded parameter values. L(M)L(M) pays to communicate them; L(D∣M)L(D\mid M) pays to reconstruct the data using that information. In regression, the second part may encode residuals, but it is a code length, not a residual count or unscaled squared error. This is a coding interpretation of regularisation. Grünwald's tutorial, §2.4, formalises the two terms.
Suppose two valid codebooks, fixed in advance, give the following lengths for the same fictional dataset, at the same recording precision. Any common side information is shared; all model-specific overhead is included.
CandidateModel descriptionData given modelTotal
A20 bits100 bits120 bits
B60 bits50 bits110 bits

B spends 40 extra model bits and saves 50 data bits. Its total is 10 bits shorter, so MDL selects B. These are stipulated code lengths, not parameter counts. The example demonstrates the trade-off; it does not establish either model's forecasting performance.

Fictional fixed-code comparison: A uses 20 model bits plus 100 data bits, total 120; B uses 60 plus 50, total 110. B saves 50 data bits at an extra model cost of 40, a net saving of 10 bits.
Fictional fixed-code comparison: A uses 20 model bits plus 100 data bits, total 120; B uses 60 plus 50, total 110. B saves 50 data bits at an extra model cost of 40, a net saving of 10 bits.
Original fictional comparison under fixed, decodable codebooks. Both bars describe the same data at the same precision; shorter total length wins.

What makes a number a code length?

A prefix code lets a decoder identify each message without needing an unpriced separator: no complete codeword starts another. The words 0, 10, 110 and 111 satisfy this rule. Their lengths, 1, 2, 3 and 3 bits, obey the Kraft inequality:
∑j2−Lj≤1.\sum_j2^{-L_j}\leq1.
The sum here is exactly 1. For nonnegative integer lengths, this condition characterises whether a binary prefix code exists. Arbitrarily awarding every candidate a tiny penalty need not define a valid code. Stanford's information-theory notes, §§1–2, explain this constraint and the distinction between ideal and integer lengths.
For a discrete outcome with probability pp, the ideal length is −log⁡2p-\log_2p bits. A Shannon code can use ⌈−log⁡2p⌉\lceil-\log_2p\rceil bits. Thus p=1/8p=1/8 gives exactly 3 bits, while p=1/3p=1/3 gives about 1.585 ideal bits and a 2-bit Shannon codeword. Fractional ideal lengths are useful scoring quantities; they are not literal fractional binary symbols. Using −ln⁡p-\ln p instead gives nats: −ln⁡(1/8)≈2.0794-\ln(1/8)\approx2.0794. Convert nats to bits by dividing by ln⁡2\ln2, and convert every term consistently.

Precision is part of the contract

A two-part code cannot communicate an arbitrary real coefficient exactly in finitely many bits. Specify a parameter grid or precision and pay for it; for example, selecting among 256 agreed grid values takes 8 fixed-length bits. Finer precision can improve fit while lengthening the model description. The coding convention matters, especially with small samples. See Grünwald, §§2.4.2–2.5.
For continuous data, a probability density is not a probability mass. As a concrete check, a uniform density of 2 on the interval from 0 to 0.5 assigns probability 0.02 to each bin of width 0.01. Its ideal bin code costs −log⁡2(0.02)≈5.644-\log_2(0.02)\approx5.644 bits; applying the formula to the density alone gives −log⁡2(2)=−1-\log_2(2)=-1, which is not a literal lossless message length. In density-based comparisons, use a common observation resolution and base measure; resolution terms cancel only when they are common to the candidates.

One principle, several constructions

Two-part coding is an accessible MDL construction, not its only form. Refined MDL can encode data through a universal distribution, including normalised maximum likelihood, without explicitly transmitting one fitted parameter vector first. Grünwald and Roos, §2.3, explain this distinction.

There is a precise connection to maximum a posteriori estimation: for discrete candidate models, if P(M)P(M) is proportional to 2−L(M)2^{-L(M)} and the conditional ideal length is −log⁡2P(D∣M)-\log_2P(D\mid M), minimising their sum gives the same choice as maximising the posterior. This discrete correspondence does not identify all MDL methods with Bayesian inference. The Bayesian information criterion is related asymptotically to some MDL constructions under regular parametric assumptions; they need not agree in finite samples.

For financial prediction, compression is a selection criterion, not proof of profitable future trades. Dependence, changing regimes and a misspecified probability model can undermine the inference; even MDL can select poorly under misspecification, as Grünwald and Roos, §6.3, demonstrate. Keep preprocessing, model selection and final evaluation within a declared information schedule. Time-Ordered Train, Validation and Test Design develops that schedule and label-availability checks; its preview is public and the full lesson requires membership.

Sources

Last updated
  • learning theory
  • model selection
  • information theory
  • compression
  • regularisation
Keep connecting the ideas
← Back to the glossaryBack to top ↑