Literature
Display
← All papers

A Tutorial Introduction to the Minimum Description Length Principle

Peter Grünwald

· Advances in Minimum Description Length: Theory and Applications, MIT Press (chapters 1–2) ↗

Learning theory16 min text · CondensedOriginal paper ↗
Contents

At a glance

MDL treats learning as finding descriptions that compress observed data. This tutorial develops the connection from an informal two-part code to universal coding, normalized maximum likelihood and predictive model selection. It explains why model complexity is more than a parameter count, how Bayesian and sequential methods relate, and where approximation or model misspecification can make MDL perform poorly.

Chapter 1 Introducing the MDL Principle

1.1 Introduction and Overview

Model selection must balance fit against the ability to fit accidental noise. MDL measures that balance in bits: a useful regularity shortens the description of data after accounting for the model. The tutorial distinguishes this inference strategy from a belief that a simple model must be true.

1.2 The Fundamental Idea: Learning as Data Compression

Repeated patterns, biased frequencies and other regularities can all reduce description length, although they require different coding languages.

Regularity …

A repeated four-bit pattern is highly regular; a fair-coin string is usually incompressible; a string with four times as many zeros as ones has a weaker statistical regularity. These examples separate deterministic structure from distributional structure.

Equations 1.1–1.3
𝟶𝟶𝟶𝟷𝟶𝟶𝟶𝟷𝟶𝟶𝟶𝟷𝟶𝟶𝟶𝟷𝟶𝟶𝟶𝟷…​ 0001000100010001000100010001\displaystyle{\tt 00010001000100010001}\ \ \ldots\ \ {\tt 0001000100010001000100010001\ } (1.1)
𝟶𝟷𝟷𝟷𝟶𝟷𝟶𝟶𝟷𝟷𝟶𝟷𝟶𝟶𝟷𝟶𝟶𝟷𝟷𝟶…​ 1010111010111011000101100010\displaystyle{\tt 01110100110100100110}\ \ \ldots\ \ {\tt 1010111010111011000101100010\ } (1.2)
𝟶𝟶𝟶𝟷𝟷𝟶𝟶𝟶𝟶𝟶𝟷𝟶𝟷𝟶𝟷𝟶𝟶𝟶𝟶𝟶…​ 0010001000010000001000110000\displaystyle{\tt 00011000001010100000}\ \ \ldots\ \ {\tt 0010001000010000001000110000\ } (1.3)

…and Compression

A loop compresses repetition; a literal print command usually cannot compress random data. A biased-coin code compresses skewed frequencies. Likewise, a short program can generate digits of π, a physical law can encode a table through coefficients and residuals, and grammar can compress language. Every saving depends on an agreed description method.

Equations
𝚏𝚘𝚛​𝚒= 1​𝚝𝚘​ 2500;𝚙𝚛𝚒𝚗𝚝​`​𝟶𝟶𝟶𝟷​`;𝚗𝚎𝚡𝚝;𝚑𝚊𝚕𝚝{\tt for\ i\ =\ 1\ to\ 2500;\ print\ `0001`;\ next;\ halt}
𝚙𝚛𝚒𝚗𝚝​`​𝟶𝟷𝟷𝟷𝟶𝟷𝟶𝟶𝟷𝟷𝟶𝟷𝟶𝟶𝟶𝟶𝟷𝟶𝟷𝟶𝟷𝟶𝟷𝟶​…​…​..1010111010111011000101100010​`;𝚑𝚊𝚕𝚝{\tt print\ `011101001101000010101010........1010111010111011000101100010`;\ halt}

1.2.1 Kolmogorov Complexity and Ideal MDL

Kolmogorov complexity is the shortest program that prints the data and halts. Changing a universal language changes this length by at most a language-dependent constant, but that constant matters for small samples. The shortest-program problem is uncomputable, so ideal MDL is a conceptual foundation rather than a practical algorithm.

1.2.2 Practical MDL

Practical MDL restricts the description language so relevant code lengths can be computed. This sacrifices some detectable regularities but permits inference. Domain knowledge can guide the model class; no computable procedure can recover every possible regularity.

1.3 MDL and Model Selection

A high-degree polynomial can interpolate every training point while predicting poorly. Two-part MDL encodes both a hypothesis and the data conditional on it, selecting the smallest combined length. A point hypothesis is one distribution or function; a model is a family, such as all polynomials of one degree. The distinction matters when selecting parameters versus model structure.

MDL: The Basic Idea The goal of statistical inference may be cast as trying to find regularity in the data. ‘Regularity’ may be identified with ‘ability to compress’. MDL combines these two insights by viewing learning as data compression: it tells us that, for a given set of hypotheses ℋ{\cal H} and data set DD, we should try to find the hypothesis or combination of hypotheses in ℋ{\cal H} that compresses DD most.
Original Figure 1.1: Figure 1.1: A simple, a complex and a
trade-off (3rd degree) polynomial.

Figure 1.1: A simple, a complex and a trade-off (3rd degree) polynomial.
Models vs. Hypotheses We use the phrase point hypothesis to refer to a single probability distribution or function. An example is the polynomial 5​x2+4​x+35x^{2}+4x+3. A point hypothesis is also known as a ‘simple hypothesis’ in the statistical literature. We use the word model to refer to a family (set) of probability distributions or functions with the same functional form. An example is the set of all second-degree polynomials. A model is also known as a ‘composite hypothesis’ in the statistical literature. We use hypothesis as a generic term, referring to both point hypotheses and models.

  Crude4, Two-part Version of MDL Principle (Informally Stated) Let ℋ(1),ℋ(2),…{\cal H}^{(1)},{\cal H}^{(2)},\ldots be a list of candidate models (e.g., ℋ(k){\cal H}^{(k)} is the set of kk-th degree polynomials), each containing a set of point hypotheses (e.g., individual polynomials). The best point hypothesis H∈ℋ(1)∪ℋ(2)∪…H\in{\cal H}^{(1)}\cup{\cal H}^{(2)}\cup\ldots to explain the data DD is the one which minimizes the sum L⁡(H)+L⁡(D|H)L(H)+L(D|H), where • L⁡(H)L(H) is the length, in bits, of the description of the hypothesis; and • L⁡(D|H)L(D|H) is the length, in bits, of the description of the data when encoded with the help of the hypothesis. The best model to explain DD is the smallest model containing the selected HH.


1.4 Crude and Refined MDL

The two-part objective becomes meaningful only after both coding rules are specified. Data codes have a principled probability interpretation; arbitrary hypothesis codes can distort inference.

Definition of L ⁡ ( D | H )

For a probabilistic hypothesis, encode data with length equal to negative log likelihood. A regression function can be turned into such a distribution by specifying a noise model. The code then rewards high-probability observations.

Definition of L ⁡ ( H ) : A Problem for Crude MDL

An arbitrary parameter code can make any chosen hypothesis cheap or expensive. Early minimax and discretization arguments constrain this freedom but can be cumbersome. Refined MDL replaces explicit parameter transmission with a universal code for the entire family.

Refined MDL

A universal code compresses nearly as well as the best family member chosen after observing the data. Refined MDL uses a minimax criterion to choose among such codes. The resulting one-part length is called stochastic complexity.

Parametric Complexity

Parametric complexity measures a family’s ability to fit possible datasets, including its geometry. Stochastic complexity decomposes into negative maximized log likelihood plus this complexity. Models with the same parameter count can therefore receive different penalties: the psychophysics example compares the greater flexibility of Stevens’ model with Fechner’s. The simplest NML formulation requires finite complexity and a restricted comparison setting.

Equation
stochastic complexity of D given ℋ=L⁡(D∣H^)+COMP​(ℋ).\text{stochastic complexity of $D$ given ${\cal H}$}=L(D\mid\hat{H})+\text{\bf COMP}({\cal H}).

1.5 The MDL Philosophy

