Elamur Research
☰
home / papers / 1992 / An Estimate of an Upper Bound for the Entropy of English

An Estimate of an Upper Bound for the Entropy of English

Written for the Research library (claude-opus-5-5) from the paper text, in our own words: the license "CC BY-NC-SA 3.0 (ACL Anthology, before 2016)" does not allow redistributing the text itself. Original — aclanthology.org/J92-1002.pdf

Summary

The paper looks for a provable upper limit on the per-character entropy of printed English. Earlier estimates, going back to Shannon (1951), had human subjects guess letters in passages of at most a few hundred characters. The IBM authors use a different principle: a model's cross-entropy on real text can never fall below the true entropy of the source. They built a word trigram language model trained on 583 million words and smoothed with Jelinek–Mercer interpolation. Extra sub-models for unknown-word spelling, capitalization and spacing let it assign probabilities to any string of the 95 printable ASCII characters. They evaluated it on the entire Brown Corpus (about 5.96 million characters), which was kept completely separate from model construction. The result is 1.75 bits per character, far below general-purpose compressors. The authors propose character-level cross-entropy on the Brown Corpus as a benchmark for language modeling that does not depend on any particular vocabulary. They invite the community to beat their figure.

Key points

  • Main result: English entropy is shown to be no more than 1.75 bits per character on the Brown Corpus (Form C: 500 samples printed in 1961, about 1.01 million tokens).
  • Breakdown by component:
    • token trigram model: 1.61 bits
    • spelling of unknown tokens: 0.08 bits
    • case: 0.04 bits
    • spacing: 0.02 bits
  • Model structure:
    • The vocabulary has 293,181 spellings, plus an unknown_token and a sentence_boundary_token.
    • Unknown words are spelled using a Poisson-distributed length, with characters drawn uniformly from the 95 printable ASCII characters.
  • Comparison with compressors on the same corpus:
    • Huffman coding: 4.46 bits per character
    • UNIX compress (Lempel-Ziv): 4.43 bits per character
    • adaptive Lempel-Ziv (Miller & Wegman): 4.20 bits per character
  • Suggested improvements: more training text, adaptive models, and use of syntactic, semantic and discourse knowledge, which the trigram approach ignores.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

Fields: Natural language processing

Cited by

70 papers of our library cite it (of the 140673 whose bibliographies we read); 2 of them have a page here, 68 not yet.

Cite

The paper itself, not this page. BibTeX from the library's record of the work.

@article{brown1992estimate,
  title = {{An Estimate of an Upper Bound for the Entropy of English}},
  author = {Brown, Peter F. and Pietra, Stephen A. Della and Pietra, Vincent J. Della and Lai, Jennifer C. and Mercer, Robert L.},
  journal = {Computational Linguistics},
  year = {1992},
  doi = {10.5555/146680.146685},
  url = {https://doi.org/10.5555/146680.146685}
}

References

9 references, 0 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. Algoet, P. and Cover, T. (1988). "A sandwich proof of the Shannon-McMillan-Breiman theorem." Annals of Probability 16(2):899-909. find
  2. Bahl, L., Baker, J., Jelinek, E, and Mercer, R. (1977). "Perplexity--a measure of the difficulty of speech recognition tasks." In Program, 94th Meeting of the Acoustical Society of America 62:$63, Suppl. no. 1. find
  3. Bell, T. C., Cleary, J. G., and Witten, I. H. (1990). Text Compression. Englewood Cliffs, N.J.: Prentice Hall. find
  4. Cover, T., and King, R. (1978). "A convergent gambling estimate of the entropy of English." IEEE Transactions on Information Theory 24(4):413-421. find
  5. Cover, T. M., and Thomas, J. A. (1991). Elements of Information Theory. New York: John Wiley. find
  6. Jelinek, F., and Mercer, R. L. (1980). "Interpolated estimation of Markov source parameters from sparse data." In Proceedings, Workshop on Pattern Recognition in Practice, Amsterdam, The Netherlands. find
  7. Kucera, H., and Francis, W. (1967). Computational Analysis of Present-Day American English. Providence, R.I.: Brown University Press. find
  8. Miller, V. S., and Wegman, M. N. (1984). "Variations on a theme by Ziv and Lempel." Technical Report RC 10630, IBM Research Division. find
  9. Shannon, C. (1951). "Prediction and entropy of printed English." Bell Systems Technical Journal 30:50-64. find