I8 · Natural Language Processing in Practice

N-gram Language Models

A language model assigns probabilities to sequences of words, usually by predicting each next word from the words before it. An n-gram model simplifies this with the Markov assumption: the next word depends only on the previous n − 1 words. A bigram model (n = 2) uses one previous word, estimated from counts: P(wₙ | wₙ₋₁) = count(wₙ₋₁ wₙ) ÷ count(wₙ₋₁). The probability of a sentence is the product of these conditional probabilities, with start and end markers. Smoothing, such as add-one (Laplace) smoothing, gives unseen word pairs a small non-zero probability. Models are compared by perplexity, where lower is better.

10 min Intermediate · Sublevel Advanced Jump to the activity

What you need: The earlier topics of this module.

Definition

Type "I am going to the" on your phone and it suggests "market" or "office". Long before ChatGPT, keyboards did this by counting which words usually follow which. These counting models, called n-grams, are the simplest language models and the best way to understand what bigger ones do.

A language model assigns probabilities to sequences of words, usually by predicting each next word from the words before it. An n-gram model simplifies this with the Markov assumption: the next word depends only on the previous n − 1 words. A bigram model (n = 2) uses one previous word, estimated from counts: P(wₙ | wₙ₋₁) = count(wₙ₋₁ wₙ) ÷ count(wₙ₋₁). The probability of a sentence is the product of these conditional probabilities, with start and end markers. Smoothing, such as add-one (Laplace) smoothing, gives unseen word pairs a small non-zero probability. Models are compared by perplexity, where lower is better.

In simple words

If you read a thousand cricket commentaries, you would notice that "hit for" is usually followed by "four" or "six". A bigram model is a table of such habits: for every word, how often each other word comes next.

Overview

  • A language model assigns probabilities to sequences of words.
  • An n-gram model predicts each word from the previous n − 1 words using counts.
  • Smoothing gives unseen sequences a small probability.
  • Perplexity measures how well a model predicts text; lower is better.
  • Claude Shannon explored n-gram models of English in 1948.
  • N-grams powered early keyboards and speech recognisers before neural models.

Why it matters

N-grams power predictive keyboards, spelling correction, speech recognition decoders and simple text generators, and they remain strong baselines. Their weaknesses, short memory and sparse counts, explain exactly why neural language models and transformers were developed.

Key terms

Language model
A model that assigns probabilities to word sequences or predicts the next word.
n-gram
A sequence of n words: unigram (1), bigram (2), trigram (3).
Markov assumption
The next word depends only on a few previous words.
Sparsity
Most possible word sequences never appear in the training text, so their counts are zero.
Smoothing
Moving a little probability to unseen n-grams, for example add-one smoothing.
Perplexity
How surprised a model is by test text; roughly the number of words it is choosing between.

Types

N-gram models come in several types by the length of context and by the smoothing method.

1. Unigram model

Each word's probability depends only on its overall frequency.

  • How it works: P(sentence) is the product of individual word probabilities, so word order is ignored.
  • Example: "tea like i" and "i like tea" get the same probability.
  • When to use it: Use it as a baseline and in simple models such as naive Bayes.

2. Bigram model

Each word depends on the one before it.

  • How it works: P(wₙ | wₙ₋₁) = count(wₙ₋₁ wₙ) ÷ count(wₙ₋₁), with start and end markers.
  • Example: "i like tea" has probability 0.0556 in this module's small corpus.
  • When to use it: Use it for autocomplete and as the simplest model that captures word order.

3. Trigram and higher-order models

Each word depends on the two or more words before it.

  • How it works: More context improves predictions, but the number of possible n-grams grows explosively, so counts become sparse.
  • Example: Google's 2006 n-gram data set of counts up to 5-grams from a trillion words of web text.
  • When to use it: Use them with lots of data and good smoothing.

4. Add-one and add-k smoothing

Adding a constant to every count.

  • How it works: Add-one (Laplace) uses (count + 1) ÷ (count(previous) + V); add-k uses a smaller constant to move less probability.
  • Example: Add-one giving the scrambled "tea like i" a tiny probability instead of zero.
  • When to use it: Use it for small examples and naive Bayes; prefer better methods for real language models.

5. Backoff, interpolation and Kneser–Ney smoothing

Combining models of different orders to handle sparse counts.

  • How it works: Backoff uses a lower-order model when a higher n-gram is unseen; interpolation mixes all orders; Kneser–Ney (1995) also counts how many contexts a word appears in.
  • Example: "Francisco" is common but almost always follows "San", so Kneser–Ney gives it a low probability after other words.
  • When to use it: Use Kneser–Ney as the standard for serious n-gram models.

Explained in detail

Counting to predict

To build a bigram model, add a start marker <s> and an end marker </s> to every sentence, count every pair of neighbouring words, and divide by how often the first word appears. If "i" appears 5 times as a previous word and is followed by "like" twice, then P(like | i) = 2 ÷ 5 = 0.4. A sentence's probability is the product of the probabilities of each step, including the first word after <s> and the final </s>. Trigram models condition on two previous words, which captures more context, such as "New Delhi" versus "new phone", but needs far more data because many more word triples are possible. Long products of small numbers underflow, so in practice we add log-probabilities instead of multiplying probabilities.

Sparsity and smoothing

Even huge corpora miss most possible word pairs. Without smoothing, any sentence containing one unseen pair gets probability zero, however natural it is. Add-one smoothing adds 1 to every pair count and the vocabulary size V to every denominator: P = (count + 1) ÷ (count(previous) + V). It is simple but moves too much probability to unseen pairs, so better methods such as Kneser–Ney smoothing and backoff (falling back to a bigram or unigram when a trigram is unseen) are used in practice. Words never seen in training at all are replaced with a special <unk> token.