Rissanen’s philosophy treats models as tools for discovering regularity, without requiring that a candidate distribution actually generated the observations.

1. Regularity as Compression

Learning separates compressible structure from residual information. Repetition is mostly structure; a fair-coin string mostly residual noise; biased frequencies supply structure while the precise order remains residual.

2. Models as Languages

A model is a language for expressing regularities. Noise is what remains expensive to encode relative to that language, rather than an intrinsic label on the data. Another model may expose structure previously treated as noise.

3. We Have Only the Data

Useful models can be known approximations: naive Bayes, speech models and linear economic models need not be literally true. MDL seeks an interpretation based on observed data and available models. This philosophical motivation does not itself guarantee robust behavior under misspecification.

4. MDL and Consistency

Consistency remains a sanity check: if a candidate distribution really does generate the data, the method should approach it with enough observations. Rates of convergence matter as well. MDL derives procedures from compression, then examines these statistical properties; exceptions and assumptions still require attention.

1.6 MDL and Occam’s Razor

Occam’s razor is an inference strategy: with limited evidence, a less flexible model can predict more reliably. The preferred complexity may grow as data accumulate.

‘1. Occam’s Razor (and MDL) is arbitrary’

Refined MDL constrains the code through minimax properties and can be invariant to parameterization. The claim that any encoding can arbitrarily determine its answer overlooks these restrictions; broader settings still require some modeling choices.

‘2. Occam’s Razor is false’

A complex underlying process can be best approximated by a simple model when samples are small. As evidence grows, richer polynomial families may improve the approximation. Minimizing training error over an unlimited family can overfit indefinitely. This is a justification for a fit–complexity trade-off, not a statement that nature is simple.

The Inherent Difference between Under- and Overfitting If we choose an overly simple model for our data, then the best-fitting point hypothesis within the model is likely to be almost the best predictor, within the simple model, of future data coming from the same source. If we overfit (choose a very complex model) and there is noise in our data, then, even if the complex model contains the ‘true’ point hypothesis, the best-fitting point hypothesis within the model is likely to lead to very bad predictions of future data coming from the same source.

1.7 History

Rissanen developed MDL beginning in 1978, drawing on algorithmic complexity and information-theoretic model selection. Two-part codes evolved into predictive and mixture codes, then the connection to Shtarkov’s NML clarified parametric complexity. Wallace’s earlier MML shares coding ideas but uses a different Bayesian interpretation and optimization criterion.

1.8 Summary and Outlook

Practical MDL replaces an uncomputable shortest-program ideal with restricted, computable codes. Universal coding refines the crude model-plus-residual picture. The next chapter formalizes probability–length correspondence and the cost of selecting a model after seeing data.

Notes

“Crude MDL” is the tutorial’s pedagogical label, not a standard name for all early MDL work. Early theoretical papers already constrained coding schemes; some applications instead used ad hoc codes. The author also distinguishes Rissanen’s strong philosophical position from milder alternatives.

Chapter 2 Minimum Description Length Tutorial

2.1 Plan of the Tutorial

The technical route is prefix coding, statistical models, two-part MDL, universal codes, and four interpretations of refined MDL. Extensions address infinitely many models, undefined normalizers, regression and parameter estimation before discussing connections and failures.

Reader’s Guide Throughout the text, paragraph headings reflect the most important concepts. Boxes summarize the most important findings. Together, paragraph headings and boxes provide an overview of MDL theory. It is possible to read this chapter without having read the non-technical overview of Chapter 1. However, we strongly recommend reading at least Sections 1.3 and Section 1.4 before embarking on the present chapter.

2.2 Information Theory I: Probabilities and Codelengths

Two facts connect probability and coding: valid prefix lengths correspond to distributions through negative logarithms, and the code matching a generating distribution minimizes expected length.

Preliminaries and Notational Conventions - Codes

A code maps each datum to a distinct binary string so decoding is lossless. MDL compares code lengths, rather than needing to implement the actual bit strings. Logarithms are base two unless stated otherwise.

Preliminaries and Notational Conventions - Probability

A defective distribution assigns total mass below one. A probabilistic source has compatible distributions over successively longer sequences; an i.i.d. source factorizes into identical single-observation distributions.

2.2.1 Prefix Codes

No codeword in a prefix code begins another codeword, allowing concatenated messages to be decoded without separators. Every uniquely decodable code has an equivalent prefix code with the same lengths, so restricting attention to prefix lengths loses no relevant efficiency.

2.2.2 The Kraft Inequality - Codelengths and Probabilities, Part I

A fixed code can shorten only a small fraction of all strings: compressing a fair-coin sequence by many bits is exponentially unlikely. Designing a code after seeing the exact data is uninformative unless the code choice is itself charged.

Equations 2.1–2.3
𝟶𝟶𝟶𝟷𝟶𝟶𝟶𝟷𝟶𝟶𝟶𝟷𝟶𝟶𝟶𝟷𝟶𝟶𝟶𝟷…​ 0001000100010001000100010001\displaystyle{\tt 00010001000100010001}\ \ \ldots\ \ {\tt 0001000100010001000100010001\ } (2.1)
𝟶𝟷𝟷𝟷𝟶𝟷𝟶𝟶𝟷𝟷𝟶𝟷𝟶𝟶𝟷𝟶𝟶𝟷𝟷𝟶…​ 1010111010111011000101100010\displaystyle{\tt 01110100110100100110}\ \ \ldots\ \ {\tt 1010111010111011000101100010\ } (2.2)
𝟶𝟶𝟶𝟷𝟷𝟶𝟶𝟶𝟶𝟶𝟷𝟶𝟷𝟶𝟷𝟶𝟶𝟶𝟶𝟶…​ 0010001000010000001000110000\displaystyle{\tt 00011000001010100000}\ \ \ldots\ \ {\tt 0010001000010000001000110000\ } (2.3)

A Most Important Observation

Kraft’s inequality links code lengths to probability masses. A uniform distribution gives fixed-length codes; nonuniform probabilities give shorter words to likelier outcomes. Ignoring a negligible rounding term permits ideal real-valued lengths. Prefix coding of arbitrary positive integers requires overhead beyond simply writing their binary value; the tutorial uses a simple approximately 2 log n code.


  Probability Mass Functions correspond to Codelength Functions Let 𝒵{\mathcal{Z}} be a finite or countable set and let PP be a probability distribution on 𝒵{\mathcal{Z}}. Then there exists a prefix code CC for 𝒵{\mathcal{Z}} such that for all z∈𝒵z\in{\mathcal{Z}}, LC​(z)=⌈−log⁡P⁡(z)⌉L_{C}(z)=\lceil-\log P(z)\rceil. CC is called the code corresponding to PP. Similarly, let C′C^{\prime} be a prefix code for 𝒵{\mathcal{Z}}. Then there exists a (possibly defective) probability distribution P′P^{\prime} such that for all z∈𝒵z\in{\mathcal{Z}}, −log⁡P′​(z)=LC′​(z)-\log P^{\prime}(z)=L_{C^{\prime}}(z). P′P^{\prime} is called the probability distribution corresponding to C′C^{\prime}. Moreover C′C^{\prime} is a complete prefix code iff PP is proper (∑zP⁡(z)=1\sum_{z}P(z)=1). Thus, large probability according to PP means small code length according to the code corresponding to PP and vice versa. We are typically concerned with cases where 𝒵{\mathcal{Z}} represents sequences of nn outcomes; that is, 𝒵=𝒳n{\mathcal{Z}}={\mathcal{X}}^{n} (n≥1)(n\geq 1) where 𝒳{\mathcal{X}} is the sample space for one observation.


Figure 2.1: The most important observation of this tutorial.

  New Definition of Code Length Function In MDL we are NEVER concerned with actual encodings; we are only concerned with code length functions. The set of all codelength functions for finite or countable sample space 𝒵{\mathcal{Z}} is defined as:

