Simple Algorithm
Artificial Intelligence · Hidden Layer · 22 min

From N-grams to Embeddings

Classic language modeling and tokenization.

Before neural networks, the best language models simply counted: how often does each word follow the previous two? Counting is exact, fast and transparent, and it fails in an instructive way, because most word sequences you will ever read have never been written before. This lesson builds n-gram models and their smoothing, the tokenizers that decide what a "word" is, and the neural models whose embeddings broke the sparsity barrier.

What you’ll learn

  • Factor a sequence probability with the chain rule, derive the maximum-likelihood n-gram estimates, and compute perplexity.
  • Explain why Zipf's law makes unsmoothed n-grams fail, and apply add-kk, interpolation and Kneser–Ney smoothing.
  • Run byte-pair encoding by hand, state its cost, and explain why byte-level subwords have no out-of-vocabulary words.
  • Explain how a neural language model with shared embeddings generalizes to unseen n-grams, and what an encoder–decoder adds.

Language models and maximum likelihood

A language model assigns a probability to every sequence of tokens. The chain rule of probability factors it exactly into next-token predictions,

P(w1,…,wT)=∏t=1TP(wt∣w1,…,wt−1),P(w_1,\dots,w_T)=\prod_{t=1}^TP(w_t\mid w_1,\dots,w_{t-1}),

so modeling language is next-token prediction. An n-gram model adds a Markov assumption (Markov property): only the last n−1n-1 tokens matter, P(wt∣w<t)≈P(wt∣wt−n+1:t−1)P(w_t\mid w_{<t})\approx P(w_t\mid w_{t-n+1:t-1}). Sentences are padded with start and end symbols ⟨s⟩\langle s\rangle and ⟨/s⟩\langle/s\rangle, so the model also learns how sentences begin and end.

