Autumn2012 Lecture9:TheMDLPrincipleJyrkiKivinen Information-TheoreticModeling

(1)

Information-Theoretic Modeling

Lecture 9: The MDL Principle

Jyrki Kivinen

Department of Computer Science, University of Helsinki

Autumn 2012

Jyrki Kivinen Information-Theoretic Modeling

(2)

Outline Occam’s Razor MDL Principle

Lecture 9: MDL Principle

Jorma Rissanen (left) receiving the IEEE Information Theory Society Best Paper Award from Claude Shannon in 1986.

IEEE Golden Jubilee Award for Technological Innovation(for the invention of arithmetic coding) 1998;IEEE Richard W. Hamming Medal(for fundamental

contribution to information theory, statistical inference, control theory, and the theory of complexity) 1993;Kolmogorov Medal2006;

IBM Outstanding Innovation Award(for work in statistical inference, information theory, and the theory of complexity) 1988;

IEEE Claude E. Shannon Award 2009; ...

(3)

1 Occam’s Razor House

Visual Recognition Astronomy

Razor

Probabilistic Models Old-Style MDL Modern MDL

(4)

Razor

2 MDL Principle Rules & Exceptions Probabilistic Models Old-Style MDL Modern MDL

(5)

House

(6)

House Visual Recognition Astronomy Razor

House

Brandon has

1 cough,

2 severe abdominal pain,

3 nausea,

4 low blood pressure,

5 fever.

1 pneumonia,

common cold,

2 appendicitis,

gout medicine,

3 food poisoning,

gout medicine,

4 hemorrhage,

gout medicine,

5 meningitis.

common cold.

No single disease causes all of these.

Each symptom can be caused bysome(possibly different) disease... Dr. House explains the symptoms with two simple causes:

1 common cold, causing the cough and fever,

2 pharmacy error: cough medicine replaced by gout medicine.

(7)

House

Brandon has

1 cough,

3 nausea,

5 fever.

1 pneumonia,

2 appendicitis,

3 food poisoning,

gout medicine,

4 hemorrhage,

gout medicine,

5 meningitis.

common cold.

Each symptom can be caused bysome(possibly different) disease... Dr. House explains the symptoms with two simple causes:

(8)

House

Brandon has

1 cough,

3 nausea,

5 fever.

1 pneumonia,

common cold,

2 appendicitis,

gout medicine,

3 food poisoning,

gout medicine,

4 hemorrhage,

gout medicine,

5 meningitis.

common cold.

Each symptom can be caused bysome(possibly different) disease...

Dr. House explains the symptoms with two simple causes:

(9)

House

Brandon has

1 cough,

3 nausea,

5 fever.

1 pneumonia,

common cold,

2 appendicitis,

3 food poisoning,

4 hemorrhage,

gout medicine,

5 meningitis.

common cold.

(10)

House

Brandon has

1 cough,

3 nausea,

5 fever.

1 pneumonia,

common cold,

2 appendicitis,

gout medicine,

3 food poisoning,

gout medicine,

4 hemorrhage,

gout medicine,

5 meningitis.

common cold.

(11)

House

Brandon has

1 cough,

3 nausea,

5 fever.

1 pneumonia,

common cold,

2 appendicitis,

gout medicine,

3 food poisoning,

gout medicine,

4 hemorrhage,

5 meningitis.

(12)

House

Brandon has

1 cough,

3 nausea,

5 fever.

1 pneumonia,

common cold,

2 appendicitis,

gout medicine,

3 food poisoning,

gout medicine,

4 hemorrhage,

gout medicine,

5 meningitis.

common cold.

(13)

House

Brandon has

1 cough,

3 nausea,

5 fever.

1 pneumonia,

common cold,

2 appendicitis,

gout medicine,

3 food poisoning,

gout medicine,

4 hemorrhage,

gout medicine,

5 meningitis.

common cold.

(14)

House

Brandon has

1 cough,

3 nausea,

5 fever.

1 pneumonia,