Perplexity and the limits of n-grams

ModelContext usedStrengthWeakness
UnigramNoneWord frequenciesIgnores order entirely
Bigram and trigram1 or 2 previous wordsFast, simple, good for autocompleteShort memory; sparse counts
Neural (RNN, LSTM)Whole history, compressedGeneralises through embeddingsSlow to train; forgets far-back words
TransformerThousands of tokens with attentionCaptures long-range meaningNeeds huge data and computing power

Perplexity is the inverse probability of the test text, normalised by its length: PP = P(w₁…w_N)^(−1/N). A perplexity of 100 means the model is, on average, as uncertain as if it were choosing uniformly among 100 words. In the code below, with add-one smoothing the natural sentence "i like tea" has perplexity 6.1 while the scrambled "tea like i" has 19.6, so the model clearly prefers proper word order. N-grams cannot connect words far apart: in "The book that my friends from Pune recommended was…", the verb depends on "book" ten words earlier, which is why attention-based models replaced them.

How it works

  1. Split text into sentences and words, and add <s> and </s> markers.
  2. Count unigrams and bigrams.
  3. Compute conditional probabilities, adding smoothing.
  4. Score sentences with summed log-probabilities, or generate by sampling the next word.
  5. Evaluate with perplexity on held-out text.

The maths

Bigram probability
Add-one smoothing
Vocabulary size
Perplexity

The code's small corpus has 8 sentences, 5 starting with "i". So P(i | <s>) = 5 ÷ 8. After "i" (5 times) comes "like" twice, so P(like | i) = 2 ÷ 5. After "like" (3 times) comes "tea" once, so P(tea | like) = 1 ÷ 3. "tea" appears 3 times as a previous word and ends the sentence twice, so P(</s> | tea) = 2 ÷ 3. The sentence "i like tea" therefore has probability 5/8 × 2/5 × 1/3 × 2/3 = 20 ÷ 360 ≈ 0.0556. The reversed "tea like i" gets 0, because no sentence starts with "tea"; add-one smoothing gives it a tiny probability instead.

In code

bigram_model.py
from collections import Counter, defaultdict
import random

corpus = [
    "i like tea", "i like coffee", "i drink tea",
    "we drink tea in the morning", "we like cricket in the evening",
    "i play cricket in the evening", "we play cricket on sunday", "i drink coffee in the morning",
]
pairs, unigrams = Counter(), Counter()
for sentence in corpus:
    words = ["<s>"] + sentence.split() + ["</s>"]
    unigrams.update(words[:-1])
    pairs.update(zip(words[:-1], words[1:]))
vocab = {w for s in corpus for w in s.split()} | {"</s>"}

def prob(prev, word, k=0.0):
    return (pairs[(prev, word)] + k) / (unigrams[prev] + k * len(vocab))

def sentence_prob(sentence, k=0.0):
    words = ["<s>"] + sentence.split() + ["</s>"]
    p = 1.0
    for prev, word in zip(words[:-1], words[1:]):
        p *= prob(prev, word, k)
    return p, len(words) - 1

print("P(like | i) =", round(prob("i", "like"), 3), "| P(tea | like) =", round(prob("like", "tea"), 3))
for s in ["i like tea", "we play cricket in the morning", "tea like i"]:
    p, n = sentence_prob(s)
    p1, _ = sentence_prob(s, k=1)
    ppl = p1 ** (-1 / n)
    print(f"{s!r:<34} P = {p:.4f}   with add-one smoothing P = {p1:.6f}, perplexity = {ppl:.1f}")

nexts = defaultdict(list)
for (prev, word), c in pairs.items():
    nexts[prev] += [word] * c
random.seed(3)
for _ in range(3):
    word, out = "<s>", []
    while True:
        word = random.choice(nexts[word])
        if word == "</s>" or len(out) > 10: break
        out.append(word)
    print("Generated:", " ".join(out))

Output

P(like | i) = 0.4 | P(tea | like) = 0.333
'i like tea'                       P = 0.0556   with add-one smoothing P = 0.000725, perplexity = 6.1
'we play cricket in the morning'   P = 0.0417   with add-one smoothing P = 0.000004, perplexity = 5.9
'tea like i'                       P = 0.0000   with add-one smoothing P = 0.000007, perplexity = 19.6
Generated: i play cricket in the morning
Generated: we like cricket in the evening
Generated: we play cricket in the evening

Try it yourself

Building a bigram model

Put the steps in order.

  1. 1Divide by the count of the first word
  2. 2Add smoothing for unseen pairs
  3. 3Measure perplexity on new sentences
  4. 4Add start and end markers to each sentence
  5. 5Count each pair of neighbouring words

Will a bigram model handle it?

Can one previous word decide the next well?

  • Suggesting "you" after "thank"

  • Choosing "was" or "were" after "The books on the top shelf"

  • Answering a question about the first paragraph of a story

  • Completing "New" with "Delhi" in an Indian news corpus

Common mistakes

  • Forgetting smoothing, so one unseen pair makes a whole sentence impossible.
  • Multiplying many small probabilities instead of adding log-probabilities.
  • Comparing perplexities of models that use different vocabularies.

Check yourself

Question 1

1. "the" appears 50 times and "the cat" 5 times. What is P(cat | the)?

Question 2

2. Why is smoothing needed?

Question 3

3. Model A has perplexity 80 and model B 200 on the same test text. Which is better?

Summary

  • An n-gram model predicts the next word from the previous n − 1 words using counts.
  • Smoothing handles unseen pairs, and perplexity measures how well a model predicts text.
  • Short memory and sparse counts limit n-grams, motivating neural and transformer models.

Finished reading?

Sources: Jurafsky and Martin, Speech and Language Processing, chapter on n-gram language models (free draft)