From Kolmogorov to Free Energy: Data Compression as a Common Problem for AIT, MDL, Bayes, and the FEP

Four major inference frameworks — AIT, MDL, Bayes, and the Free Energy Principle — are the same compression problem viewed under progressively relaxed constraints on what the compressor is allowed to be.

The core intuition is simple: a "model" is really just a program that compresses data. If your model is good, it absorbs the structure in the observations and leaves behind a residual that looks like noise — nothing left to exploit. Shannon showed that probability and codelength are the same thing (short code ↔ high probability). Kolmogorov complexity is just the ultimate version of this: the shortest program that reproduces the data, full stop. The paper's move is to hold that compression framing fixed and show that MDL, Bayes, and the Free Energy Principle (FEP) are successive relaxations of the same ideal, each one trading some optimality for tractability.

The hierarchy works like this. Kolmogorov complexity (AIT) asks for the globally shortest program — perfect, but uncomputable. MDL makes it operational: restrict to a computable family of candidate compressors, then pick the one minimizing model-description-length plus residual-description-length. Bayesian inference softens that hard pick into a weighted mixture over all candidate compressors, which provably achieves a shorter code than any single choice. Variational free energy (the FEP's mathematical engine) then approximates that mixture when exact Bayesian averaging is itself too expensive — you optimize over a tractable family of distributions q(z) instead. The paper shows these aren't just analogies: point-mass q recovers MDL exactly, unconstrained q recovers exact Bayes, and restricted q gives variational Bayes. The "bits-back" interpretation makes the entropy term in the free energy concrete: it's the number of model-index bits the decoder can recover, not a formal regularizer inserted by hand.

One practically useful clarification the paper makes explicit: a probabilistic model isn't a separate kind of thing from a compressor. Pair any probability law with an arithmetic coder and you have a lossless compressor; the negative log-likelihood is literally the codelength. This dissolves a lot of apparent distance between "statistical modeling" and "data compression." The paper also pins down what successful modeling means in residual terms: for a stochastic model, success isn't small numerical error — it's innovations (normalized residuals) that are white, meaning no remaining temporal structure a better model could exploit.

The paper is explicit that its contribution is organizational rather than theorem-level — the individual bridges (Shannon, Solomonoff/Levin, Rissanen, Hinton/Zemel, Friston) are classical results. What it adds is a single executable reading that keeps the compressor object visible at every stage, and connects to the companion paper WP0017 (Navigating Complexity), where a resource-limited agent facing this compression problem is shown to naturally derive probabilistic inference and an Occam prior. A brief section on sequential model revision notes that switching compressors is worth it exactly when the compression gain on past data exceeds the information cost of the switch — a clean algorithmic payoff condition.