Information Theory

Claude Shannon's 1948 paper "A Mathematical Theory of Communication" opens by noting that the "fundamental problem of communication is that of reproducing at one point either exactly or approximately a message selected at another point," and to solve it he needed a way to quantify how much information a message actually carries. His answer was entropy: for a discrete random variable X with outcomes x taking probability p(x), the entropy is H(X) = −Σ p(x) log₂ p(x), measured in bits when the logarithm is base 2. Shannon frames this quantity as measuring "how much choice is involved in the selection of the event or of how uncertain we are of the outcome" — a rare, unlikely outcome carries more information (a larger −log p(x) term) than a common, expected one, and entropy is simply the probability-weighted average of that surprise across every possible outcome. This single formula, borrowed in form from statistical mechanics, became the founding equation of information theory and now underlies data compression, cryptography, and the loss functions used to train modern classifiers.

A worked example makes the formula concrete. A fair coin flip has two equally likely outcomes, p(heads) = p(tails) = 0.5, so H = −(0.5·log₂0.5 + 0.5·log₂0.5) = −(0.5·(−1) + 0.5·(−1)) = 1 bit: exactly enough uncertainty to be resolved by a single yes/no question, which is why a fair binary choice is the canonical unit of one bit. Now consider a four-symbol alphabet {A,B,C,D} with probabilities 0.5, 0.25, 0.125, 0.125 — a skewed distribution typical of natural-language letter frequencies. Its entropy is H = −(0.5·log₂0.5 + 0.25·log₂0.25 + 0.125·log₂0.125 + 0.125·log₂0.125) = 0.5(1) + 0.25(2) + 0.125(3) + 0.125(3) = 1.75 bits. Notice this is lower than the 2 bits a naive fixed-length code would need for four symbols, because the skew toward A makes the source more predictable — and, as the next paragraph shows, more compressible.

Two properties of entropy matter for everything downstream. First, entropy is maximized when a distribution is uniform (all outcomes equally likely) and falls to zero when one outcome is certain (p = 1) — uncertainty is highest when you have the least information to go on, and lowest when the outcome is already known. Second, Shannon's source coding theorem, a core topic in MIT's graduate information theory sequence alongside related results on lossless and lossy compression, establishes entropy as the theoretical lower bound on the average number of bits needed to encode symbols drawn from a source without loss, which is exactly why compression schemes like Huffman coding target codeword lengths close to −log₂ p(x) for each symbol. The skewed four-symbol example above can in fact be losslessly compressed to an average of exactly 1.75 bits per symbol, matching its entropy exactly, by assigning shorter codewords to the more probable symbol A and progressively longer codewords to the rarer symbols B, C, and D — a direct illustration of how uncertainty and compressibility are two names for the same underlying quantity.

Entropy measures the uncertainty in one true distribution p; cross-entropy measures the cost of using an approximate distribution q to describe outcomes actually drawn from p, defined as H(p,q) = −Σ p(x) log q(x). Because H(p,q) is minimized exactly when q equals p, and the gap H(p,q) − H(p) is the Kullback-Leibler divergence — a nonnegative measure of how far q strays from p, equal to zero only when the two distributions coincide — cross-entropy is the natural loss function for training a classifier: if p is the true label distribution (e.g., a one-hot vector marking the correct class as probability 1 and every other class as probability 0) and q is the model's predicted probability distribution over classes, minimizing cross-entropy loss during training is mathematically equivalent to pushing the model's predictions toward the true labels, since driving H(p,q) down necessarily drives the KL divergence toward zero. This is why "cross-entropy loss" is the default training objective for logistic regression and neural network classifiers alike, a direct descendant of the same entropy formalism Shannon introduced for an entirely different problem — measuring information in a communication channel.

Mutual information asks a different question: how much does knowing one variable Y reduce your uncertainty about another variable X? It is defined as I(X;Y) = H(X) − H(X|Y), where H(X|Y) is the conditional entropy — the remaining uncertainty in X once Y is known — and the quantity is symmetric: I(X;Y) = I(Y;X), so the reduction in uncertainty runs equally in both directions. A worked example: suppose X and Y are both binary with joint probabilities P(X=0,Y=0)=0.4, P(X=0,Y=1)=0.1, P(X=1,Y=0)=0.1, P(X=1,Y=1)=0.4, so each marginal is 50/50 and H(X) = H(Y) = 1 bit. The joint entropy works out to H(X,Y) = −(2·0.4·log₂0.4 + 2·0.1·log₂0.1) ≈ 1.722 bits, so I(X;Y) = H(X) + H(Y) − H(X,Y) ≈ 1 + 1 − 1.722 ≈ 0.278 bits: knowing Y tells you a modest but nonzero amount about X, reflecting the fact that X and Y tend to agree (both 0 or both 1) more often than chance would predict. Had X and Y instead been statistically independent, the joint entropy would equal exactly H(X)+H(Y)=2 bits and mutual information would fall to zero, confirming that I(X;Y)=0 precisely characterizes independence.

Information gain, the criterion used to grow decision trees in algorithms descending from Quinlan's ID3, is mutual information applied to a specific choice: given a labeled dataset and a candidate splitting feature, information gain is the entropy of the labels before the split minus the weighted average entropy of the labels within each branch after splitting on that feature. A tree-building algorithm greedily picks, at each node, whichever feature maximizes this quantity — the feature that most reduces label uncertainty — and repeats the process recursively within each resulting branch until the labels in a branch are pure (entropy zero) or some stopping rule is reached. This is precisely why entropy and mutual information, quantities Shannon defined in 1948 for the engineering problem of communication over a noisy channel, ended up decades later as the backbone of a completely different discipline, supervised machine learning, where the "channel" is a dataset and the "message" being decoded is the class label.