N-Grams

The pages on either side of this one decide where the pieces of a text are, splitting on spaces by the simplest rule there is and the Unicode boundaries by a standard written to cover every writing system at once. This page starts after that decision has been made. It takes the pieces as given and asks a different question, which is how often each run of adjacent pieces occurs, and what those counts let you say about a word you have not read yet.

Context can help a speech recogniser choose between words that sound similar. A count-based language model supplies one source of that contextual evidence.

Predicting the next token is also a training task for autoregressive neural language models. Those models learn prediction parameters instead of relying on an explicit table of n-gram counts. The counting version gives us a transparent starting point for the shared prediction problem.

A run of n adjacent pieces is called an n-gram. One word is a unigram, two a bigram, three a trigram, and above that people usually say the number. The pieces do not have to be words, and character n-grams are common, though everything on this page is counted over words.

Runs have to be counted rather than words because a table of how often each word occurs contains no information about order at all. It gives exactly the same answer for a sentence and for the same sentence with its words reversed, and step 19 measures that coming out equal to the last digit on six real sentences. Everything a model of this kind knows about which word follows which is in the runs of two or more.

Take the sentence this section of the site carries throughout, Dr. Alvarez didn’t expect the low-cost re-analysis. Split on spaces and it is seven words, and the last of them is re-analysis. with the full stop attached, because a space splitter has no reason to take the stop off. Slide a window of three along those seven and you get the trigrams. Slide a window of two and you get the bigrams.

The widget below cuts it at four widths. The chip that matters in each row is the last one, since that is the word the run predicts, and everything to its left is what the prediction is made from.

…

A sentence has a beginning and an end, and both have to be written down or the counting cannot see them. The first word of a sentence has nothing before it, so if the model is to predict it at all there must be something standing in for the place where the sentence starts. A model reading two words back needs two such markers, one for each empty position, which is why the count of them changes with the width of the window.

The end matters for a different reason. A marker after the last word is predicted exactly like a word, so the model learns which words tend to end a sentence, and a model that has learned that is a model that knows when to stop. Without it the probabilities of all the sentences of a given length would sum to one separately for each length, and the model would have no way of preferring a short sentence to a long one.

The start markers are the mirror image. They are never predicted, only ever read back from, since the beginning of a sentence is where the model starts rather than somewhere it can arrive. A run whose last position is a start marker is not counted at all.

P(sentence)  =  P(w₁ | start) · P(w₂ | w₁) · … · P(end | wₙ)

Everything on this page from here on is fitted to forty-four short sentences from the world the running sentence belongs to, reports and analyses and samples arriving late. They hold 326 word occurrences and 62 distinct words, so with the end marker and one stand-in for anything unseen the model has 64 words it is allowed to answer with.

Sixty-four words allow 4,096 different pairs and 262,144 different triples. The forty-four sentences produced 141 pairs and 202 triples. That is the ordinary condition of the method rather than a shortage of text, and it gets worse as the window widens, since the number of possible runs is multiplied by the vocabulary each time while the number of positions in the corpus stays where it was.

The 63 distinct single words are the 62 words of the corpus plus the end marker; the stand-in is in the vocabulary without ever having been counted, which is a detail that comes back in Part 3.

The probability of a sentence is the probability of its first word, times the probability of its second given the first, times the probability of its third given the first two, and so on to the end. That is exact and it is useless, because by the fourth or fifth word the thing being conditioned on is a phrase that has never been written before, so there is nothing to count and no estimate to make.

P(w₁ … wₘ)  =  Π over i of  P(wᵢ | w₁ … wᵢ₋₁)

The n-gram model throws away all of that history except the last few words. A model of width three believes that the probability of a word given everything before it equals the probability of that word given the two words immediately before, and nothing else about the sentence matters. This is the Markov assumption, and it is false about language, since what a sentence is about survives across any number of words.

It is useful anyway, because it turns an unanswerable question into a table of counts, and a table of counts can be built from any text at all and read in constant time.

P(wᵢ | w₁ … wᵢ₋₁)  ≈  P(wᵢ | wᵢ₋ₙ₊₁ … wᵢ₋₁)

The width n is the whole trade and it is the only real dial the method has. A model of width one knows which words are common and nothing else. A model of width three knows which words follow which pairs and has seen very few of the pairs a new text will contain. Part 5 measures where the trade lands here.

With the history cut down to a fixed length, the estimate is the obvious one. Count how often the run occurred, count how often its first words stood before anything at all, and divide. Nothing about it is a choice; it is the estimate that makes the training text as probable as it can be, which is why it is called the maximum-likelihood estimate.

P(word | context)  =  C(context word) ⁄ C(context)

