Information theory measures uncertainty. Its central quantity, entropy, says how unpredictable a random variable is, in a unit, the bit, that turns out to count the binary digits needed to record its outcomes. Shannon (1948) built the theory to find the limits of communication. Statistics and machine learning use the same quantities for other purposes: to score a probabilistic model against data, to say how far one distribution is from another, and to measure how much one variable tells about a second.
Those uses are spread across this site. A language model is trained by minimizing a cross-entropy (the bigram language model). A decision tree chooses the split with the largest information gain (Classification Trees). Terms are selected for a classifier, and clusterings are scored, by mutual information (feature selection, evaluating clusterings). Topic models are compared by perplexity (Evaluating Topic Models), posting lists are compressed with codes whose lengths are surprisals in disguise (Index Compression), and an evolution strategy measures its steps by a Kullback–Leibler divergence (natural evolution strategies). Each of those pages defines what it needs and moves on. This unit is the common ground beneath them: one set of definitions, with the properties proved once.
What the unit assumes
The unit needs discrete probability at the level of the Probability and Theoretical Probability Distributions units of the applied course: mass functions, joint and conditional probability, independence and expectation. From the Probability Theory unit it uses expectation (Expectation, Variance and Covariance), Jensen's inequality (Probability Inequalities) and the law of large numbers (The Laws of Large Numbers). It meets the Likelihood and Estimation unit at one point that matters to both: the cross-entropy loss of a model on a sample is its average negative log-likelihood, so maximum likelihood is the minimization of a divergence. The last two articles need densities and integrals.
Conventions
The articles share one notation.
- Random variables are capitals, $X$ and $Y$, on finite alphabets. Probability mass functions are lowercase: $p$ for the distribution that produces the data and $q$ for a model of it.
- $H(X)$ or $H(p)$ is entropy; $H(X, Y)$ and $H(Y \mid X)$ are joint and conditional entropy; $H(p, q)$ is the cross-entropy of the model $q$ under $p$; $D(p \,\|\, q)$ is the Kullback–Leibler divergence; $I(X; Y)$ is mutual information; $h(X)$ is differential entropy.
- $\log$ without a base stands for any fixed base and is used only in statements that hold in every base. Bits ($\log_2$) are used for codes, for decision trees and for tables of counts, in agreement with the course pages on feature selection and trees. Nats ($\ln$) are used for losses and likelihoods, in agreement with PyTorch's
F.cross_entropyand the language model pages, and wherever calculus is done. Every number is given with its unit. One nat is 1.4427 bits. - $0\log 0$ is taken as 0, and a model that gives probability 0 to an outcome that occurs has infinite cross-entropy and divergence.
Two datasets run through the unit. The Tiny Shakespeare text of the language model walkthrough, 1,115,394 characters over an alphabet of 65, supplies distributions of characters, pairs and longer blocks, and the losses of the walkthrough's models. The Reuters-21578 training stories of the information retrieval course supply tables of terms against classes.
What is proved and what is cited
Every property of entropy, divergence and mutual information that the unit states is proved on the page, for finite alphabets. Almost all of the proofs rest on two tools, the inequality $\ln x \le x - 1$ and the chain rule; a few also use Taylor's theorem, limits of sequences, or Jensen's inequality. Shannon's theorem that three requirements determine the entropy formula is proved in full. Kraft's inequality and the source coding bound are proved. The last two articles treat variables with densities, saying which of the discrete results carry over, and derive the maximum entropy distributions.
In the first three articles, four things are cited and not proved: Shannon's noisy channel coding theorem; the large-sample chi-squared distribution of the likelihood ratio statistic (Wilks's theorem, which belongs to Likelihood Ratio, Wald and Score Tests); the quadratic form of the divergence in the Fisher information matrix for several parameters and for densities (proved here for one parameter on a finite alphabet); and Jensen's inequality and the law of large numbers, which are proved in the Probability Theory unit. The last three articles cite, in addition: the entropy rate of sources with memory and the Shannon–McMillan–Breiman theorem, and the two-bit bound for arithmetic coding (Perplexity and Source Coding); the general form of the limit of binned entropy, divergence and mutual information outside the class of joint densities treated, the formulas for random vectors, and the first-order bias of an entropy computed from counts, to which Mutual Information also points (Differential Entropy and the Gaussian); and the conditional form of the equivalence of maximum entropy and maximum likelihood (Maximum Entropy Distributions). Each article has a section saying exactly what it proves, what it cites and what its experiment shows, and that section is the authority.
Numbers are computed by scripts kept with the site's source (tools/experiments/statistics/), which assert every figure shown. The entropies of the text are exact descriptions of one file. They are not estimates of the entropy of English, and three of the articles show by experiment how estimates from counts go wrong when the counts are thin: the entropy of long contexts in Entropy, the floor of a short validation text in Cross-Entropy and Kullback–Leibler Divergence, and the mutual information of independent variables in Mutual Information.
Articles
In reading order. Each article ends with worked problems solved in full.
- Entropy: surprisal and its average; bits and nats; the bounds zero and the logarithm of the alphabet size; joint and conditional entropy and the chain rule; why conditioning lowers entropy only on average; grouping and concavity; and a full proof of Shannon's theorem that three requirements leave no other formula. A character of the text has 4.7794 bits of entropy, and 3.5383 bits given the character before it.
- Cross-Entropy and Kullback–Leibler Divergence: what a model pays for wrong probabilities. Gibbs' inequality proved two ways; the cross-entropy loss shown to be the average negative log-likelihood, so that maximum likelihood is minimum divergence from the data; the asymmetry of the divergence and its two directions; its relation to the chi-square statistic and to Fisher information.
- Mutual Information: the divergence of a joint distribution from independence. Its equivalent forms and bounds, conditional mutual information and the chain rule, and the data processing inequality with its case of equality, applied to feature selection, information gain and the evaluation of clusterings.
- Perplexity and Source Coding: why entropy is a number of bits. Kraft's inequality, the source coding bound, Shannon's and Huffman's codes, and perplexity as an exponentiated cross-entropy, measured for the character and token models of the text.
- Differential Entropy and the Gaussian: entropy for a variable with a density, and which properties of discrete entropy survive. Why it can be negative and depends on the unit of measurement, its relation to the entropy of a finely binned variable, Gibbs' inequality for densities, the divergence between two normal densities, and the normal as the density of greatest entropy for its variance.
- Maximum Entropy Distributions: the most uncertain distribution that satisfies given constraints. The general theorem that the maximizer has exponential form, the uniform, geometric, exponential and normal distributions as its cases, and the link to exponential families and the softmax function.
Where the unit leads
Later units of the collection, planned and not yet written, start from results proved here. Prediction Error and Model Choice derives the Akaike information criterion from the divergence of the second article. Statistics of Model Evaluation treats the log score, which is that article's cross-entropy, as a proper scoring rule. Generalized Linear Models takes up the exponential families that the maximum entropy article arrives at, and Bayesian Inference uses the reverse direction of the divergence in variational inference.
References
- Cover, T. M., and Thomas, J. A. (2006). Elements of Information Theory, 2nd edition. Wiley. record · 8 pages
- Kullback, S., and Leibler, R. A. (1951). On information and sufficiency. The Annals of Mathematical Statistics, 22(1), 79–86. record · 2 pages
- MacKay, D. J. C. (2003). Information Theory, Inference, and Learning Algorithms. Cambridge University Press. record · 5 pages
- Shannon, C. E. (1948). A mathematical theory of communication. Bell System Technical Journal, 27(3), 379–423, and 27(4), 623–656. record · 6 pages