Vol. I · What a Language Model Is Plate 2 of 10n-gram, bigram, unigram, Markov model, counts, corpusDL

Models From Counting.

Before neural networks, a language model was a table: for every context seen in a corpus, how often each next symbol followed it.

The simplest way to predict the next letter of a text is to have read a lot of text and remember what tended to come next. After the letters th, English text continues with e far more often than with q; a table that records, for every pair of letters, how often the second followed the first is a bigram model. Remember the last two letters instead of one and it is a trigram model; in general an n-gram model predicts from the previous n − 1 symbols, by dividing counts.

n-gram models are language models in exactly the sense of plate I.1 — they return a distribution over the next symbol — and they dominated speech recognition and machine translation for thirty years. They are also the easiest way to see what “learning from a corpus” means: the workshop counts every context in a slice of the course corpus and shows what follows.

Below: an n-gram model counted from about 140 000 characters of the course corpus. Choose n, type a context, and read what followed it in the corpus; the lower panel is text sampled from the counts.

What you will learn

Build unigram, bigram and n-gram models from counts.
Turn counts into conditional probabilities.
Generate text by sampling from the counts.
See how the number of distinct contexts grows with n.

Workshop

Top: the next characters that followed the last n − 1 characters of the context in the corpus slice, with their counted probabilities. Bottom: 160 characters sampled from the same counts, starting from “The cell divides ”.

Counting is learning, of a kind

With n = 3 the model remembers two characters of context. The corpus slice of 139,999 characters contains 2,192 distinct two-character contexts; after the last two characters of the cell it saw 18 different next characters in 383 occurrences, the most frequent taking 30.0%. A bigram model (n = 2) needs only 162 contexts; at n = 5 there are 22,881, and at n = 7 61,781. Each extra character of memory multiplies the number of contexts, and the sampled text shows what that buys: at n = 2 it is a soup of plausible letter pairs, at n = 4 it is made of real-looking words, at n = 7 it starts copying whole phrases from the corpus.

That last effect is the problem the next plates take up. A count table can only answer for contexts it has seen; the longer the context, the more of them it has never seen (plate I.6), and the more its “predictions” are recitations of its training text. Neural language models (plate I.7) replace the table with a function that can answer for contexts it never saw — but they are trained on the same thing the table was built from: what followed what, in a corpus.

Andrey Markov counted vowel and consonant pairs in the first 20 000 letters of Pushkin’s Eugene Onegin in 1913 — by hand — to show that letters are not independent: the first n-gram model of a text.

Terms

n-gram model: A model that predicts each symbol from the previous n − 1 symbols, using counts from a corpus.
Unigram, bigram, trigram: n = 1, 2, 3: no context, one symbol of context, two symbols of context.
Corpus: The body of text a model is built or trained from.
Markov assumption: The assumption that only the last few symbols matter for predicting the next.

An n-gram model is a table of counts: what followed each context of n − 1 symbols in the corpus. The longer the context, the bigger the table and the fewer times each context was seen.