Three sentences are enough to see the whole thing. The report was late, the report was short, a summary was late. Nine words can be predicted once the end marker and the stand-in are counted, and there are fifteen predicted positions in all, twelve words and three ends.

…

P(the report was late)  =  (2⁄3)(1)(1)(2⁄3)(1)  =  4⁄9  =  0.4444

Fit the same rule to the forty-four sentences, ask it to read the running sentence, and every step is one division. Two of the sentence’s words are not in the vocabulary at all, since nothing in the training text contains didn’t or expect, and both are replaced by the one stand-in the model keeps for that purpose before anything is looked up.

Two rows are worth staring at. Dr. was followed by Alvarez every one of the seven times it occurred, and the model very nearly says so. The two rows reading 0.0156 are the model with nothing at all to go on, since the stand-in never occurred in training and so never stood before anything, and 0.0156 is one divided by the 64 words the model is allowed to answer with.

Asking the probability of one word is asking one entry of a larger answer. For any context the model has a number for every word it knows, the numbers sum to one, and it is only together that they say anything. The largest is the model’s guess. How evenly the rest are spread is how unsure it is, and that spread has a standard measurement in bits, with two to the power of the bits being the number of equally likely words the answer is worth.

bits  =  −Σ over words of  P(word) log₂ P(word)

…

Four contexts are worth comparing there. At the start of a sentence the model has 44 observations and only five words ever began one, so the answer is the narrowest of the four at 4.9775 bits. After the it has 46 observations spread over eighteen different words and reads 5.6283. After Dr. it has seven observations all agreeing, which ought to be the narrowest answer of all and is instead the widest at 5.8117, for a reason Part 4 is about.

And after a word it never saw it has nothing, so every word of the vocabulary gets the same number and the answer is exactly 6 bits, which is 64 equally likely words.

Go back to the three sentences. The word summary never followed the, so the count of that pair is zero, so the probability of summary given the is zero. Now ask for the probability of the sentence the summary was late. Every other step of it is perfectly ordinary and one step is zero, and a product with a zero in it is zero.

The model is not saying that sentence is unlikely. It is saying the sentence cannot happen, which is a claim of a different kind, and a false one about a sentence a reader has just read. The same thing happens to a report was short, whose every word and every idea is in the three sentences and whose pair a report is not.

How often that happens is a measurable thing rather than a fear. Take six sentences the model was never fitted to, frame them, and count how many of their runs are runs the training text never produced. There are 53 predicted positions across the six.

The single-word row is the only one that is small, and even there three words of the new text were never seen. Everything above one word is a model that would refuse most of what it is shown. This is the ordinary condition of the method rather than a symptom of a small corpus, and it is worse at the widths that would otherwise be the most informative.

Dividing one count by another is not a careless choice that a more careful one would improve on. It is the estimate that maximises the probability of the training text, and it is the best possible estimate by that standard. Every scrap of probability it gives to a run it never saw would have to be taken from a run it did see, and that would lower the number it was maximising.

So the failure is exactly the success viewed from outside. On the forty-four sentences it was fitted to, a two-word model scores 2.9970 and a five-word model 1.6025, both far better than anything else on this page. On the six sentences it was not fitted to, the same models have no score at all, at every width from one to five.

The repair every method here is a version of is to pretend the counting saw a little more than it did. Before dividing, add the same constant to every count, and add the matching amount to the denominator so that the numbers still sum to one, which means adding the constant once for every word the model is allowed to answer with. A run that never occurred now has a small numerator instead of nothing.

P(word | context)  =  ( C(context word) + k ) ⁄ ( C(context) + k V )

V there is the size of the vocabulary and k is how many times every word is pretended to have followed every context. Setting k to one is the oldest version, and it is Laplace’s rule of succession from the Essai philosophique sur les probabilités of 1814, which is where anyone reading about this for the first time starts.

Adding one sounds modest until you notice that it is added once per word of the vocabulary, so the denominator grows by the size of the vocabulary while a typical numerator grows by one. When the context is rare that swamps the evidence completely.

In the forty-four sentences, Dr. occurs seven times and is followed by Alvarez all seven. The counts are as certain as counts get. Adding one leaves the probability of Alvarez at 0.1127, because the denominator went from 7 to 71, and the answer as a whole costs 5.8117 bits, which is very close to the 6 bits of knowing nothing at all.

Nothing requires the constant to be one. Any positive number works, and a fraction takes less from what was seen while still leaving nothing at zero. Which fraction is a question with an answer, and the answer is found by trying them and scoring each on text the counts were not taken from.

