Sampling sentences from a language model

In 1948 Claude Shannon wanted to show what a statistical model of English "knows", so he generated text from one. His first-order word approximation picks each word independently, with its real frequency:

REPRESENTING AND SPEEDILY IS AN GOOD APT OR COME CAN DIFFERENT NATURAL HERE HE THE A IN CAME THE TO OF TO EXPERT GRAY COME TO FURNISHES THE LINE MESSAGE HAD BE THESE.

His second-order approximation picks each word given the one before it, using word-transition probabilities:

THE HEAD AND IN FRONTAL ATTACK ON AN ENGLISH WRITER THAT THE CHARACTER OF THIS POINT IS THEREFORE ANOTHER METHOD FOR THE LETTERS THAT THE TIME OF WHO EVER TOLD THE PROBLEM FOR AN UNEXPECTED.

The jump is obvious. The first is a bag of English words; the second has runs like "ATTACK ON AN ENGLISH WRITER" that read as real phrases. Shannon observed that such samples "have reasonably good structure out to about twice the range that is taken into account in their construction". Nobody had to inspect a single probability to see the difference. Jurafsky and Martin make this the official motivation: "One important way to visualize what kind of knowledge a language model embodies is to sample from it", crediting the idea to Shannon and to Miller and Selfridge (1950).

The rule behind it is simple. A Language model is a probability distribution over sentences. Sampling draws sentences from that distribution, so a sentence the model gives probability 0.001 shows up ten times as often as one it gives 0.0001. The sentences you see are therefore a portrait of where the model puts its mass. Train N-gram models of increasing order on Shakespeare and sample from each:

Reading samples like these gives you three diagnostics at once.

• Local coherence grows with n. The window of words that make sense together is about twice the model order, as Shannon noted.
• Verbatim fragments are a warning. A line you can find word for word in the training text, like the 4-gram's "It cannot be but so", means the model is replaying its corpus. Fluent output here is Overfitting, not understanding; Part 06 shows the sparse counts that cause it.
• Samples reveal the genre. The same procedure on 40 million words of Wall Street Journal text produces talk of percentages, dollars and interest rates instead. That is Genre dependence made visible, and Part 06 draws the lesson for choosing training data.

Start with the simplest model, a Unigram model computed from the text of the SLP3 book. Lay its words end to end along a ruler from 0 to 1, giving each word a strip exactly as wide as its probability. "the" has probability 0.06, so it owns [0, 0.06). "of" has 0.03 and owns [0.06, 0.09). Then "a" owns [0.09, 0.11), "to" owns [0.11, 0.13), and "in" owns [0.13, 0.15). Far along the line, "however" (p = 0.0003) sits near 0.66, and "polyphonic" (p = 0.0000018) is a hairline near 0.99.

Now draw a random number. If u = 0.10, it lands in [0.09, 0.11), so the model emits "a". If u = 0.07, it lands in [0.06, 0.09) and the model emits "of". That is the whole algorithm. Because u is uniform, the chance it lands in a strip equals the strip's width, and the width is P(w). Every word is drawn with exactly its model probability.

The general rule: inverse-CDF sampling

Put the vocabulary in any fixed order w_1, w_2, …, w_V and compute the running totals F(w_k), the cumulative distribution. Draw u from the uniform distribution on [0, 1), and return the first word whose running total exceeds u. Statisticians call this the inversion or inverse-CDF method: you are reading the cumulative distribution backwards, from a height on the vertical axis to the word underneath it.

A unigram model has no context, so to produce a sentence you simply repeat the draw. When do you stop? SLP3 generates "until we randomly generate the sentence-final token" </s>. That only works if </s> is itself a word on the line, which is one more reason the Sentence boundary tokens are part of the vocabulary. It also fixes the length distribution. If P(</s>) = p, every draw ends the sentence with chance p, so sentence length (counting </s>) is geometric with mean 1 / p. With p = 0.05, sentences average 20 tokens.

In code, this is exactly what Python's random.choices does: it turns weights into cumulative weights ("[10, 5, 30, 5] are equivalent to the cumulative weights [10, 15, 45, 50]") and binary searches them with bisect. The five-word toy below renormalizes over just those five words by scaling u by the total.

import bisect, itertools, random

words = ["the", "of", "a", "to", "in"]
probs = [0.06, 0.03, 0.02, 0.02, 0.02]
cumulative = list(itertools.accumulate(probs))
u = random.random() * cumulative[-1]
word = words[bisect.bisect_right(cumulative, u)]

Stanford's CS224N trains a Trigram model on about 1.7 million words of Reuters news and starts generating from "today the ___". The model's top candidates are "company" (0.153), "bank" (0.153) and "price" (0.077). It samples "price", a lower-ranked word, and the window moves to "the price ___", where "of" has probability 0.308. Keep going and you get:

today the price of gold per ton , while production of shoe lasts and shoe industry , the bank intervened …

