Topic 8: Statistical Modelling and Optimal Estimation

Question 1

Describe Kolmogorov Complexity

Answer 1

The Kolmogorov Complexity of a string/sequence S/D is the length of the shortest program that generates S/D on a universal Turing machine.

It measures the information content of “compressibility” of S/D:

• Described randomness: High complexity implies compressible
• Foundation for the Minimum Description Length (MDL) principle

This so-called invariance theorem says that as long as the sequence D is long enough, it’s not essential which language one chooses, as long as the language is general-purpose.

Kolmogorov Complexity is uncomputable: no algorithm can calculate it for every string/sequence.

Question 2

Describe MDL principle

Answer 2

MDL is based on the following insight: any regularity in the data can be used to compress the data, i.e. to describe it using fewer symbols than the number of symbols needed to describe the data literally. The more we are able to compress the data, the more we have learned about the data.

Attractive properties about MDL

Occam’s Razor - MDL chooses a model that trades-off goodness-of-fit on the observed data with ‘complexity’ or ‘richness’ of the model.

No overfitting, automatically - MDL procedures automatically and inherently protect against overfitting and can be used to estimate both the parameters and the structure (e.g. number of parameters) of a model.

Bayesian interpretation - MDL is closely related to Bayesian inferences, but avoids some of the difficulties, especially in the realistic case, with priors.

No need for ‘underlying truth’ - like said before, no need for an underlying true model.

Predictive interpretation - MDL methods can be interpreted as searching for a model with good predictive performance on unseen data.

Question 3

Describe universal modelling and the NML principle

Answer 3

Universal coding

Observation: There’s no code that will always mimic the best code x^n. This is because the best compression depends on the specific properties of the data, which vary from one sequence to another.

Is there a code for all x^n that is almost as good as the optimal code hat L(x^n)????

YESSSSS, this is called universal code!!! Distributions corresponding to the universal codes are called universal models.

Universal modelling
Universal Modelling is the concept of designing codes or models that perform well across a wide range of possible datasets. Instead of assuming a “true” model, universal modelling focuses on finding a model that compresses data efficiently across many possibilities.

Universal Modelling: Instead of assuming the existence of a true model, universal modelling involves designing codes that can compress data well across a broad range of models. They’re probability distributions that correspond to universal codes.

NML principle

NML Principle: NML (Normalised Maximum Likelihood) is a universal coding scheme that defines the optimal universal code for a model class. It selects models by minimising the stochastic complexity.

Question 4

Describe two part MDL, and the NML criterion: Optimal estimation

Answer 4

his is the so-called two-part code version of MDL:

Part 1: Model Description Length L(H)

• This measures how many bits we need to describe our model
• Includes both structure and parameters
• Example in Linear Regression:
  
  • L(H) would be larger if you have 10 predictors (y ~ x₁ + x₂ + … + x₁₀)
  • L(H) would be smaller if you have 2 predictors (y ~ x₁ + x₂)

Part 2: Data Description Length Given Model L(D|H)

• This measures how many bits we need to describe our data using the model
• Essentially measures how well the model fits the data
• Example in Linear Regression:
  
  • If model fits perfectly, L(D|H) is small (just need to encode tiny residuals)
  • If model fits poorly, L(D|H) is large (need to encode large residuals)

NML criterion

The Normalised Maximum Likelihood (NML) principle is a modern refinement of MDL, addressing the limitations of the two-part approach. It is based on stochastic complexity, which measures how well a model compresses data by considering all possible datasets the model could describe.

Question 5

Describe model capacity

Answer 5

Model capacity is about how much a model can learn or represent:

• A model with low capacity is simple and can only capture basic patterns in the data.
• A model with high capacity is complex and can capture very detailed or intricate patterns.
• Low Capacity (Simple Model):
  
  • You use a straight line (linear regression).
  • This model is simple and might miss important details (underfitting).
• High Capacity (Complex Model):
  
  • You use a wiggly curve with many bends.
  • This model is very flexible but might fit the noise in the data too closely (overfitting)

Question 6

Describe application of the
MDL principle.

Answer 6

• Model Selection: Choosing between competing models by selecting the one with the shortest total description length.
• Preventing Overfitting: Automatically avoiding overfitting by penalizing models with higher complexity.
• Data Compression: MDL aligns well with the principle of data compression, where regularities in the data reduce the total description length.

Question 7

What is optimal estimation?

Answer 7

Optimal Estimation involves selecting the best model
f(Y |Xs; θ, s) to describe data Y, given explanatory variables X.

Model Selection: Based on structure s (important variables) and parameters θ.
Goal: Maximize the capacity C^n, which represents the probability or density of the observed data.
Key Insight: Maximum capacity is equivalent to the maximum mutual information an estimator can extract about the models.