Six sentences are held back for the choosing and six more are held back from that too, so the number reported is a number nothing selected. The indigo curve below is the choosing text and the amber curve is the reporting text; the ring marks the lowest point of the indigo curve, which is the setting a person would take away.

…

At two words the chosen constant is 0.005, two hundred times smaller than the textbook one. It scores 8.9626 on the reporting text where adding one scores 23.6179, so the textbook setting is more than two and a half times worse than a setting nobody had to be clever to find. The same shape holds at three, four and five words, with the chosen constant drifting up as the counts thin out.

The constant has a limit in each direction, and both limits are models we have already met. Send it towards zero and the added amount stops mattering beside the real counts, so the answer approaches one count divided by another and the zeroes come back. Send it upwards and the real counts stop mattering beside the added amount, so every word of the vocabulary gets the same number whatever stands before it.

The upper limit is more useful than it looks, because it is the yardstick. A model over 64 words that knows nothing scores 64, and any real model has to come in under that to have earned anything. It also has a sting in it, which Part 5 comes back to, since a model over a smaller vocabulary starts from a smaller number without having done anything better.

Adding a constant is the baseline rather than the state of the art, and it has been known to be a poor one since Gale and Church argued in the early 1990s that it hands unseen events far more probability than they deserve. Everything measured above is a demonstration of their point on a small scale.

The rules that replaced it are named here without being drawn, because this page measures only what it can show. The Good-Turing estimate uses how many runs were seen exactly once to estimate how much probability the unseen runs should share. Interpolation mixes the estimate from a wide window with the estimate from a narrower one, so a triple nobody has seen falls back on the pair inside it.

Kneser and Ney’s rule refines the fallback by asking, of the lower-order estimate, not how often a word occurred but in how many different contexts it occurred, which is what stops a word like Francisco from looking common when it only ever appears after one other word.

There is one way of scoring a model of this kind and it is the obvious one. Take text the model has never seen, ask it for the probability of each word in turn given what came before, and multiply. A model that gives the actual text a high probability is a model that would have guessed well.

Multiplying thousands of numbers below one underflows, and the result depends on how long the text is, so the reported figure is the geometric mean of the inverses. Ask over how many equally likely words a model would have to be guessing to do this well, and that number is the perplexity. A model with one chance in a hundred at every word has a perplexity of 100, a model certain of every word has 1, and lower is better because a smaller number of effective choices is a better-informed guess.

perplexity  =  exp( −(1⁄M) Σ over positions of  ln P(word | context) )

The same quantity in bits per word is the cross-entropy, and perplexity is two to that power. A reader of the literature meets both and neither is more fundamental. On the six reporting sentences a two-word model with one added scores 4.5618 bits per word, and two to that power is 23.6179, which is the perplexity quoted above.

Now the trade of Part 2 can be measured. Fit the same corpus at every width from one to five, score each on the six reporting sentences, and see where the curve turns.

…

The grey line falls all the way, from 35.06 at one word to 1.6025 at five, and it is the score on the sentences the counts came from, so it is measuring how much of the corpus the model has memorised. The indigo line, on text nothing was fitted to, turns immediately. One word scores 46.73, two words 8.9626, and from there it rises through 13.00, 20.09 and 23.40. Two words is the best this corpus supports, and every wider window is worse despite having strictly more information available to it.

The reason is Part 3’s table. At three words per run, two fifths of the reporting text is runs that never occurred, so most of what a three-word model says comes from the constant rather than from the counts. The extra context it could use is context it has almost never seen.

Step 1 claimed that counting words one at a time carries no information about order. That is checkable rather than arguable. Take the six reporting sentences, reverse the words of each, and score both versions with the same model.

The equality in the first row is exact and has to be, because a product does not depend on the order of its factors and the factors are the same set of words either way. Every one of the 53 positions is scored from the same table however the sentence is arranged, so the two columns could not have differed.

The third row is the part worth noticing. A three-word model is less offended by the scrambling than a two-word model, at 111.8429 against 1715.1308, and the reason is the smoothing rather than any weaker grasp of order. Most of what a three-word model says about any text at all comes from the constant, so it was never very confident about the original either.

A perplexity is a number about one model reading one text with one vocabulary, and moving any of those three moves the number for reasons that have nothing to do with how good the model is. The vocabulary is the one that catches people, because a smaller vocabulary makes every guess easier without making any guess better informed.

This corpus can be made to show it. Fitted to eleven of the forty-four sentences the model has a vocabulary of 36 words, and a model over 36 words that knows nothing scores 35.9998. Fitted to all forty-four it has 64 words, and knowing nothing there scores 63.9975. The ignorant model looks nearly twice as good on the smaller vocabulary, and it is the same model.

