Information Theory in One Sitting

Sign in<br>Subscribe

In Posts 3 and 4 we built the probabilistic foundations and learned how to update beliefs with Bayes' rule. Now we put that machinery to work on a concrete question: how much information is actually in a piece of text? This post measures that quantity on WikiText-2, a two-million-token slice of Wikipedia, and ends with a number that quantifies how predictable English really is. By the time we finish, we will have watched the cost of encoding a token fall from 15.99 bits under a uniform guess to 8.39 bits with a bigram model, and we will understand every step between those two extremes. A token is one lowercase word here, and a bigram model predicts each token from the previous token alone.<br>The through-line of this post is a simple one: information is a budget. Every token in a text costs bits to transmit, and the whole game of language modeling is spending fewer bits than a naive encoding would. We start with the cheapest possible accounting, the entropy of a single token, and work our way up to the conditional models that actually predict words. Along the way we meet the tools that connect raw counts to real predictions: cross-entropy, KL divergence, Jensen-Shannon divergence, and mutual information. Each one tightens our accounting by a different mechanism, and each one pays off when we finally measure bits per token on held-out data.<br>The Data<br>WikiText-2 comes from Hugging Face with train, validation, and test splits already separated, which is exactly what we need for honest evaluation. The train split holds 36,718 documents and about 1.76 million tokens after a simple lowercase word tokenizer. The validation and test splits are smaller, 184,069 and 207,136 tokens respectively, and they share no documents with the training set. That clean separation matters: when we measure a model on validation, we are measuring generalization, not memorization.<br>Plotting token frequency against rank on log-log axes produces a nearly straight line, the classic Zipf curve. A handful of tokens dominate: the most common token, "the", appears with probability 0.0744, meaning it accounts for roughly one token in thirteen. The vocabulary is large, 64,916 distinct tokens, but the distribution over it is anything but uniform. That skew is the first hint that information is cheaper than a naive count would suggest.<br>The second finding is more practical. When we check the validation split against the training vocabulary, we find a substantial out-of-vocabulary rate. A fixed-vocabulary model needs an token to absorb those unseen words, and it needs smoothing to keep every probability nonzero.<br>Entropy<br>The OOV problem is about tokens the model has not counted. Entropy is the baseline for the tokens it has counted. Entropy is the first topic, and it answers the simplest version of our budget question: how many bits does one token cost on average? For a uniform distribution over V tokens, the answer is log2 V bits. With 64,917 tokens in our closed vocabulary (the fixed list of tokens the model can emit), that baseline sits at 15.9863 bits per token. But our distribution is not uniform, and the Zipf curve tells us why.<br>The empirical entropy of the training tokens comes to 10.9438 bits per token. The skew of the frequency distribution saves us 5.04 bits compared to a fair draw from the whole vocabulary. That is the first payoff of the Zipf curve: a few frequent tokens make token prediction easier than a uniform guess would suggest. The dominant token's share buys much of that saving, while the long tail of rare words contributes less to the average cost than their sheer number might imply.<br>def empirical_entropy(counts):<br># Average surprise of one token under the observed distribution.<br>total = sum(counts.values())<br>return -sum((count / total) * math.log2(count / total) for count in counts.values() if count > 0)<br>The entropy calculation is a sum over all tokens of probability times log probability, negated. It is the average number of bits a perfect encoder would spend per token, and it is the floor that no model can beat. Everything we do from here on is an attempt to approach that floor with a model that does not know the true distribution.<br>Cross-Entropy<br>Cross-entropy is the second topic, and it measures what happens when we use the wrong distribution to encode the right one. The formula is the same shape as entropy, but the log probability comes from a model Q while the averaging happens under the data distribution P. If Q assigns zero probability to any token P can produce, the cost is infinite.<br>That is exactly what happens when we try to encode the training distribution using the raw validation counts. The validation split does not contain every training token, so the naive cross-entropy comes back as infinity. The fix is add-one smoothing, which gives every vocabulary token a small probability floor. With smoothing, the cross-entropy between train and validation lands at 11.3583...