N-Grams in NLP, explained in 5 lines

Module 04 · NLP · 20 concepts

In depth / 15 lines

N-Grams, in more detail

An n-gram is a window of n consecutive tokens, and the whole idea is that simple.

The dog barked contains the bigrams the dog and dog barked, and one trigram, the dog barked.

Bag of words throws away order completely, so New York and York New look identical to it.

Adding bigrams restores just enough order for multi-word names and common phrases to survive.

That was for years the cheapest available upgrade to a text classifier, and it usually worked.

N-grams also underpinned the first practical language models, before neural networks were involved.

Such a model estimates the probability of the next word from the previous n minus one words.

The estimate is a count: how often did this word follow this context in the training corpus.

The trouble is that the number of possible n-grams grows exponentially with n.

Most four-word sequences of English have never appeared in any corpus, however large.

So counts are zero for perfectly reasonable phrases, and a zero probability is fatal.

Smoothing techniques exist entirely to move a little probability mass onto the sequences never seen.

The deeper limit is that the model only ever sees n minus one words of history.

It cannot connect a pronoun to a name mentioned two sentences earlier, which recurrent networks could.

N-grams survive today in evaluation metrics such as BLEU and ROUGE, which score overlap by matching them.

Want the full technical article? Wikipedia ↗

Deep dive

What is underneath N-Grams

A language model you can count

P(w_1, \dots, w_n) = \prod_{i=1}^{n} P(w_i \mid w_1, \dots, w_{i-1})

The probability of a sentence is the product of each word given everything before it, which is exact and impossible to estimate.

P(w_i \mid w_1, \dots, w_{i-1}) \approx P(w_i \mid w_{i-n+1}, \dots, w_{i-1})

The n-gram assumption truncates that history to the last $n-1$ words, which makes the counting tractable and throws away everything further back.

P(w_i \mid w_{i-1}) = \frac{C(w_{i-1}, w_i)}{C(w_{i-1})}

The estimate is then just division: how often this pair appeared, over how often the first word appeared at all.

The counts explode and the data does not

|V|^n

A 50,000-word vocabulary has $2.5 \times 10^{9}$ possible bigrams and $1.25 \times 10^{14}$ trigrams.

No corpus contains even a fraction of them, so almost every count is zero, and a single zero makes the whole sentence probability zero.

P(\text{sentence}) = 0 \text{ because one trigram was unseen}

That is not a rare edge case. It is the normal outcome for any sentence not in the training data, which is every sentence you care about.

Smoothing, which is the real subject

P_{\mathrm{add}}(w_i \mid w_{i-1}) = \frac{C(w_{i-1}, w_i) + \alpha}{C(w_{i-1}) + \alpha |V|}

Add-alpha smoothing pretends every possible n-gram was seen $\alpha$ times.

It is simple, it never returns zero, and it is badly wrong because it spreads mass uniformly over events that are not uniform.

P_{\mathrm{interp}} = \lambda_3 P(w_i \mid w_{i-2}, w_{i-1}) + \lambda_2 P(w_i \mid w_{i-1}) + \lambda_1 P(w_i)

Interpolation mixes the orders, so an unseen trigram falls back on the bigram and then on the unigram, with the weights fitted on held-out data.

P_{\mathrm{KN}}(w) \propto |\{ w' : C(w', w) > 0 \}|

Kneser-Ney, the best of the classical methods, changes what the fallback estimates: not how often a word occurs, but in how many different contexts it occurs.

That distinction is why it handles a word like Francisco correctly, which is frequent overall and almost never appears outside one phrase.

One model, in order

Choose $n$ , usually 3 for text and 5 for speech.
Count every n-gram and every prefix in the corpus.
Estimate the conditional probabilities by division.
Smooth them, so nothing is zero and the mass still sums to one.
Score a new sentence by summing log probabilities rather than multiplying, to avoid underflow.

What it can and cannot do

\text{perplexity} = 2^{-\frac{1}{N}\sum_i \log_2 P(w_i \mid \text{history})}

A well-smoothed 5-gram model reaches a perplexity in the low hundreds on English news, which was the state of the art for two decades.

It is fast, interpretable and still used in keyboards, spell checkers and speech decoders where latency is measured in milliseconds.

Take the sentence "The man who grew up in Paris before moving abroad still speaks fluent French".

Its limit is structural. The word French depends on Paris, seven words back, and no fixed $n$ small enough to count is large enough to see it.

Neural language models replaced the lookup table with a learned function.

That function shares statistical strength between similar contexts, instead of treating every n-gram as unrelated to every other.

Test yourself

One question on this card. Every option explains itself once you pick, right or wrong.

Question 1

What does adding bigrams give a bag-of-words model?

NLP

20 concepts in this module, then a graded test with every answer explained.

Study this module →