Chapter 3The Empirical Laws of Text

Counting words, seriously

Before this book fits a single model, do something that sounds too simple to be scientific: take a large body of text, count how often each word occurs, and then stare at the counts. This is the cheapest experiment in natural language processing, since a few lines of shell script will do it, and it also produces one of the most consequential findings in the field.

Language is wildly and lawfully unbalanced, and every system we build afterwards either respects that imbalance or is quietly broken by it.

Run the experiment on any sizeable English corpus and the same picture appears, with a handful of words such as the, of, and, to and a taking a startling share of all running text.

The Brown corpus makes a good witness, and this chapter measures it repeatedly. Every figure comes from autograder/nlp_pipeline.py, which is the tokeniser and fitting code Project 1 is graded against, so the numbers here are the ones your own submission should reproduce.

Under it Brown holds $1{,}023{,}734$ tokens and $44{,}324$ distinct words, of which the alone accounts for $6.84$ per cent, and the ten most frequent words together for $24.1$ per cent.

A different tokeniser gives different totals. A stricter rule that keeps only fully alphabetic tokens, discarding the digits and the apostrophe forms that TOKEN_RE admits, drops $V$ to $41{,}151$. Neither count is wrong, and neither is comparable to the other, so state the tokeniser whenever you state a count.

At the other end of the table something stranger shows up, because almost half of all distinct words occur exactly once. In Brown the figure is $39.5$ per cent, with $54.3$ per cent occurring twice or fewer. These singletons have a name, hapax legomena, which is Greek for “said once”, and their sheer abundance is the first sign that word frequency does not behave the way intuition expects.

Two clarifications before we go on, because the vocabulary of counting causes endless confusion. A token is a running occurrence of a word and a type is a distinct word, so the sentence “the cat saw the dog” has five tokens but four types, because the occurs twice. Everything in this chapter is a statement about how types and tokens relate.

Zipf’s law

Order the types by frequency, most frequent first, and give each one a rank, so that the most frequent word has rank 1, the next has rank 2, and so on.

George Kingsley Zipf did this in the 1930s, by hand and in heroic quantity, and he found that frequency and rank trade off almost exactly inversely:

$$\begin{equation} f(r) \;\approx\; \frac{C}{r^{\alpha}}, \qquad \alpha \approx 1, \label{eq:zipf} \quad\text{(3.1)} \end{equation}$$

where $f(r)$ is the frequency of the rank-$r$ word and $C$ is a constant of the corpus.

Read literally, that says the second word is about half as frequent as the first, the tenth about a tenth as frequent, and the hundredth about a hundredth.

A power law is a straight line

Take logarithms of both sides. Equation (3.1) becomes

$$\begin{equation} \log f(r) \;=\; \log C \;-\; \alpha \log r, \label{eq:zipf-log} \quad\text{(3.2)} \end{equation}$$

which is $y = mx + c$ with $y = \log f$, $x = \log r$, slope $m = -\alpha$ and intercept $c = \log C$.

That is the whole trick, and it is worth learning once because it keeps returning. Plot frequency against rank on log log axes and the law becomes a check you can make by eye, since if the points lie on a line then the law holds and the steepness of that line is $\alpha$. Fitting the exponent is then ordinary least squares rather than curve fitting.

Every empirical law in this chapter is a power law, so every one of them becomes a line under logarithms, and so do the neural scaling laws of Chapter 18.

This is the most reproduced plot in corpus linguistics and you will draw it in Project 1, with dots hugging a descending line across three or four orders of magnitude, from the down into the fog of hapaxes.

The line is not perfect, and its imperfections are informative. At the very top the few most frequent words sit slightly off it, while at the bottom the singletons form discrete horizontal shelves, because a word can occur once or twice but never $1.4$ times.

Benoît Mandelbrot proposed a small correction that fits the head far better:

$$\begin{equation} f(r) \;\approx\; \frac{C}{(r + \beta)^{\alpha}}, \label{eq:mandelbrot} \quad\text{(3.3)} \end{equation}$$

where the shift $\beta$ flattens the curve for the first few ranks.