Equationℒ𝒵={L:𝒵→[0,∞]∣∑z∈𝒳2−L⁡(z)≤1},\mathcal{L}_{{\mathcal{Z}}}=\bigl\{L:{\mathcal{Z}}\rightarrow[0,\infty]\mid\sum_{z\in{\mathcal{X}}}2^{-L(z)}\leq 1\bigr\},
(2.4) or equivalently, ℒ𝒵\mathcal{L}_{{\mathcal{Z}}} is the set of those functions LL on 𝒵{\mathcal{Z}} such that there exists a function QQ with ∑zQ⁡(z)≤1\sum_{z}Q(z)\leq 1 and for all zz, L⁡(z)=−log⁡Q⁡(z)L(z)=-\log Q(z). (Q⁡(z)=0Q(z)=0 corresponds to L⁡(z)=∞L(z)=\infty). Again, 𝒵{\mathcal{Z}} usually represents a sample of nn outcomes: 𝒵=𝒳n{\mathcal{Z}}={\mathcal{X}}^{n} (n≥1)(n\geq 1) where 𝒳{\mathcal{X}} is the sample space for one observation.


Figure 2.2: Code lengths are probabilities.
Equations 2.5
∑x∈1,2,…P⁡(x)=∑x∈1,2,…2−2​log⁡x−1=12​∑x∈1,2,…x−2<12+12​∑x=2,3,…1x⁡(x−1)=1,\sum_{x\in 1,2,\ldots}P(x)=\sum_{x\in 1,2,\ldots}2^{-2\log x-1}=\frac{1}{2}\sum_{x\in 1,2,\ldots}x^{-2}<\frac{1}{2}+\frac{1}{2}\sum_{x=2,3,\ldots}\frac{1}{x(x-1)}=1,
−log⁡P0​(xn)=log⁡(15)n[1]​(45)n[0]=n⁡[−(15+ϵ)​log​15−(45−ϵ)​log​45]=n⁡[log⁡5−85+2​ϵ],-\log P_{0}(x^{n})=\log\biggl(\frac{1}{5}\biggr)^{n_{[1]}}\biggl(\frac{4}{5}\biggr)^{n_{[0]}}=n\bigl[-\bigl(\frac{1}{5}+\epsilon\bigr)\log\frac{1}{5}-\bigl(\frac{4}{5}-\epsilon\bigr)\log\frac{4}{5}\bigr]=\\ n[\log 5-\frac{8}{5}+2\epsilon], (2.5)

Continuous Sample Spaces

For continuous observations, densities correspond to code lengths at an agreed precision. Sums become integrals; comparisons must use a common precision so irrelevant discretization constants cancel.

2.2.3 The Information Inequality - Codelengths & Probabilities, II

If data follow P, coding with Q costs cross-entropy, minimized at Q=P. The information inequality formalizes the excess cost. With suitable independence or ergodicity assumptions, long-run average code lengths approach their expectations. A distribution can nevertheless be used as a code without claiming it is the true generator.


  The PP that corresponds to LL minimizes expected codelength Let PP be a distribution on (finite, countable or continuous-valued) 𝒵{\mathcal{Z}} and let LL be defined by

EquationL:=arg⁡minL∈ℒ𝒵​EP​[L⁡(Z)].L{:=}\underset{L\in\mathcal{L}_{{\mathcal{Z}}}}{\ \arg\min\ }E_{P}[L(Z)].
(2.6) Then LL exists, is unique, and is identical to the codelength function corresponding to PP, with lengths L⁡(z)=−log⁡P⁡(z)L(z)=-\log P(z).


Figure 2.3: The second most important observation of this tutorial.
Equation
EP​[−log⁡Q⁡(X)]>EP​[−log⁡P⁡(X)].E_{P}[-\log Q(X)]>E_{P}[-\log P(X)].

Summary and Outlook

Probability supplies both valid length assignments and an expected-efficiency criterion. The next step is to specify the candidate statistical models.

2.3 Statistical Preliminaries and Example Models

Markov chains provide a running example because model order controls flexibility while parameter estimates have a simple frequency interpretation.

Statistical Preliminaries

A parametric family is smoothly indexed by finitely many parameters. Maximum likelihood chooses the member assigning greatest probability to the observations. In binary Markov models, transition probabilities are empirical conditional frequencies; the number of parameters grows exponentially with order. Searching all orders using likelihood alone can memorize the sequence.

Equations 2.7–2.8
P⁡(Xn=1∣Xn−1=xn−1,…,Xn−k=xn−k)=P⁡(Xn=1∣Xn−1=xn−1,…,Xn−k=xn−k,…,X1=x1).P(X_{n}=1\mid X_{n-1}=x_{n-1},\ldots,X_{n-k}=x_{n-k})=\\ P(X_{n}=1\mid X_{n-1}=x_{n-1},\ldots,X_{n-k}=x_{n-k},\ldots,X_{1}=x_{1}). (2.7)
P⁡(xn∣θ)=∏i=1nP⁡(xi∣θ)=θn[1]​(1−θ)n[0],P(x^{n}\mid\theta)=\prod_{i=1}^{n}P(x_{i}\mid\theta)=\theta^{n_{[1]}}(1-\theta)^{n_{[0]}},
log⁡P⁡(xn∣θ)=n[1]​log⁡θ+n[0]​log⁡(1−θ).\log P(x^{n}\mid\theta)=n_{[1]}\log\theta+n_{[0]}\log(1-\theta). (2.8)
log⁡P⁡(xn∣θ)=n[1|1]​log​θ[1|1]+n[0|1]​log⁡(1−θ[1|1])+n[1|0]​log​θ[1|0]+n[0|0]​log⁡(1−θ[1|0]),\log P(x^{n}\mid\theta)=n_{[1|1]}\log\theta_{[1|1]}+n_{[0|1]}\log(1-\theta_{[1|1]})+n_{[1|0]}\log\theta_{[1|0]}+n_{[0|0]}\log(1-\theta_{[1|0]}),

2.4 Crude MDL

Two-part MDL selects a hypothesis by adding its description length to negative log likelihood; model selection can then choose the smallest family containing that hypothesis.

Crude9, Two-part Version of MDL Principle Let ℋ(1),ℋ(2),…{\cal H}^{(1)},{\cal H}^{(2)},\ldots be a set of candidate models. The best point hypothesis H∈ℋ(1)∪ℋ(2)∪…H\in{\cal H}^{(1)}\cup{\cal H}^{(2)}\cup\ldots to explain data DD is the one which minimizes the sum L⁡(H)+L⁡(D|H)L(H)+L(D|H), where • L⁡(H)L(H) is the length, in bits, of the description of the hypothesis; and • L⁡(D|H)L(D|H) is the length, in bits, of the description of the data when encoded with the help of the hypothesis. The best model to explain DD is the smallest model containing the selected HH.

2.4.1 Description Length of Data given Hypothesis

The conditional data length is negative log likelihood. This matches the optimal expected code when the hypothesis is correct and yields consistency in a finite family. Arbitrarily reassigning data codes to hypotheses can destroy even this elementary guarantee.

2.4.2 Description Length of Hypothesis

A hypothesis code must be fixed by a valid protocol. Uncharged dependence on sample size can reintroduce pure maximum-likelihood overfitting by making complex memorizing models artificially cheap.

Consistency of Two-part MDL

Fixed two-part codes give broad asymptotic consistency results, but finite-sample performance can remain poor. Encoding Markov order and empirical transition counts gives a concrete, initially crude parameter code.

Equations 2.9
L⁡(P)=L⁡(k,Θ(k))=2​log⁡k+1+k​log⁡(n+1),L(P)=L(k,\Theta^{(k)})=2\log k+1+k\log(n+1),
L⁡(k,θ(k))+L⁡(D∣k,θ(k))=2​log⁡k+1+k​log⁡(n+1)−log⁡P⁡(D∣k,θ(k)),L(k,\theta^{(k)})+L(D\mid k,\theta^{(k)})=2\log k+1+k\log(n+1)-\log P(D\mid k,\theta^{(k)}), (2.9)

