1 Historical and conceptual foundations of MDL

1.1 Compression as an inference criterion

The minimum description length (MDL) principle reframes statistical inference as a data-compression problem. Given multiple candidate models, MDL chooses the model that permits the shortest overall representation of the observed data—counting not only the bits needed to describe the data under a model, but also the bits required to specify the model itself. This viewpoint motivates a synthesis of model selection and estimation: a model is preferred when it captures regularities efficiently enough to offset the cost of describing that model.

1.2 Relationship to information theory

MDL grows out of themes from information theory and universal coding, where probability distributions serve as coding schemes and code lengths correspond to uncertainty. In this setting, the likelihood of a model provides a way to assign an “ideal” code length to data. The MDL objective then becomes a principled trade-off between how concentrated the model’s predictions are (good fit) and how complex the model class is to specify (coding overhead).

1.3 Coding interpretation of probability

A central conceptual move is to treat probabilities as relative frequencies of codewords in an optimal coding system. When a model assigns probability \(p(x)\) to an observation \(x\), an idealized code length can be taken as proportional to \(-\log p(x)\). MDL then uses these probability-induced code lengths to compare models under a consistent coding interpretation. While practical implementations rely on approximate codes, the principle remains tied to this “probability as code length” correspondence.

2 Formal statement of the MDL principle

2.1 Basic definition: total code length

At its core, MDL selects the model that minimizes a sum of two parts: the length of a code that transmits the model description, and the length of a code that transmits the data given that model.

2.1.1 Model description length

Let \(M\) denote a candidate model, including whatever parameters and structural choices are needed to specify it. The model description length quantifies the number of bits required to identify \(M\) (and potentially its parameters) according to a chosen coding scheme.

2.1.2 Data given model description length

After the receiver knows \(M\), the data \(x\) must be encoded using a distribution implied by \(M\). Under ideal coding, the code length for \(x\) given \(M\) is typically tied to \(-\log p_M(x)\), where \(p_M\) is the probability model associated with \(M\).

2.2 Optimization objective for model selection

The MDL rule can be stated as: \[ \hat{M}=\arg\min_{M}\bigl[ L(M)+L(x\mid M)\bigr]. \] Different variants differ in how the two terms are defined, especially when parameters are unknown, continuous, or require discretization. Nonetheless, all share the principle that optimal selection is driven by the total achievable compression.

2.3 Assumptions and idealized coding setup

Formal MDL statements often assume the existence of a coding system satisfying Kraft’s inequality and enabling near-optimal code lengths. In theoretical treatments, one works with “ideal” real-valued code lengths derived from probabilities, while acknowledging that practical codes require discretization, finite precision, and computable approximations. The quality of an MDL application depends on how closely the implemented code tracks the intended probabilistic coding interpretation.

3 MDL formulations and variants

3.1 Two-part (two-stage) MDL

Two-part MDL splits encoding into a model stage and a data stage.

3.1.1 Deterministic model encoding

In a common two-part setting, the model description includes selecting a specific parameter vector \(\hat{\theta}\) (often by maximum likelihood) within the chosen model class. The code length for the parameters reflects how finely \(\hat{\theta}\) is specified and how many bits are needed to transmit it under the assumed discretization.

3.1.2 Residual/data encoding

Given the transmitted parameters, the data are encoded using the likelihood under that parameter value. The overall score therefore resembles a penalized likelihood criterion: a goodness-of-fit term through \(-\log p_{\hat{\theta}}(x)\), plus a penalty term capturing the cost of transmitting the model (including parameter precision and structural index).

3.2 Stochastic (normalized maximum likelihood) MDL

Stochastic MDL replaces point parameter coding with a distribution over sequences induced by model class performance.

3.2.1 Prequential view and sequential coding

In prequential (predictive sequential) coding, data are encoded one step at a time using the model’s predictive distribution computed from prior observations. This yields a cumulative code length that depends on the order and the evolving predictive distribution.