How large $\beta$ comes out depends almost entirely on how much of the tail you fit, because $\beta$ is what absorbs the bend. On Brown:

Fit the head alone and $\beta$ comes out exactly zero, so Mandelbrot buys nothing and plain Zipf already describes the head. Fit every rank, which is what fit_mandelbrot does, and $\beta$ runs into the hundreds.

A large $\beta$ is therefore not a verdict on your corpus but simply what a single power law needs in order to cover a curve that bends. Notice that $\alpha$ climbs along with it, because both are absorbing the same curvature, so quote $\alpha$, $\beta$ and the rank range together or quote none of them.

Zipf’s own explanation for why language does this was a principle of least effort, where speakers want a small vocabulary of reusable words while listeners want a large vocabulary of precise ones, and the power law is where that tug of war settles.

Later work is a useful corrective, because surprisingly weak assumptions produce Zipf like curves, including random typing with a space bar. The law’s existence therefore tells us less than one might hope, while its consequences for us are concrete, and we return to them at the end of the chapter.

Fitting the exponent

Reading a law off a plot is not the same as measuring it, so this section fits $\alpha$ properly, on data you can check by hand.

The corpus is a collection of Indian budget speeches, and the frequency table gives fifteen rows covering ranks $1$ through $10$ and ranks $233$ through $237$. The top word, the, occurs $59{,}042$ times, the word at rank $10$ occurs $9{,}070$ times, and the word at rank $235$ occurs $477$ times.

The first instinct is to solve for $\alpha$ from two points, and dividing Equation (3.1) by itself at two ranks makes the constant $C$ cancel:

$$\frac{f(1)}{f(10)} = \frac{C/1^{\alpha}}{C/10^{\alpha}} = 10^{\alpha}, \qquad\text{so}\qquad \alpha = \log_{10}\frac{f(1)}{f(10)} = \log_{10} 6.509 = 0.8136.$$

Now test that number where it was not fitted. Predicting rank $235$ gives $59{,}042 / 235^{0.8136} = 695$ against a measured $477$, which makes the estimate $46$ per cent too high.

The fix is to stop throwing data away, so take logarithms and fit the line of Section 3.2.1 by least squares over all fifteen points:

$$\begin{equation} \hat{\alpha} \;=\; -\, \frac{\sum_i (x_i - \bar{x})(y_i - \bar{y})}{\sum_i (x_i - \bar{x})^2}, \qquad x_i = \log r_i, \quad y_i = \log f_i. \label{eq:zipf-ls} \quad\text{(3.4)} \end{equation}$$

That gives $\alpha = 0.9426$ and $C = 83{,}239$, and the same test now predicts $485$ against $477$, so the error falls from $46$ per cent to under $2$.

These are exactly the values fit_zipf returns on the same fifteen rows, so the procedure above is the graded one, not an illustration of it.

Table 1.1 adds Mandelbrot’s correction to the comparison. The shift $\beta$ sits inside the logarithm, so least squares cannot reach it, and the remedy is to scan $\beta$, fit $\alpha$ and $C$ at each value, and keep the best. That one extra parameter buys a third off the error.

Notice that the fitted $C = 83{,}239$ is larger than the observed $f(1) = 59{,}042$, so the line does not pass through the top word, and it should not. The head is flatter than the body, which means a fit dominated by the head understates $\alpha$, and that is exactly what the two point estimate did.

Now the warning promised earlier. The Mandelbrot fit is a two parameter optimisation with a shallow valley:

Doubling $\beta$ moves $\alpha$ by more than three per cent while barely moving the error, so report $(\alpha, \beta)$ as a pair, because otherwise neither number means anything.

The exponent is not a constant

One more measurement settles what $\alpha$ actually is. Fit Brown over different rank ranges and the answer moves:

The tail falls faster than the head, so a wider window gives a steeper line, and that is why the textbook claim $\alpha \approx 1$ is safe: it is a statement about the first few thousand ranks and nothing more.

An exponent quoted without its fitting range is not a measurement, so report the range every time.

Zipf as a probability

