PaperlayerView exact revision on arXiv

Source-linked AI summary

Stochastic model for the vocabulary growth in natural languages

Martin Gerlach, Eduardo G. Altmann

arXiv:1212.1362v3physics.soc-phcs.CLphysics.data-an

TL;DR

Vocabulary growth depends on database size and word usage, but whether vocabulary size saturates as databases grow remains an open question. The paper models word growth with two word classes and finds that two-scaling functions describe vocabulary growth and rank frequencies, with parameters stable across databases and centuries but language-dependent.

  • Problem

    How vocabulary size depends on database size and word usage, and whether it saturates as databases grow, remain important open questions for linguistic study and search-engine estimation.

    Source: §I · p. 1

  • Method

    The paper proposes a stochastic vocabulary-growth model with two word categories, extending simpler Heaps’ and Zipf’s scalings to two regimes.

    Source: §I · p. 1

  • Results

    Two-scaling functions best describe rank frequencies and vocabulary growth, with their parameters remaining almost unchanged across centuries and databases while depending on language.

    Source: §I · p. 1, §V · p. 7

  • Takeaways & Limitations

    The findings support interpreting vocabulary growth as arising from a finite core vocabulary whose words differ from the virtually unlimited remainder.

    Source: §V · p. 7

Abstract

from arXiv · show

We propose a stochastic model for the number of different words in a given database which incorporates the dependence on the database size and historical changes. The main feature of our model is the existence of two different classes of words: (i) a finite number of core-words which have higher frequency and do not affect the probability of a new word to be used; and (ii) the remaining virtually infinite number of noncore-words which have lower frequency and once used reduce the probability of a new word to be used in the future. Our model relies on a careful analysis of the google-ngram database of books published in the last centuries and its main consequence is the generalization of Zipf's and Heaps' law to two scaling regimes. We confirm that these generalizations yield the best simple description of the data among generic descriptive models and that the two free parameters depend only on the language but not on the database. From the point of view of our model the main change on historical time scales is the composition of the specific words included in the finite list of core-words, which we observe to decay exponentially in time with a rate of approximately 30 words per year for English.

I. INTRODUCTION

The paper introduces a stochastic vocabulary-growth model with two word categories and two scaling regimes, motivated by the need to describe vocabulary growth and extrapolate beyond simple scaling laws.

I. INTRODUCTION

  • Vocabulary size has shown no saturation as databases grow, motivating study of word birth, death, and how database size affects new-word usage.Estimating vocabulary size matters for linguistic studies and search-engine applications.Source: §I · p. 1
  • Heaps’ law describes vocabulary growth as N ∼ M^λ, while Zipf’s law gives F(r) ∼ 1/r; deviations in their tails complicate large-database extrapolation.The relationship between the laws has drawn interest, and tail deviations have been observed.Source: §I · p. 1
  • The proposed stochastic growth model distinguishes two word categories and produces two scaling regimes in Heaps’ and Zipf’s plots, fitting observed distribution tails.It differs from simpler Yule-, Simon-, Gibrat-, and preferential-attachment growth models.Source: §I · p. 1
  • Google-ngram analysis indicates that the model’s two scaling parameters remain unchanged over centuries, depend only on language, and accompany slow changes in category membership.The analysis supports the model’s description of Heaps’ and Zipf’s plots.Source: §I · p. 1

II. DATA ANALYSIS

The section analyzes Google Books n-gram data across five languages to characterize vocabulary patterns over time, using yearly and cumulative database partitions and filtering intended to reduce data biases.

II. DATA ANALYSIS

  • The analysis uses Google Books n-grams for English, German, French, Spanish, and Russian, with yearly word-frequency data from 1520–2000.The corpus spans several centuries and contains several million books.Source: §II · p. 1
  • Words are restricted to alphabetic 1-grams occurring at least 41 times to reduce effects of symbols, foreign words, numbers, scanning problems, and database filtering.The authors caution that this pragmatic definition should be considered when interpreting vocabulary findings.Source: §II · pp. 1–2
  • The English rank-frequency distribution shows double scaling behavior, with fit parameters tracked in yearly and cumulative databases over 1805–2000.The figure shows the English 2000 distribution and reports yearly and cumulative fit parameters for the reliable time range.Source: Figure 1 · p. 2
  • For each language, the authors analyze yearly databases y(t) and cumulative databases Y(t), formed by summing yearly data from t0.Detailed analysis focuses on English from 1805–2000; main findings for the other four languages are reported, with details left to the supplement.Source: §II · p. 2

