THE OCCAMS RAZOR

Occam's razor, made rigorous: a shorter hypothesis that fits needs less evidence to trust. Hypotheses are coded by a prefix code with description length k(h) bits; the Occam / MDL bound turns each hypothesis's code length into a per‑hypothesis generalization guarantee that shrinks with k(h). Rendered, not quoted.

source Blumer, Ehrenfeucht, Haussler & Warmuth, “Occam's Razor,” Inf. Proc. Lett. 24 (1987) 377–380 · Rissanen, MDL (1978). Classic result — cited by year, not paraphrased.

Blue Team · builds & defends

The Model

A hypothesis class H = {h₁, h₂, h₃, …}, possibly countably infinite. A prefix code assigns each h a codeword of length k(h) bits. No codeword is a prefix of another, so Kraft's inequality holds:

Σ_h∈H 2^−k(h) ≤ 1

Read 2^−k(h) as a prior on h. The Occam bound: with prob ≥ 1−δ, every h consistent with m samples satisfies

err(h) ≤ ( k(h)·ln2 + ln(1/δ) ) / m

Shorter code ⇒ smaller bound ⇒ fewer samples for the same guarantee. Simplicity is not aesthetic here — it is a shorter address in a fixed prior.

The Lineage

Compression is generalization. The prior 2^−k(h) is the learnable shadow of the-kolmogorov shortest‑program length — Kolmogorov complexity is uncomputable, but a fixed prefix code is a computable stand‑in that still buys a bound.

Downstream, this same 2^−k(h) prior is the penalty term behind the-maximum-a-posteriori: MAP maximizes log‑prior + log‑likelihood, i.e. −(description length + data misfit). MDL is MAP with a code‑length prior.

The Witness

Re‑checks the load‑bearing invariant live: Kraft holds for the current code, so the union bound sums to ≤ 1. If Red (6) rewrites a code length to break Kraft, this badge flips.

WITNESS — booting…

Σ 2^−k(h)—

Kraft ≤ 1 ?—

The Machine

Data In in ↓

A learning problem over 3‑bit instances x ∈ {0…7}, labels from target t(x) = x₀ XOR x₁. Six candidate rules of growing complexity, coded by the complete prefix code k(hᵢ) = i bits (Kraft = 1 exactly). Tune ε, δ, m below.

▼

The Panel LIT

Live engine — every number is computed from the code lengths and the real bound. Nothing is typed in by hand.

accuracy ε0.10

confidence δ0.05

samples m40

rule

k(h)

2^−k

m needed

Kraft Σ 2^−k(h)—

union bound = Kraft·(1−ε)^m—

shorter needs fewer m ?—

MDL pick = argmin(k + 2·misfit)—

data errors

k + 2·err

▼

Data Out out ↓

Proven result, set at boot after the self‑check passes:

—

The MDL winner is the shortest rule that fits — here h₄ = x₀ XOR x₁, the true target, with the smallest description‑plus‑misfit cost.

Red Team · attacks & breaks

The Adversary

wall The bound protects only against overfitting a short code. It is silent about three real walls:

Realizability. The guarantee err(h) ≤ … is for h consistent with the data. If no short h fits (target not in / near H), the razor selects the least‑bad short rule and the misfit term dominates — the bound says nothing about that residual.

Code choice is a prior. Whoever picks the prefix code picks which hypotheses are “short.” A malicious code makes your favourite overfit rule cheap. The theorem is only as honest as the assumed code.

Kraft is the whole load. Break Σ2^−k ≤ 1 and the union bound no longer sums to a probability — the guarantee is void. See window 6.

The Graveyard

~~“Simpler theories are more likely true.”~~ → No metaphysics. Shorter code = smaller prior mass to spread over δ, so it needs less data to certify — a sample‑complexity claim, not a truth claim.
~~“Fewer parameters ⇒ better generalization.”~~ → It is description length, not parameter count. A 1‑parameter rule with a real‑valued threshold can have huge k(h); a many‑bit boolean rule can be short.
~~“MDL always beats maximum likelihood.”~~ → Only when the code‑length prior matches the problem. Wrong code = wrong prior = the assumed penalty can underfit.
~~“The bound works because H is finite.”~~ → It works for countably infinite H too — Kraft, not cardinality, is what makes Σ2^−k finite.

The Tamper

planted void Rewrite one code length to violate Kraft: shorten h₂ from 2 bits to 1. Now two rules claim a length‑1 codeword — no valid prefix code — and Σ2^−k jumps to 1.25 > 1. The union bound stops being a probability; the Witness (7) catches it live.