Equation (3.1) gives counts. Divide by the total count and it becomes a distribution over the vocabulary:

$$\begin{equation} p(r) \;=\; \frac{r^{-\alpha}}{H_{V,\alpha}}, \qquad H_{V,\alpha} \;=\; \sum_{k=1}^{V} k^{-\alpha}, \label{eq:zipf-prob} \quad\text{(3.5)} \end{equation}$$

where $H_{V,\alpha}$ is the generalised harmonic number.

Where the normaliser comes from

That equation is usually read past, so it is worth slowing down. Zipf’s law assigns each rank a weight, $r^{-\alpha}$, and weights are not probabilities, because nothing makes them sum to one and in general they do not.

$H_{V,\alpha}$ is simply their total, so dividing every weight by it turns the weights into probabilities, since a set of numbers divided by its own sum always sums to one. Dividing changes no ratio between two words either, so the shape the law describes survives the normalisation untouched.

A vocabulary of eight with $\alpha = 1$ makes this concrete, and the weight of rank $r$ is then just $1/r$.

The second column sums to $2.7179$ rather than to one, and that total is $H_{8,1}$. The third column is the second divided by it, and now it does sum to one.

With that in hand, $p(r)$ is the chance that a token drawn at random from the corpus is the rank $r$ word, and summing it gives the coverage of the top $k$ words:

$$\begin{equation} \operatorname{Coverage}(k) \;=\; \sum_{r=1}^{k} p(r) \;=\; \frac{\sum_{r=1}^{k} r^{-\alpha}}{\sum_{r=1}^{V} r^{-\alpha}} \;=\; \frac{H_{k,\alpha}}{H_{V,\alpha}}. \label{eq:coverage} \quad\text{(3.6)} \end{equation}$$

The middle step is the whole derivation. Summing the first $k$ probabilities means summing the first $k$ weights and dividing by the same total, and a sum of the first $k$ terms is precisely what a harmonic number is, so the ratio is not a trick. The numerator is the mass you keep, the denominator is all the mass there is, and both are sums of the same terms.

On the toy vocabulary, the top two words hold $H_{2,1}/H_{8,1} = 1.5000/2.7179 = 0.5519$, and the running sum column agrees, because it is the same arithmetic.

Why the exponent decides the tail

The normaliser also answers a question the previous section left open. What happens to coverage as the vocabulary grows?

For $\alpha \le 1$ the sum diverges, so a thousand times more vocabulary keeps adding to the denominator, the coverage of any fixed $k$ keeps falling, and the tail never becomes negligible however much text you collect. Above one the sum converges and the head holds a stable share no matter how large $V$ gets.

Measured $\alpha$ for natural language sits close to one and usually just below it, which means language lives on the side of this boundary where the tail is permanent. That is the mathematical statement of a fact Heaps’ law states empirically in Section 3.5.1, namely that new words keep arriving forever.

Coverage counts tokens, not types

One distinction has to be nailed down before the table below, because it is where the reading usually goes wrong. A type is a distinct word in the vocabulary while a token is a word as it occurs in running text, so the sentence the cat sat on the mat has six tokens and five types, because the appears twice.

Coverage counts tokens and the size of a vocabulary counts types. Those are different units, and the distance between them is the whole content of Zipf’s law, which is why a number like “two per cent of the vocabulary” and a number like “sixty-nine per cent of the text” can describe the same cut-off and still look nothing alike.

This is also why coverage is the useful form of the law. Raw counts depend on how much text you happened to collect, so two corpora cannot be compared with them, whereas $p(r)$ and $\operatorname{Coverage}(k)$ are fractions and can be. Coverage converts a curve into a budget, and that is what makes it the single most useful number in the chapter.

Read column two against column four of Table 1.2. About two per cent of the vocabulary carries about $69$ per cent of the running text. Equivalently, discarding the rarest $77$ per cent of the types costs under eight per cent of the tokens.

The model tracks the measurement closely at the head and drifts at the tail, for the reason the previous section gave, since one $\alpha$ cannot bend twice.