common cold,

2 appendicitis,

gout medicine,

3 food poisoning,

gout medicine,

4 hemorrhage,

gout medicine,

5 meningitis.

common cold.

2 pharmacy error: cough medicine replaced bygout medicine.

(15)

House

Brandon has

1 cough,

3 nausea,

5 fever.

1 common cold,

2 appendicitis,

3 food poisoning,

4 hemorrhage,

gout medicine,

5 common cold.

(16)

House

Brandon has

1 cough,

3 nausea,

5 fever.

1 common cold,

2 gout medicine,

3 gout medicine,

4 gout medicine,

5 common cold.

(17)

Visual Recognition

(18)

Visual Recognition

(19)

Visual Recognition

(20)

Visual Recognition

(21)

Visual Recognition

(22)

Visual Recognition

(23)

Visual Recognition

(24)

Visual Recognition

(25)

Astronomy

(26)

Astronomy

(27)

Astronomy

(28)

William of Ockham (c. 1288–1348)

(29)

Occam’s Razor

Entities should not be multiplied beyond necessity.

appearances.”

Diagnostic parsimony: Find the fewest possible causes that explain the symptoms.

(Hickam’s dictum: “Patients can have as many diseases as they damn well please.”)

(30)

Occam’s Razor

Isaac Newton: “We are to admit no more causes of natural things than such as are both true and sufficient to explain their

appearances.”

(31)

Occam’s Razor

appearances.”

(32)

Occam’s Razor

appearances.”

(33)

Visual Recognition

(34)

Visual Recognition

(35)

Visual Recognition

(36)

Visual Recognition

(37)

Razor

2 MDL Principle Rules & Exceptions Probabilistic Models Old-Style MDL Modern MDL

(38)

Rules & Exceptions Probabilistic Models Old-Style MDL Modern MDL

MDL Principle

Minimum Description Length (MDL) Principle (2-part) Choose the hypothesis which minimizes the sum of

1 the codelength of the hypothesis, and

2 the codelength of the data with the help of the hypothesis.

How to encode datawith the help of a hypothesis?

(39)

MDL Principle

Minimum Description Length (MDL) Principle (2-part) Choose the hypothesis which minimizes the sum of

1 the codelength of the hypothesis, and

2 the codelength of the data with the help of the hypothesis.

How to encode datawith the help of a hypothesis?

(40)

Encoding Data: Rules & Exceptions

Idea 1: Hypothesis = rule; encode exceptions.

Black box of size 25×25 = 625, white dots at (x1,y1), . . . ,(xk,yk).

For image of sizen= 625, there are 2ⁿ different images, and

n

k

= n!

k!(n−k)! different groups ofk exceptions.

(41)

Encoding Data: Rules & Exceptions

n

k

= n!

k!(n−k)! different groups ofk exceptions.

(42)

Encoding Data: Rules & Exceptions

n

k

= n!

k!(n−k)!

different groups ofk exceptions.

(43)

Encoding Data: Rules & Exceptions

n

k

= n!

k!(n−k)!

k= 1 :

n

1

= 6252⁶²⁵ ≈1.4·10¹⁸⁸. Codelength log₂(n+ 1) + log₂

n

k

≈19 vs. log₂2⁶²⁵= 625

(44)

Encoding Data: Rules & Exceptions

n

k

= n!

k!(n−k)!

k= 2 :

n

2

= 195 0002⁶²⁵≈1.4·10¹⁸⁸. Codelength log₂(n+ 1) + log₂

n

k

≈27 vs. log₂2⁶²⁵= 625

(45)

Encoding Data: Rules & Exceptions

n

k

= n!

k!(n−k)!

k= 3 :

n

3

= 40 495 0002⁶²⁵≈1.4·10¹⁸⁸. Codelength log₂(n+ 1) + log₂

n

k

≈35 vs. log₂2⁶²⁵= 625

(46)

Encoding Data: Rules & Exceptions

n

k

= n!

k!(n−k)!

