Predicting the Next Word with n-grams

Predict the next word from a short window Lec 2 · Aug 27 · recapped Lec 3 · Sep 1

Suppose the last word is want. A simple model could look at all the times want appeared in its training text, count what came next, and use those counts to predict the next word. It would not need to remember the whole sentence.

This is the idea behind an n-gram model. It applies the Markov assumption using a window of \(n\) words, including the word being predicted. To predict \(w_i\), it looks back at the previous \(n-1\) words.

The difference becomes visible when we ask these models to generate text. A unigram model can choose common words, but each choice ignores the words already chosen. The slides give this sample:

We can remember more words by moving to trigrams, 4-grams, 5-grams, and so on. Each step gives the model a longer context.

Some connections reach beyond the window

Consider “The computer which I had just put into the machine room on the fifth floor crashed.” The verb crashed belongs with computer, even though many words separate them. A short window cannot keep that connection in view.

Sentence structure can also lead a reader toward the wrong first interpretation. The slides use these garden-path sentences:

• “The complex houses married and single soldiers and their families.” Here, complex names a building complex, and houses is the verb.
• “The horse raced past the barn fell.” The horse that was raced past the barn is the one that fell.
• “The old man the boat.” Here, the old means older people, and man means to operate or staff.

These examples show why a short window is not a complete account of language. Even so, a small \(n\) can capture enough local patterns to be useful for particular tasks.

Turn bigram counts into probabilities Lec 2 · Aug 27

To estimate the chance that one word follows another, count how often the pair appears, then divide by how often the first word appears as a context. This is the maximum likelihood estimate:

What happens at \(i = 1\), where there is no previous word? Add a special beginning marker, <s>. Also add an end marker, </s>, so the model can predict that the sentence stops here. This lets \(P(W)\) describe sentences of different lengths; a proper probability distribution over finite sentences also requires the model to eventually stop with probability one.

<s> I am Sam </s>
<s> Sam I am </s>
<s> I do not like green eggs and ham </s>

A larger example: restaurant queries Lec 2 · Aug 27 · recapped Lec 3 · Sep 1

The Berkeley Restaurant Corpus contains 9,222 sentences about finding restaurants. Its queries include:

• “can you tell me about any good cantonese restaurants close by”
• “mid priced thai food is what i'm looking for”
• “tell me about chez panisse”
• “i'm looking for a good place to eat breakfast”
• “when is caffe venezia open during the day”

The slides work through three stages: count individual words, count word pairs, and divide the pair counts by the corresponding context counts. Here are the individual counts for the eight words shown in the slides:

In the bigram count table, the row identifies the previous word \(w_{i-1}\), and the column identifies the next word \(w_i\). Some of its entries are:

Most cells in the full table are zero: most possible n-grams never appear in the training text. For a pair that does appear, divide its count by the individual count for its row word. Using the slides' rounded values, \(P(\text{want} \mid \text{i}) = 827/2533 = 0.33\), \(P(\text{to} \mid \text{want}) = 0.66\), \(P(\text{eat} \mid \text{to}) = 0.28\), and \(P(\text{food} \mid \text{chinese}) = 0.52\).

Multiply the steps to score a whole sentence

What have the counts picked up?

The model only counted adjacent words, yet the resulting probabilities reflect several kinds of patterns:

• The topic of the corpus: \(P(\text{english} \mid \text{want}) = 0.0011\), compared with \(P(\text{chinese} \mid \text{want}) = 0.0065\). People in these queries ask about Chinese food more often.
• Grammar: \(P(\text{to} \mid \text{want}) = 0.66\), \(P(\text{eat} \mid \text{to}) = 0.28\), and \(P(\text{food} \mid \text{to}) = 0\). The counts favor common grammatical combinations, although a zero count alone does not prove a combination is impossible.
• How people frame a query: \(P(\text{i} \mid \text{<s>}) = 0.25\). Starting with “I” is common in this collection; this is a simple discourse pattern.

Use logarithms to avoid losing tiny probabilities Lec 2 · Aug 27

Multiplying many small probabilities can produce a number too small for the computer to represent. It may be rounded down to zero, a problem called numerical underflow. We avoid this by storing and adding log probabilities:

• The sum of the logarithms stays in a manageable numerical range even when the original product is extremely small.
• Once log probabilities are available, scoring a sequence uses additions instead of repeated multiplications. The slides note this computational convenience; numerical stability is the main reason to do it.