Zipf’s analysis

For English, a double power-law best fits large word-frequency databases, extending Zipf’s law with a transition at high ranks. Its fitted parameters are similar across English corpora, while results vary across languages.

Zipf’s analysis

  • Zipf’s 1/r scaling must break at high ranks in sufficiently large databases, because cumulative word frequencies would otherwise exceed the text size.For English, the passage estimates this issue arises around N ≈106.Source: Zipf’s analysis · p. 2
  • The authors compared seven heavy-tailed distributions with at most two free parameters, using maximum-likelihood estimation, χ2 p-values, and relative likelihoods.These tests assessed both whether each model fit the data and which model was more likely to describe it.Source: Zipf’s analysis · p. 2
  • For English, the two-power-law distribution is the best fit for every database larger than 10^9 words (1−p < 10−15), although every tested distribution is rejected as an exact fit (p < 10−15).The double power-law is also the best fit for English Wikipedia, supporting the result across databases of different origins.Source: Zipf’s analysis · p. 2
  • The double power-law recovers Zipf’s law for high-frequency words, transitioning at critical rank r=b; non-overlapping English databases gave b ∈ [7·10^3, 12·10^3] and γ ∈ [1.8, 2.5], though English Wikipedia had b=7830 and γ=1.68.For the largest English database Y(2000), the analysis used b*=7873 and γ*=1.77.Source: Zipf’s analysis · p. 3
  • French and Spanish are also best described by the double power-law above particular database sizes, while it is second-best for German and Russian but may better fit their tails.No lemmatization was applied; greater inflection in German and Russian raises measured b, and larger databases are needed to characterize deviations from the 1/r regime.Source: Zipf’s analysis · p. 3

Heaps’ analysis

Vocabulary growth across languages and databases is well described by a double-scaling Zipfian-ensemble model, while available data do not distinguish among large hypothetical vocabulary caps.

Heaps’ analysis

  • Under the Zipfian ensemble’s Poisson-use assumption, Zipfian rank-frequency and vocabulary-growth power laws are linked, with γ = 1/λ.The threshold n rescales the growth-curve constant C; near the transition, observed distinct-word counts may depend more on the particular realization.Source: Heaps’ analysis · p. 3
  • Within 50%, the double-scaling model with Poisson word usage describes vocabulary growth across databases and languages over 9 orders of magnitude.Fine details of the observed curve are not compatible with the fluctuations expected under the Zipfian ensemble’s simplifying assumptions.Source: Figure 2 · p. 4, Heaps’ analysis · p. 4
  • Different hypothetical vocabulary caps produce negligible differences in predicted growth, so the vocabulary is practically infinite given currently accessible data.The observed vocabulary exceeds 10^6 different words without apparent saturation; it remains bounded by combinatorial limits from finite alphabets and word lengths.Source: Heaps’ analysis · p. 4, Figure 2 · p. 4
  • Across years, fixed rank-frequency parameters account for the observations, indicating that database size—not changing vocabulary richness—mainly drives the number of distinct words.Source: Heaps’ analysis · p. 4

III. MODEL

The section proposes a generative word-growth model with finite core and potentially infinite noncore vocabularies. It links declining new-word probability to noncore vocabulary growth to recover the double scaling of Heaps’ and Zipf’s laws.