k= 10 :

n

10

= 2 331 354 000 000 000 000 0002⁶²⁵. Codelength log₂(n+ 1) + log₂

n

k

≈80 vs. log₂2⁶²⁵= 625

(47)

Encoding Data: Rules & Exceptions

n

k

= n!

k!(n−k)!

k= 100 :

n

100

≈9.5·10¹¹⁷ 2⁶²⁵≈1.4·10¹⁸⁸. Codelength log₂(n+ 1) + log₂

n

k

≈401 vs. log₂2⁶²⁵= 625

(48)

Encoding Data: Rules & Exceptions

n

k

= n!

k!(n−k)!

k= 300 :

n

300

≈2.7·10¹⁸⁶ <2⁶²⁵ ≈1.4·10¹⁸⁸. Codelength log₂(n+ 1) + log₂

n

k

≈629 vs. log₂2⁶²⁵= 625

(49)

Encoding Data: Rules & Exceptions

n

k

= n!

k!(n−k)!

k= 372 :

n

372

≈5.1·10¹⁸¹ 2⁶²⁵≈1.4·10¹⁸⁸. Codelength log₂(n+ 1) + log₂

n

k

≈613 vs. log₂2⁶²⁵= 625

(50)

Encoding Data: Probabilistic Models

Idea 2: Hypothesis = probability distribution.

Noisy PSNR=19.8 MDL (A-B) PSNR=32.9

Rissanen & Shannon: log₂ 1 p_θ_ˆ(D) +k

2 log₂n.

(51)

Encoding Data: Probabilistic Models

Idea 2: Hypothesis = probability distribution.

Rissanen & Shannon: log₂ 1 p_θ_ˆ(D)+ k

2 log₂n.

(52)

Polynomials

From P. Gr¨unwald

(53)

Old-Style MDL

With the precision ^√¹_n the codelength for data is almost optimal:

min

θ^q∈{θ⁽¹⁾,θ⁽²⁾,...}`θ^q(D) ≈ min

θ∈Θ`θ(D) = log₂ 1 p_θ_ˆ(D) .

“Steam MDL”

`θ^q(D) +`(θ^q)≈log₂ 1 pθˆ(D) +k

2log₂n .

(54)

Old-Style MDL

With the precision ^√¹_n the codelength for data is almost optimal:

min

θ^q∈{θ⁽¹⁾,θ⁽²⁾,...}`θ^q(D) ≈ min

θ∈Θ`θ(D) = log₂ 1 p_θ_ˆ(D) . This gives the total codelength formula:

“Steam MDL”

`θ^q(D) +`(θ^q)≈log₂ 1 pθˆ(D) +k

2log₂n .

(55)

Old-Style MDL

The ^k₂log₂n formula is only a rough approximation, and works well only for very large samples.

likelihood, etc.

(56)

Old-Style MDL

The ^k₂log₂n formula is only a rough approximation, and works well only for very large samples.

MDL in the 21st century:

More advanced codes: mixtures, normalized maximum likelihood, etc.

(57)

MDL Model Selection

Perhaps the best known use for MDL is formodel class selection (which is often called just model selection).

We want to pick the one that seems best suited for our dataD. TypicallyM₁⊂ · · · ⊂ M_m, so M_m always achieves the best fit to data, but may beoverfitting(see Introduction to machine

learning).

Therefore we use MDL and pickM_i that minimizes the total code length.

(58)

MDL Model Selection

Suppose we have a family of model classesM₁, . . . ,M_m, each with their own parameter set Θ₁, . . . ,Θ_m.

We want to pick the one that seems best suited for our dataD.

TypicallyM₁⊂ · · · ⊂ M_m, so M_m always achieves the best fit to data, but may beoverfitting(see Introduction to machine

learning).

(59)

MDL Model Selection

Suppose we have a family of model classesM₁, . . . ,M_m, each with their own parameter set Θ₁, . . . ,Θ_m.

We want to pick the one that seems best suited for our dataD.

