Hilberg's Hypothesis

Hilberg's Hypothesis (also known as Hilberg's Law) is a conjecture in quantitative linguistics or a statistical law in information theory. It states that measures of information in natural language texts or samples of particular stochastic processes grow as a sublinear power of the sample length, possibly in addition to the term that is linear. It is closely related to Zipf's law and the neural scaling law for large language models.

Overview

Hilberg's hypothesis was proposed by the German telecommunication engineer Wolfgang Hilberg in 1990, based on data originally published by Claude Shannon in 1951 on the predictability of English text. Hilberg observed that the amount of new information per character appears to decrease with context length in a manner consistent with a power law. His analysis implied that the Shannon entropy $H(n)$ of text blocks of length $n$ grows approximately as

$H(n)-hn\propto n^{\beta },$

where parameter $h$ is the entropy rate of the process and parameter $\beta \in (0,1)$ is called the Hilberg exponent. The term proportional to $n^{\beta }$ represents a memory effect, suggesting that human language carries a large amount of information in a repetitive way. Hilberg originally assumed that $h=0$ and $\beta =1/2$ basing his hypothesis on a visually meagre evidence. Hilberg's article was published in a local telecommunication journal and was initially noticed by physicists working in complex systems.

Hilberg's hypothesis implies that written or spoken language exhibits potentially infinite memory or long-range statistical dependencies that cannot be captured by finite-state hidden Markov models. The refutation of finite-state models based on Hilberg's hypothesis is close in spirit to Zipf's law for the unbounded arbitrary lexicon, which needs to be learned and memorized by heart. This mechanism differs to the refutation of finite-state models that is based on the unbounded stack of the push-down automaton for processing syntax of natural language, the latter argument developed by Noam Chomsky in Syntactic Structures in 1957.

By contrast to "Hilberg's hypothesis", the term "Hilberg's law" or "Hilberg's condition" often applies to any stationary process that satisfies a power-law scaling of $H(n)-hn$. Quantity $H(n)$ may represent various information measures, such as Shannon entropy, (resource-bounded) Kolmogorov complexity, or the length of a universal code. In the context of deep learning, the term neural scaling law is used for analogous power-law relations describing how performance of a large language model, measured by cross entropy, improves with data size, model parameters, or computation. Yet another expression involves the mutual information between two adjacent text blocks of length $n$,

$I(n)=2H(n)-H(2n).$

Using this concept, Hilberg's law is equivalent to

$I(n)\propto n^{\beta }.$

This version does not depend on the precise value of the entropy rate and is used in theoretical studies.

The value of the Hilberg exponent $\beta$ depends crucially on the applied information measure, or the compression algorithm in case of the universal code. Simultaneously, it exhibits a certain degree of universality across particular languages and writing systems, being $\beta \approx 0.8$ for the prediction by partial matching code run on English, French, Russian, Korean, Chinese, and Japanese news corpora.

Examples of processes

The intuitive meaning of Hilberg's hypothesis can be motivated by some toy models of stationary processes, which link Hilberg's law with Zipf's law for an unbounded arbitrary lexicon that needs to be learned by heart. Equivalently, the following examples may be considered as idealized information sources that convey an unbounded amount of algorithmically random knowledge in a repetitive fashion. This knowledge can be either immutable, giving rise to non-ergodic or perigraphic processes, or slowly evolving, yielding mixing processes. A priori, this knowledge may encode also facts different to the knowledge of a particular lexicon.

A simple model of a stochastic process that satisfies Hilberg's law $I(n)\propto n^{\beta }$ is given by the Santa Fe process. The Santa Fe process is a stationary non-ergodic process $(X_{i})_{i\in \mathbb {Z} }$ that consists of pairs $X_{i}=(K_{i},Z_{K_{i}})$, where $(K_{i})_{i\in \mathbb {Z} }$ is a sequence of independent random natural numbers distributed according to Zipf's law $P(K_{i}=k)\propto k^{-1/\beta }$ and $(Z_{k})_{k\in \mathbb {N} }$ is the uniform Bernoulli process, i.e., a sequence of fair coin flips. Process $(K_{i})_{i\in \mathbb {Z} }$ is called narration and process $(Z_{k})_{k\in \mathbb {N} }$ is called knowledge. Individual variables $Z_{k}$ are called (independent elementary) facts.