III. MODEL

  • The model separates a finite core vocabulary from a potentially infinite noncore vocabulary, with existing words sampled in proportion to prior occurrences and new-word probability declining as noncore vocabulary grows.Core-word use does not affect the probability of a new word; the model makes that probability depend on the number of noncore words already used.Source: §III · p. 5
  • When N ≪ N_max_c, vocabulary growth is approximately N ∼ M^1; when N ≫ N_max_c, it is sublinear, with λ = (1 + α)^-1.The model identifies N_max_c with core-vocabulary size b and α = γ − 1, linking its parameters to the empirical scaling parameters.Source: §III · pp. 5–6
  • Direct simulations with traditional parameters b = b* and γ = γ* produce Zipf and Heaps curves resembling the original fits after normalization, threshold rescaling, and first-word weight adjustments.The model’s assumption that used-word probability is proportional to prior occurrences also recovers the double scaling in the Zipf plot.Source: §III · p. 6
  • Unlike the ZE model, which derives Heaps’ curves from Zipf distributions and vice versa, this generative model produces double scaling in both; databases are treated as small stationary-language subsamples approximated by ZE.The approximation applies when M_database ≪ M, so word-frequency changes are negligible during database creation.Source: §III · p. 6
  • Assuming an unbounded vocabulary motivates a new-word probability that decays at least as slowly as M^-δ, yielding power-law vocabulary growth and Eq. (4) as a minimal assumption.The passage specifies δ ≤ 1 and derives N(M) ∼ M^λ with λ = 1 − δ.Source: §III · p. 6

IV. HISTORICAL CHANGES

Although the model’s parameters and core-vocabulary size remain fixed, its core-word membership changes over historical time. Core-word retention decays exponentially, with replacement occurring on a timescale of centuries.

IV. HISTORICAL CHANGES

  • Core-word size stays fixed while membership changes: from 1891–1900 to 1991–2000, majesty and napoleon left, while technology and computer entered.The model uses the same fixed two parameters across databases and years, but does not assume the core-vocabulary’s composition is unchanged.Source: §IV · p. 6
  • κN_c ≈30 words per year, and κ increased by more than 50% from 1805 to 2000, indicating faster core-word replacement.The decay rate κ describes continuous replacement of core-words over time.Source: Figure 4 · p. 7, §IV · p. 7
  • Core-word retention follows an exponential decay in both forward and backward time, measured for yearly databases from 1805 to 2000.Retention tracks words with rank r < 7,873 that remain core-words after a time interval; the fitted curves use equal numbers of points in each direction.Source: §IV · pp. 6–7, Figure 4 · p. 7
  • f₀ ≈0.98 means about 150 core-words differ between yearly databases because of finite sampling, though f₀ rises as database size grows.The discontinuous change depends on book selection and the database’s finite size, which can lead to misestimation of the true core-words.Source: §IV · p. 7
  • Because core-vocabulary replacement takes centuries, the constant-core assumption holds over decades; longer timescales require modeling core-word replacement and finite memory or core/noncore distinctions.The model’s preferential-attachment component would also need refinement to incorporate finite memory or distinguish core- from noncore-words.Source: §IV · p. 7

V. DISCUSSION

The paper finds that two-scaling functions describe language rank frequencies and vocabulary growth, with language-specific parameters stable across centuries and databases. The authors interpret these patterns through a finite core vocabulary and report that English core-word composition decays exponentially.

V. DISCUSSION

  • Two-scaling functions best describe rank frequencies and vocabulary growth, with related free parameters that remain nearly constant across centuries and databases but vary by language.The authors derive this description from a generative stochastic model.Source: §V · p. 7
  • In English, core-vocabulary composition decays exponentially at 30 words per year, with the decay steadily accelerating in recent decades.The model distinguishes a finite core vocabulary from virtually unlimited noncore words with different properties.Source: §V · p. 7
  • The analysis offers the first rigorous statistical confirmation of double-scaling Zipf-law proposals; its Heap’s-law consequence is that new-word introduction slows but never vanishes as databases grow.This contrasts with claims of a maximum vocabulary size, which the authors suggest may reflect single-book databases near the transition point.Source: §V · pp. 7–8
  • A related Yule-type network process has fixed exponents and does not generate texts word by word, while thesaurus-network analysis also identified a similarly sized core-word set.The authors present both as points of comparison with their model and observations.Source: §V · p. 8
  • Knowing database size and language-specific parameters lets users estimate distinct words appearing more than n times and preallocate search-index memory [9–11].The model also computes fluctuations, but its Poisson word-usage assumption ignores correlations and typically underestimates them; the authors call it a simplest null model. The two-scaling transition also means Herdan’s coefficient [8] depends on which regime a text reaches.Source: §V · p. 8
  • For the whole vocabulary, vocabulary size is mainly driven by the available database size.The passage begins contrasting this observation with earlier conclusions based on the same Google Ngram database, but its claim is incomplete in the supplied text.Source: §V · p. 8

