Zipf and Heaps: the shape of vocabulary

Take a novel, count every word, and sort the counts from largest to smallest. Manning and Schütze did exactly this for Mark Twain's Tom Sawyer: 71,370 tokens and 8,018 distinct types. The most frequent type is "the" with 3,332 occurrences, then "and" with 2,972, then "a" with 1,775. At the other end sit thousands of words like "applausive" that appear exactly once. The hundred most common types alone cover 50.9% of every token in the book.

Give each type a rank R, with R = 1 for the most frequent word. Now multiply frequency by rank. For most of the list the product hovers around a constant, roughly 8,000 to 10,000, a relationship Estoup noticed in 1916 and George Kingsley Zipf made famous in the 1930s and 1940s, so it carries Zipf's name. Zipf's law says that frequency falls off as a power of rank.

Because the law is a proportionality, the useful working form anchors it to the top word. If you know how often the most frequent word occurs, everything else follows from the rank alone.

With α = 1 the arithmetic is nothing more than division. The word at rank 10 occurs about a tenth as often as the top word, the word at rank 1,000 about a thousandth as often. Slide 12 will show that natural language has α slightly below one, so the fall is a little gentler and the rare words a little less rare than the pure 1 / R rule predicts.

Read the table across a row and you see the fall; read it down a column and you see what α does. A smaller exponent leaves more mass in the tail, which for a language model means more probability spread across rare words. A larger exponent concentrates the text in fewer types. The exponent is a property of the corpus, so it differs slightly between languages, genres and preprocessing choices such as case folding.

Slide 12 plots rank against frequency for three corpora, English Wikipedia, Arabic Wikipedia and an undotted Arabic Wikipedia in which the dots that distinguish letters such as ب, ت and ث have been removed. Both axes are logarithmic, labelled from 10^0 to 10^6 in rank (the Arabic curve runs on to about 2 × 10^6) and to 10^7 in frequency, and two dashed straight lines, each pinned to the top word of its corpus, are drawn with α = 0.9252 for Arabic and α = 0.9290 for English. The first thing to understand is why anyone would expect a straight line at all.

Write Zipf's law as an equation with a constant, f(R) = C · R^−α, and take the logarithm of both sides. A product becomes a sum and a power becomes a multiplier, which is the whole trick.

On axes that show log R and log f, this is the equation of a straight line with slope −α and intercept log C, which is log f(1) since log 1 = 0. The Stanford IR book states the special case directly: log cf_i = log c + k log i with k = −1. So the two fitted slopes on the slide, −0.9252 and −0.9290, are the exponents of the two Zipf fits, and the fact that they are nearly parallel says Arabic and English share the same kind of head-and-tail shape.

Two places where the real curve leaves the line

Look at the slide again and the solid curves do not follow the dashed lines everywhere. They deviate in two characteristic ways, and both are diagnostic rather than noise. At the head, the curve is flatter than the power law: the top few words are common, but the drop from rank 1 to rank 10 is smaller than R^−α demands. This is the same shortfall the Tom Sawyer table showed: f × R was 3,332 for "the" against 8,000 to 10,000 further down, and it is why Mandelbrot added the shift term (R + ρ).

How that flat head looks on a plot depends on where the line is anchored. On slide 12 both fits pass through f(1). The blue English curve bulges slightly above the purple line only for ranks 2 to about 15, then runs just under it. The Arabic curves behave differently: they dip below the red line for ranks 3 to about 50 and cross back above it. At Wikipedia scale the head deviation is small, and the head is not uniformly flatter. The flat head is clearest in small texts such as Tom Sawyer and the explorer's sample; on slide 12 the dominant departure is the tail.

At the tail, beyond about rank 10^4, the curves steepen sharply below both lines and then turn into a staircase with horizontal steps at frequencies 3, 2 and 1, stretching out to about rank 2 × 10^6 for Arabic. The reason is that a frequency is a count, and counts are integers. There is no word that occurs 1.5 times. If 400,000 types each occur exactly once, they occupy 400,000 consecutive ranks at height f = 1, which draws as one long flat step. The step at f = 2 is shorter because fewer types occur exactly twice, and so on upward until the counts are large enough that adjacent ranks rarely share a value and the curve looks smooth. The bottom step is the longest because types seen once are the largest single group, the hapax legomena that concept four returns to.

One more thing the slide shows without saying it. In the tail, the Arabic curves sit above the English one: at any low count, Arabic has more types occurring at least that often. Templatic morphology and attached clitics mean that a single Arabic lexeme surfaces as many distinct spelled forms, each of which is a separate type for a whitespace tokenizer. That is a preview of the next concept, where the same fact shows up as a larger k in Heaps' law.

Zipf describes a Corpus frozen at one size. Now let the corpus grow. Read the first thousand words of Pride and Prejudice and you meet 361 distinct types. After ten thousand words the count is 1,698; after fifty thousand, 4,304; at the end of the novel, 123,627 tokens have produced 6,298 types. Each new stretch of text adds fewer new words than the last, but it never adds none. The same pattern holds across corpora of every size.

The rule behind these numbers is Heaps' law, also called Herdan's law after the linguist who described it in 1960, nearly two decades before Heaps (1978). The Vocabulary size is a power of the token count, with an exponent strictly between zero and one.

