N-gram Language Models

3.7 Perplexity and entropy

1. Define the entropy of a random variable \(X\).
   \(H(X) = -\sum_{x} p(x)\log_2 p(x)\), measured in bits with log base 2. It is a lower bound on the average number of bits needed to encode outcomes in an optimal code.
   • Jurafsky & Martin, Speech and Language Processing, 3rd ed. draft, ch. 3, §3.7, p. 85
2. In the horse-race example, why can an 8-horse bet be sent in 2 bits on average rather than 3?
   With probabilities ½, ¼, ⅛, 1/16 and four horses at 1/64, the entropy is 2 bits: give probable horses short codes (0, 10, 110, …) and improbable ones long codes. With equally likely horses the entropy is \(\log_2 8 = 3\) bits.

   • Jurafsky & Martin, Speech and Language Processing, 3rd ed. draft, ch. 3, §3.7, pp. 85–86
3. What is the entropy rate of a language?
   The per-word entropy in the limit of infinitely long sequences: \(H(L) = \lim_{n\to\infty} \frac{1}{n} H(w_{1:n})\).
   • Jurafsky & Martin, Speech and Language Processing, 3rd ed. draft, ch. 3, §3.7, p. 86
4. What does the Shannon–McMillan–Breiman theorem let us do?
   For a stationary and ergodic process, estimate the entropy rate from a single long-enough sequence: \(H(L) = \lim_{n\to\infty} -\frac{1}{n}\log p(w_{1:n})\), instead of summing over all sequences.
   • Jurafsky & Martin, Speech and Language Processing, 3rd ed. draft, ch. 3, §3.7, p. 87
5. What is a stationary process, and is natural language one?
   One whose probabilities are invariant to shifts in the time index. n-gram (Markov) models are stationary; natural language is not, since upcoming words can depend on arbitrarily distant context. So our entropy estimates are approximations.
   • Jurafsky & Martin, Speech and Language Processing, 3rd ed. draft, ch. 3, §3.7, p. 87
6. What is cross-entropy, and why is it useful?
   \(H(p, m)\): the entropy of data drawn from the true distribution \(p\) measured with log probabilities from a model \(m\). We can estimate it from a long sample, \(-\frac{1}{n}\log m(w_{1:n})\), without knowing \(p\).
   • Jurafsky & Martin, Speech and Language Processing, 3rd ed. draft, ch. 3, §3.7, p. 87
7. What is the relation between cross-entropy and the true entropy?
   \(H(p) \le H(p, m)\) for any model \(m\): cross-entropy is an upper bound. The more accurate the model, the closer the bound; between two models, the one with lower cross-entropy is better.
   • Jurafsky & Martin, Speech and Language Processing, 3rd ed. draft, ch. 3, §3.7, p. 87
8. How is perplexity formally defined in terms of cross-entropy?
   \(\text{Perplexity}(W) = 2^{H(W)}\), where \(H(W) = -\frac{1}{N}\log_2 P(w_1 \ldots w_N)\). This equals \(P(w_1 \ldots w_N)^{-1/N}\), which explains the inverse probability.
   • Jurafsky & Martin, Speech and Language Processing, 3rd ed. draft, ch. 3, §3.7, p. 88