Skip to content
Tutorials Center
My learning

Topics

Lesson 19 of 63 ยท Language Models Before Neural Nets

N-gram Language Models

Learn how n-gram language models assign probabilities to sentences using the chain rule and the Markov assumption, then build one and a text generator.

A language model answers one question: how likely is this sequence of words? "The cat sat on the mat" should score higher than "mat the on sat cat the", and both should score higher than random noise. That simple ability sits behind speech recognition (pick the transcript that sounds right and reads like English), spelling correction, machine translation, autocomplete and, today, the large language models that write whole paragraphs.

This lesson builds the classic version, the n-gram language model. It needs nothing but counting, which makes it the best place to understand what a language model actually is before neural networks enter the picture. You should be comfortable with n-grams and with word frequencies.

Probability of a sentence

A sentence is a sequence of words w1, w2, ..., wn. We want P(w1, w2, ..., wn). The chain rule of probability lets us split that joint probability into a product of conditional ones, each word given everything before it:

TEXT
P(the cat sat) = P(the) * P(cat | the) * P(sat | the cat)

This is exact, not an approximation. The trouble is practical. To estimate P(sat | the cat) from counts you would divide how often "the cat sat" appears by how often "the cat" appears. For a long history such as "last night the cat sat on the" the history has probably never appeared in your corpus, so the count is zero and the estimate is useless. Almost every long sentence you will ever see is new.

The Markov assumption

The fix is to forget most of the history. A bigram model assumes a word depends only on the one word before it; a trigram model looks back two words. In general, an n-gram model keeps n - 1 words of context:

TEXT
bigram:   P(sat | the cat)  is approximated by  P(sat | cat)
trigram:  P(sat | the cat)  is kept as it is (two words of context)

This is called the Markov assumption: the future depends on a short window of the past, not on all of it. It is wrong in detail ("the dogs that chased the cat are" needs a verb to agree with a noun far away), but it works well enough to be useful, and it makes the model trainable from plain counts.

From counts to a language model

Count Tally every n-gram and its history.
Divide Count of n-gram over count of history.
Multiply Chain the word probabilities.

The whole model is a table of ratios.

1 / 2

Estimating probabilities by counting

The maximum likelihood estimate for a bigram model is a ratio of counts:

TEXT
P(word | prev) = count(prev word) / count(prev)

Two practical details. First, wrap every sentence in boundary markers: <s> at the start and </s> at the end. Then "how likely is a sentence to start with the" is just P(the | <s>), and "how likely is the sentence to end here" is P(</s> | rug). Second, count within each sentence so you do not pair the last word of one sentence with the first of the next (see sentence segmentation).

Python A bigram model from five sentences

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

After "the", the corpus continues with cat, dog, mat or rug, so each of cat and dog gets one third. After "cat" the model sees sat in half of the cases (the other cases are chased and the end of the sentence). After "rug" a sentence always ends, so that probability is exactly 1.

Now score whole sentences by multiplying the bigram probabilities along the sentence, boundary markers included.

Python Scoring sentences

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

"The cat sat on the rug" never occurs in the corpus, yet it scores 0.029630: every pair in it was seen, even though the whole sentence was not. That is the power of the Markov assumption, because it lets the model recombine pieces it has seen. "The dog sat on the mat" is less likely because mat follows the only one time in nine. The last two sentences get exactly 0, because they contain a pair the model never saw (mat sat and <s> cat). A single unseen pair wipes out the whole product, which is a real problem that smoothing solves in the next lesson.

Real models multiply many numbers below 1, and the product quickly underflows to zero. Software works with log probabilities and adds them instead of multiplying: log(a * b) = log(a) + log(b). You will use that in the next lesson.

Generating text

A language model can be run backwards. Instead of scoring words, sample them: start at the beginning-of-sentence marker, pick the next word with probability proportional to its count, append it, shift the context and repeat until the model picks </s>. The result is text with the statistics of the corpus.

This example uses a trigram model, so the context is the previous two words, and a seeded random generator so you get the same output every run. Two start markers let the model learn how sentences begin.

Python A trigram text generator

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

After "the king" the model has seen four different continuations once each, so any of them is equally likely. The generated sentences look plausible locally, because every three-word window really occurs in the corpus, but they have no plan and no meaning: one of them rambles through "the castle and the queen sent a letter to the castle" and is cut off only by the length limit. That is the signature of an n-gram model: fluent in the short range, aimless in the long range. Larger n copies the training text more faithfully; with a small corpus a high-order model mostly reproduces whole sentences it has memorized.

What n-gram models are good and bad at

  • Cheap and fast. Training is one pass of counting; scoring is a few dictionary lookups. That is why they ran inside phones and keyboards for years.
  • Transparent. You can read every probability in the table.
  • Short memory. Anything beyond n - 1 words is invisible, so agreement and meaning over long distances are lost.
  • Huge tables. The number of possible n-grams grows as V^n for a vocabulary of size V, and storage grows with the corpus.
  • Sparse. Most valid word sequences never appear in training, so they get probability zero unless you smooth.
  • No sense of similarity. The model has no idea that "dog" and "cat" behave alike, so what it learns about one does not help the other. Word embeddings and neural models fix this.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What does the Markov assumption say in a bigram model?

    A bigram model approximates P(word | whole history) by P(word | previous word). Keeping a short window makes the counts reliable enough to estimate.
  2. 2. In the maximum likelihood bigram estimate, which ratio gives P(sat | cat)?

    You count how often "cat" is followed by "sat" and divide by how often "cat" occurs as a context. That is the share of times "cat" was followed by "sat".
  3. 3. Why does a sentence receive probability 0 in the unsmoothed model above if it contains one bigram never seen in training?

    The sentence probability is a product of bigram probabilities. One unseen bigram has a count of 0, so its factor is 0 and the whole product collapses, even if every other pair is common.
  4. 4. Why do we add <s> and </s> markers to each sentence?

    With a start marker, P(the | <s>) describes how sentences begin, and P(</s> | word) describes how they end. Without them the model cannot say where a sentence stops, which also breaks generation.

Summary

  • A language model assigns a probability to a sequence of words; the chain rule writes it as a product of conditional probabilities.
  • The Markov assumption keeps only n - 1 words of context, so an n-gram model can be estimated from counts: count(history word) / count(history).
  • Start and end markers let the model learn sentence boundaries; real systems add log probabilities instead of multiplying.
  • A model can generate text by sampling the next word from the counts; the output is locally fluent and globally aimless.
  • Unseen n-grams give probability zero, and long-range structure is invisible: the two core weaknesses.

Next, fix zero probabilities and measure model quality with Smoothing and Perplexity.