Why (not) this code?

Encoding every possible empirical parameter value wastes precision. A coarser grid can reduce total length even if likelihood worsens slightly. The natural statistical resolution is often of order 1/√n rather than 1/n, motivating a principled regret criterion.

Equation 2.10
L⁡(k,θ(k))+L⁡(D∣k,θ(k))=−log⁡P⁡(D∣k,θ^(k))+k2​log​n+ck,L(k,\theta^{(k)})+L(D\mid k,\theta^{(k)})=-\log P(D\mid k,\hat{\theta}^{(k)})+\frac{k}{2}\log n+c_{k}, (2.10)

The Good News and the Bad News

Negative log likelihood is well motivated, but an arbitrary model code is not enough for good small-sample inference. Universal coding provides a broader framework in which coding choices can be compared and improved.

2.5 Information Theory II: Universal Codes and Models

A universal code competes with each code in a specified family. Two-part, Bayesian mixture and NML codes are different constructions with different guarantees.

Coding as Communication

Sender and receiver must agree on the decoding protocol before the message arrives. Choosing a convenient code after inspecting the data requires communicating that choice or integrating it into a shared universal code.

Universal Coding

Taking the shortest candidate length separately for every possible dataset generally fails Kraft’s inequality. A universal code must pay overhead to approximate that impossible hindsight oracle. The objective is small regret relative to the best candidate for each dataset.

Equations 2.11
L8​(xn)=−log⁡P⁡(xn|0.8)=−n[0]​log⁡0.2−n[1]​log⁡0.8L9​(xn)=−log⁡P⁡(xn|0.9)=−n[0]​log⁡0.1−n[1]​log⁡0.9.\begin{array}[]{l}L_{8}(x^{n})=-\log P(x^{n}|0.8)=-n_{[0]}\log 0.2-n_{[1]}\log 0.8\\ L_{9}(x^{n})=-\log P(x^{n}|0.9)=-n_{[0]}\log 0.1-n_{[1]}\log 0.9.\end{array}
∑xnP¯​(xn)≥∑xnP⁡(xn∣θ^​(xn))=∑xnmaxθ⁡P⁡(xn∣θ)>1,\sum_{x^{n}}\bar{P}(x^{n})\geq\sum_{x^{n}}P(x^{n}\mid\hat{\theta}(x^{n}))=\sum_{x^{n}}\max_{\theta}P(x^{n}\mid\theta)>1, (2.11)

2.5.1 Two-part Codes as simple Universal Codes

For a finite family, transmitting its best member’s index costs log of the family size, then the chosen code transmits the data. Countably infinite families need a nonuniform index code. Each fixed member can still be approached asymptotically, but there is no uniform constant overhead for all members.

Equations 2.12
L¯2-p​(xn)=minL∈ℒ⁡L⁡(xn)+log⁡9.\bar{L}_{\text{\rm 2-p}}(x^{n})=\min_{L\in\mathcal{L}}L(x^{n})+\log 9.
L¯2-p​(xn)=minL∈ℒ⁡L⁡(xn)+log⁡M.\bar{L}_{\text{\rm 2-p}}(x^{n})=\min_{L\in\mathcal{L}}L(x^{n})+\log M. (2.12)
L¯2-p​(xn)≤infL∈{L1,…,Lk}L⁡(xn)+2​log⁡k+1.\bar{L}_{\text{\rm 2-p}}(x^{n})\leq\inf_{L\in\{L_{1},\ldots,L_{k}\}}L(x^{n})+2\log k+1.

2.5.2 From Universal Codes to Universal Models

A universal model is a single coding distribution representing a family; it need not belong to that family. A Bayesian mixture averages candidate distributions with fixed weights. For a discrete candidate with positive weight, mixture regret is bounded by the negative logarithm of that weight.

Equations 2.13–2.14
P¯Bayes​(xn):=∑θ∈ΘP⁡(xn∣θ)​W​(θ).\bar{P}_{\text{\rm Bayes}}(x^{n}):=\sum_{\theta\in\Theta}P(x^{n}\mid\theta)W(\theta). (2.13)
−logP¯Bayes(xn):=−log∑θ∈ΘP(xn∣θ)W(θ)≤−logP(xn∣θ0)+cθ0-\log\bar{P}_{\text{\rm Bayes}}(x^{n}):=-\log\sum_{\theta\in\Theta}P(x^{n}\mid\theta)W(\theta)\leq-\log P(x^{n}\mid\theta_{0})+c_{\theta_{0}} (2.14)

Bayes is Better than Two-part

For matching prior weights, a mixture code never uses more bits than selecting one weighted component and transmitting its index. This does not settle which prior or criterion is best; minimax regret supplies one answer.

Equations 2.15
L¯2-p​(xn)=minθ∈Θ−log⁡P⁡(xn|θ)−log⁡W⁡(θ)\bar{L}_{\text{\rm 2-p}}(x^{n})=\min_{\theta\in\Theta}-\log P(x^{n}|\theta)-\log W(\theta) (2.15)
−logP¯Bayes(xn)=−log∑θ∈ΘP(xn∣θ)W(θ)≤minθ∈Θ−logP(xn|θ)−logW(θ).-\log\bar{P}_{\text{\rm Bayes}}(x^{n})=-\log\sum_{\theta\in\Theta}P(x^{n}\mid\theta)W(\theta)\leq\min_{\theta\in\Theta}-\log P(x^{n}|\theta)-\log W(\theta).

2.5.3 NML as an Optimal Universal Model

Regret is extra code length relative to the best-fitting family member for the realized data. NML normalizes maximized likelihood across all possible datasets. If the normalizing sum/integral is finite, Shtarkov’s result makes it the unique distribution minimizing worst-case regret.

Equations 2.16–2.19
−log⁡P¯​(xn)−minP∈ℳ⁡{−log⁡P⁡(xn)}.-\log\bar{P}(x^{n})-\min_{P\in{\cal M}}\{-\log P(x^{n})\}. (2.16)
−log⁡P¯​(xn)−{−log⁡P⁡(xn∣θ^​(xn))}.-\log\bar{P}(x^{n})-\{-\log P(x^{n}\mid\hat{\theta}(x^{n}))\}.
ℛmax​(P¯):=maxxn∈𝒳n⁡{−log⁡P¯​(xn)−{−log⁡P⁡(xn∣θ^​(xn))}}.\mathcal{R}_{\max}(\bar{P}){:=}\max_{x^{n}\in{\mathcal{X}}^{n}}\bigl\{-\log\bar{P}(x^{n})-\{-\log P(x^{n}\mid\hat{\theta}(x^{n}))\}\bigr\}.
minP¯⁡ℛmax​(P¯)=minP¯⁡maxxn∈𝒳n​{−log⁡P¯​(xn)−{−log⁡P⁡(xn∣θ^​(xn))}}\min_{\bar{P}}\ \mathcal{R}_{\max}(\bar{P})=\min_{\bar{P}}\ \max_{x^{n}\in{\mathcal{X}}^{n}}\ \bigl\{-\log\bar{P}(x^{n})-\{-\log P(x^{n}\mid\hat{\theta}(x^{n}))\}\bigr\} (2.17)
COMPn(ℳ):=log∑xn∈𝒳nP(xn∣θ^(xn)).\text{\bf COMP}_{n}({\cal M}){:=}\log{\sum_{x^{n}\in{\mathcal{X}}^{n}}P(x^{n}\mid\hat{\theta}(x^{n}))}. (2.18)
P¯nml​(xn):=P⁡(xn∣θ^​(xn))∑yn∈𝒳nP⁡(yn∣θ^​(yn)).\bar{P}_{\text{\rm nml}}(x^{n}){:=}\frac{P(x^{n}\mid\hat{\theta}(x^{n}))}{\sum_{y^{n}\in{\mathcal{X}}^{n}}P(y^{n}\mid\hat{\theta}(y^{n}))}. (2.19)