Three later decisions rest on this table. A stop list is short because the head is short, a truncated vocabulary loses many types and few tokens, and a subword vocabulary of $32{,}000$ pieces spends its whole budget on the head, with Chapter 5 showing what it does with the rest.

One caveat is worth keeping in view. When $\alpha \le 1$ the sum $H_{V,\alpha}$ grows without bound as $V$ grows, so the tail never becomes negligible however much text you add.

Heaps’ law: the vocabulary never closes

Zipf’s law describes a frozen corpus, whereas Heaps’ law describes what happens as a corpus grows.

Let $N$ be the number of tokens read so far and $V(N)$ the number of distinct types seen. Empirically,

$$\begin{equation} V(N) \;\approx\; K \, N^{b}, \label{eq:heaps} \quad\text{(3.7)} \end{equation}$$

with $K$ usually between 10 and 100, and the exponent $b$ usually quoted between $0.4$ and $0.6$ for English.

Quote the two together, because they are coupled. A fit that raises $b$ must lower $K$ to pass through the same data, so a large $b$ always arrives with a small $K$. Pin $b$ on Brown and watch the best $K$ move with it:

So “$K$ between 10 and 100 and $b$ between 0.4 and 0.6” is one statement about a curve rather than two independent ones. Brown measures $K = 16.18$ and $b = 0.5764$ in Section 3.5.1, while Figure 1.2 shows a smaller and more homogeneous corpus at $b = 0.78$ with $K$ under two. That figure is right, because small corpora really do fit that high.

Two properties matter here. First, the exponent is less than one, so vocabulary growth decelerates, which means the second million tokens bring fewer new words than the first million did and doubling a corpus does not come close to doubling its vocabulary.

Second, and this is the part with teeth, the function never flattens, because a power law has no asymptote and there is no corpus size at which $V(N)$ stops growing. However much text you collect, the next document can still hold a word you have never seen, whether a name, a typo, a coinage, a chemical formula or a hashtag. The vocabulary of a natural language is not a closed set, and any system built around a fixed word list has already decided to fail on the tail.

You will check both properties in Project 1 by plotting $V(N)$ as your corpus streams past, and in the spirit of Section 3.8 below you will predict the curve’s shape before you draw it.

Fitting Heaps, and what extrapolation costs

Equation (3.7) linearises the same way Zipf’s law did:

$$\begin{equation} \log V(N) \;=\; \log K \;+\; b \log N. \label{eq:heaps-log} \quad\text{(3.8)} \end{equation}$$

So $b$ is a slope, and it is also an elasticity, because doubling the corpus multiplies the vocabulary by $2^{b}$. At $b = 0.5$, four times the text gives twice the vocabulary.

Sample the vocabulary every $1{,}000$ tokens, which is what fit_heaps does, and fit all $1{,}024$ points. Five of them:

The fit gives $b = 0.5764$ and $K = 16.18$. The corpus grew by a factor of a thousand while the vocabulary grew by a factor of $93$.

Fitting the full curve matters, because least squares on five hand-picked marks gives a visibly different pair and would not agree with the grader.

Now for the experiment that matters more. Fit the law on the first $100{,}000$ tokens only and use it to predict a corpus ten times larger, where that prefix gives $b = 0.7176$ and $K = 3.50$, so

$$\hat{V}(10^{6}) = 3.50 \times (10^{6})^{0.7176} = 70{,}799, \qquad\text{against a measured } 43{,}648.$$

One decade of extrapolation, $62$ per cent too many types.

The cause is the same concavity that moved $\alpha$ earlier, because the exponent $b$ is not a constant of the language either and drifts downward as $N$ grows as the log log curve bends gently. Fit over the range you will actually operate in, and treat any extrapolation as an upper bound.

That the error is an over-estimate is worth noticing, since it is the safe direction for sizing an embedding table and the wrong direction for a cost estimate.

Zipf and Heaps are one fact seen twice

The two laws are not independent observations. If frequency falls as $r^{-\alpha}$, then a word at rank $r$ needs roughly $r^{\alpha}$ tokens of text before it appears at all. Reading that backwards, $N$ tokens reveal about $N^{1/\alpha}$ distinct types, so

