Heaps' Law

The Law

As a corpus grows, its vocabulary keeps growing, but with diminishing returns. No matter how much text you collect, you will always encounter new word types.

$\lvert V \rvert = k \times N^\beta$

• $\lvert V \rvert$: vocabulary size (number of unique types)
• $N$: total number of tokens in the corpus
• $\beta$: exponent, typically 0.4-0.6
• $k$: language-dependent constant, typically 30-100

Log-Log Estimation

Taking logs:

$\log\lvert V \rvert = \log(k) + \beta \cdot \log(N)$

Plot $\log(\text{vocabulary size})$ against $\log(\text{total tokens})$. The result is a straight line:

• Slope = $\beta$
• Y-intercept = $\log(k)$

Why Growth Diminishes

When only 100 tokens have been seen, each new token is likely to be a new type. After 10,000 tokens, most new tokens are repeats of known words. After 1 million tokens, genuinely new types are rare. Yet mathematically, $\lvert V \rvert$ never plateaus: it grows as $N^\beta$, which is unbounded (albeit slowly).

With $\beta = 0.5$: doubling $N$ increases $\lvert V \rvert$ by a factor of $2^{0.5} \approx 1.41$. Quadrupling $N$ doubles $\lvert V \rvert$.

Heaps’ Law and Zipf’s Law: The Connection

Zipf’s Law explains the shape of the frequency distribution (many rare words). Heaps’ Law explains the growth of vocabulary with corpus size (unbounded new types). Together they tell a single story: the tail of rare words is not only long but also inexhaustible. Collecting more data reduces but never eliminates the problem of unseen words.

Consequence for Classification

Smoothing is a mathematical necessity, not a pragmatic convenience. Heaps’ Law guarantees that:

1. Any finite training corpus will have an incomplete vocabulary.
2. New text will contain types never seen in training, regardless of training corpus size.
3. Without smoothing, $P(w \mid c) = 0$ for unseen words, collapsing all class probabilities to zero.

This is the theoretical justification for Laplace (add-one) smoothing: it assigns non-zero probability to the infinite set of possible but unseen word types by reserving a portion of the probability mass.

Summary

Aspect	Detail
Heaps’ Law	$\lvert V \rvert = k \times N^\beta$
$\beta$ range	0.4-0.6
$k$ range	30-100
Estimation	Least-squares on log-log plot
Consequence	Vocabulary is effectively infinite; smoothing is mandatory

Past paper questions: y2024p3q7 (feature engineering)