Information Theory, Inference, and Learning Algorithms

David J.C. MacKay‘s textbook, published by cambridge-university-press in September 2003 and left permanently readable on the author’s site. The held copy is version 7.2, the fourth printing, dated 28 March 2005: 640 PDF pages, 50 chapters in seven parts. The copyright line permits on-screen viewing and forbids printing.

It is the first source in this spoke that is a textbook rather than a codebase, a vendor post or a catalog, and the first with any claim to being foundational rather than current.

The argument the book is built on

MacKay states it in the preface, and the whole structure follows from it:

“Why unify information theory and machine learning? Because they are two sides of the same coin. In the 1960s, a single field, cybernetics, was populated by information theorists, computer scientists, and neuroscientists, all studying common problems. Information theory and machine learning still belong together. Brains are the ultimate compression and communication systems. And the state-of-the-art algorithms for both data compression and error-correcting codes use the same tools as machine learning.”

So the book runs conventional Shannon material and Bayesian data modelling through the same machinery, with information-theory on one side and bayesian-inference on the other, and monte-carlo-methods and message passing as the shared computational tools. The claim is not that the two subjects are adjacent; it is that they are the same subject seen twice.

What’s in it

Seven parts, and roughly half the page count is coding theory that no spoke in this hub owns:

Exercises carry a Knuth-style 1–5 difficulty rating and many have worked solutions in the text; MacKay marks the recommended ones in the margin and flags the ones needing a computer. Four course roadmaps are printed in the preface, including his own Cambridge course Information Theory, Pattern Recognition, and Neural Networks and a standalone Course on Bayesian Inference and Machine Learning. The book is assembled so the ML half can be taught without the coding half.

What it gives this wiki

Learning is inference, and the loss function is a likelihood. Chapter 41 takes the objective a neural network minimizes, M(w) = G(w) + E_W(w), and reads the two terms probabilistically: the error function is minus the log likelihood, P(D|w) = exp(−G(w)), and the quadratic regularizer is a log prior, specifically a Gaussian over the weights with variance 1/α. Minimizing the objective therefore locates the most probable parameter vector, not merely a good one. Error functions add and probabilities multiply, and the log is what reconciles them. See bayesian-inference.

The output of learning is an ensemble, not a point. MacKay’s sharpest framing: “The product of traditional learning is a point in w-space, the estimator w*… In contrast, in the Bayesian view, the product of learning is an ensemble of plausible parameter values.” Everything else in Part IV — Laplace’s method, Monte Carlo, variational bounds — exists because that ensemble is usually intractable to write down.

Model complexity is priced automatically. Chapter 28 argues Occam’s razor needs no separate justification: a complex model must spread its predictive probability P(D|H) more thinly across data space, so the evidence term in Bayes’ theorem penalizes it without anyone adding a penalty. “Coherent inference (as embodied by Bayesian probability) automatically embodies Occam’s razor, quantitatively.”

Redundancy beats better hardware. Chapter 1 opens on a noisy disk drive rather than an abstraction: a drive flipping 10% of bits, against the ~10⁻¹⁵ error rate you need to read and write a gigabyte a day for ten years. The physical fix is better components, vacuum, bigger magnetic patches, all of which cost more. The system fix adds an encoder and a decoder and accepts the channel as it is. Shannon’s capacity for that channel is about 0.53, so a rate-½ code gets there with two noisy drives where naive triple-repetition needs sixty.

Coding and inference use one algorithm. The decoder for a low-density parity-check code (chapter 47) is the sum–product algorithm — belief propagation on a factor graph — the same message passing used for marginalization in chapter 26. Optimal LDPC decoding is NP-complete; what makes the codes practical is that approximate inference works well enough.

And one chapter is pure information accounting on biology. Why have Sex? (ch. 19) treats natural selection as a teaching signal and bounds it: an individual either has more grandchildren or fewer, so selection conveys at most one bit per offspring, and those bits are highly redundant across a species.

Tier, age, and what has dated

• T1. A university-press textbook by a working researcher in the subject: chapter 47 cites MacKay’s own 1999 LDPC results alongside Gallager (1963). Derivations are shown rather than asserted, and the exercises come with solutions, so the claims are checkable inside the book.
• Twenty-three years old, and the two halves have aged very differently. The information theory and the Bayesian inference are mathematics and have not moved. Part V has. It is a 1990s Bayesian-neural-network account — single-neuron capacity, Hopfield networks, Boltzmann machines, Gaussian processes as the successor to multilayer perceptrons — written a decade before the scaling era. Nothing here on ReLUs, batch normalization, attention, or training at scale. Read Part V as the probabilistic interpretation of network training, not as current practice.
• Not an engineering source. This spoke treats machine-learning as an engineering discipline, and the book is squarely theory: no data pipelines, no deployment, no cost. It answers why does fitting work, never what will it cost to run.
• The GNU Ghostscript-produced PDF carries no author metadata; the version, printing and date come from the title verso. Held at raw/mackay-itila.pdf; the arriving URL had a Facebook click tracker attached, and the canonical address is inference.org.uk/itprnn/.
• MacKay dedicates the book “to the campaign against the arms trade” and thanks the Royal Society, Darwin College, university-of-cambridge and the Gatsby Charitable Foundation for supporting its ten-year gestation.

Cross-spoke context

Routed here whole rather than split, on the ML-and-inference substance. The rest is noted, not duplicated:

• No spoke owns information and coding theory. Parts I, II, III and VI — compression, channel capacity, LDPC and fountain codes — are roughly half the book and have no home in the hub’s 30 spokes. information-theory exists here because this book made it inseparable from the inference material, not because this spoke claims coding theory. Flagged for the router.
• ../optimization-algorithms-wiki — chapters 29–32 are the Monte Carlo tradition (importance and rejection sampling, the Metropolis method, Gibbs, slice sampling) that spoke’s simulated-annealing page descends from. The standing homonym warning applies in the usual direction: MacKay’s samplers explore a posterior, not an objective landscape with no gradient.
• ../llm-inference-wiki — the compression-equals-prediction identity in Part I is the ancestor of every argument that a language model is a compressor. That spoke owns serve-time mechanism and has no page on it; the identity stays here with its derivation.

Related

information-theory · bayesian-inference · monte-carlo-methods · david-mackay · cambridge-university-press · university-of-cambridge · machine-learning · classical-ml-algorithms · synthesis