DEV Community

Cover image for NLP #4: N-gram Language Models
GradientGym
GradientGym

Posted on Originally published at almoghagbi.com

NLP #4: N-gram Language Models

Originally published on almoghagbi.com, where the figures are interactive.

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
.

Two strips of the same four word tiles. The top reads "i want a coffee" with a green check and the label "likely"; the bottom reads "coffee a want i" with a red cross and the label "unlikely". Dashed lines link the identical tiles, under the caption "same words, different order".

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 N−1N - 1
words. A bigram model ( N=2N = 2 ) predicts "coffee" from "a" alone, and forgets
"i want". A trigram model ( N=3N = 3 ) 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.

Word tiles "i", "want", "a" and a question mark. "i" and "want" are faded grey, "a" is blue under a spotlight, and an arrow from "a" points to the question mark. Two cards float above it: "coffee" and "cake", each labeled 1/2.

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 2/32/3 and "coffee" with
probability 1/31/3 .

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 34⋅23⋅23⋅12⋅1=16\frac{3}{4} \cdot \frac{2}{3} \cdot \frac{2}{3} \cdot \frac{1}{2} \cdot 1 = \frac{1}{6} .
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 112\frac{1}{12} . "coffee a want i" gets 0. Try your own sentences:

▶ Interactive figure: try it on the original post.

A chalkboard with the four orders, "want" circled in each line. An arrow leads to a blue box headed "after want", with two tally marks and 2/3 beside "a", and one tally mark and 1/3 beside "coffee".

More context, more zeros

Why not look further back? Switch the widget to trigram. "i want a coffee"
rises from 16\frac{1}{6} to 14\frac{1}{4} : 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 strip "you want a" twice. Top: a magnifying glass over "want", labeled "look 1 word back", with a green badge "2/3". Bottom: a wider magnifying glass over "you want", labeled "look 2 words back", with a red badge "0".

The math

The chain rule

Definition 1 (Language model). A language model assigns a probability
P(w1:n)P(w_{1:n}) to every sequence of words w1,…,wnw_1, \dots, w_n from a vocabulary VV ,
and a probability P(wn∣w1:n−1)P(w_n \mid w_{1:n-1}) to each next word wnw_n given the
words before it.

Key equation (Chain rule). By the
chain rule of probability,
the two are the same thing:

P(w1:n)=P(w1) P(w2∣w1) P(w3∣w1:2)⋯P(wn∣w1:n−1)=∏k=1nP(wk∣w1:k−1). P(w_{1:n}) = P(w_1)\, P(w_2 \mid w_1)\, P(w_3 \mid w_{1:2}) \cdots P(w_n \mid w_{1:n-1}) = \prod_{k=1}^{n} P(w_k \mid w_{1:k-1}).

It's exact, with no assumptions. For our order,

P(i want a coffee)=P(i) P(want∣i) ⋅P(a∣i want) P(coffee∣i want a). \begin{aligned} P(\text{i want a coffee}) = {} & P(\text{i})\,P(\text{want} \mid \text{i}) \ & \cdot P(\text{a} \mid \text{i want})\,P(\text{coffee} \mid \text{i want a}). \end{aligned}

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 nn words. An
n-gram model makes the Markov assumption: the next word depends only on
the last N−1N - 1 words,

P(wn∣w1:n−1)≈P(wn∣wn−N+1:n−1). P(w_n \mid w_{1:n-1}) \approx P(w_n \mid w_{n-N+1:n-1}).

N=1N = 1 is a unigram model (no context), N=2N = 2 a bigram model, N=3N = 3
a trigram model. Each sentence gets N−1N - 1 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:

P(w1:n)≈∏k=1nP(wk∣wk−1), P(w_{1:n}) \approx \prod_{k=1}^{n} P(w_k \mid w_{k-1}),

with $w_0 = $ <s>, and the end marker counted as the last word, $w_n = $ </s>.
For "i want a coffee" ( n=5n = 5 ) that's the five factors of the table above.

Five blue boxes joined by multiplication signs: P(i | <s>), P(want | i), P(a | want), P(coffee | a), P(</s> | coffee). Below them, 3/4, 2/3, 2/3, 1/2 and 1, equal to 1/6 in green.

Maximum likelihood estimates

Definition 3 (MLE for n-grams). Let C(x)C(x) count how often the word
sequence xx 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:

P(wn∣wn−1)=C(wn−1wn)∑wC(wn−1w)=C(wn−1wn)C(wn−1). P(w_n \mid w_{n-1}) = \frac{C(w_{n-1} w_n)}{\sum_{w} C(w_{n-1} w)} = \frac{C(w_{n-1} w_n)}{C(w_{n-1})}.