$$\begin{equation} b \;\approx\; \frac{1}{\alpha}, \qquad \alpha > 1. \label{eq:zipf-heaps} \quad\text{(3.9)} \end{equation}$$

Brown fitted over all ranks gives $\alpha = 1.3492$, so Equation (3.9) predicts $b = 0.7412$ against a measured $b$ of $0.5764$. That is the right order of magnitude from two unrelated measurements, and not much better than that.

They do not agree exactly, and they should not, because the derivation assumes a single $\alpha$ holds across the whole rank range and Section 3.3 showed that it does not. The lesson is the relationship rather than the decimal places: steeper frequency decay means fewer rare words, which in turn means slower vocabulary growth.

Type token ratio and the length trap

A natural summary of lexical richness is the type token ratio

$$\begin{equation} \operatorname{TTR} \;=\; \frac{V}{N}, \label{eq:ttr} \quad\text{(3.10)} \end{equation}$$

which is vocabulary size divided by text length. Rich, varied prose should score high and repetitive, formulaic text should score low, and on the whole it does.

There is a trap, though, and Heaps’ law describes it exactly. Since $V \approx K N^{b}$ with $b < 1$, we get $\operatorname{TTR} \approx K N^{\,b-1}$, which falls as $N$ grows.

Take a 1,000 word essay and a 100,000 word novel by one author, and their TTRs will differ wildly, with the novel’s far lower, for no stylistic reason whatever. TTR is a property of a text at a length, never of the text alone.

Brown’s own fit, $K = 16.18$ and $b = 0.5764$, puts numbers on that:

Same author, same style, four different answers, and the measured column is the one that matters, falling by a factor of ten.

The first row is worth pausing on, because the fitted law is good near a million tokens and poor at a thousand, since the log log curve is concave and $1{,}024$ points pull the line towards the large $N$ end. A fitted law is a summary of a curve rather than an oracle for every point on it.

The trap, measured

Table 1.3 runs the experiment on six genres of Brown. The raw column uses the whole genre. The standardised column cuts each genre into non-overlapping windows of $8{,}000$ tokens, computes TTR in each, and averages them.

Raw TTR crowns humour as the richest genre in Brown, and humour is also the shortest genre in Brown, at $18{,}450$ tokens against $164{,}036$ for learned prose. The measurement is reading length rather than style.

Two rankings actually reverse. Raw TTR puts fiction above press reportage, while on equal windows press reportage wins, and raw TTR puts government above learned prose, while on equal windows learned prose wins. Neither reversal is noise, because both hold at every window size from $2{,}000$ tokens up to $18{,}000$.

The discipline that follows is simple and not negotiable. Never compare type token ratios across samples of different sizes. Compare equal length slices instead, or use a length corrected variant.

Length corrected variants

The measure used in Table 1.3 is the mean segmental type token ratio. Cut the text into $m$ windows of fixed size $W$ and average:

$$\begin{equation} \operatorname{MSTTR} \;=\; \frac{1}{m}\sum_{j=1}^{m} \frac{V_j}{W}. \label{eq:msttr} \quad\text{(3.11)} \end{equation}$$

It is simple and it works, and its weakness is that the answer still depends on $W$, so $W$ must be reported and held fixed across everything being compared.

A cheaper variant is the root type token ratio, $V/\sqrt{N}$, which is Equation (3.7) with $b$ forced to $0.5$, and it only removes the length effect where $b$ really is near $0.5$. Brown’s is $0.58$, close enough to make the shortcut tempting and far enough to bias a comparison.

The honest summary of lexical richness is neither of these. It is the fitted pair $(K, b)$ from Section 3.5.1, which describes the whole curve rather than one point on it.

Project 1 asks you to compare your corpus against a contrast genre, and it fixes the sample size for exactly this reason. When the measured TTRs still differ, the difference is real, because legal boilerplate and technical templates repeat themselves and fiction does not.

What the laws mean for everything downstream

These three regularities look like curiosities, but they are the standing constraints under which every model in this book operates.

Which knob moves tokens, and which moves types