In general, Hilberg's law may arise for non-ergodic or perigraphic processes depending whether one considers Shannon entropy or Kolmogorov complexity as the chosen information measure. A perigraphic process is roughly an algorithmically random ergodic component of a non-ergodic process with a non-atomic invariant sigma-algebra. An example of a perigraphic process is a modified Santa Fe process $(X_{i})_{i\in \mathbb {Z} }$ that consists of pairs $X_{i}=(K_{i},z_{K_{i}})$ where $(z_{k})_{k\in \mathbb {N} }$ is a fixed algorithmically random binary sequence such as the halting probability.

Hilberg's law may also arise for some mixing processes. An example of such a process is a modified Santa Fe process $(X_{i})_{i\in \mathbb {Z} }$ that consists of pairs $X_{i}=(K_{i},Z_{i,K_{i}})$ where $(Z_{i,k})_{i\in \mathbb {Z} ,k\in \mathbb {N} }$ is a collection of independent binary Markov processes, where the flipping probabilities $P(Z_{i,k}\neq Z_{i-1,k})$ are smaller than the mentioning probabilities $P(K_{i}=k)$.

Related conditions

Hilberg's hypothesis connects quantitative linguistics, information theory, and modern machine-learning research on scaling behavior. By means of mathematical theorems, Hilberg's law can be related to some similar conditions for stationary processes over a finite, a countably infinite, or an uncountable set of possible outcomes.

Hilberg's law can be deductively linked to Zipf's law and Heaps' law for word-like subwords or chunks by means of grammar-based codes and prediction by partial matching, non-ergodic processes, and the data-processing inequality for mutual information. There is a general result concerning stationary processes, called the theorem about facts and words, which states that the mutual information between two adjacent text blocks is sandwiched by the number of independent elementary facts and the number of distinct word-like strings expressed in the concatenated text block.

Deductive links between Hilberg's law and the neural scaling law are a subject of ongoing research.

Hilberg's hypothesis has been discussed as evidence that language production involves infinite memory, contrasting with finite-state Markov models and hidden Markov models. In general, Hilberg's law is incompatible with finite-state hidden Markov models. The mutual information between past and future $E=\lim _{n\to \infty }I(n)$ is called excess entropy or predictive information. Condition $E<\infty$ holds for finite-state hidden Markov models and non-degenerate autoregressive moving-average Gaussian processes. By contrast, condition $E=\infty$ holds for non-ergodic processes with a non-atomic invariant sigma-algebra. There also exist countably infinite-state hidden Markov models that enjoy condition $E=\infty$ and Hilberg's law.

A less direct is the link of Hilberg's law with the power-law logarithmic scaling of the maximal repetition length, empirically observed for natural language, as this involves a power-law growth of Renyi entropies rather than the Shannon entropy.

In the case of stationary processes over a countable alphabet, it is unknown whether Hilberg's law (under a mild condition) implies a slow decay of the two-point mutual information $I(X_{0};X_{n})$, which seems to hold for natural language. For the non-ergodic Santa Fe processes, one also observes $I(X_{0};X_{n})={\text{const}}$ for $n\neq 0$.

In the case of real-valued non-degenerate Gaussian processes, condition $E=\infty$ is equivalent to $\sum _{k=1}^{\infty }k\alpha _{k}^{2}=\infty$, where $\alpha _{k}$ is the partial autocorrelation function.. Additionally, if the Gaussian process has a positive and continuous spectral density then condition $E=\infty$ is equivalent to $\sum _{k=1}^{\infty }k\rho _{k}^{2}=\infty$, where $\rho _{k}$ is the autocorrelation function. By contrast, the long-range dependence condition is $\sum _{k=1}^{\infty }|\rho _{k}|=\infty$, which is equivalent to the previous condition if the autocorrelation function $\rho _{k}$ decays exactly according to a power law. Thus Hilberg's law implies long-range dependence if the process is Gaussian, the spectral density is positive and continuous, and the autocorrelation function follows a power law.

See also

• Shannon entropy
• Kolmogorov complexity
• Power laws
• Neural scaling law
• Zipf's law
• Heaps' law
• Excess entropy
• Long-range dependence
• Ergodicity