The sum counts every bigram that starts with wn−1w_{n-1} , which is just the number
of times wn−1w_{n-1} 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 NN , divide by the count of the context:

P(wn∣wn−N+1:n−1)=C(wn−N+1:n−1 wn)C(wn−N+1:n−1). P(w_n \mid w_{n-N+1:n-1}) = \frac{C(w_{n-N+1:n-1}\, w_n)}{C(w_{n-N+1:n-1})}.

For our orders, P(a∣want)P(\text{a} \mid \text{want}) is
C(want a)/C(want)=2/3C(\text{want a}) / C(\text{want}) = 2/3
and, as a trigram, P(a∣i want)=2/2=1P(\text{a} \mid \text{i want}) = 2/2 = 1 . A context that never
occurs, like "you want" followed by "a", gives 0/1=00/1 = 0 .

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.08333333333333333
Enter fullscreen mode Exit fullscreen mode

Log probabilities

Definition 4 (Log probability). A model stores and adds
natural logarithms of
probabilities instead of multiplying the probabilities:

p1×p2×⋯×pn=exp⁡(log⁡p1+log⁡p2+⋯+log⁡pn). p_1 \times p_2 \times \cdots \times p_n = \exp(\log p_1 + \log p_2 + \cdots + \log p_n).

Every factor is at most 1, so a long product shrinks fast. A 400-word text with
factors of 0.1 has probability 10−40010^{-400} , smaller than the smallest normal
64-bit float (about 10−30810^{-308} ), so the product
underflows to 0. Its log
is 400⋅log⁡0.1≈−921400 \cdot \log 0.1 \approx -921 , an ordinary number.

For our order,

log⁡16=log⁡34+log⁡23+log⁡23+log⁡12+log⁡1 ≈−0.288−0.405−0.405−0.693+0=−1.79, \begin{aligned} \log \tfrac{1}{6} &= \log \tfrac{3}{4} + \log \tfrac{2}{3} + \log \tfrac{2}{3} + \log \tfrac{1}{2} + \log 1 \ &\approx -0.288 - 0.405 - 0.405 - 0.693 + 0 = -1.79, \end{aligned}

which is the "log P" the widget shows. A zero factor gives log⁡0=−∞\log 0 = -\infty .

Left, "multiply": blue cards 0.01, 0.0001 and 0.000001 shrinking, ending in a red label "underflow → 0". Right, "add logs": three equal green jumps of −4.6 along a number line, from 0 to −13.8.

What you can do now

  • Compute a sentence's probability with a bigram model: add <s> and </s>, then multiply C(wk−1wk)/C(wk−1)C(w_{k-1} w_k) / C(w_{k-1}) for each word.
  • Explain the Markov assumption: keep only the last N−1N - 1 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.

1. (Intuition) What does a language model give you?

  • A. A label for the whole text, such as positive or negative.

  • B. A probability for each word that could come next.

  • C. A list of grammar rules the text must follow.

  • D. The most common words in the training text.

Answer

B. A language model scores each possible next word given the words so far. Multiplying those scores gives a probability for a whole sentence.

  • A is wrong: that's a classifier, a different task.
  • C is wrong: an n-gram model holds counts, not rules.
  • D is wrong: word frequencies ignore order, so they score "coffee a want i" like "i want a coffee".

2. (Intuition) Why not estimate the next word's probability by counting the entire history before it?

  • A. Counting is too slow on a computer.

  • B. The chain rule doesn't allow conditioning on many words.

  • C. Long histories are easy to count, but they all give the same answer.

  • D. Most long histories never occur in any training text, so their counts are zero.

Answer

D. Language is creative: almost every long sentence is new. A history that was never seen has count 0, and nothing can be divided by it.

  • A is wrong: the problem is missing data, not speed.
  • B is wrong: the chain rule conditions on the whole history. It's exact, just impossible to estimate.
  • C is wrong: the histories can't be counted, because they don't occur.

3. (Intuition) A bigram model has seen "you want a" and must predict the next word. Which words does it use?

  • A. Only "a".

  • B. "want a".

  • C. "you want a".

  • D. No words: it predicts the most common word.

Answer

A. A bigram model ( N=2 ) looks back N−1=1 word.

  • B is wrong: that's a trigram model's context.
  • C is wrong: that's the full history, which the Markov assumption drops.
  • D is wrong: that's a unigram model.

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?

  • A. The model gives every sentence a probability above 0.

  • B. It finds the most similar sentence in the training text.

  • C. Each of its word pairs appears somewhere in the training text.

  • D. Short sentences always get a probability above 0.

Answer

C. The bigram model only needs <s> you, you want, want a, a cake and cake </s>, and each of them occurs in some order. Its probability is 41​⋅1⋅32​⋅21​⋅1=121​ .

  • A is wrong: "i want cake" gets 0, since "want" is never followed by "cake".
  • B is wrong: the model has no notion of similar sentences, only counts of word pairs.
  • D is wrong: length doesn't matter. "coffee i" is short and gets 0.