Proof

NML has the same regret for every dataset. Any different normalized distribution assigns less probability somewhere and therefore has larger worst-case regret. If the normalizer diverges, this construction is undefined and no finite constant-regret distribution exists.

Equations 2.20–2.21
−log⁡P¯​(xn)−{−log⁡P⁡(xn∣θ^​(xn))}=ℛmax​(P¯)=COMPn​(ℳ),-\log\bar{P}(x^{n})-\{-\log P(x^{n}\mid\hat{\theta}(x^{n}))\}=\mathcal{R}_{\max}(\bar{P})=\text{\bf COMP}_{n}({\cal M}), (2.20)
ℛmax​(P)≥−log⁡P⁡(zn)+log⁡P⁡(zn∣θ^​(zn))>−log⁡P¯nml​(zn)+log⁡P⁡(zn∣θ^​(zn))=ℛmax​(P¯nml).\mathcal{R}_{\max}(P)\geq-\log P(z^{n})+\log P(z^{n}\mid\hat{\theta}(z^{n}))>\\ -\log\bar{P}_{\text{\rm nml}}(z^{n})+\log P(z^{n}\mid\hat{\theta}(z^{n}))=\mathcal{R}_{\max}(\bar{P}_{\text{\rm nml}}).{\@index{\@indexphrase{Shtarkov, Y.}}}{\@index{\@indexphrase{normalized maximum likelihood}}}{\@index{\@indexphrase{minimax regret}}} (2.21)

  Summary: Universal Codes and Models Let ℳ{\cal M} be a family of probabilistic sources. A universal model in an individual sequence sense16 relative to ℳ{\cal M}, in this text simply called a ‘universal model for ℳ{\cal M}’, is a sequence of distributions P¯(1),P¯(2),…\bar{P}^{(1)},\bar{P}^{(2)},\ldots on 𝒳1,𝒳2,…{\cal X}^{1},{\cal X}^{2},\ldots respectively, such that for all P∈ℳP\in{\cal M}, for all ϵ>0\epsilon>0,

Equationmaxxn∈𝒳n⁡1n​{−log⁡P¯(n)​(xn)−[−log⁡P⁡(xn)]}≤ϵ​ as ​n→∞.\max_{x^{n}\in{\cal X}^{n}}\frac{1}{n}\biggl\{-\log\bar{P}^{(n)}(x^{n})-[-\log P(x^{n})]\biggr\}\leq\epsilon\text{\ as \ }n\rightarrow\infty.
Multiplying both sides with nn we see that P¯\bar{P} is universal if for every P∈ℳP\in{\cal M}, the codelength difference −log⁡P¯​(xn)+log⁡P⁡(xn)-\log\bar{P}(x^{n})+\log P(x^{n}) increases sublinearly in nn. If ℳ{\cal M} is finite, then the two-part, Bayes and NML distributions are universal in a very strong sense: rather than just increasing sublinearly, the codelength difference is bounded by a constant. We already discussed two-part, Bayesian and minimax optimal (NML) universal models, but there several other types. We mention prequential universal models (Section 2.6.4), the Kolmogorov universal model, conditionalized two-part codes [2001] and Cesaro-average codes [1998].


2.6 Simple Refined MDL and its Four Interpretations

For finitely many models with finite complexity, choose the smallest NML code length: negative maximized likelihood plus the log normalizer. This stochastic complexity balances fit with a model’s ability to fit other possible data, rather than using training fit alone.

Equations 2.22
−log⁡P¯nml​(D∣ℳ(j))=−log⁡P⁡(D∣θ^(j)​(D))+COMPn​(ℳ(j))-\log\bar{P}_{\text{\rm nml}}(D\mid{\cal M}^{(j)})=-\log P(D\mid\hat{\theta}^{(j)}(D))+\text{\bf COMP}_{n}({\cal M}^{(j)}) (2.22)
|−log⁡P¯nml​(D∣ℳ(1))−[−log⁡P¯nml​(D∣ℳ(2))]|.\biggl|-\log\bar{P}_{\text{\rm nml}}(D\mid{\cal M}^{(1)})-[-\log\bar{P}_{\text{\rm nml}}(D\mid{\cal M}^{(2)})]\biggr|.

2.6.1 Compression Interpretation

NML shortens the description when the family fits better while imposing equal regret across datasets. This makes its coding criterion intrinsic to the model and sample space once those are specified.

Compression and Separating Structure from Noise

The fit term can be read as residual noise and the complexity term as the cost of distinguishable structure. This is relative to the chosen family, and the tutorial presents the interpretation more informally than the underlying minimax statement.

2.6.2 Counting Interpretation

Model complexity counts effectively distinguishable distributions. Nearly identical members do not contribute as much as clearly different ones. For a finite i.i.d. family, increasing data eventually distinguishes all members and complexity approaches log family size.

Equation 2.23
∑xn∈𝒳nP(xn|θ^(xn))=∑j=1..M∑xn:θ^​(xn)=θjP(xn|θj)=∑j=1..M(1−∑xn:θ^​(xn)≠θjP(xn|θj))=M−∑jP(θ^(xn)≠θj|θj).\sum_{x^{n}\in{\mathcal{X}}^{n}}P(x^{n}|\hat{\theta}(x^{n}))=\sum_{j=1..M}\sum_{x^{n}:\hat{\theta}(x^{n})=\theta_{j}}P(x^{n}|\theta_{j})=\\ \sum_{j=1..M}\bigl(1-\sum_{x^{n}:\hat{\theta}(x^{n})\neq\theta_{j}}P(x^{n}|\theta_{j})\bigr)=M-\sum_{j}P(\hat{\theta}(x^{n})\neq\theta_{j}|\theta_{j}). (2.23)

Asymptotic Expansion of P ¯ nml and COMP n

For regular k-dimensional families, complexity has a leading (k/2) log n term plus a Fisher-information volume term and a vanishing remainder. The geometric term matters for equal-dimensional or small-sample comparisons. The expansion requires regularity, interior estimates and suitable integrability; it can fail or converge slowly when dimension approaches sample size or the model is irregular.

Equations 2.24
COMPn(ℳ)=k2logn2​π+log∫θ∈Θ|I⁡(θ)|dθ+o(1).\text{\bf COMP}_{n}({\cal M})=\frac{k}{2}\log\frac{n}{2\pi}+\log\int_{\theta\in\Theta}\sqrt{|I(\theta)|}d\theta+o(1). (2.24)
Ii​j​(θ∗):=Eθ∗​{−∂2∂θi​∂θj​log⁡P⁡(X|θ)}θ=θ∗.I_{ij}(\theta^{*}){:=}\text{\rm E}_{\theta^{*}}\biggl\{-\frac{\partial^{2}}{\partial\theta_{i}\partial\theta_{j}}\log P(X|\theta)\biggr\}_{\theta=\theta^{*}}.
Ii​j​(θ∗):=limn→∞1n​Eθ∗​{−∂2∂θi​∂θj​log⁡P⁡(Xn|θ)}θ=θ∗.I_{ij}(\theta^{*}){:=}\lim_{n\rightarrow\infty}\frac{1}{n}\text{\rm E}_{\theta^{*}}\biggl\{-\frac{\partial^{2}}{\partial\theta_{i}\partial\theta_{j}}\log P(X^{n}|\theta)\biggr\}_{\theta=\theta^{*}}.
COMPn​(ℬ(0))=12​log​n+12​log​π2−3+o⁡(1)=12​log​n−2.674251935+o⁡(1).\text{\bf COMP}_{n}({\mathcal{B}}^{(0)})=\frac{1}{2}\log n+\frac{1}{2}\log\frac{\pi}{2}-3+o(1)=\frac{1}{2}\log n-2.674251935+o(1).
The Asymptotic Expansion of COMPn\text{\bf COMP}_{n} Should Be Used with Care! (2.24) does not hold for all parametric models; and for some models for which it does hold, the o⁡(1)o(1) term may only converge to 00 only for quite large sample sizes. Foster and Stine [?, ?] show that the approximation (2.24) is, in general, only valid if kk is much smaller than nn.