CS224N's verdict is "Surprisingly grammatical! …but incoherent." Every three-word window is plausible newswire; the sentence as a whole is about nothing.

The loop

The unigram number line had a single, fixed line. A Bigram or trigram model has one line per context, and the loop chooses which line to throw at.

1. Start from <s>. A bigram needs one start symbol; a trigram pads with two, so the first context is <s> <s>.
2. Draw w_1 from P(w | <s>) using the number-line method on that conditional distribution. SLP3 describes it as "first generating a random bigram that starts with <s>", then choosing "a random bigram starting with w".
3. In general draw w_i from P(w_i | w_(i−N+1) … w_(i−1)): the Markov assumption decides how many previous words select the line.
4. Stop when </s> is drawn. Without </s> there is no stopping event, and no proper distribution over sentence lengths.

Because each draw is made with exactly its conditional probability, the probability of producing a particular sentence is the product of the conditionals you drew along the way. That is the Chain rule of probability under the Markov assumption, run forwards as a generator instead of backwards as a scorer. In practice you would add log probabilities rather than multiply.

SLP3 chapter 7 writes the same loop for neural language models, under the name random multinomial sampling: i ← 1; w_i ∼ p(w); while w_i != EOS: i ← i + 1; w_i ∼ p(w_i | w_<i). The only change is that an LLM conditions on all of w_<i, not on the last N − 1 words.

For an n-gram model the reason greedy text repeats is mechanical. The context is just the last N − 1 words, so there are finitely many contexts, and greedy decoding maps each context to one fixed next word. Greedy output either reaches </s> before any context repeats, or it comes back to a context it has already been in. From then on it must repeat everything it produced from there, forever: it already went through that stretch once without drawing </s>, so it never will. Sampling escapes because each visit draws a fresh u.

The lecture's walkthrough generates a phrase about machine learning one word at a time. After the context "deep", the model's top continuations are "learning" 0.23, "reinforcement" 0.05, "convolutional" 0.04, "neural" 0.04, "multi" 0.02, "-" 0.02 and "image" 0.01. The listed words add up to 0.41, so 0.59 of the probability sits on words the slide does not show. The draw lands on "learning".

Next, conditioning on "deep learning", the distribution is much flatter: "models" 0.06, "." 0.05, ";" 0.05, "based" 0.05, "," 0.05, "for" 0.04, "methods" 0.04, a listed mass of 0.34. The draw is ",", even though "models" is the single most likely word.

Three operations per step

1. The context selects one conditional distribution out of the model's table.
2. That distribution is laid on [0, 1), exactly like the unigram line.
3. A fresh u is drawn and the word whose interval contains it is emitted.

The shape of the two distributions matters as much as the draws. After "deep", one word holds 0.23 and the model is fairly confident. After "deep learning", the top word holds only 0.06: many continuations are plausible, the model is uncertain, and its effective Weighted branching factor is large. That is precisely what Perplexity from Part 04 measures when averaged over a test set. Flat steps are also where samples become diverse.

The output so far is "deep learning ,". To pick the next word, the model strikes "deep" out of its context and conditions on "learning ,". The distribution there is "and" 0.14, "we" 0.07, "which" 0.05, "the" 0.05, "where" 0.03, "a" 0.02, "but" 0.02, listed mass 0.38. The draw is "but", whose interval in listed order is [0.36, 0.38). The output becomes "deep learning , but", and "deep" is still printed at the front.

The probability of this particular path, given the start "deep", is the product of the three drawn conditionals: 0.23 × 0.05 × 0.02 = 0.00023. Three ordinary-looking steps already put the continuation at about one chance in four thousand, which is why sampled texts almost never repeat.

The window is a queue

An order-N model keeps exactly the last N − 1 tokens as its context. After each draw, the new token is pushed onto the back and the oldest is popped off the front: a first-in, first-out queue of fixed length. Two details are easy to get wrong.

• The popped word leaves the context, not the output. The text keeps growing; only the conditioning window has a fixed length.
• Punctuation is a token like any other. The comma fills one of the two context slots, which is why the Trigram context after "deep learning ," is "learning ," and not "deep learning".

This is the Markov assumption made physical. Once "deep" has scrolled out, nothing it contributed can influence any later draw. The model cannot remember that the sentence is about deep learning three words later, which is exactly why the Reuters sample drifts from gold to shoes to banks: every window is locally fluent, and the sentence is globally incoherent. The same queue mislabelled as a bigram explains the errata in the previous concept: a bigram queue has one slot, and the slides clearly hold two.

The obvious fix is a longer window, and CS224N states the dilemma directly: "We need to consider more than three words at a time if we want to model language well. But increasing n worsens sparsity problem, and increases model size". Longer windows mean more never-seen contexts, the Sparsity problem that leads to the memorized 4-gram Shakespeare. Breaking that trade-off is what a Neural language model does: SLP3 chapter 7 runs the very same loop, sampling each token "conditioned on our previous choices", but with a context of thousands of tokens that is represented rather than counted.