Elamur Research⌕
☰
home / papers / 1996 / An Empirical Study of Smoothing Techniques for Language Modeling

An Empirical Study of Smoothing Techniques for Language Modeling

Summary

Smoothing adjusts maximum-likelihood n-gram estimates so that unseen word sequences do not get zero probability. Before this paper, the literature offered no fair head-to-head comparison of smoothing methods. Earlier studies usually tested about two methods on one corpus with one training size. Chen and Goodman compare the main methods systematically: additive-style baselines, Jelinek-Mercer interpolation (held-out and deleted variants), Katz, and Church-Gale. Their test data comes from the Brown corpus (via the Penn treebank) and the TIPSTER newswire collections. They vary training size widely, build both bigram and trigram models, and score each method by test-set cross-entropy. Tunable parameters are optimized automatically on held-out data. The authors also propose two new methods, average-count and one-count. Which method ranks best depends strongly on training-set size and n-gram order. Church-Gale is strongest for bigrams trained on large data, and Katz does well on smaller data. The two new methods beat existing techniques on trigrams. The study shows that a single-setting comparison can mislead researchers choosing a smoother.

Key points

  • Corpora: about 1M words of Brown text from the Penn treebank, plus TIPSTER AP (123M words), WSJ (84M) and SJM (43M) data.
  • Vocabularies:
    • Brown: all 53,850 words that occur in it.
    • TIPSTER: 65,173 frequent words.
  • Training sizes and runs: small sets of up to 50,000 sentences were averaged over ten runs. Large sets of up to 10,000,000 sentences were run once each.
  • Methods compared:
    • interp-baseline, interp-held-out, interp-del-int
    • katz, church-gale
    • new-avg-count, new-one-count
  • Main findings:
    • Katz and Jelinek-Mercer are consistently solid performers.
    • Katz beats Jelinek-Mercer on bigrams overall and on trigrams trained on large data.
    • Church-Gale had never before been compared with the common methods, and it wins on large-data bigrams.
    • Badly chosen parameters can noticeably hurt any method's results.

Interesting ideas

  • I1. Bucket by sparseness, not raw frequency. Interpolation weights are grouped by the average count per non-zero word in a context, rather than by the context's total count. This captures how concentrated a distribution is. A similar trick could help whenever parameters are tied across sparse contexts, for example in tagger or parser backoff.
  • I2. Use singletons to set pseudo-counts. In one-count, the number of pseudo-counts added to a context grows with the number of words seen exactly once there. Those extra counts are spread according to the lower-order model. This Good-Turing-inspired rule is very easy to implement and makes a good default when a quick, strong smoother is needed.
  • I3. Evaluate along a full grid. Methods are compared across many training sizes, both n-gram orders, and several corpora, with repeated runs on small data to check significance. Any comparison of methods for low-resource settings, such as Ukrainian data, should adopt this design.
  • I4. Tune every method before comparing. Each method's parameters are searched automatically on held-out data, and the results show how much performance moves with those parameters. This prevents a well-tuned method from beating a poorly tuned rival unfairly.
  • I5. Report results relative to a baseline. Cross-entropy differences are plotted against a simple interpolation baseline. Small but consistent gaps become visible across scales, a presentation that works for any learning-curve study.

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: Machine translation · Natural language processing

Cited by

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

Cite

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