Two-part codes and COMP n ​ ( ℳ )

Optimally quantized two-part codes approach NML regret up to a bounded dimension-dependent overhead under regularity assumptions. This does not justify arbitrary parameter discretizations used in some applications.

Equation
−logP¯2-p(xn∣ℳ)+logP(xn∣θ^(xn))=k2logn2​π+log∫θ∈Θ|I⁡(θ)|dθ+f(k)+o(1),-\log\bar{P}_{\text{2-p}}(x^{n}\mid{\cal M})+\log P(x^{n}\mid\hat{\theta}(x^{n}))=\frac{k}{2}\log\frac{n}{2\pi}+\log\int_{\theta\in\Theta}\sqrt{|I(\theta)|}d\theta+f(k)+o(1),

2.6.3 Bayesian Interpretation

Bayes-factor selection compares marginal likelihoods. Its relation to MDL depends on the prior, family regularity and whether the data-generating process belongs to the family.

Equation 2.25
P¯Bayes​(xn∣ℳ(j))=∫P⁡(xn∣θ)​w(j)​(θ)​𝑑θ.\bar{P}_{\text{\rm Bayes}}(x^{n}\mid{\cal M}^{(j)})=\int P(x^{n}\mid\theta)w^{(j)}(\theta)d\theta. (2.25)

ℳ is Exponential Family

For regular exponential families, a Laplace approximation relates mixture-code regret to Fisher information and the prior density. Jeffreys’ prior cancels the parameter-dependent part, giving asymptotically minimax regret and agreement with NML under the stated conditions.

Equations 2.26–2.27
−log⁡P¯Bayes​(xn)−[−log⁡P⁡(xn∣θ^​(xn))]=k2​log⁡n2​π−log⁡w⁡(θ^)+log⁡|I⁡(θ^)|+o⁡(1).-\log\bar{P}_{\text{\rm Bayes}}(x^{n})-[-\log P(x^{n}\mid\hat{\theta}(x^{n}))]=\frac{k}{2}\log\frac{n}{2\pi}-\log w(\hat{\theta})+\log\sqrt{{|I(\hat{\theta})|}}+o(1). (2.26)
wJeffreys​(θ)=|I⁡(θ)|∫θ∈Θ|I⁡(θ)|​𝑑θ,w_{\text{Jeffreys}}(\theta)=\frac{\sqrt{|I(\theta)|}}{\int_{\theta\in\Theta}\sqrt{|I(\theta)|}d\theta}, (2.27)

ℳ is not an Exponential Family

Outside exponential families, observed rather than expected Fisher information enters the approximation. With correct specification they converge under regularity conditions; under misspecification an order-one discrepancy can remain. Bayes and NML are therefore not universally identical.

Equation 2.28
−log⁡P¯Bayes​(xn∣ℳ)=−log⁡P⁡(xn∣θ^​(xn))+k2​log⁡n2​π−log⁡w⁡(θ^)+log⁡|I^​(xn)|+o⁡(1).-\log\bar{P}_{\text{\rm Bayes}}(x^{n}\mid{\cal M})=\\ -\log P(x^{n}\mid\hat{\theta}(x^{n}))+\frac{k}{2}\log\frac{n}{2\pi}-\log w(\hat{\theta})+\log\sqrt{\bigl|\hat{I}(x^{n})\bigr|}+o(1). (2.28)

2.6.4 Prequential Interpretation

Distributions as Prediction Strategies

The chain rule expresses a joint distribution as successive predictive distributions. Negative joint log likelihood equals cumulative one-step log loss. This gives every sequence code a predictive interpretation: predict the next outcome using only the preceding outcomes.

Equations 2.29–2.30
P⁡(xn)=∏i=1nP⁡(xi)P⁡(xi−1)=∏i=1nP⁡(xi∣xi−1),P(x^{n})=\prod_{i=1}^{n}\frac{P(x^{i})}{P(x^{i-1})}=\prod_{i=1}^{n}P(x_{i}\mid x^{i-1}), (2.29)
−logP(xn)=∑i=1n−logP(xi∣xi−1)-\log P(x^{n})=\sum_{i=1}^{n}-\log P(x_{i}\mid x^{i-1}) (2.30)

Log Loss for Universal Models

Predictive MDL evaluates a sequence of estimators on data they have not yet seen. Plug-in maximum likelihood can be near-optimal under conditions but can also assign zero probability disastrously: a first observed zero makes a later one impossible in naive Bernoulli estimation. Laplace or Jeffreys smoothing avoids that failure; Jeffreys’ half-count rule approaches NML for the Bernoulli model.

Equations 2.31–2.34
P¯plug-in(Xi=⋅∣xi−1):=P(X=⋅∣θ^(xi−1)).\bar{P}_{\text{plug-in}}(X_{i}=\cdot\mid x^{i-1}){:=}P(X=\cdot\mid\hat{\theta}(x^{i-1})). (2.31)
−logP¯plug-in(xn):=∑i=1n−logP(xi∣θ^(xi−1)).-\log\bar{P}_{\text{plug-in}}(x^{n}){:=}\sum_{i=1}^{n}-\log P(x_{i}\mid\hat{\theta}(x^{i-1})). (2.32)
−log⁡P¯plug-in​(xn)=−log⁡P⁡(xn∣θ^​(xn))+k2​log⁡n+O⁡(1),-\log\bar{P}_{\text{plug-in}}(x^{n})=-\log P(x^{n}\mid\hat{\theta}(x^{n}))+\frac{k}{2}\log n+O(1), (2.33)
−log⁡P¯plug-in​(xn)≥−log⁡P¯plug-in​(x3∣x1,x2)=∞,-\log\bar{P}_{\text{plug-in}}(x^{n})\geq-\log\bar{P}_{\text{plug-in}}(x_{3}\mid x_{1},x_{2})=\infty,
θ^λ​(xn):=n[1]+λn+2​λ.\hat{\theta}_{\lambda}(x^{n}){:=}\frac{n_{[1]}+\lambda}{n+2\lambda}. (2.34)

Summary

Compression, distinguishable-model counting, Bayesian mixture behavior and sequential log loss explain the same refined selection criterion under their respective assumptions.

2.7 General Refined MDL: Gluing it All Together

Two complications require extensions: infinitely many candidate families and models with divergent NML normalizers. Both can be addressed by constructing an additional valid universal code.

2.7.1 Model Selection with Infinitely Many Models

Comparing infinitely many family code lengths without charging a family index can recreate memorization. Add a prefix length for the model index, often a slowly growing integer code. For a finite family this index charge can be uniform and cancel in comparisons.

Equation 2.35
−log⁡P¯nml​(xn∣ℳ(k))+L⁡(k),-\log\bar{P}_{\text{\rm nml}}(x^{n}\mid{\cal M}^{(k)})+L(k), (2.35)

2.7.2 The Infinity Problem

Even the unrestricted Gaussian location family has infinite NML complexity. Restricting the range makes a conditional normalizer finite, but the restriction must be encoded or otherwise chosen through a valid protocol. A meta-code communicates the needed range with small overhead relative to hindsight, rather than selecting an arbitrary cutoff for free.