The two halves of the constraint on β say two different things. Because β < 1, growth is sublinear: doubling the corpus does not double the vocabulary. Because β > 0, growth is unbounded: the derivative d|V| / dN = k β N^(β − 1) is positive for every N, so the curve keeps rising however far you extend it. SLP3 phrases the second half bluntly: no matter how big our vocabulary, we will never have a vocabulary that captures all the possible words that might occur.

The slide's three fits, and what the constants mean

Slide 14 fits the law to the same three corpora as before and reports k and β for each. The constants are worth reading as a pair. k is a multiplicative scale (the predicted |V| at N = 1) that shifts the whole curve up, and β sets the slope on log-log axes: the ratio between two corpus sizes, (N2 / N1)^β, depends on β alone. Plugging in three corpus sizes makes the comparison concrete.

Now compare languages. At a million tokens Arabic Wikipedia reaches 115,672 types, about two and a half times the English figure, and undotted Arabic reaches 98,312. Arabic gets there because of its k, 73 against 15: templatic morphology and attached clitics such as wa-, bi- and -hu multiply the surface forms of every lexeme, so the vocabulary is large from the very first pages. Its β is lower, though, so the curve bends sooner: a hundredfold larger corpus multiplies the English vocabulary by 100^0.583 ≈ 14.7 but the Arabic vocabulary by only 100^0.533 ≈ 11.6. Removing the dots collapses distinct letters into one shape, and the fit agrees that this shrinks the vocabulary: undotted Arabic is below dotted Arabic at every size in the table. Its larger k (90 against 73) is offset by its smaller β, and the two curves cross below about 2,400 tokens, so k alone never tells you which vocabulary is bigger; evaluate k N^β at the N you care about. Parts 03 and 04 explain the morphology.

Typical values, and how the slide compares

The constants reported across five reference points are easiest to read side by side.

SLP3 summarizes the law as vocabulary growing a little faster than the square root of the corpus length in words, with β depending on corpus size and genre. The Arabic exponents, 0.533 and 0.506, fall inside SLP3's 0.44 to 0.56 band; the English 0.583 is just above it, which SLP3's "or even higher" allows. The English k of 14.9 is on the low side, which is what you get when a fit trades a smaller k for a larger β; the two constants are not independent estimates.

Put the two laws together and a design problem falls out. In Tom Sawyer, 3,993 of the 8,018 types occur exactly once, which is 49.8%. In the three chapters of Pride and Prejudice inside the explorer, 475 of 845 types occur once, or 56%. A type seen exactly once is a Hapax legomenon, from the Greek for "read only once", and in corpus after corpus these are about half of everything a model must store.

That one half is not a coincidence; it falls out of Zipf's law. With α = 1, the type at rank R has count C / R, so the number of types with count at least m is the rank at which the count drops to m, namely C / m. The types with count exactly m are then C / m − C / (m + 1) = C / (m (m + 1)), and dividing by the total C gives a share of 1 / (m (m + 1)): one half seen once, one sixth seen twice, one twelfth seen three times.

Baayen (2001) develops this connection between the frequency spectrum and vocabulary growth in full, and it is why the bottom step of the staircase on slide 12 is the longest.

Slides 15 and 16 list the consequences, and they form a chain rather than a list. Start with size. Heaps' law says a word-level Vocabulary on a large corpus runs to hundreds of thousands or millions of types, and every one of them needs a row in an embedding matrix and a column in the output softmax. Memory grows with |V| × d, where d is the embedding width. Then comes sparsity, which is Zipf's contribution: since half of those types belong to hapax legomena, half of the parameters in that matrix have been trained on a single example. Whatever the model learned about "applausive" it learned from one sentence.

Next comes the guarantee. Because Heaps' law has a positive derivative at every N, any finite training corpus stops somewhere on a curve that is still rising. New text therefore always contains types that were never seen, and those types are out-of-vocabulary. This is not a defect of a small corpus that a bigger one would cure; a bigger corpus only pushes the OOV rate down along the same curve, never to zero. Finally, evaluation inherits the problem. Earlier SLP3 drafts warned that mapping unseen words to an <UNK> special token lets a model buy a lower perplexity simply by choosing a smaller vocabulary, since more of the test set collapses onto one easy symbol. The current chapter 3 sidesteps the issue by making the vocabulary subword tokens, so that, in its words, the test set can never contain unseen tokens.

• Huge word-level vocabularies: memory in the embedding and output layers scales with |V|.
• Sparsity: about half of all types are hapax legomena, so about half of the rows have one training example.
• Guaranteed OOV: Heaps' law keeps rising, so new text always brings unseen types.
• Evaluation sensitivity: mapping unseen words to <UNK> changes what a perplexity number means.

Two answers to the same problem

The two families of language model respond to the chain at different points. N-gram models keep the word as the unit and repair the probability estimate: smoothing moves a little probability mass from seen events to unseen ones, and backoff falls back to a shorter context when the longer one was never observed. Lecture 3 and SLP3 chapter 3 develop both. Neural models change the unit instead. With Subword tokenization, learned by byte-pair encoding as Sennrich, Haddow and Birch showed for machine translation in 2016, a word never seen in training is spelled out of pieces that were, and with byte-level fallback there is nothing left that cannot be represented. The vocabulary becomes a design choice of tens of thousands of units rather than a fact about the corpus, which is exactly the trade part 6 examines.