Chapter 51
Mathematical Beauty as Minimum Description Length

Flow Algebra

flow "Mathematical Beauty as Minimum Description Length (MDL)"

# ---------- CONCEPT ----------
# 'Beautiful' theories are those that compress reality most: they explain much with little.
# Minimum Description Length (MDL) formalises this as: choose the model that minimises
# total code length = length(model) + length(data given model).
# Beauty = parsimony + predictive power = shortest faithful description (algorithmic elegance).

# ---------- STATES ----------
state MDLSystem(Ξ):
  Data:
    description: "x ∈ 𝒳^n — observations to be explained/compressed."
  ModelClass:
    description: "𝓜 = { M_θ : θ ∈ Θ } — candidate families (hypotheses, theories)."
  Codebook:
    description: "Prefix-free codes for models and for data given a model; satisfies Kraft inequality."
  DescriptionLengths:
    model_len: "L(M) — bits to specify model / parameters (complexity penalty)."
    data_len:  "L(x | M) — bits to encode data with model (residual complexity)."
  UniversalPrior (optional):
    description: "w(M) ∝ 2^{−L(M)} — Solomonoff/MDL prior; beauty favours shorter codes."
  AlgorithmicCore:
    description: "Kolmogorov complexity K(x): length of shortest program producing x (uncomputable ideal)."

# ---------- PARAMETERS ----------
params:
  sample_size: "n — number of observations."
  code_design: ["Two-part codes", "NML (stochastic complexity)", "Bayes/mixture codes"]
  penalty_form: ["BIC ~ (k/2)log n", "MDL via NML: L_NML(x) = −log p(x|θ̂(x)) + log C_n"]
  regularity: "Identifiability, Kraft inequality, prefix-freeness, Kraft sum ≤ 1"
  compressor: "Practical proxy for K(·): gzip/LZ/PPM/NN-based coder for NCD etc."

# ---------- INVARIANTS ----------
invariants:
  - "Total length: L_total(x,M) = L(M) + L(x|M)."
  - "MDL principle: choose M* = argmin_M L_total(x,M)."
  - "Kraft inequality: ∑_m 2^{−L(m)} ≤ 1 ⇒ codes ↔ (semi)measures."
  - "Shorter codes ↔ larger prior weight: w(M) ≍ 2^{−L(M)} (MDL–Bayes correspondence)."
  - "Asymptotics: MDL ≈ BIC = −log p(x|θ̂) + (k/2)log n + o(1)."
  - "No free lunch: average code length ≥ entropy; beauty must earn compression by capturing structure."
  - "Symmetry/compositionality reduce L(M) and L(x|M) via parameter sharing / invariances."
  - "Overfitting test: if L(M)↓ but L(x|M)↑ more ⇒ total length ↑ → penalised."

# ---------- TRANSFORMS (DESIGN & SELECTION) ----------
transforms:
  TwoPartCode(𝓜, x):
    rule: "Encode θ (or model index) with L(M), then encode x with optimal code under M ⇒ L_total."
  NMLCode(𝓜, x):
    rule: "Use normalized maximum likelihood: L_NML(x)=−log p(x|θ̂(x)) + log ∑_{y∈𝒳^n} p(y|θ̂(y))."
  BayesianCode(𝓜, x):
    rule: "L(x; prior w) = −log ∫ p(x|θ) w(θ) dθ; set w(θ) ∝ 2^{−L(θ)} for MDL–Bayes equivalence."
  ParametricPenalty(θ̂, n, k):
    rule: "Approximate L_total ≈ −log p(x|θ̂) + (k/2) log n (BIC) for regular models."
  CompressionProxy(x, M):
    rule: "Use off-the-shelf compressor to estimate L(x|M) by encoding residuals; use code length as score."
  StructureSearch:
    rule: "Add symmetries/constraints/low-rank/sparsity; accept only if ΔL_total<0."
  ModelAveraging:
    rule: "Mixture codes: L(x) = −log ∑_M 2^{−L(M)} p(x|M) — implicit Occam weighting."

# ---------- MONITORS (BEAUTY METRICS) ----------
monitors:
  TotalDescriptionLength:
    measure: "L_total(x,M)"
    goal: "Minimise; beauty = shorter yet faithful."
  Regret (StochasticComplexity):
    measure: "L_NML(x) − (−log p(x|θ*))"
    meaning: "Gap to oracle; smaller is better."
  PredictiveLogLoss:
    measure: "−∑_t log p(x_t | x_{<t}, M)"
    link: "Prequential MDL; beauty predicts well with few bits."
  CompressionRatio:
    measure: "CR = L_total / (n·baseline_bits)"
    target: "CR < 1 indicates genuine structure captured."
  StabilityUnderRefinement:
    test: "Does M* persist as n↑? Is ΔL_total robust to resampling?"
  NCD_Beauty:
    measure: "NCD(x,y) = (C(xy)−min{C(x),C(y)})/max{C(x),C(y)}"
    use: "Detect elegant unifications across datasets by compression proximity."

# ---------- EQUATIONS ----------
equations:
  - "L_total(x,M) = L(M) + L(x|M)"
  - "M^* = \\arg\\min_M L(M) + L(x|M)"
  - "K(x) = \\min_{\\text{program }p: U(p)=x} |p|  \\quad (\\text{uncomputable ideal})"
  - "w(M) \\propto 2^{-L(M)}"
  - "BIC(M) = -\\log p(x|\\hat{\\theta}) + \\tfrac{k}{2}\\log n"
  - "Solomonoff prior: P(x) \\propto 2^{-K(x)}"
  - "\\text{MDL} \\approx \\text{MAP with prior } w(M) \\propto 2^{-L(M)}"
  - "I(X;Y) = L(X)+L(Y)-L(X,Y) \\quad (\\text{compression gain as mutual info})"

# ---------- NOTES ----------
notes:
  - "A theory is 'beautiful' when its code for itself (L(M)) is small *and* its residual code L(x|M) is tiny — simple rules with big explanatory reach."
  - "Symmetry, sparsity, low rank, and compositional reuse are compression mechanisms; they collapse description length by sharing parameters."
  - "MDL operationalises Occam’s razor without metaphysics: shorter codes win when (and only when) they compress the data."
  - "Kolmogorov complexity defines the Platonic limit of beauty; MDL gives a computable, statistical proxy via codes and likelihoods."
  - "AIC rewards out-of-sample fit; BIC/MDL reward parsimony at O((k/2)log n). Prefer MDL when the goal is explanatory economy and long-run predictivity."
  - "In practice: compare models by bits, not aesthetics. The most beautiful proof is the shortest correct program that reproduces the phenomenon."
  - "In Flow Algebra, beauty = **coherent compression**: the minimal message that preserves maximal structure, aligning theory and data by the shortest faithful path."