3.2.2 Normalization over model space

Normalized maximum likelihood (NML) is a canonical stochastic formulation for many discrete settings. It constructs an “optimal” predictive distribution by normalizing the maximized likelihood across all possible data sequences of the fixed length. The resulting code length is minimized in a way that aligns with minimax regret properties, though exact NML can be difficult to compute for complex models.

3.3 Bayesian MDL and coding interpretations

Bayesian approaches can be interpreted through MDL by mapping posterior or marginal probabilities to code lengths.

3.3.1 Prior as model description

In Bayesian MDL interpretations, the prior distribution contributes to how many bits are needed to describe model parameters. Intuitively, more plausible parameter settings (under the prior) require fewer bits to identify because the coding system assigns them larger probability mass.

3.3.2 Marginal likelihood as total code length

The marginal likelihood (evidence), \[ p(x\mid M)=\int p(x\mid \theta,M)\,p(\theta\mid M)\,d\theta, \] can be converted to an MDL-style score via \(-\log p(x\mid M)\). In this view, integrating over parameters replaces the need to separately transmit a point estimate, producing a unified “total” code length that naturally includes a complexity penalty.

4 Connections to common model selection criteria

MDL reduces to maximum likelihood behavior when coding costs for the model description are negligible or identical across candidates. More generally, MDL can be seen as maximum likelihood with an additional penalty term reflecting how much the model has to “explain” and how expensive it is to specify the explanation. This link helps interpret MDL as a refinement of likelihood-based fitting.

4.2 Relationship to AIC

Akaike’s information criterion (AIC) is derived from approximations to expected predictive performance, often expressed in terms of an estimated Kullback–Leibler divergence. MDL and AIC are related in spirit because both balance fit and complexity, but they arise from different formal targets: AIC emphasizes prediction risk, while MDL is grounded in coding length under explicit compression interpretations. In many regular settings, one can find asymptotic correspondences between MDL penalties and the effective number of parameters that appear in AIC.

4.3 Relationship to BIC