DerivationMaximum likelihood is counting
  1. ℓ(θ)=∑h∑wc(h,w)log⁡θw∣hsubject to∑wθw∣h=1  for each h\ell(\theta)=\sum_h\sum_wc(h,w)\log\theta_{w\mid h}\qquad\text{subject to}\quad\sum_w\theta_{w\mid h}=1\ \text{ for each }h

    Parametrize the model by θw∣h=P(w∣h)\theta_{w\mid h}=P(w\mid h) for each history hh of n−1n-1 tokens. If the pair (h,w)(h,w) occurs c(h,w)c(h,w) times in the training text, the log-likelihood is

  2. ∂∂θw∣h[ℓ(θ)−∑h′λh′(∑w′θw′∣h′−1)]=c(h,w)θw∣h−λh=0\frac{\partial}{\partial\theta_{w\mid h}}\Big[\ell(\theta)-\sum_{h'}\lambda_{h'}\Big(\sum_{w'}\theta_{w'\mid h'}-1\Big)\Big]=\frac{c(h,w)}{\theta_{w\mid h}}-\lambda_h=0

    The constraints decouple across histories. Add a Lagrange multiplier λh\lambda_h for each one and set the derivative to zero:

  3. P^MLE(w∣h)=c(h,w)c(h)\hat P_{\text{MLE}}(w\mid h)=\frac{c(h,w)}{c(h)}

    So θw∣h=c(h,w)/λh\theta_{w\mid h}=c(h,w)/\lambda_h, and normalization forces λh=∑wc(h,w)=c(h)\lambda_h=\sum_wc(h,w)=c(h). The objective is concave, so this stationary point is the global maximum: the maximum-likelihood estimate is a relative frequency.

Predict before you look

A bigram model is trained on three sentences: "⟨s⟩ the cat sat ⟨/s⟩", "⟨s⟩ the cat ran ⟨/s⟩" and "⟨s⟩ a dog sat ⟨/s⟩". What probability, in percent, does it assign to "⟨s⟩ the cat sat ⟨/s⟩"?

Show the answer

33 %

P(the∣⟨s⟩)=23P(\text{the}\mid\langle s\rangle)=\tfrac23, P(cat∣the)=22P(\text{cat}\mid\text{the})=\tfrac22, P(sat∣cat)=12P(\text{sat}\mid\text{cat})=\tfrac12 and P(⟨/s⟩∣sat)=22P(\langle/s\rangle\mid\text{sat})=\tfrac22, so the product is 13≈33%\tfrac13\approx33\%. Yet "⟨s⟩ the dog sat ⟨/s⟩" gets probability 00: the bigram "the dog" was never seen, although both words were.

The parameter count explodes. With a vocabulary of ∣V∣=50,000|V|=50{,}000 there are 2.5×1092.5\times10^9 possible bigrams and 1.25×10141.25\times10^{14} trigrams, while a billion-word corpus contains at most 10910^9 trigram occurrences. Storage is not the problem, since only observed n-grams need entries; estimation is. Almost every possible n-gram has count zero, and the next step measures what that costs.

Perplexity, Zipf and smoothing

Language models are compared by perplexity on held-out text w1,…,wTw_1,\dots,w_T, the inverse probability of the text normalized per token:

PP=P(w1,…,wT)−1/T=exp⁡(−1T∑t=1Tlog⁡P(wt∣w<t)).\mathrm{PP}=P(w_1,\dots,w_T)^{-1/T}=\exp\Big(-\frac1T\sum_{t=1}^T\log P(w_t\mid w_{<t})\Big).

It is the exponential of the average cross-entropy per token: the effective number of equally likely choices the model faces at each step (the coding-theoretic reading is derived in Information Theory for AI). A model that assigns probability 00 to even one test token has infinite perplexity.

Zeros are not rare accidents; Zipf's law guarantees them. The rr-th most frequent word has frequency roughly proportional to 1/rα1/r^{\alpha} with α≈1\alpha\approx1, so a few types ("the", "of", "and") cover a large share of the tokens, followed by an enormous tail. Often around half of the word types in a corpus occur exactly once, and the vocabulary keeps growing with corpus size NN (Heaps' law, ∣V∣∝Nβ|V|\propto N^{\beta} with β≈0.4\beta\approx0.4–0.60.6). Word combinations are sparser still. Smoothing moves probability mass from seen events to unseen ones:

MethodEstimate of P(w∣h)P(w\mid h)Idea
Add-kk (Laplace: k=1k=1)c(h,w)+kc(h)+k∣V∣\dfrac{c(h,w)+k}{c(h)+k\abs V}pretend every word was seen kk extra times
Interpolation (Jelinek–Mercer)λ3P^(w∣u,v)+λ2P^(w∣v)+λ1P^(w)\lambda_3\hat P(w\mid u,v)+\lambda_2\hat P(w\mid v)+\lambda_1\hat P(w)mix orders; tune the λ\lambdas on held-out data
Backoff (Katz)the trigram estimate if the trigram was seen, else a discounted, renormalized bigram estimatetrust long contexts only when they have data
Kneser–Neymax⁡(c(v,w)−D,0)c(v)+λ(v) Pcont(w)\dfrac{\max(c(v,w)-D,0)}{c(v)}+\lambda(v)\,P_{\text{cont}}(w)subtract a fixed discount D≈0.75D\approx0.75 and give the freed mass to words that follow many different histories
Kneser–Ney's continuation probability Pcont(w)∝∣{v:c(v,w)>0}∣P_{\text{cont}}(w)\propto\abs{\{v:c(v,w)>0\}} fixes a subtle flaw. "Francisco" is frequent, but almost only after "San", so it should rarely be predicted after an unfamiliar word, which plain unigram backoff would do often. Interpolated modified Kneser–Ney was the strongest count-based smoother in Chen and Goodman's (1999) comparison; the Deep Layer derives these estimators.
Check your understanding

A history hh occurred c(h)=20c(h)=20 times, 1010 of them followed by the word ww. The vocabulary has 10,00010{,}000 words. What does add-one smoothing give for P(w∣h)P(w\mid h)?

  1. 0.50.5
  2. 11/21≈0.5211/21\approx0.52
  3. 11/10,020≈0.001111/10{,}020\approx0.0011
  4. 1/10,020≈0.00011/10{,}020\approx0.0001
Show the answer

C. 11/10,020≈0.001111/10{,}020\approx0.0011

(10+1)/(20+10,000)≈0.0011(10+1)/(20+10{,}000)\approx0.0011, down from the MLE of 0.50.5. Add-one hands each of the 10,00010{,}000 words a pseudo-count, so over 99% of this history's mass goes to words never seen after it. With large vocabularies add-one is far too aggressive, which is why discounting methods such as Kneser–Ney win.

Tokenization and byte-pair encoding

What counts as a token? A word-level model has a fixed vocabulary, so any word missing from it becomes an out-of-vocabulary [UNK] symbol and its meaning is lost. Characters never fail but make sequences long. Subword tokenization sits between them: frequent words stay whole and rare words are split into frequent pieces. The standard algorithm is byte-pair encoding, adapted from Gage's (1994) compression method by Sennrich, Haddow and Birch (2016):

text
BPE-TRAIN(corpus, number of merges M)
  split every word into base symbols (characters, or the 256 bytes for byte-level BPE)
  for m = 1..M:
      count each adjacent pair (a, b), weighted by word frequency
      (a, b) ← the most frequent pair                 // ties broken by a fixed rule
      replace every adjacent occurrence of a b by the new symbol ab
      append (a, b) to the merge list
  return the merge list                           // vocabulary = base symbols + M merges

BPE-ENCODE(word, merge list)
  start from base symbols; apply the merges in the order they were learned

Text is first pre-tokenized at spaces and punctuation, so merges never cross word boundaries. Naive training rescans the corpus for every merge, O(NM)\order{NM} for NN symbols and MM merges; incremental pair counts with a priority queue are much faster. Vocabularies of tens to hundreds of thousands of tokens are typical as of the mid-2020s.

Check your understanding

A BPE learner starts from characters and the word counts tower ×4, lower ×6, low ×5 and slow ×3. Which pair does it merge first?

  1. l + o
  2. e + r
  3. o + w
  4. w + e
Show the answer

C. o + w

"o w" occurs in every word: 4+6+5+3=184+6+5+3=18 times. Next come "l o" (6+5+3=146+5+3=14), then "w e" and "e r" (4+6=104+6=10 each). After the first merge, "l ow" (14) is the most frequent pair, so low soon becomes a single token.

Neural language models and embeddings

Bengio, Ducharme, Vincent and Jauvin (2003) attacked sparsity head-on. Their neural probabilistic language model looks up a learned embedding for each of the n−1n-1 context words, concatenates them, and feeds the result through a hidden layer and a softmax over the vocabulary:

P(wt∣wt−n+1:t−1)=softmax⁡(Utanh⁡(Hx+d)+b)wt,x=[Cwt−1; … ; Cwt−n+1]P(w_t\mid w_{t-n+1:t-1})=\softmax\big(U\tanh(H\mathbf x+\mathbf d)+\mathbf b\big)_{w_t},\qquad\mathbf x=\big[C_{w_{t-1}};\,\dots;\,C_{w_{t-n+1}}\big]
The embedding table C∈R∣V∣×mC\in\R^{|V|\times m} is shared across positions and trained jointly with everything else by maximum likelihood. The parameter count, ∣V∣m+(n−1)mh+h∣V∣|V|m+(n-1)mh+h|V|, grows linearly in ∣V∣|V| and nn, not like ∣V∣n|V|^n. (The original model also had optional direct connections from x\mathbf x to the output.)

Why does this beat counting? Words used in similar contexts get similar vectors, so evidence about one sentence transfers to sentences never seen. Bengio et al.'s example: having seen "The cat is walking in the bedroom", the model should give a reasonable probability to "A dog was running in a room", because cat and dog, the and a, walking and running have similar embeddings, while an n-gram table treats all those n-grams as unrelated. The price is compute: the output softmax costs O(h∣V∣)\order{h|V|} per token, which motivated hierarchical softmax, sampled losses and word2vec's negative sampling (Representation Learning).

A fixed window still caps the context at n−1n-1 words. A recurrent language model (Mikolov et al., 2010) carries a state, ht=tanh⁡(Wht−1+UCwt)\mathbf h_t=\tanh(W\mathbf h_{t-1}+UC_{w_t}), and predicts wt+1w_{t+1} from ht\mathbf h_t, so in principle the whole history counts. Training by backpropagation through time suffers from vanishing gradients, which LSTMs mitigate (Recurrent Networks & LSTMs). Each step costs O(h2+h∣V∣)\order{h^2+h|V|}.

From language models to translation

Many tasks map one sequence to another: translation, summarization, speech recognition. A conditional language model factors P(y∣x)=∏tP(yt∣y<t,x)P(\mathbf y\mid\mathbf x)=\prod_tP(y_t\mid y_{<t},\mathbf x). In the encoder–decoder architecture (Sutskever, Vinyals & Le, 2014; Cho et al., 2014), one RNN reads x\mathbf x into a vector and a second RNN, a language model conditioned on that vector, writes y\mathbf y. Squeezing a whole sentence into one vector is a bottleneck. Attention (Bahdanau, Cho & Bengio, 2015) removed it by letting the decoder take a weighted average of all encoder states at every step, the idea that grew into the transformer (Attention & Transformers).

Generating from P(y∣x)P(\mathbf y\mid\mathbf x) is a search problem. Greedy decoding takes the most likely token at each step, and beam search keeps the BB best partial outputs; neither is guaranteed to find the most probable sequence, and the most probable sequence is not always the best output. Translation quality was long measured by BLEU, which counts n-grams shared with human reference translations.

Key takeaways

  • The chain rule makes language modeling next-token prediction; an n-gram model keeps only n−1n-1 tokens of history, and its maximum-likelihood estimate is the relative frequency c(h,w)/c(h)c(h,w)/c(h).
  • Perplexity, the exponential of the per-token cross-entropy, is the standard metric; one zero probability makes it infinite, and Zipf's law guarantees zeros.
  • Smoothing reallocates mass to unseen events: add-kk (a Dirichlet posterior mean, too crude for large vocabularies), interpolation, backoff, and Kneser–Ney's discounts and continuation counts.
  • Byte-pair encoding builds a subword vocabulary by repeatedly merging the most frequent adjacent pair; at the byte level nothing is out of vocabulary.
  • Neural language models share embeddings across contexts, so similar words share statistical strength; recurrent networks remove the fixed window, and encoder–decoders with attention lead to transformers.

Check yourself

In the interactive lesson these are scored with your confidence, and what you miss comes back for review.

Question 1

An unsmoothed trigram model assigns probability 00 to one trigram of a 10,00010{,}000-token test text and reasonable probabilities to all the others. What is its perplexity on that text?

  1. Slightly higher than without that token
  2. Unchanged: one token in 10,00010{,}000 is negligible
  3. Infinite
  4. Zero
Show the answer

C. Infinite

The text's probability is a product containing a factor 00, so P−1/T=∞P^{-1/T}=\infty. Equivalently, the per-token cross-entropy contains −log⁡0=∞-\log0=\infty. One unseen event ruins the whole evaluation, which is why every practical model is smoothed.

Question 2

Why does Kneser–Ney back off to a continuation probability, proportional to the number of distinct words that precede ww, instead of ww's plain frequency?

  1. Continuation counts are cheaper to store than frequencies
  2. The lower-order estimate is used mainly for unfamiliar contexts, where words seen after many different histories are the better guesses
  3. It guarantees that the model never assigns probability zero
  4. Plain frequencies cannot be estimated for rare words
Show the answer

B. The lower-order estimate is used mainly for unfamiliar contexts, where words seen after many different histories are the better guesses

A word like "Francisco" can be frequent while appearing after only one history ("San"). When the bigram context is new, what matters is how readily ww follows new words, which the number of distinct predecessors measures.

Question 3

On the same test text, model A has perplexity 4040 with tokenizer X and model B has perplexity 6060 with tokenizer Y. Which model is better?

  1. A, because its perplexity is lower
  2. B, because longer tokens are harder to predict
  3. They tie, since perplexity does not depend on tokenization
  4. It cannot be decided from these numbers: per-token perplexities over different token sequences must first be converted to a common unit, such as bits per character
Show the answer

D. It cannot be decided from these numbers: per-token perplexities over different token sequences must first be converted to a common unit, such as bits per character

The total log-probability of the text is comparable; the per-token average is not, because the two tokenizers produce different numbers of tokens. If Y's tokens are longer, 6060 per token may mean fewer bits per character than 4040.

Question 4

Why can a byte-level BPE tokenizer encode any string, including emoji and scripts it never saw in training?

  1. All 256 byte values are in the base vocabulary, and merges only combine them, so any text is at worst a sequence of single bytes
  2. It maps unseen characters to a special unknown token
  3. It learns a merge for every Unicode character during training
  4. It falls back to a word-level vocabulary
Show the answer

A. All 256 byte values are in the base vocabulary, and merges only combine them, so any text is at worst a sequence of single bytes

Every string is a sequence of UTF-8 bytes, and every byte is a token. Rare text simply costs more tokens: an unseen script may take one token per byte.

Go deeper

Further reading

  • D. Jurafsky & J. H. Martin, Speech and Language Processing (3rd ed. draft), chapters on n-gram language models and on tokenization, free at web.stanford.edu/~jurafsky/slp3.
  • S. F. Chen & J. Goodman, "An empirical study of smoothing techniques for language modeling," Computer Speech & Language 13, 359–394 (1999).
  • R. Sennrich, B. Haddow & A. Birch, "Neural machine translation of rare words with subword units," ACL (2016).
  • Y. Bengio, R. Ducharme, P. Vincent & C. Jauvin, "A neural probabilistic language model," Journal of Machine Learning Research 3, 1137–1155 (2003).