Equations 2.36–2.38
P⁡(x|μ)=12​π​σ​e−(x−μ)22​σ2,P(x|\mu)=\frac{1}{\sqrt{2\pi}\sigma}e^{-\frac{(x-\mu)^{2}}{2\sigma^{2}}},
COMPn​(ℳ)=∫xnP⁡(xn∣μ^​(xn))​d​xn=∞,\text{\bf COMP}_{n}({\cal M})=\int_{x^{n}}P(x^{n}\mid\hat{\mu}(x^{n}))dx^{n}=\infty,
∫Θ|I⁡(θ)|​𝑑θ=∫μ∈ℝ|I⁡(μ)|​𝑑μ=∞.\int_{\Theta}\sqrt{|I(\theta)|}d\theta=\int_{\mu\in{\mathbb{R}}}\sqrt{|I(\mu)|}d\mu=\infty.
∫xn:μ^​(xn)∈[a,b]P(xn∣μ^(xn))dxn=b−a2​π​σ⋅n.\int_{x^{n}:\hat{\mu}(x^{n})\in[a,b]}P(x^{n}\mid\hat{\mu}(x^{n}))dx^{n}=\frac{b-a}{\sqrt{2\pi}\sigma}\cdot\sqrt{n}. (2.36)
P¯nml(xn∣ℳK)=P′​(xn∣μ^​(xn))∫xn:|μ^​(xn)|<KP′(xn∣μ^(xn))dxn,\bar{P}_{\text{\rm nml}}(x^{n}\mid{\cal M}_{K})=\frac{P^{\prime}(x^{n}\mid\hat{\mu}(x^{n}))}{\int_{x^{n}\;:\;|\hat{\mu}(x^{n})|<K}P^{\prime}(x^{n}\mid\hat{\mu}(x^{n}))dx^{n},}
COMPn(ℳK)=log∫|μ^​(xn)|<KP′(xn∣μ^(xn))dxn=logK+12logn2​π−logσ+1.\text{\bf COMP}_{n}({\cal M}_{K})=\log\int_{|\hat{\mu}(x^{n})|<K}P^{\prime}(x^{n}\mid\hat{\mu}(x^{n}))dx^{n}=\log K+\frac{1}{2}\log\frac{n}{2\pi}-\log\sigma+1.
−log⁡P¯meta​(xn|ℳ):=minK⁡{−log⁡P¯meta​(xn∣ℳK)+L⁡(K)}.-\log\bar{P}_{\text{\rm meta}}(x^{n}|{\cal M}){:=}\min_{K}\ \bigl\{-\log\bar{P}_{\text{\rm meta}}(x^{n}\mid{\cal M}_{K})+L(K)\bigr\}. (2.37)
−log⁡P¯meta​(xn∣ℳ)−[−log⁡P⁡(xn∣μ^​(xn))]=minK:log⁡K∈{1,2,…}{logK+12logn2​π−logσ+1+2log⌈logK⌉}+1≤log⁡|μ^​(xn)|+2​log⁡log|μ^​(xn)|+12​log⁡n2​π−log⁡σ+4≤COMPn​(ℳ|μ^|)+2​log⁡COMPn​(ℳ|μ^|)+3.-\log\bar{P}_{\text{\rm meta}}(x^{n}\mid{\cal M})-[-\log P(x^{n}\mid\hat{\mu}(x^{n}))]=\\ \min_{K:\log K\in\{1,2,\ldots\}}\ \bigl\{\log K+\frac{1}{2}\log\frac{n}{2\pi}-\log\sigma+1+2\log\lceil\log K\rceil\ \bigr\}+1\leq\\ \log|\hat{\mu}(x^{n})|+2\log\log|\hat{\mu}(x^{n})|+\frac{1}{2}\log\frac{n}{2\pi}-\log\sigma+4\leq\\ \text{\bf COMP}_{n}({\cal M}_{|\hat{\mu}|})+2\log\text{\bf COMP}_{n}({\cal M}_{|\hat{\mu}|})+3. (2.38)

Renormalized Maximum Likelihood

Renormalized maximum likelihood attempts a more efficient one-part solution by normalizing a likelihood already optimized over a range parameter. It improves on duplicated descriptions in a meta two-part code, but its applicability still requires checking the resulting normalizer.

Equation 2.39
P¯rnml​(xn|ℳ)=P¯nml​(xn|ℳK^​(xn))∫xn∈ℝnP¯nml​(xn∣ℳK^​(xn))​d​xn.\bar{P}_{\text{\rm rnml}}(x^{n}|{\cal M})=\frac{\bar{P}_{\text{\rm nml}}(x^{n}|{\cal M}_{\hat{K}(x^{n})})}{\int_{x^{n}\in{\mathbb{R}}^{n}}\bar{P}_{\text{\rm nml}}(x^{n}\mid{\cal M}_{\hat{K}(x^{n})})dx^{n}}. (2.39)

Region Indifference

Generalized schemes can prefer particular parameter regions. Changing an origin may change some code lengths. Conditioning an improper Jeffreys prior on initial observations offers another approach, though its integration into the tutorial’s MDL framework is not settled.

2.7.3 The General Picture

The common principle is to construct one valid code that competes as evenly as possible with the available candidate descriptions. Infinite settings force some nonuniform preference. When computation only finds local likelihood maxima, complexity should reflect that actual estimator’s ability to fit data rather than the unattainable global optimum.


  GENERAL ‘REFINED’ MDL PRINCIPLE for Model Selection Suppose we plan to select between models ℳ(1),ℳ(2),…{\cal M}^{(1)},{\cal M}^{(2)},\ldots for data D=(x1,…,xn)D=(x_{1},\ldots,x_{n}). MDL tells us to design a universal code P¯\bar{P} for 𝒳n{\cal X}^{n}, in which the index kk of ℳ(k){\cal M}^{(k)} is encoded explicitly. The resulting code has two parts, the two sub-codes being defined such that 1. All models ℳ(k){\cal M}^{(k)} are treated on the same footing, as far as possible: we assign a uniform prior to these models, or, if that is not a possible, a prior ‘close to’ uniform. 2. All distributions within each ℳ(k){\cal M}^{(k)} are treated on the same footing, as far as possible: we use the minimax regret universal model P¯nml​(xn∣ℳ(k))\bar{P}_{\text{\rm nml}}(x^{n}\mid{\cal M}^{(k)}). If this model is undefined or too hard to compute, we instead use a different universal model that achieves regret ‘close to’ the minimax regret for each submodel of ℳ(k){\cal M}^{(k)} in the sense of (2.38). In the end, we encode data DD using a hybrid two-part/one-part universal model, explicitly encoding the models we want to select between and implicitly encoding any distributions contained in those models.


Figure 2.4: The Refined MDL Principle.
Equations 2.40
P¯nml′​(xn):=P⁡(xn∣θ˙​(xn))∑xn∈𝒳nP⁡(xn∣θ˙​(xn)),\bar{P}_{\text{\rm nml}}^{\prime}(x^{n}){:=}\frac{P(x^{n}\mid\dot{\theta}(x^{n}))}{\sum_{x^{n}\in{\cal X}^{n}}P(x^{n}\mid\dot{\theta}(x^{n}))},
COMPn′(ℳ):=log∑xn∈𝒳nP(xn∣θ˙(xn)),\text{\bf COMP}^{\prime}_{n}({\cal M}){:=}\log\sum_{x^{n}\in{\cal X}^{n}}P(x^{n}\mid\dot{\theta}(x^{n})), (2.40)

Summary

Refined MDL combines minimax universal codes with additional valid coding layers when a single finite normalizer is unavailable. The model-selection prescription then needs further adaptation for other inference tasks.

2.8 Beyond Parametric Model Selection

MDL extends to density estimation, parameter estimation, regression and classification. Extensions do not inherit every model-selection guarantee automatically.

Non-Parametric Inference

Nonparametric estimation can compare increasingly rich model classes that approximate an infinite-dimensional target. Complexity controls how quickly flexibility grows with available evidence.

