CONCEPT INDEXevery term, one place
Concept index
How to use this — the pages tell the story in order; this page is for when you already know the story and need the definition. Everything is in bits (base-2 logarithms) unless said otherwise. Throughout, p is the distribution reality draws from and q is the distribution your model asserts — keeping those two straight is most of the subject.
The five that matter
| Term | Definition | Reads as | Page |
|---|---|---|---|
| Information content surprisal |
I(x) = log₂(1/p(x)) = −log₂ p(x) | How surprised you should be by one outcome, in bits. Also the length of the code word an optimal encoder would spend on it. | P4 |
| Entropy H(p) |
H(p) = Σ p(x)·log₂(1/p(x)) | Average surprise. The floor on bits per symbol that no encoder can beat, and the yardstick for every compressor. | P6 |
| Cross-entropy H(p, q) |
H(p, q) = Σ p(x)·log₂(1/q(x)) | What you actually pay: q's prices at p's frequencies. Always at least H(p), equal only when q = p. | P9 · P10 |
| KL divergence D(p‖q) |
D(p‖q) = H(p, q) − H(p) = Σ p(x)·log₂(p(x)/q(x)) | The surcharge for being wrong — the bits you paid over the unavoidable minimum. Non-negative, zero only at q = p, asymmetric. | P15 |
| Perplexity | PP = 2^H (or e^H if H is in nats) | Entropy exponentiated back into "number of options". A perplexity of 20 means the model is as uncertain as someone choosing uniformly among 20 things. | P12 |
The one identity to carry: cross-entropy = entropy + KL. The first term is the cost reality imposes and no model can remove; the second is the cost your model adds. Training can only ever attack the second, which is why minimising cross-entropy and minimising KL are the same optimisation.
Coding and compression
- Code word — the bit string standing in for one symbol. P2
- Prefix-free code (also instantaneous or prefix code) — no code word is a prefix of another, so the receiver knows where each one ends without separators. Equivalently, the code words are the leaves of a binary tree. P2
- Kraft's inequality — a prefix-free code with lengths l₁, l₂, … exists if and only if Σ 2^(−lᵢ) ≤ 1. This is the budget that makes code length a zero-sum game: shortening one word forces another to lengthen. P2 · P8
- Source coding theorem (Shannon's noiseless coding theorem) — the average length L of any uniquely decodable code satisfies L ≥ H(p), and a code exists with L < H(p) + 1. Coding blocks of symbols pushes the gap towards zero. P6
- Huffman coding — the algorithm that builds the optimal per-symbol prefix code for a known distribution. Optimal among integer-length codes, which is why it can still sit above the entropy floor. P2
- Arithmetic coding — encodes a whole message as a single number in an interval, so it spends effectively fractional bits per symbol and reaches the entropy floor in the limit. This is the machinery that turns any probabilistic model, a language model included, into a compressor. P3 · P1
- Bits per character / bits per byte — cross-entropy per unit of raw text, the unit in which compressors and language models can be compared on the same axis. P5 · P12
- Nats — the same quantities with natural logs instead of base 2. Deep-learning frameworks report nats; divide by ln 2 ≈ 0.6931 to get bits. P12
Where it lands in machine learning
- Cross-entropy loss — with a one-hot target the sum collapses to −log q(correct token). That is the entire pre-training objective, and it is measured in bits (or nats) per token, which is to say in compressed file size. P12
- Softmax — the map from raw model outputs (logits) to a probability distribution q, so that there is something for cross-entropy to score. P12
- Proper scoring rule — a loss whose expected value is optimised by reporting your true beliefs. Strictly proper means uniquely so. Cross-entropy (the log score) is strictly proper, which is the formal reason it cannot be gamed by bluffing or hedging. P13
- Maximum likelihood — minimising cross-entropy against observed one-hot outcomes is exactly maximum likelihood estimation. Two vocabularies, one procedure. P13
- Distillation — replace the one-hot target with a teacher model's full distribution, so every vocabulary entry contributes to the sum and the student inherits the teacher's shape of uncertainty, not just its top answer. P14
- Forward vs. reverse KL — D(p‖q) punishes a model for assigning near-zero probability to things that happen, so it spreads out to cover every mode; D(q‖p) lets a model ignore modes, so it collapses onto one. Which direction you minimise decides which failure you get. P15
- Expected information gain — the entropy of the distribution over outcomes an action could produce; the score that picks a Wordle guess, and the same quantity that drives active learning and optimal experiment design. P16
The other side of the channel
- Parity bit — one bit recording whether the number of ones in a group is even or odd. Detects a single flip; cannot locate it. P19
- Hamming code — overlapping parity groups arranged so that the set of failing checks spells the binary index of the flipped bit. The (15,11) code carries 11 message bits in 15. P19
- SECDED — single error correction, double error detection: one extra whole-block parity bit upgrades the (15,11) code to (16,11) and lets it tell one flip from two. P19
- Syndrome — the pattern of failing parity checks, read as a number. In the one-line implementation it is just the XOR of the indices of every bit that is on. P20
- Noisy-channel coding theorem — Shannon's other 1948 result: every noisy channel has a capacity, and below it arbitrarily reliable transmission is possible. Compression removes redundancy; error correction adds a measured amount back. P19
Names and papers
- A Mathematical Theory of Communication — Claude Shannon (1948). Entropy, the source coding theorem and the noisy-channel coding theorem, all in one paper. The series is a rebuild of its first half.
- Prediction and Entropy of Printed English — Claude Shannon (1951). The guessing-game measurement of English, and the first clear statement that a language's entropy is only defined relative to a predictor.
- Visual Information Theory — Chris Olah (2015). The visual treatment Grant credits in the description of Part 1; the best companion reading for P9 and P10.
- Distilling the Knowledge in a Neural Network — Hinton, Vinyals and Dean (2015). The origin of the soft-target trick in P14.
- Richard Hamming — Bell Labs, late 1940s. The error-correcting codes of P19 and P20.
- Solomon Kullback and Richard Leibler — the 1951 paper that names the divergence in P15.