That first row is worth naming plainly. A two-word model fitted to eleven sentences, at the constant chosen for the full corpus, is worse on the reporting text than a model that gives every word of its vocabulary the same probability. The counting only starts to pay once there is enough text for the counts to mean something, and on the way there it can be beaten by the crudest thing available.

The answer in step 8 is a distribution, and there are two things to do with a distribution. One is to look up the probability of a word somebody else wrote, which is everything above. The other is to draw a word from it at random in proportion to the numbers, write that word down, slide the window along, and draw again. Stop when the end marker is drawn.

This is worth doing because it makes the model’s opinion visible in a way a score does not. A perplexity of 8.9626 tells you a model is better than one at 23.6179 and tells you nothing about what either of them thinks English is.

…

A one-word model produces the right words in no order, since it has no notion of order to have. Two words gives phrases that hold together for three or four words and then wander. Three gives sentences that are mostly grammatical, and by five and six the sentences are grammatical because they are the training sentences.

The draw can be reshaped before a word is taken. Raise every probability to the power of one over a temperature and renormalise, and the answer becomes more or less peaked without any word being ruled in or out. Below a temperature of one the likely words become likelier and the text more predictable; above one the tail comes up and the text more surprising. At a temperature of exactly one the draw is the model’s own answer untouched.

At a temperature of a quarter a three-word model draws The analysis of the samples was expected to agree, which is one of the forty-four sentences word for word. At a temperature of one the same seed gives The analysis of the samples. first summary delay. reviewed cost. rewrote, which is the smoothing showing through, since a little probability was spread over every word and the draw occasionally takes it.

The bar chart above is the measurement rather than the impression. Draw fifty sentences at each width with no smoothing at all and count how many come back as one of the forty-four training sentences word for word. At one word it is 0 of 50. At two it is 2, at three 10, at four 37, at five 45, and at six all fifty.

A six-word model on this corpus draws nothing that was not already written down, which is the same fact as the grey line in step 18 falling to 1.6025, seen from the other side. What it has learned is the forty-four sentences, and its excellent score on those sentences is a report of that and not of anything else.

The Markov assumption is not an approximation that more data improves. It is a statement about what the model is allowed to condition on, and anything outside that window is absent from the description altogether rather than approximated badly.

Here is a corpus in which that can be watched. Six sentences, each of the form the samples that somebody read were late or the sample that somebody read was late, so the verb agrees with the subject every single time and the subject stands five words before the verb. There is nothing ambiguous about the corpus and nothing statistical about the rule.

Widening the window until it reaches is not a general answer. Every extra word multiplies the number of possible contexts by the size of the vocabulary, which is Part 1’s table, so the width that would reach a dependency of ten words describes a space no corpus can populate. English has agreements and references that reach much further than that, and a fixed window cannot be widened to cover them without the counting collapsing first.

A model of this kind has no content beyond the text it counted. It does not know that Dr. is usually followed by a surname; it knows that in these forty-four sentences it was followed by Alvarez seven times out of seven, and it will say so about any text you show it. Every regularity it reports is a regularity of one corpus, including the ones that are accidents of that corpus.

The measurement in step 20 is the same point in another form. Changing which sentences were counted changed the vocabulary from 36 words to 64, changed how many of a new text’s 53 predicted positions were recognised at all from 38 to 50, and changed the score from 52.03 to 8.96. None of that is the method working better or worse; it is the model being a different model because the text was different.

This is not peculiar to counting runs. Anything fitted to a corpus inherits it. It is worth stating here because the counting is so direct that the inheritance can be looked up entry by entry, which is more than can be said for most of the models on this site.

The deepest gap is the one Part 4 measured without naming. The counts say how often each run occurred. They cannot say how much probability the runs that did not occur ought to share, because that is a question about events the counting has no observations of, and no amount of counting produces observations of them.

So a smoothing rule is an assumption brought in from outside, and the choice among rules is not settled by the data. Adding one assumes every unseen run is as plausible as every other, which is why a certainty of seven out of seven falls to 0.1127. Choosing 0.005 instead assumes far less, and it was chosen by scoring candidate values on further text, which is a measurement of the consequence rather than a derivation of the rule. Somebody had to decide what to sweep over and which text to sweep on.

That the sweep found 0.005 at two words and 0.02 at four is itself the evidence. An amount that followed from the counts would not have to be searched for, and it would not have moved by a factor of four when the only thing that changed was how many words the model reads back.

Beside the three limits above there are cases where the definition simply has nothing to say, and it is worth knowing which is which. Each row below is a fact about the mathematics rather than a matter of taste, and several of them carry a choice that somebody has to make and that changes the answer.