Information theory

Shannon’s account of how much information a message carries, how far it can be compressed, and how reliably it can be sent through a channel that corrupts it. The page exists in a machine-learning spoke for one reason: information-theory-inference-learning-algorithms argues the two subjects are one subject, and the corpus has no better home for the argument: no spoke in the hub owns information or coding theory.

The two problems

Compression. How few bits can represent a source without losing it. The answer is its entropy; the source coding theorem sets the floor and symbol and stream codes (Huffman, arithmetic coding) approach it.

Noisy-channel coding. How much can be sent through a channel that flips bits. MacKay opens on a disk drive rather than an abstraction: one flipping 10% of bits, against the roughly 10⁻¹⁵ error rate you need to read and write a gigabyte a day for ten years. Two responses are available.

• The physical solution buys incremental reliability at ever-increasing cost. Better components, an evacuated enclosure, larger magnetic patches, colder circuitry.
• The system solution accepts the channel as it is, adds an encoder and a decoder, and uses deliberate redundancy to infer both the message and the noise.

Shannon’s noisy-channel coding theorem says the second works, and says how far: reliable communication is possible at every rate up to the channel’s capacity and impossible beyond it. For that 10%-error channel capacity is about 0.53, so a rate-½ code reaches an arbitrarily small error rate with two noisy drives, where naive triple repetition needs sixty to do worse information-theory-inference-learning-algorithms.

Why it sits next to learning

MacKay’s claim is that compression, error correction and inference run on the same machinery, and his book’s structure is the argument:

• The decoder for a low-density parity-check code is the sum–product algorithm — belief propagation on a factor graph — which is the same message passing used to marginalize a probabilistic model. Optimal decoding is NP-complete; approximate inference is what makes the codes work.
• Compression is prediction. A code assigns short strings to what the model expects, so a better model of the source is directly a better compressor.
• Chapter 19 runs the accounting the other way, on evolution: natural selection’s teaching signal is at most one bit per offspring, since all it reports is whether an individual had more descendants or fewer.

The modern restatement, that a language model is a compressor, descends from this identity. That argument’s home spoke would be ../llm-inference-wiki, which has no page on it; the derivation stays here.

Scope note

This page covers only what the ingested book establishes and what bears on learning. Coding theory proper — hash codes, binary codes, turbo and fountain codes, constrained channels — is roughly half that book and is unowned across the hub. If more sources land on it, it wants its own spoke rather than growth inside this one.

Related

information-theory-inference-learning-algorithms · bayesian-inference · monte-carlo-methods · machine-learning · synthesis