Bayesian information criterion (BIC) approximates \(-2\log p(x\mid M)\) using asymptotic expansions, yielding a penalty that scales like \(\tfrac{1}{2}(\#\text{parameters})\log n\). BIC can be regarded as a particular asymptotic form of a Bayesian evidence/MDL score. Thus, MDL in Bayesian guise often matches BIC-like behavior in large samples, especially for well-regularized and identifiable models.

4.4 Regularization viewpoint

Although MDL is sometimes described purely as coding, it also aligns with regularization perspectives. The complexity term acts like a data-dependent restraint on overly flexible models. Under certain coding schemes, MDL penalties mirror those produced by regularizers that constrain model capacity, making it easier to compare MDL to methods used in statistical learning.

4.5 Asymptotic behavior comparisons

Different MDL variants, as well as MDL versus AIC/BIC, lead to distinct asymptotic regimes. In broad terms, penalties that grow with sample size tend to favor consistency under model nesting assumptions, while penalties that do not grow as strongly may prioritize predictive optimality. The precise asymptotic comparisons depend on whether the true model is assumed to lie in the candidate class, how parameters behave near boundaries, and how the coding scheme treats discretization and integration.

5 Practical implementations of MDL

5.1 Choosing a coding scheme

Implementing MDL requires translating the principle into a concrete computable code length. This involves selecting:

  1. How to encode model identities and structural choices.
  2. How to encode continuous parameters (directly or via discretization).
  3. Which probability model to use for data coding.

Because the total score is defined relative to a coding scheme, different reasonable codings can yield different rankings in finite samples.

5.2 Discretization and quantization issues

Many practical settings need discretization because exact real-valued parameters cannot be transmitted.

5.2.1 Finite precision encoding

One approach quantizes parameters to a grid whose resolution depends on sample size and desired code accuracy. The model description then includes the number of bits needed to specify the quantized parameter values. This choice influences the balance between fit and complexity, particularly when parameters can vary continuously.

5.2.2 Grid resolution effects

The resolution of the quantization grid affects the coding overhead and the induced likelihood term. Coarse grids underfit by forcing parameters into a restricted set, whereas very fine grids increase the parameter-description cost. Good MDL implementations therefore tie grid resolution to both the model’s sensitivity and the data volume so that the discretization error does not dominate the trade-off.

5.3 Handling unknown parameters

Unknown parameters can be treated either by point estimates or by averaging within a coding model.

5.3.1 Plug-in strategies

Plug-in MDL uses a single estimated parameter value (e.g., maximum likelihood) and then codes data conditionally on it. While computationally simpler, plug-in methods must incorporate the extra uncertainty due to estimation, often through explicit parameter-precision penalties.

5.3.2 Integrated/numerical coding approaches

Integrated variants approximate marginal likelihood or predictive distributions by numerical integration, variational methods, or Monte Carlo estimation. These approaches can yield more coherent uncertainty accounting, but they may introduce additional approximation error and computational burden.

5.4 Model class design considerations

MDL outcomes depend on how candidate model classes are constructed. If the true data-generating process is poorly represented or if model classes are too expressive without proper coding controls, compression may not correspond to generalization. Practical design often aims to include models with meaningful structure and manageable flexibility, and to ensure that the coding scheme can efficiently express the chosen models.

6 MDL for specific problem types

6.1 Classification and prediction settings

MDL can be adapted to classification when labels and features are encoded with compatible probability models.

6.1.1 Code length for labels

A typical strategy codes the label sequence using predicted class probabilities conditioned on features or using a joint model for features and labels. The resulting label code length reflects the uncertainty in class assignment and rewards models that provide confident yet calibrated predictions.

6.1.2 Loss functions induced by coding

Because code length is often proportional to a negative log-likelihood, MDL effectively induces loss functions equivalent to log-loss (cross-entropy) for the chosen probabilistic model. When combined with model-encoding penalties, this yields an MDL-driven form of regularized training or model selection for classification.

6.2 Density estimation and coding-based clustering

For density estimation, MDL prefers mixture or nonparametric models that compress data well. In clustering, one may encode cluster assignments plus within-cluster parameters and then code data given those assignments. This turns the clustering problem into a joint encoding task, where both partition complexity and within-group fit contribute to the score.

6.3 Time series and sequential data

Sequential data allow prequential coding, encoding observations in time order using one-step-ahead predictors. This naturally supports non-stationary behaviors and can incorporate autoregressive structures. The MDL objective then becomes a measure of how efficiently the model can compress future observations based on past context.

6.4 Graphical models and structured hypotheses

Graphical models introduce additional structure whose encoding cost must be accounted for. MDL can compare different graph topologies by coding adjacency structure and then coding conditional distributions. In this way, both statistical dependence structure and parameter fit influence model preference, aligning the selection process with a structured coding interpretation.

7 Theoretical properties

7.1 Consistency and optimality goals

A central theoretical question is whether MDL selects the “true” model as data size grows. Under favorable conditions (e.g., correct model class inclusion, identifiability, regularity), some MDL formulations are consistent. Optimality may also be defined in terms of minimizing expected redundancy or achieving near-minimax regret in coding regimes.

7.2 Regret and approximation analysis

For stochastic MDL (particularly NML-related approaches), theoretical bounds often express performance as regret relative to an oracle that knows the best code in hindsight. Approximation analyses examine how implemented codes deviate from ideal codes, and how that deviation impacts redundancy and model ranking.

7.3 Identifiability and model misspecification

Identifiability affects how parameter uncertainty maps to encoding costs. If different parameter values yield the same distribution, the effective model complexity can differ from naive parameter counting. Under misspecification—when no candidate model perfectly matches the data—MDL may converge to the best approximating model in a predictive or coding sense rather than the “true” generative one, depending on the variant and assumptions.

7.4 Complexity penalties and effective degrees of freedom

Complexity penalties can sometimes be interpreted through effective degrees of freedom rather than raw parameter count. This is particularly relevant in models with regularization, hierarchical structures, or constraints that reduce or alter the set of distinguishable distributions. Modern theoretical treatments connect coding complexity to geometric and statistical notions, such as curvature of likelihood surfaces and approximation capacity.

8 Example workflows and worked illustrations

8.1 Selecting between simple parametric models

A typical workflow compares two or more parametric families, such as a low-parameter regression model versus a more flexible one. One encodes the model identity and (if using two-part MDL) a quantized parameter estimate. The data code uses the likelihood under those parameters. The chosen model is the one whose improvement in fit outweighs the additional bits required to transmit a more elaborate explanation.

8.2 Polynomial/feature selection via code length

In feature selection with polynomial models, MDL can compare candidate degrees or subsets of basis functions. Higher-degree polynomials may fit training data better but require more bits to specify the chosen degree and coefficients (especially when coefficients are quantized). The MDL score thus favors degrees that capture regularities while avoiding overfitting that does not translate into effective compression.

8.3 Toy coding scheme demonstration

Consider a simplified binary scenario where candidate models encode a sequence using different Bernoulli parameters. Under a two-part code, one would:

  1. Encode the chosen parameter value (or an index over a grid).
  2. Encode the observed sequence with the Bernoulli likelihood at that parameter.

By computing the total code length for each candidate, one can observe how models with better likelihood may still lose if parameter-description cost is too high. Even in this small example, the MDL mechanism illustrates the “fit versus description” balancing principle.

9 Limitations and open considerations

9.1 Dependence on coding assumptions

MDL is not a single number computed from data alone; it depends on how the coding scheme is defined. Choices about priors, discretization, parameter quantization, and model encoding can change results. Consequently, MDL is best viewed as a framework where the coding design expresses modeling preferences and assumptions.

9.2 Computational cost of MDL evaluation

Evaluating MDL for many candidate models can be expensive, especially for stochastic MDL with normalization terms, integrated likelihoods, or sequential predictive computations. In practice, one may restrict model classes, reuse computations, or employ approximations, but such strategies can affect the fidelity of the MDL objective.

9.3 Sensitivity to model class coverage

If the candidate set is too narrow, MDL cannot represent the patterns present in the data efficiently, leading to suboptimal selection. If the set is overly broad without appropriate coding controls, the model description overhead might not be sufficient to prevent choosing models that compress training data in ways that do not generalize.

9.4 Challenges in high-dimensional settings

In high dimensions, parameter counts can be misleading, and discretization becomes harder. Likelihood surfaces can be complex, and integrated codes may be difficult to approximate. These factors can make MDL implementation and theoretical guarantees more challenging, motivating research into scalable approximations and refined complexity characterizations.

10.1 Information-theoretic criteria

Information-theoretic criteria include approaches that measure predictive uncertainty or divergence, such as Kullback–Leibler-based objectives and universal coding bounds. MDL is closely related to these themes because code length naturally corresponds to negative log probability and thus to divergence measures.

10.2 Bayesian model evidence and MDL overlaps

Bayesian evidence, marginal likelihood, and MDL-style scores overlap via shared log-probability structures. Bayesian methods provide a probabilistic mechanism for integrating over parameters, while MDL interprets the same quantity as a total description length. The overlap is especially strong for coding interpretations of priors and marginal likelihoods.

10.3 Minimum description length in universal coding

Universal coding studies schemes that achieve near-optimal compression across broad model classes without knowing the generating distribution. MDL and universal coding share common objectives: compress data using a code that adapts to structure while controlling complexity.

10.4 Notation and terminology glossary

Common terminology includes “code length” for negative log probability under a chosen model, “two-part” for model-and-data decomposition, “prequential” for sequential predictive coding, and “regret” for comparisons to ideal hindsight codes. Notation typically distinguishes model indices, parameter vectors, probability assignments, and logarithm base choices that affect constant factors in reported scores.