@inproceedings{chen1996empirical,
  title = {{An Empirical Study of Smoothing Techniques for Language Modeling}},
  author = {Chen, Stanley F. and Goodman, Joshua},
  booktitle = {34th Annual Meeting of the Association for Computational Linguistics},
  year = {1996},
  doi = {10.3115/981863.981904},
  url = {https://doi.org/10.3115/981863.981904}
}

References

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

  1. Bahl, Lalit R., Frederick Jelinek, and Robert L. Mercer. 1983. A maximum likelihood approach to continuous speech recognition. IEEE Transactions on Pattern Analysis and Machine Intelligence, PAMI-5(2):179-190, March. find
  2. Brown, Peter F., John Cocke, Stephen A. DellaPietra, Vincent J. DellaPietra, Frederick Jelinek, John D. Lafferty, Robert L. Mercer, and Paul S. Roossin. 1990. A statistical approach to machine translation. Computational Linguistics, 16(2):79-85, June. find
  3. Brown, Peter F., Stephen A. DellaPietra, Vincent J. DellaPietra, Jennifer C. Lai, and Robert L. Mercer. 1992. An estimate of an upper bound for the entropy of English. Computational Linguistics, 18(1):31-40, March. find our card
  4. Chen, Stanley F. 1996. Building Probabilistic Models for Natural Language. Ph.D. thesis, Harvard University. In preparation. find
  5. Church, Kenneth. 1988. A stochastic parts program and noun phrase parser for unrestricted text. In Proceedings of the Second Conference on Applied Natural Language Processing, pages 136-143. find
  6. Church, Kenneth W. and William A. Gale. 1991. A comparison of the enhanced Good-Turing and deleted estimation methods for estimating probabilities of English bigrams. Computer Speech and Language, 5:19-54. find
  7. Collins, Michael and James Brooks. 1995. Prepositional phrase attachment through a backed-off model. In David Yarowsky and Kenneth Church, editors, Proceedings of the Third Workshop on Very Large Corpora, pages 27-38, Cambridge, MA, June. find our card
  8. Gale, William A. and Kenneth W. Church. 1990. Estimation procedures for language context: poor estimates are worse than none. In COMP-STAT, Proceedings in Computational Statistics, 9th Symposium, pages 69-74, Dubrovnik, Yugoslavia, September. find
  9. Gale, William A. and Kenneth W. Church. 1994. What's wrong with adding one? In N. Oostdijk and P. de Haan, editors, Corpus-Based Research into Language. Rodolpi, Amsterdam. find
  10. Gale, William A. and Geoffrey Sampson. 1995. Good-Turing frequency estimation without tears. Journal of Quantitative Linguistics, 2(3). To appear. find
  11. Good, I.J. 1953. The population frequencies of species and the estimation of population parameters. Biometrika, 40(3 and 4):237-264. find
  12. Jeffreys, H. 1948. Theory of Probability. Clarendon Press, Oxford, second edition. find
  13. Jelinek, Frederick and Robert L. Mercer. 1980. Interpolated estimation of Markov source parameters from sparse data. In Proceedings of the Workshop on Pattern Recognition in Practice, Amsterdam, The Netherlands: North-Holland, May. find
  14. Johnson, W.E. 1932. Probability: deductive and inductive problems. Mind, 41:421-423. find
  15. Katz, Slava M. 1987. Estimation of probabilities from sparse data for the language model component of a speech recognizer. IEEE Transactions on Acoustics, Speech and Signal Processing, ASSP-35(3):400-401, March. find
  16. Kernighan, M.D., K.W. Church, and W.A. Gale. 1990. A spelling correction program based on a noisy channel model. In Proceedings of the Thirteenth International Conference on Computational Linguistics, pages 205-210. find
  17. Lidstone, G.J. 1920. Note on the general case of the Bayes-Laplace formula for inductive or a posteriori probabilities. Transactions of the Faculty of Actuaries, 8:182-192. find
  18. MacKay, David J. C. and Linda C. Peto. 1995. A hierarchical Dirichlet language model. Natural Language Engineering, 1(3):1-19. find
  19. Magerman, David M. 1994. Natural Language Parsing as Statistical Pattern Recognition. Ph.D. thesis, Stanford University, February. find
  20. Nadas, Arthur. 1984. Estimation of probabilities in the language model of the IBM speech recognition system. IEEE Transactions on Acoustics, Speech and Signal Processing, ASSP-32(4):859-861, August. find
  21. Press, W.H., B.P. Flannery, S.A. Teukolsky, and W.T. Vetterling. 1988. Numerical Recipes in C. Cambridge University Press, Cambridge. find

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/chen-1996-empirical-study-smoothing-techniques-language/