· 15 min read
NLP #4: N-gram Language Models
On this page
By the end of this post, you'll be able to compute the probability of a sentence from a handful of counts, and predict the next word the way your phone's keyboard does. A language model is the part of natural language processing (NLP) that does this: it gives a probability to each word that could come next. Section 3.1 of Speech and Language Processing starts with the simplest kind, the n-gram model. Its trick: look only at the last word or two, count, and divide.

Intuition
A language model scores what comes next
Type "i want a" on your phone and it suggests a few next words. A speech recognizer that hears "I scream" or "ice cream" picks the one people say more often in that spot. Both ask a language model the same question: how likely is each next word, given the words so far?
Our running example is a tiny training text of four café orders:
i want a coffee
i want a cake
you want coffee
i like cake
A tempting first idea: a sentence is likely when its words are common. But "coffee a want i" uses exactly the same words as "i want a coffee". Any score that only looks at the words, one at a time, gives both the same number. Order is the whole point, so a language model scores each word given the words before it.

Look only at the last word
The ideal model would look at the whole history: after "i want a", what comes next? To learn that from data, we'd count how often "i want a" appears and what follows it. That works for three words. For a whole paragraph it fails: almost every long history is new, even on the entire web, so its count is zero.
An n-gram model gives up on the full history and keeps only the last words. A bigram model () predicts "coffee" from "a" alone, and forgets "i want". A trigram model () keeps two words: "want a".
This is a bet that the last word carries most of the information, and for short-range patterns it often does. After "a" comes a noun; after "want" comes what you want.

Count and divide
Where do the numbers come from? Count. In our four orders, "want" is followed by something 3 times: by "a" twice and by "coffee" once. So the model says that after "want", the next word is "a" with probability and "coffee" with probability .
To score a whole sentence, add a start marker <s> and an end marker </s>,
then multiply the next-word probabilities along the way:
| Word | Given | Count | Probability |
|---|---|---|---|
| i | <s> | 3 of 4 | 3/4 |
| want | i | 2 of 3 | 2/3 |
| a | want | 2 of 3 | 2/3 |
| coffee | a | 1 of 2 | 1/2 |
</s> | coffee | 2 of 2 | 1 |
The product is . The end marker matters: it's the model's way of saying "the order is complete".
Here is the payoff of looking back only one word: "you want a cake" never appears in the training text, yet each of its word pairs does, so it gets probability . "coffee a want i" gets 0. Try your own sentences:
- P(i | <s>) = 3/4 = 0.750
- P(want | i) = 2/3 = 0.667
- P(a | want) = 2/3 = 0.667
- P(coffee | a) = 1/2 = 0.500
- P(</s> | coffee) = 2/2 = 1.000
P = 0.167, log P = -1.79
Next word
- </s>2/2

More context, more zeros
Why not look further back? Switch the widget to trigram. "i want a coffee" rises from to : with two words of context, the model knows that "i want" is always followed by "a" here.
But "you want a cake" drops to 0. The trigram "you want a" never occurs in the training text, so the model has no count for it. Longer context makes the model sharper on sentences it has seen and blind to new ones. Real systems use trigrams up to 5-grams, trained on billions of words, and still need fixes for zero counts (section 3.6, a later post).
Swap in a word the model has never seen, like "i want a tea", and every model gives 0. That's the same unknown word problem subword tokens solve for the vocabulary.

The math
The chain rule
Definition 1 (Language model). A language model assigns a probability to every sequence of words from a vocabulary , and a probability to each next word given the words before it.
Key equation (Chain rule). By the chain rule of probability, the two are the same thing:
It's exact, with no assumptions. For our order,
The problem is the last factors: their histories grow with the sentence.
The Markov assumption
Definition 2 (N-gram model). An n-gram is a sequence of words. An n-gram model makes the Markov assumption: the next word depends only on the last words,
is a unigram model (no context), a bigram model,
a trigram model. Each sentence gets start markers <s> in front and
one end marker </s> after it. The start markers give the first words a
context. The end marker lets the model say where a sentence stops, so the
probabilities of all sentences, of every length, sum to 1.
Key equation (Bigram sentence probability). Put the bigram assumption into the chain rule:
with <s>, and the end marker counted as the last word, </s>.
For "i want a coffee" () that's the five factors of the table above.

