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-, 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,
so modeling language is next-token prediction. An n-gram model adds a Markov assumption (Markov property): only the last tokens matter, . Sentences are padded with start and end symbols and , so the model also learns how sentences begin and end.
Parametrize the model by for each history of tokens. If the pair occurs times in the training text, the log-likelihood is
The constraints decouple across histories. Add a Lagrange multiplier for each one and set the derivative to zero:
So , and normalization forces . The objective is concave, so this stationary point is the global maximum: the maximum-likelihood estimate is a relative frequency.
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 %
, , and , so the product is . Yet "⟨s⟩ the dog sat ⟨/s⟩" gets probability : the bigram "the dog" was never seen, although both words were.
The parameter count explodes. With a vocabulary of there are possible bigrams and trigrams, while a billion-word corpus contains at most 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 , the inverse probability of the text normalized per token:
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 to even one test token has infinite perplexity.
Zeros are not rare accidents; Zipf's law guarantees them. The -th most frequent word has frequency roughly proportional to with , 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 (Heaps' law, with –). Word combinations are sparser still. Smoothing moves probability mass from seen events to unseen ones:
| Method | Estimate of | Idea |
|---|---|---|
| Add- (Laplace: ) | pretend every word was seen extra times | |
| Interpolation (Jelinek–Mercer) | mix orders; tune the s on held-out data | |
| Backoff (Katz) | the trigram estimate if the trigram was seen, else a discounted, renormalized bigram estimate | trust long contexts only when they have data |
| Kneser–Ney | subtract a fixed discount and give the freed mass to words that follow many different histories |
A history occurred times, of them followed by the word . The vocabulary has words. What does add-one smoothing give for ?
Show the answer
C.
, down from the MLE of . Add-one hands each of the 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):
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 learnedText is first pre-tokenized at spaces and punctuation, so merges never cross word boundaries. Naive training rescans the corpus for every merge, for symbols and 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.
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?
- l + o
- e + r
- o + w
- w + e
Show the answer
C. o + w
"o w" occurs in every word: times. Next come "l o" (), then "w e" and "e r" ( 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 context words, concatenates them, and feeds the result through a hidden layer and a softmax over the vocabulary:
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 per token, which motivated hierarchical softmax, sampled losses and word2vec's negative sampling (Representation Learning).
A fixed window still caps the context at words. A recurrent language model (Mikolov et al., 2010) carries a state, , and predicts from , 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 .
From language models to translation
Many tasks map one sequence to another: translation, summarization, speech recognition. A conditional language model factors . In the encoder–decoder architecture (Sutskever, Vinyals & Le, 2014; Cho et al., 2014), one RNN reads into a vector and a second RNN, a language model conditioned on that vector, writes . 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 is a search problem. Greedy decoding takes the most likely token at each step, and beam search keeps the 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 tokens of history, and its maximum-likelihood estimate is the relative frequency .
- 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- (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.
An unsmoothed trigram model assigns probability to one trigram of a -token test text and reasonable probabilities to all the others. What is its perplexity on that text?
- Slightly higher than without that token
- Unchanged: one token in is negligible
- Infinite
- Zero
Show the answer
C. Infinite
The text's probability is a product containing a factor , so . Equivalently, the per-token cross-entropy contains . One unseen event ruins the whole evaluation, which is why every practical model is smoothed.
Why does Kneser–Ney back off to a continuation probability, proportional to the number of distinct words that precede , instead of 's plain frequency?
- Continuation counts are cheaper to store than frequencies
- The lower-order estimate is used mainly for unfamiliar contexts, where words seen after many different histories are the better guesses
- It guarantees that the model never assigns probability zero
- 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 follows new words, which the number of distinct predecessors measures.
On the same test text, model A has perplexity with tokenizer X and model B has perplexity with tokenizer Y. Which model is better?
- A, because its perplexity is lower
- B, because longer tokens are harder to predict
- They tie, since perplexity does not depend on tokenization
- 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, per token may mean fewer bits per character than .
Why can a byte-level BPE tokenizer encode any string, including emoji and scripts it never saw in training?
- 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
- It maps unseen characters to a special unknown token
- It learns a merge for every Unicode character during training
- 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
- N-gram Models & Smoothing · Counting, perplexity and the zero-probability problem.
- Tokenization: BPE & Friends · How text becomes tokens, and why it matters.
- Sequence-to-Sequence Models · Encoders, decoders and the birth of attention.
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).