1 Max Planck Institute for the Physics of Complex Systems, 01187 Dresden, Germany … B. Results

The paper screens Google Books n-gram data and sets distinct time ranges for yearly and cumulative analyses. It fits rank-frequency models by maximum likelihood and evaluates fit quality and relative model support.

I. DATA

  • Words were decapitalized and restricted to language-alphabet letters and apostrophes; yearly and cumulative datasets retained only words appearing more than 40 times in the respective period.This filtering was intended to reduce foreign-word, number, scanning, and raw-database inclusion biases.Source: §I · p. 11
  • Yearly data cover 1805–2000 because database composition changes discontinuously around 1800, while cumulative data include all years before 1805.The authors attribute the time-range choice to a discontinuity in Kendall’s rank correlation between database compositions.Source: §I · p. 11

A. Theory

  • The analysis fits rank-frequency distributions, following Zipf’s formulation, and normalizes each model so its probabilities sum to one over ranks.The normalization constant depends on the model parameters; the paper reports computing it with the Euler–Maclaurin formula.Source: A. Theory · p. 11
  • Model parameters are estimated by numerically minimizing negative log-likelihood, using a Nelder–Mead simplex algorithm on the observed tokens and their ranks.The authors fit rank-frequency distributions directly rather than the word-frequency distribution used in Ref..Source: A. Theory · pp. 11–12
  • Fit quality is assessed with a χ2-based p-value, partitioning the domain so each cell has at least five expected observations.The alternative random-data comparison was deemed computationally infeasible, requiring approximately 10^15 draws for 0.01 p-value precision on a database exceeding 10^11 tokens.Source: A. Theory · p. 12
  • Models are compared using AIC, with the minimum-AIC model treated as most likely and relative likelihoods and model probabilities calculated from the AIC values.AIC accounts for the number of fitted parameters.Source: A. Theory · p. 12

Google-ngram

The Google-ngram fits favor different rank-frequency models depending on language, database size, and whether data are yearly or cumulative. With sufficiently large datasets, the double power-law (i=7) best captures distributions, particularly their tails.

Google-ngram

  • For English, i=7 best describes yearly data from ≳1950 and cumulative data from ≳1810; the database must exceed ≈10^9 tokens to distinguish it from alternatives.The inset shows i=7 outperforming i=3 and i=5 especially in the tail.Source: Google-ngram · p. 13
  • For languages other than English, yearly data favor i=3, while cumulative French and Spanish data increasingly favor i=7 as database size grows.The largest cumulative datasets are Y(2000); in the tails, i=7 fits better than i=3 and i=5.Source: Google-ngram · p. 13
  • For cumulative German and Russian data, i=7 ranks second-best, likely because datasets remain too small to distinguish a second power-law regime.Their transition rank b* is higher, leaving a smaller tail fraction and requiring larger databases to distinguish i=3 and i=5; tail fits show i=7 deviating less from data.Source: Google-ngram · p. 13
  • For Y(2000), German and Russian have larger b values and different tail exponents than English, French, and Spanish, possibly reflecting language differences beyond inflection.The other three languages have approximately the same values for the largest cumulative dataset.Source: Google-ngram · p. 13

Wikipedia · III. ZIPFIAN ENSEMBLE · A. Theory

The Wikipedia analysis supports the double power-law fit beyond Google Books. The Zipfian Ensemble models vocabulary growth from ranked word frequencies using independent Poisson occurrences.