TypicallyM₁⊂ · · · ⊂ M_m, so M_m always achieves the best fit to data, but may beoverfitting(see Introduction to machine

learning).

(60)

MDL Model Selection

Actually here we have a “three-part” code:

1 Encoding of the model class: `(M_i), i ∈ {1, . . . ,m}.

2 Encoding of the parameter (vector): `1(θ), θ ∈Θi.

3 Encoding of the data: log₂ 1

pθ(D), D∈ D.

If we have a finite family ofm model classes, we can do Part 1 with`(M_i) = log₂m for alli.

This can be generalized to infinite families of model classes, in which case we often to pickp which is “as uniform as possible” overNand`(M_i) = log₂(1/p(i)).

(61)

MDL Model Selection

3 Encoding of the data: log₂

pθ(D), D∈ D.

(62)

MDL Model Selection

pθ(D), D∈ D.

(63)

MDL Model Selection

pθ(D), D ∈ D.

(64)

MDL Model Selection

pθ(D), D ∈ D.

If we have a finite family ofm model classes, we can do Part 1 with`(M_i) = log₂mfor all i.

This can be generalized to infinite families of model classes, in which case we often to pickp which is “as uniform as possible”

overNand`(M_i) = log₂(1/p(i)).

(65)

MDL Model Selection

If we are interested in choosing a model class (and not the

parameters), we can improve parts 2 & 3 by combining them into a better universal code than two-part:

M_i M_i

universal code-length (e.g., mixture, NML) based on model classM_i.

(66)

MDL Model Selection

1 Encoding of the model class index: `(M_i), i ∈N.

2 Encoding of the data: `M_i(D), D∈ D, where`M_i is a universal code-length (e.g., mixture, NML) based on model classM_i.

(67)

MDL Model Selection

1 Encoding of the model class index: `(M_i), i ∈N.

2 Encoding of the data: `M_i(D), D∈ D, where`M_i is a universal code-length (e.g., mixture, NML) based on model classM_i.

(68)

MDL Model Selection

MDL Explanation of MDL

The success in extracting the structure from data can be measured by the codelength.

In practice, we only find the structure that is “visible” to the used model class(es). For instance, the Bernoulli (coin flipping) model only sees the number of 1s.

(69)

MDL Model Selection

MDL Explanation of MDL

The success in extracting the structure from data can be measured by the codelength.

In practice, we only find the structure that is “visible” to the used model class(es). For instance, the Bernoulli (coin flipping) model only sees the number of1s.

(70)

MDL & Bayes

The MDL model selection criterion

minimize`(θ) +`_θ(D) can be interpreted (viap = 2^−`) as

maximizep(θ)·p_θ(D) .

In Bayesian probability, this is equivalent tomaximization of posterior probability:

p(θ|D) = p(θ)p(D|θ) p(D) ,

where the termp(D) (the marginal probability ofD) is constant wrt.θ and doesn’t affect model selection.

⇒Probabilistic Modelling

(71)

MDL & Bayes

p(θ|D) = p(θ)p(D |θ) p(D) ,

(72)

MDL & Bayes

p(θ|D) = p(θ)p(D |θ) p(D) ,

⇒Probabilistic Modelling

(73)

Example: Denoising

Complexity = Information + Noise

= Regularity + Randomness

= Algorithm + Compressed file

The MDL principle gives a natural method for denoising since the very idea of MDL is to separate the total complexity of a signal into information and noise.

First encode a smooth signal (information), and then the difference to the observed signal (noise).

(74)

Example: Denoising

Denoisingmeans the process of removing noise from a signal.

(75)

Example: Denoising

(76)

Example: Denoising

(77)

Example: Denoising

(78)

Example: Denoising

(79)

Example: Denoising

(80)

Example: Denoising

(81)

Example: Denoising

(82)

Example: Denoising

(83)

Coming next

We’ll see some more MDL:

MDL on continuous data

examples of MDL in applications.

Then we move on toKolmogorov complexity.