Upper Bound of Entropy Rate Revisited --A New Extrapolation of Compressed Large-Scale Corpora--

Ryosuke Takahira, Kumiko Tanaka-Ishii, Lukasz DebowskiCL4LC @ COLING 2016 · OpenReview

Introduction

How much information is packed into a single character of human language? This fundamental question in information theory, first explored by Claude Shannon in the 1940s, defines the "entropy rate"—the ultimate limit of data compression and a measure of linguistic complexity. In the paper "Upper Bound of Entropy Rate Revisited," Takahira et al. challenge long-standing estimates, suggesting that human language is significantly more predictable than previously believed. By applying a novel mathematical model to multi-gigabyte corpora, the researchers found that entropy rates might be 20% lower than the standard figures.

The Challenge of Infinite Extrapolation

The true entropy rate of a language is defined as the limit of information growth as the text length approaches infinity. Since researchers only have access to finite datasets, they must use "ansatz" functions—mathematical models used to extrapolate from finite observations to an infinite limit.

Historically, there has been a debate over whether the entropy rate is a positive constant (Shannon’s view) or if it decays toward zero (the Hilberg hypothesis). This study aims for a more precise middle ground by utilizing larger datasets and a more robust extrapolation model.

Methodology: Compression and the Stretched Exponential

The researchers employed a two-step methodology to refine entropy estimates:

  1. Compression as Estimation: The study utilized various compression algorithms, with 7z (PPMd) (Prediction by Partial Matching) proving to be the most effective. The encoding rate of a state-of-the-art compressor serves as a reliable upper bound for the true entropy rate. As shown in the comparison of algorithms, PPMd consistently achieves the lowest bits-per-character (bpc) across varying text lengths.
Comparison of encoding rates across different compression algorithms. 7z (PPMd) consistently achieves the lowest rates, serving as the best upper bound for entropy.
  1. The Stretched Exponential Ansatz: Previous studies often relied on power-law or logarithmic functions for extrapolation. Takahira et al. introduced a stretched exponential function: $$f_3(n) = \exp(An^{\beta-1} + h')$$ This model accounts for the slow convergence of natural language, where new vocabulary and shifts in topic continue to emerge even in very large datasets. To mitigate "noise" from topic shifts in news archives, the team performed document-level shuffling and averaged results over multiple permutations.

Results: A More Predictable Language

The study analyzed an extensive range of corpora, including up to 7.8 GB of English text (NYT, WSJ) and significant datasets for Chinese, Japanese, French, Korean, and Russian.

The core finding is that the choice of extrapolation function is more critical than the volume of data. The stretched exponential function ($f_3$) consistently demonstrated a smaller error of fit compared to the standard modified Hilberg function ($f_1$). For the Wall Street Journal corpus, the new model estimated an entropy rate ($h$) of approximately 1.04 bpc, compared to 1.30 bpc from the older model.

Extrapolation of the encoding rate for the Wall Street Journal corpus. The stretched exponential ansatz (solid red line) provides a superior fit and a lower entropy estimate compared to the standard power-law model (dotted line).

Key findings include:

  • English Entropy Rate: Revised to approximately 1.13 bpc, a 20% reduction from the widely accepted 1.3–1.4 bpc range.
  • Chinese Entropy Rate: Estimated at 3.85 bpc, reflecting the higher information density per character in logographic scripts.
  • Long-Range Dependencies: Even with 7.8 GB of data, the encoding rate continues to "bend" toward the limit, suggesting that language possesses extremely long-range structural dependencies.

Conclusion

The results suggest that the "floor" of language complexity is lower than previously thought. Human communication is more repetitive and predictable over long spans than earlier models could capture. While the data does not support the radical Hilberg hypothesis of a zero entropy rate, it confirms that our previous upper bounds were too conservative. Future research using even larger corpora and modern deep-learning-based language models may push these estimates even lower, further refining our understanding of the information density of human thought.

Summary updated

Abstract

The article presents results of entropy rate estimation for human languages across six languages by using large, state-of-the-art corpora of up to 7.8 gigabytes. To obtain the estimates for data length tending to infinity, we use an extrapolation function given by an ansatz. Whereas some ansatzes of this kind were proposed in previous research papers, here we introduce a stretched exponential extrapolation function that has a smaller error of fit. In this way, we uncover a possibility that the entropy rates of human languages are positive but 20% smaller than previously reported.
BibTeX
@inproceedings{takahira2016upper,
  author = {Ryosuke Takahira and Kumiko Tanaka-Ishii and Lukasz Debowski},
  title = {{Upper Bound of Entropy Rate Revisited --A New Extrapolation of Compressed Large-Scale Corpora--}},
  booktitle = {CL4LC @ COLING},
  year = {2016},
  url = {https://openreview.net/forum?id=Yd7GNu0LEG},
}
Figure