Wikipedia

  • The English Wikipedia snapshot was chosen for its large text volume, lack of scanning, and publishing process distinct from books.After filtering, it contained approximately 3.7 × 10^6 word types and 1.3 × 10^9 tokens.Source: Wikipedia · p. 13
  • 1 − p < 10^-15 supports the double power-law as the best fit among proposed models for English Wikipedia's rank-frequency distribution.Its estimates are γ = 1.68 and b = 7830, close to the Google-ngram values γ∗ = 1.77 and b∗ = 7873.Source: Wikipedia · pp. 13–14, Table S2 · p. 13

A. Theory

  • The Zipfian Ensemble models vocabulary size as a function of text length using the rank-frequency distribution F(r).The framework considers word ranks from 1 to a hypothetical maximum vocabulary size.Source: A. Theory · p. 14
  • Each word type is assumed to occur independently in a Poisson process whose intensity equals its frequency, with time measured in tokens.The framework gives the probability that a word type occurs at least once in an interval of text length M.Source: A. Theory · p. 14
  • The expected vocabulary size N(M) is calculated by summing the word types that have appeared at least once by text length M.It represents the average number of distinct words across realizations.Source: A. Theory · p. 14
  • The ensemble variance describes expected fluctuations around N(M) across realizations.The passage defines this variance but does not provide its expression here.Source: A. Theory · p. 14
  • Unlike a bag-of-words model, the ensemble allows noninteger expected occurrence times and simultaneous occurrences of two words, limiting token-by-token interpretation.This independence enables analytic treatment, and the continuous-time approximation improves for large databases.Source: A. Theory · p. 14

B. ZE in the double power-law … C. Zipf’s plot

The paper derives how a double power-law rank-frequency distribution produces double-scaling vocabulary growth in the ZE, then tests the stochastic model against Heaps’ and Zipf’s plots. Simulations recover the two Heaps’ scaling regimes and agree with the data within 50% over seven orders of magnitude.

B. ZE in the double power-law

  • For n > 8, ZE growth curves for the double power law are almost indistinguishable from the asymptotic solution, and the approximation is practical for n > 10.The example uses γ* = 1.77 and b* = 7873; increasing the threshold reduces vocabulary-growth fluctuations.Source: B. ZE in the double power-law · p. 15
  • For thresholds n > 10, the ZE’s asymptotic growth is a good approximation, linking the double power-law rank-frequency distribution directly to vocabulary growth.As n increases, growth-curve fluctuations decrease; the paper attributes the asymptotic approximation to the central limit theorem.Source: B. ZE in the double power-law · pp. 14–15

IV. SELFCONSISTENT SOLUTION FOR EQ. (6)

  • λ = (1 + α)^-1 makes N(M) = c1M^λ a selfconsistent solution when pnew = c2N^-α, with c2 = λc.Source: §IV · p. 15

V. NUMERICAL SIMULATION OF THE STOCHASTIC MODEL

  • The numerical simulations test the model proposed in the main text, using vocabulary growth to assess its recovery of the observed scaling regimes.The reported numerical results include comparison with Google-ngram data after rescaling token count by the threshold.Source: §V · p. 15, B. Heaps’ plot · p. 16

A. Parameters and initialization

  • For English simulations, the setup uses c = 7873, α = 0.77, and pnew = 0.0922, with the first word type expected near M̃ ≈ 1/F(1).The model starts with an empty word-type list and averages 100 realizations, each capped at 10^9 token steps.Source: A. Parameters and initialization · p. 16

B. Heaps’ plot

  • Within 50% over 7 orders of magnitude, the simulated vocabulary growth recovers the two Heaps’ scaling regimes against Google-ngram data.The comparison uses the rescaled token count M̃ = M/n, with n = 41; agreement is poorer at large M̃ because the model slightly overestimates the transition point.Source: B. Heaps’ plot · p. 16

C. Zipf’s plot

  • Removing only the first word type yields English Zipf-plot agreement within 50% over 7 orders of magnitude, with the transition slightly shifted from the data.Yule-type preferential attachment overweights early word types; excluding low-rank types and renormalizing addresses this artifact.Source: C. Zipf’s plot · p. 16
Loading 1212.1362v3…