The laws also price the preprocessing decisions of Chapter 2. Measured on Brown, each figure a share of the raw counts:

Read the two columns against each other. Stop word removal takes $44$ per cent of the tokens and $0.2$ per cent of the types, which is Zipf’s law stated as an engineering fact, because stop words are very few types carrying very many tokens.

Stemming is the mirror image, leaving every token where it is while $35$ per cent of the vocabulary collapses.

Dropping every type seen five times or fewer removes $72$ per cent of the vocabulary and costs $5.9$ per cent of the tokens, which is the trade Table 1.2 priced and why a fixed subword vocabulary is less of a sacrifice than it looks.

One thing barely moves at all. The Heaps fit goes from $K = 16.18$, $b = 0.5764$ to $K = 17.33$, $b = 0.5958$ once stop words and numbers are gone, so the curve is a property of the language rather than of your cleaning.

Try it yourself. code/worked_examples/empirical_laws.py prints every fit and table in this chapter. python3 empirical_laws.py harmonic builds the normaliser on a vocabulary of eight, where every division can be checked on paper, and then shows $H$ diverging at $\alpha \le 1$. python3 empirical_laws.py mandelbrot shows $\beta$ climbing from $0$ to $403$ as the fitting range widens. python3 empirical_laws.py heaps pins $b$ and watches $K$ move, then extrapolates a decade and misses by $62$ per cent.

Run it in ColabNotebookSource

The head motivates weighting. The most frequent words are overwhelmingly function words, and glue like the and of appears everywhere and so distinguishes nothing. Any similarity measure built on raw counts will be dominated by exactly the words that carry least content, which is the problem inverse document frequency solves in Chapter 4. At bottom, tf-idf is a machine for discounting the Zipfian head.

The tail motivates smoothing. Roughly half the vocabulary occurs once, and the exact fraction depends on corpus size, rising as the corpus shrinks. Full Brown gives $39.5$ per cent, its news genre $49$ per cent and its science fiction $62$ per cent, and at any of those figures reliable statistics exist for almost no specific word. Events unseen in training are the normal case. That is why the zero probability problem of Chapter 10 is the central difficulty of statistical language modelling, and why no amount of patching corner cases will address it. Every model, up to the largest LLM, must reserve belief for the unseen.

Heaps’ law motivates subwords. If the vocabulary never closes then a word level system meets out of vocabulary items forever, and mapping them all to one <unk> symbol, as in Chapter 10, throws their identity away. The modern answer is to decompose rare words into pieces that are in a closed set. That is the next chapter, and it is best read as a direct engineering response to Equation (3.7).

The empirical discipline

This chapter closes with a habit rather than a law.

Every quantitative claim above is checkable in minutes on any corpus you can lay hands on, whether the slope near $-1$, the exponent near $0.5$, or the falling TTR. This course will repeatedly ask you to predict the number before you measure it.

The point is not ritual. A prediction forces your mental model into the open where the measurement can correct it, whereas a measurement taken with no prediction slides past the mind and teaches nothing.

Calibration is knowing how far off your guesses tend to be, and it is a trainable skill as well as the difference between a practitioner who understands a system and one who merely operates it.

We start training it on word counts because word counts are cheap, and by the end of the book you will be predicting perplexities, attention patterns and retrieval failures the same way.

Further reading.

Zipf (1949), Human Behavior and the Principle of Least Effort, is still a strange and rewarding read. Manning and Schütze (1999) give the sober statistical treatment of both laws. Baayen (2001) is the modern reference for the mathematics of the tail. Both laws can be fitted in one line with numpy.polyfit or scipy.optimize.curve_fit, and the last exercise below is there because one line is enough to fit the wrong thing.

Code for this chapter

Each one reproduces the tables above. Open it in Colab, change an input and watch which numbers move.

• empirical_laws.pyZipf and Heaps, fitted

  Fitting both laws to real rank counts, the coverage curve, and the length trap that makes type token ratio misleading.

  standard library only Run it in Colab Notebook Source

From Natural Language Processing: From Corpus Statistics to Grounded LLMs, by Ramaseshan Ramachandran.