MDL Parameter Estimation: Three Approaches

After selecting a family, one may use its maximum-likelihood estimate, an optimally quantized two-part estimate, or a predictive estimate. They can agree asymptotically in fixed-dimensional regular families while differing substantially on small samples.

Regression

With Gaussian residuals, conditional negative log likelihood is proportional to squared error plus noise-scale terms. Compare conditional universal codes for outputs given inputs and charge the model index. Input lengths can be ignored only when their coding rule is identical across candidates.

Equations 2.41–2.44
Yi=h⁡(Xi)+Zi,Y_{i}=h(X_{i})+Z_{i}, (2.41)
P⁡(yn∣xn,σ,h)=(12​π​σ)n​exp⁡(−∑i=1n(yi−h⁡(xi))22​σ2).P(y^{n}\mid x^{n},\sigma,h)=\biggl(\frac{1}{\sqrt{2\pi}\sigma}\biggr)^{n}\exp\biggl(-\frac{\sum_{i=1}^{n}(y_{i}-h(x_{i}))^{2}}{2\sigma^{2}}\biggr). (2.42)
−log⁡P⁡(yn∣xn,σ,h)=12​σ2​∑i=1n(yi−h⁡(xi))2+n2​log⁡2​π​σ2.-\log P(y^{n}\mid x^{n},\sigma,h)=\frac{1}{2\sigma^{2}}\sum_{i=1}^{n}(y_{i}-h(x_{i}))^{2}+\frac{n}{2}\log 2\pi\sigma^{2}. (2.43)
−log⁡P¯​(yn∣ℳ(k),xn)+L⁡(k)-\log\bar{P}(y^{n}\mid{\cal M}^{(k)},x^{n})+L(k) (2.44)
−log⁡P¯​(yn∣ℳ(k),xn)+L⁡(k)+L′​(xn)-\log\bar{P}(y^{n}\mid{\cal M}^{(k)},x^{n})+L(k)+L^{\prime}(x^{n})

  When the Codelength for xnx^{n} Can Be Ignored If all models under consideration represent conditional densities or probability mass functions P⁡(Y∣X)P(Y\mid X), then the codelength for X1,…,XnX_{1},\ldots,X_{n} can be ignored in model and parameter selection. Examples are applications of MDL in classification and regression.


Figure 2.5: Ignoring codelengths.

‘Non-probabilistic’ Regression and Classification

Direct loss-based regression and classification aim to avoid explicit noise assumptions, but some MDL classifications can overfit persistently under misspecification. Proposed fixes need not retain a natural literal coding interpretation. The tutorial treats this as an unresolved limitation, not a universal robustness guarantee.

Summary

The general coding viewpoint is broader than one formula. Whether an extension predicts well must be checked for its model class, loss and approximation.

2.9 Relations to Other Approaches to Inductive Inference

MDL is related to Bayesian inference, MML, prequential validation, cross-validation and algorithmic complexity. Similar-looking criteria can have distinct objectives and assumptions.

2.9.1 What is ‘MDL’?

Here MDL means inductive inference using universal models, while refined MDL refers more specifically to the minimax model-selection construction. It is neither restricted to a BIC formula nor a label for every conceivable compression heuristic.

2.9.2 MDL and Bayesian Inference

NML, predictive codes and estimator-dependent variants are not generally Bayesian mixtures. Bayesian methods remain important implementations within the broader MDL viewpoint.

MDL as a Maximum Probability Principle

MDL interprets distributions primarily as predictive/coding devices and need not update every construction through a prior and posterior. When it uses a prior, coding regret guides its choice. This offers an interpretation for useful but known-imperfect models, while the tutorial acknowledges Bayesian philosophies that also accommodate such use.

MDL and BIC

BIC keeps negative maximized log likelihood plus (k/2) log n and drops order-one terms. That is a fixed-dimensional asymptotic approximation, not the full MDL principle. It can lose important geometric effects and behave differently when the candidate dimension grows with sample size.

Equation 2.45
−log⁡P⁡(xn∣θ^​(xn))+k2​log⁡n,-\log P(x^{n}\mid\hat{\theta}(x^{n}))+\frac{k}{2}\log n, (2.45)

MDL and MML

MML chooses a two-part description minimizing expected absolute length under a subjective prior; refined MDL emphasizes worst-case relative length. MML naturally selects both family and parameters and can provide an invariant, interpretable point summary when a full posterior mixture is unwieldy.

Original Figure 2.6: Figure 2.6: Rissanen’s MDL, Wallace’s MML and Dawid’s
Prequential Approach.

Figure 2.6: Rissanen’s MDL, Wallace’s MML and Dawid’s Prequential Approach.

2.9.3 MDL, Prequential Analysis and Cross-Validation

Prequential validation scores forecasts made before each observation. Log-loss versions correspond to code lengths, while Dawid’s framework also permits other losses. Compared with ordinary cross-validation, the sequential protocol never uses future data to predict past data and predicts each outcome once.

2.9.4 Kolmogorov Complexity and Structure Function; Ideal MDL

Ideal MDL uses universal programs to describe computable distributions, but cannot generally find the optimizing description. Kolmogorov’s structure-function viewpoint instead isolates a model capturing all compressible structure, leaving typical residual noise. Sending only that structure suggests lossy compression and links practical MDL to the theoretical separation of structure and randomness.

Equation 2.46
K⁡(P)+[−log⁡P⁡(D)],K(P)+\bigl[-\log P(D)\bigr], (2.46)

Summary and Outlook

These connections supply useful interpretations without making the methods identical. Their practical performance depends on the detailed procedure.

2.10 Problems for MDL?

Conceptual objections about simplicity must be separated from concrete failures caused by approximation, computational constraints or misspecified models.

2.10.1 Conceptual Problems: Occam’s Razor

The relevant question is whether a coding prescription is justified and predicts well, not whether the world is intrinsically simple.

1. ‘Occam’s Razor (and MDL) is arbitrary’ (page 1.6 )

Finite, well-defined NML comparisons are invariant to smooth reparameterization. Infinite families, divergent normalizers and the choice of submodel hierarchy introduce unavoidable preferences. Such choices should be explicit rather than disguised as universally intrinsic simplicity.

2. ‘Occam’s razor is false’ (page 1.6 )

A complexity penalty can yield consistency where unrestricted maximum likelihood overfits. That supports the strategy of starting simple at small samples, but does not prove MDL optimal for every loss, setting or finite dataset.

2.10.2 Practical Problems with MDL

Poor results can follow from using asymptotic expansions too early or cutting off parameter ranges arbitrarily. Prefer the actual NML or an appropriate mixture when defined and computable; otherwise use a carefully designed predictive or two-part code. The validity of approximations remains a practical research question.

MDL and Misspecification

A deeper problem arises when no candidate distribution approximates the data well: MDL and Bayes can choose poor predictive approximations, including persistent classification overfitting. This matters precisely because MDL’s philosophical motivation sought to avoid reliance on a true model.

2.11 Conclusion

Universal coding unifies several sensible inference strategies and often gives strong consistency and convergence results. It remains fallible under some practical approximations and misspecification. Further refinement is needed; compression alone is not a blanket guarantee of predictive success.

Further Reading

The bibliography includes the foundational Rissanen work and surveys by Barron, Rissanen, Yu and others. Earlier monographs remain useful for the philosophy even where their technical prescriptions have been superseded.

Acknowledgments

The author thanks Jay Myung, Mark Pitt, Steven de Rooij and Teemu Roos for comments on the tutorial.

Notes

The notes qualify technical conventions: code lengths can be idealized, finite-sample codes must charge any data-dependent choice, and individual-sequence universality differs from expected universality. Not every universal distribution forms a compatible probabilistic source across sample sizes. Claims about consistency, Bayesian equivalence and empirical success depend on the cited conditions.

Concept demonstration

Open image ↗