Maximum likelihood estimates
Definition 3 (MLE for n-grams). Let count how often the word sequence occurs in the training text. The maximum likelihood estimate (MLE) of a bigram probability is the count of the bigram divided by the count of its first word:
The sum counts every bigram that starts with , which is just the number of times is followed by something. The probabilities after each word then sum to 1. Of all ways to set the probabilities, these make the training text most likely, hence the name.
Key equation (N-gram MLE). For any , divide by the count of the context:
For our orders, is and, as a trigram, . A trigram that never occurs, like "you want a", gives .
A bigram model in Python:
from collections import Counter
def train(sentences):
pairs, firsts = Counter(), Counter()
for s in sentences:
words = ["<s>"] + s.split() + ["</s>"]
for prev, word in zip(words, words[1:]):
pairs[prev, word] += 1
firsts[prev] += 1
return lambda prev, word: pairs[prev, word] / firsts[prev] if firsts[prev] else 0
def score(p, sentence):
words = ["<s>"] + sentence.split() + ["</s>"]
prob = 1
for prev, word in zip(words, words[1:]):
prob *= p(prev, word)
return prob
p = train(["i want a coffee", "i want a cake", "you want coffee", "i like cake"])
print(p("want", "a"), score(p, "i want a coffee"), score(p, "you want a cake"))
# 0.6666666666666666 0.16666666666666666 0.08333333333333333Log probabilities
Definition 4 (Log probability). A model stores and adds natural logarithms of probabilities instead of multiplying the probabilities:
Every factor is at most 1, so a long product shrinks fast. A 400-word text with factors of 0.1 has probability , smaller than the smallest normal 64-bit float (about ), so the product underflows to 0. Its log is , an ordinary number.
For our order,
which is the "log P" the widget shows. A zero factor gives .

What you can do now
- Compute a sentence's probability with a bigram model: add
<s>and</s>, then multiply for each word. - Explain the Markov assumption: keep only the last words, because long histories are almost never seen twice.
- Predict the trade-off: a longer context is sharper on familiar text and gives more zeros on new text.
- Add log probabilities instead of multiplying probabilities, so long texts don't underflow to 0.
Exercises
Each question has one correct answer. Pick your answer, then read the explanation. Questions 6–10 use the definitions and equations above.
You can change your answer at any time. The answers come in a new order each time.
1. (Intuition) What does a language model give you?
2. (Intuition) Why not estimate the next word's probability by counting the entire history before it?
3. (Intuition) A bigram model has seen "you want a" and must predict the next word. Which words does it use?
4. (Intuition) "you want a cake" never appears in our four café orders. Why does the bigram model still give it a probability above 0?
5. (Intuition, widget) In the widget, pick trigram and score "you want a cake". Which factor is zero?
6. (Math · Chain rule) Which is the exact chain-rule expansion of , without end markers?
7. (Math · Definition 3) A training text has four lines: "green tea please", "green tea", "green apple", "black coffee". What is the MLE of ?
8. (Math · Bigram sentence probability) With the same four lines and start and end markers, what is the bigram probability of "green tea"?
9. (Math · Definition 2) A trigram model scores the first word of "green tea". Which factor does it use?
10. (Math · Definition 4) A model scores a 400-word text, and every factor is 0.1. Using natural logs, what is its log probability?
Score: 0 of 10 (0 answered)
Next: How to tell whether a language model is any good: training and test sets, and perplexity (chapter 3, sections 3.2 and 3.3).