5. (Intuition, widget) In the widget, pick trigram and score "you want a cake". Which factor is zero?

  • A. P(you | <s> <s>)

  • B. P(a | you want)

  • C. P(cake | want a)

  • D. P(</s> | a cake)

Answer

B. "you want" occurs once, followed by "coffee", so P(a∣you want)=0/1=0 , and the whole sentence gets 0.

  • A is wrong: one of the four orders starts with "you", so it's 1/4 .
  • C is wrong: "want a" is followed by "cake" once out of twice, so it's 1/2 .
  • D is wrong: "a cake" ends its order, so it's 1/1 .

6. (Math · Chain rule) Which is the exact chain-rule expansion of P(i like cake)P(\text{i like cake}) , without end markers?

  • A. P(i) P(like) P(cake)P(\text{i})\,P(\text{like})\,P(\text{cake})

  • B. P(i) P(like∣i) P(cake∣like)P(\text{i})\,P(\text{like} \mid \text{i})\,P(\text{cake} \mid \text{like})

  • C. P(i) P(like∣i) P(cake∣i like)P(\text{i})\,P(\text{like} \mid \text{i})\,P(\text{cake} \mid \text{i like})

  • D. P(cake) P(like∣cake) P(i∣like)P(\text{cake})\,P(\text{like} \mid \text{cake})\,P(\text{i} \mid \text{like})

Answer

C. Each word is conditioned on every word before it, so the last factor has the history "i like".

  • A is wrong: that treats the words as independent, which only holds as a unigram approximation.
  • B is wrong: that's the bigram approximation. It drops "i" from the last factor.
  • D is wrong: it conditions "i" on "like" alone and drops "cake". Read right to left, the exact version would need P(i∣like cake) .

7. (Math · Definition 3) A training text has four lines: "green tea please", "green tea", "green apple", "black coffee". What is the MLE of P(tea∣green)P(\text{tea} \mid \text{green}) ?

  • A. 2/32/3

  • B. 2/42/4

  • C. 11

  • D. 3/43/4

Answer

A. C(green tea)=2 and C(green)=3 , so the estimate is 2/3 .

  • B is wrong: it divides by the number of lines, not by the count of "green".
  • C is wrong: it divides by C(tea)=2 , the second word instead of the first.
  • D is wrong: 3/4 is P(green∣) , the chance a line starts with "green".

8. (Math · Bigram sentence probability) With the same four lines and start and end markers, what is the bigram probability of "green tea"?

  • A. 1/21/2

  • B. 1/31/3

  • C. 2/32/3

  • D. 1/41/4

Answer

D. P(green∣)=3/4 , P(tea∣green)=2/3 and P(∣tea)=1/2 , since "tea" ends one of its two lines. The product is 43​⋅32​⋅21​=41​ .

  • A is wrong: it leaves out the end marker's factor.
  • B is wrong: it leaves out the start marker's factor.
  • C is wrong: that's only P(tea∣green) .

9. (Math · Definition 2) A trigram model scores the first word of "green tea". Which factor does it use?

  • A. P(green)P(\text{green})

  • B. P(green∣ )P(\text{green} \mid \text{ })

  • C. P(green∣)P(\text{green} \mid \text{})

  • D. P(∣green)P(\text{} \mid \text{green})

Answer

B. A trigram model looks back N−1=2 words, so each sentence gets two start markers and the first word's context is <s> <s>.

  • A is wrong: that's the unigram factor, with no context.
  • C is wrong: that's the bigram factor, with one word of context.
  • D is wrong: it predicts the marker from the word, the wrong way round.

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?

  • A. 00

  • B. −400-400

  • C. About −921-921

  • D. About −2.3-2.3

Answer

C. log0.1≈−2.303 , and the logs add: 400⋅(−2.303)≈−921 .

  • A is wrong: 0 is what the product of the probabilities underflows to, not the log.
  • B is wrong: that uses base-10 logs, where log10​0.1=−1 .
  • D is wrong: that's the log of a single factor.

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).

Co-authored with AI.

Top comments (1)

Collapse
 
ahmetozel profile image
Ahmet Özel •

Walking through the four cafe orders makes the Markov trade-off concrete without burying it in notation. The point about explicit start and end markers prevent the model from systematically favoring shorter fragments is a subtle detail that even experienced engineers forget when comparing raw log-probabilities across variable-length sequences.

Zero-count sparsity is where n-gram intuition still pays off in modern LLM engineering too: seeing why unseen word histories collapse to zero probability immediately explains why subword tokenization and smoothing were necessary before neural embeddings took over.