Lecture 10: Evaluation of Language Models, Basic Smoothing

Main Ideas

1. Evaluating Language Models

A language model is useful when it assigns high probability to real, grammatical sentences and lower probability to implausible ones. Although this can be checked manually, it is impractical at scale. Instead, models are evaluated using data:

• Train a model on one part of a corpus.
• Test it on separate, unseen data.
• Use an evaluation measure to assess how well it predicts the test data.
• Compare models using the same test set.

The lecture distinguishes two kinds of evaluation:

• Extrinsic (task-based) evaluation: Use the language model in an application—such as spelling correction, speech recognition, or machine translation—and compare the application’s performance with different models. The model that improves task performance is preferred.
• Intrinsic evaluation: Assess the language model itself without embedding it in a downstream task. The main measure discussed is perplexity.

2. Perplexity

Perplexity measures how well a model predicts unseen text. The idea is related to the Shannon game: given a context, how well can a model predict the next word?

For a test sequence (w_1,\ldots,w_N), perplexity is:

[ \mathrm{PP}(w_1,\ldots,w_N) = P(w_1,\ldots,w_N)^{-1/N} ]

Using the chain rule, the sequence probability can be written as a product of next-word probabilities. The language model supplies those conditional probabilities using whatever context its n-gram assumption allows. Lower perplexity indicates better prediction; higher perplexity means the model is more uncertain.

For example, a model that assigns equal probability (1/10) to each of ten possible digits has a perplexity of 10. It is as uncertain as choosing uniformly among ten options at each position.

A Wall Street Journal experiment reported these test-set perplexities:

• Unigram: 962
• Bigram: 170
• Trigram: 109

The lower values for bigrams and trigrams indicate better predictions in that experiment. A perplexity of 962 can be interpreted roughly as uncertainty equivalent to choosing uniformly among 962 possibilities at each word position.

3. Generating Text from an N-Gram Model

A trained language model can generate text by sampling words from its probability distributions:

1. Sample the first word from the distribution for the start of a sentence.
2. Use the selected word—or the relevant preceding n-gram context—to choose a distribution for the next word.
3. Sample the next word and repeat.
4. Stop when the model produces the end-of-sentence marker.

The lecture illustrates how model order affects generated text:

• Unigrams produce individually common words but do not use context, so their sequences are generally incoherent.
• Bigrams capture local word pairings and can produce more plausible fragments, though sentences may still lack coherence.
• Trigrams and higher-order models can produce sequences that more closely resemble the training text.

For Shakespeare, the vocabulary contained about 29,066 tokens, making roughly 844 million possible bigrams, while only about 300,000 were observed. This illustrates how sparse n-gram data can be.

4. The Zero-Probability Problem and Smoothing

N-gram models estimated from counts assign probability zero to any n-gram not seen in the training data. This creates a serious problem: if even one test n-gram has probability zero, the probability of the entire test sequence becomes zero, and its perplexity cannot be computed meaningfully.

The lecture’s example considers the context “denied the.” In the training data, it is followed by “allegations,” “reports,” “claims,” and “request,” with counts of 3, 2, 1, and 1. If test examples include unseen continuations such as “offer” or “loan,” their estimated probabilities would be zero without smoothing.

Smoothing addresses this by shifting some probability mass away from observed events and assigning it to events not seen in training. The redistribution must preserve a total probability of 1.

Add-One (Laplace) Smoothing

Pretend that every possible n-gram occurred once more than it actually did. For a bigram model:

[ P(w_i \mid w_{i-1}) = \frac{C(w_{i-1},w_i)+1} {C(w_{i-1})+V} ]

Here, (C(w_{i-1},w_i)) is the bigram count, (C(w_{i-1})) is the context count, and (V) is the vocabulary size. The denominator increases by (V) because one is added for each possible next word.

Add-(k) Smoothing

The added count need not be 1. Add-(k) smoothing adds (k) to every possible n-gram count and (kV) to the denominator:

[ P(w_i \mid w_{i-1}) = \frac{C(w_{i-1},w_i)+k} {C(w_{i-1})+kV} ]

Setting (k=1) gives add-one smoothing.

Unigram-Prior Smoothing

Instead of spreading the added probability mass uniformly across the vocabulary, it can be distributed according to unigram probabilities. This gives more prior mass to words that are common in the corpus and less to rare words. The motivation is that a word’s overall frequency may provide a better estimate of its chance of occurring after a particular context than a uniform distribution does.

Effective Counts

The lecture also introduces effective n-gram counts: the counts that would produce the smoothed probability if interpreted as ordinary maximum-likelihood counts. Smoothing reduces the effective counts of observed events and gives positive effective counts to previously unseen events. The effective count assigned to an unseen continuation can vary with the context because the context’s total count affects the normalization.

Speakers and Sources Featured

• Speaker: An unnamed instructor delivering the lecture.
• Sources and examples mentioned: Shannon’s game of predicting the next word; the Wall Street Journal corpus; a Shakespeare corpus; and a restaurant corpus.