An Empirical Study of Smoothing Techniques for Language Modeling

Stanley F. ChenJoshua Goodman

article1996ACL3,571 citations

Evaluates prominent n-gram smoothing methods across diverse corpora and training set sizes while introducing novel interpolation techniques that consistently outperform classical baselines.

Listen

This paper presents a large-scale empirical comparison of smoothing methods used to build n-gram language models, which assign probabilities to word sequences and are central to applications such as speech recognition. Without effective smoothing, maximum-likelihood estimates from limited training data produce many zero probabilities that harm performance; earlier comparisons had examined only a few methods on single corpora and data sizes, leaving practitioners without clear guidance on which approach to choose.

The work set out to measure how the relative accuracy of established smoothing techniques varies with training-set size, corpus, and n-gram order (bigram versus trigram), while also testing two new methods. Performance was quantified by cross-entropy on held-out test text.

The authors implemented eight smoothing families—including additive smoothing, Katz smoothing, Church-Gale smoothing, and Jelinek-Mercer interpolation—on corpora ranging from one million to more than 100 million words. They trained models on data sets from 100 sentences to several million, optimized free parameters on separate development sets, and repeated runs on smaller data to assess statistical significance.

Katz and standard Jelinek-Mercer interpolation performed consistently well across conditions, with Katz showing a modest edge on bigrams and on large-data trigrams. Church-Gale smoothing was best on the largest bigram sets but lagged elsewhere. Additive smoothing performed poorly in all settings. The two new techniques—one that re-buckets interpolation weights by average count per observed word and one that adds a count proportional to the number of singletons—matched or exceeded the best prior methods on bigrams and were clearly superior on trigrams. Suboptimal parameter choices or use of deleted rather than held-out interpolation could increase cross-entropy by several tenths of a bit, corresponding to roughly 10–20 percent higher perplexity.

These differences matter because language-model quality directly affects error rates and search effort in downstream systems. The results indicate that no single existing method is optimal for every operating regime, so developers should match the smoother to expected data size and n-gram order rather than defaulting to the most common choice.

The clearest next step is to measure whether the observed cross-entropy gains translate into word-error-rate reductions in a full speech recognizer or other end application. Additional work could also test whether the new methods remain advantageous when extended to higher-order n-grams or to tasks such as tagging and parsing.

The study covers multiple corpora and data scales, yet all test sets are drawn from newswire or balanced written text; results may shift for other domains or for vocabularies an order of magnitude larger. Parameter optimization was limited on the biggest training sets for computational reasons, so the reported figures for those conditions carry somewhat lower confidence.

Aiken Computation Laboratory Harvard University n-gram language models spline interpolation interpolation algorithms smoothing techniques language modeling Good-Turing frequency estimation

arXiv: cmp-lg/9606011

Paper: Word Association Norms, Mutual Information, and Lexicography, Kenneth Ward Church et al. (1989). This paper establishes foundational corpus-based statistical estimation methods and mutual information metrics that underpin early n-gram statistical modeling and count estimation.

Paper: A study of smoothing methods for language models applied to Ad Hoc information retrieval, ChengXiang Zhai et al. (2001). This work extends Chen and Goodman's systematic analysis of n-gram smoothing techniques to document-level language models used in information retrieval.
Paper: TnT – A Statistical Part-of-Speech Tagger, Thorsten Brants (2000). This paper directly applies linear interpolation and n-gram smoothing principles to build an efficient, highly competitive statistical part-of-speech tagger.
Paper: A Neural Probabilistic Language Model, Yoshua Bengio et al. (2003). This seminal work uses classical smoothed n-gram language models as the primary baseline to demonstrate how distributed neural representations overcome traditional n-gram sparsity.

Cover for An Empirical Study of Smoothing Techniques for Language Modeling

Abstract

We present an extensive empirical comparison of several smoothing techniques in the domain of language modeling, including those described by Jelinek and Mercer (1980), Katz (1987), and Church and Gale (1991). We investigate for the first time how factors such as training data size, corpus (e.g., Brown versus Wall Street Journal), and n-gram order (bigram versus trigram) affect the relative performance of these methods, which we measure through the cross-entropy of test data. In addition, we introduce two novel smoothing techniques, one a variation of Jelinek-Mercer smoothing and one a very simple linear interpolation technique, both of which outperform existing methods.

Topics

n-gram language models spline interpolation interpolation algorithms noise removal optimization problems

Keywords

smoothing techniques language modeling Good-Turing frequency estimation Jelinek-Mercer smoothing Katz smoothing Church-Gale smoothing additive smoothing trigram models Brown corpus speech recognition

1 Introduction
1.1 Smoothing nn-gram Models
2 Previous Work
3 Novel Smoothing Techniques
3.1 Method average-count
3.2 Method one-count
4 Experimental Methodology
4.1 Data
4.2 Smoothing Implementations

Knowls

Knowl 1 — One-Count Smoothing Method
model/method
The one-count smoothing technique is a linear interpolation language modeling method that adjusts maximum likelihood counts using the number of singletons (words appearing exactly once in a given context history). For an $n$ -gram sequence $w_1 \dots w_l$ , the conditional probability of word $w_i$ given the preceding $n-1$ words $w_{i-n+1}^{i-1}$ is defined recursively as:

$P_{\text{one}}(w_i \mid w_{i-n+1}^{i-1}) = \frac{c(w_{i-n+1}^i) + \alpha_n P_{\text{one}}(w_i \mid w_{i-n+2}^{i-1})}{c(w_{i-n+1}^{i-1}) + \alpha_n}$

where $c(\alpha)$ denotes the count of string $\alpha$ in the training text, and the base distribution for $n=0$ is the uniform distribution $P_{\text{unif}}(w_i) = \frac{1}{|V|}$ over vocabulary $V$ .

The parameter $\alpha_n$ represents pseudo-counts added to the distribution, allocated according to the smoothed lower-order distribution $P_{\text{one}}(w_i \mid w_{i-n+2}^{i-1})$ . Derived from Good-Turing intuitions, $\alpha_n$ is defined to be linear in the number of words observed exactly once in context $w_{i-n+1}^{i-1}$ :

$\alpha_n = \gamma_n \left[ n_1(w_{i-n+1}^{i-1}) + \beta_n \right]$

where $n_1(w_{i-n+1}^{i-1}) = |\{w_i \in V : c(w_{i-n+1}^i) = 1\}|$ , and $\beta_n$ and $\gamma_n$ are order-specific constants optimized on held-out development data.
Knowl 2 — Average-Count Bucketing for Jelinek-Mercer Smoothing
model/method
In Jelinek-Mercer smoothing, higher-order maximum likelihood estimates are linearly interpolated with smoothed lower-order distributions:

$P_{\text{interp}}(w_i \mid w_{i-n+1}^{i-1}) = \lambda_{w_{i-n+1}^{i-1}} P_{\text{ML}}(w_i \mid w_{i-n+1}^{i-1}) + (1 - \lambda_{w_{i-n+1}^{i-1}}) P_{\text{interp}}(w_i \mid w_{i-n+2}^{i-1})$

where $P_{\text{ML}}(w_i \mid w_{i-n+1}^{i-1}) = \frac{c(w_{i-n+1}^i)}{c(w_{i-n+1}^{i-1})}$ .

To prevent parameter proliferation, contexts $w_{i-n+1}^{i-1}$ are grouped into discrete buckets, constraining all contexts in a bucket to share the same interpolation weight $\lambda$ . Rather than bucketing contexts purely by their total history frequency $c(w_{i-n+1}^{i-1})$ , the average-count method partitions contexts according to the average count per non-zero vocabulary word:

$\text{avg\_count}(w_{i-n+1}^{i-1}) = \frac{c(w_{i-n+1}^{i-1})}{|\{w_i \in V : c(w_{i-n+1}^i) > 0\}|}$

This quantity captures the distribution's sparseness more accurately than raw history count by accounting for count dispersion across vocabulary items. Buckets are constructed so that each contains at least a minimum threshold $c_{\text{min}}$ of total words in the parameter estimation set.
Knowl 3 — Trigram Smoothing Performance Across Corpora and Training Set Sizes
empirical result
Empirical evaluation of smoothing methods on trigram language models across training set sizes ranging from 100 sentences to 10,000,000 sentences on the Brown and TIPSTER (Associated Press, Wall Street Journal, San Jose Mercury News) corpora demonstrates:
1. The novel new-avg-count (Jelinek-Mercer with average-count bucketing) and new-one-count smoothing techniques consistently achieve the lowest test cross-entropy across all training set sizes, improving upon standard Jelinek-Mercer and Katz baselines by up to 0.14 to 0.16 bits/token (corresponding to over a 10% reduction in perplexity).
2. Standard held-out Jelinek-Mercer smoothing (interp-held-out) and Katz smoothing (katz) perform consistently well across training sizes, with interp-held-out slightly outperforming Katz on smaller sets and Katz performing better on large sets.
3. Church-Gale smoothing (church-gale) performs poorly across trigram training sizes, trailing baseline linear interpolation by multiple bits on small datasets.
4. Additive smoothing methods (plus-one and plus-delta) perform extremely poorly, yielding test cross-entropies 3 to 7 bits/token worse than baseline interpolation.
5. Relaxed deleted interpolation (interp-del-int) performs substantially worse than held-out interpolation (interp-held-out) when single words are deleted one at a time during parameter estimation.
Knowl 4 — Bigram Smoothing Performance Across Corpora and Training Set Sizes
empirical result
Empirical evaluation of bigram language models across training set sizes ranging from 100 sentences to 10,000,000 sentences on Brown, TIPSTER, and Wall Street Journal corpora reveals:
1. Church-Gale smoothing (church-gale) achieves superior cross-entropy performance on large training corpora (above 100,000 sentences), outperforming Katz smoothing, Jelinek-Mercer, and the novel methods. However, it performs poorly on small training sets.
2. For small to moderate training set sizes (fewer than 50,000 sentences), Katz smoothing (katz), new-avg-count, and new-one-count yield the best performance, outperforming held-out Jelinek-Mercer (interp-held-out) and Church-Gale.
3. Additive smoothing methods (plus-one and plus-delta) consistently perform poorly across all training sizes.
4. The relative ranking of algorithms remains consistent across different text domains (Brown vs. WSJ/TIPSTER), but varies substantially depending on training set size and $n$ -gram order (bigram vs. trigram).
Knowl 5 — Parameter Sensitivity and Training Size Dependency in Smoothing Methods
empirical result
Smoothing techniques containing tunable parameters exhibit high performance sensitivity to parameter values, and optimal parameter settings shift systematically with training set size:
1. In Katz smoothing, the additive parameter $\delta$ used for unigram smoothing significantly affects test cross-entropy. On small training sets (100 sentences), optimal performance occurs near $\delta \approx 0.05$ , whereas on larger sets (50,000 sentences), the optimal value shifts to $\delta \approx 100$ . Sub-optimal $\delta$ selection can degrade cross-entropy by over 1.4 bits/token.
2. In bucketed Jelinek-Mercer smoothing (new-avg-count), the minimum count per bucket threshold $c_{\text{min}}$ shifts from small values ( $c_{\text{min}} \approx 1\text{--}10$ ) on 100-sentence datasets to large values ( $c_{\text{min}} \approx 1,000\text{--}10,000$ ) on 10,000,000-sentence datasets. Sub-optimal $c_{\text{min}}$ choices lead to cross-entropy penalties of 0.04 to 0.08 bits/token.

Knowl 6 — Implementation Complexity of Smoothing Techniques

data/table

The implementation difficulty of different language model smoothing algorithms was quantified by the number of lines of C++ code required, excluding shared core infrastructure.

Method	Lines of C++ Code
interp-baseline	400
plus-one	40
plus-delta	40
katz	300
church-gale	1000
interp-held-out	400
interp-del-int	400
new-avg-count	400
new-one-count	50

The comparison shows that while competitive techniques such as church-gale (1000 lines), katz (300 lines), and interp-held-out / new-avg-count (400 lines) require substantial code, the novel new-one-count method achieves state-of-the-art trigram performance with only 50 lines of C++ code.

Knowl 7 — Modified Multi-Order Katz Smoothing Implementation
model/method
Katz smoothing calculates conditional $n$ -gram probabilities by recursively backing off from higher-order maximum likelihood estimates to lower-order smoothed estimates using Good-Turing discounting for counts up to a threshold $k_n$ :

$P_{\text{katz}}(w_i \mid w_{i-n+1}^{i-1}) = \begin{cases} \frac{c^*(w_{i-n+1}^i)}{c(w_{i-n+1}^{i-1})} & \text{if } c(w_{i-n+1}^i) > 0 \\ \alpha(w_{i-n+1}^{i-1}) P_{\text{katz}}(w_i \mid w_{i-n+2}^{i-1}) & \text{if } c(w_{i-n+1}^i) = 0 \end{cases}$

where $c^*(r)$ is the Good-Turing discounted count:

$c^*(r) = \begin{cases} r & \text{if } r > k_n \\ \frac{(r+1)\frac{n_{r+1}}{n_r} - r\frac{(k_n+1)n_{k_n+1}}{n_1}}{1 - \frac{(k_n+1)n_{k_n+1}}{n_1}} & \text{if } 1 \le r \le k_n \end{cases}$

and $\alpha(w_{i-n+1}^{i-1})$ is a normalization constant ensuring conditional probabilities sum to 1 over vocabulary $V$ .

In this multi-order formulation, a separate threshold $k_n$ is tuned for each $n$ -gram order $n > 1$ (rather than a single global $k$ ). The base unigram distribution is smoothed using additive smoothing with parameter $\delta$ :

$P_{\text{katz}}(w_i) = \frac{c(w_i) + \delta}{N_S + \delta |V|}$

where $N_S$ is the total token count in the training corpus.
Knowl 8 — Modified Church-Gale Smoothing Implementation
model/method
Church-Gale smoothing partitions $n$ -grams into disjoint buckets based on their predicted frequency from lower-order distributions and applies Good-Turing estimation within each bucket.

In this implementation:
1. Count-of-count frequencies $n_r$ are smoothed using Simple Good-Turing (Gale and Sampson, 1995).
2. The unigram distribution is smoothed using standard unbucketed Good-Turing estimation.
3. The lower-order probability product space is partitioned dynamically such that each bucket contains at least $c_{\text{min}}$ observed $n$ -grams with non-zero counts.
4. For trigram models, trigrams $w_{i-2}w_{i-1}w_i$ are partitioned into buckets based on the product $P(w_{i-2}^{i-1})P(w_i)$ (using smoothed bigram and unigram probabilities), and the resulting Good-Turing corrected counts within each bucket are normalized to produce valid probabilities.
Knowl 9 — Cross-Entropy Metric for Language Model Evaluation
definition
The quality of a language model smoothing method $m$ is evaluated by calculating the empirical cross-entropy on a test dataset $T$ composed of sentences $(t_1, \dots, t_{l_T})$ containing $N_T$ total words:

$H(T; P_m) = -\frac{1}{N_T} \sum_{i=1}^{l_T} \log_2 P_m(t_i)$

where $P_m(t_i)$ is the probability assigned to sentence $t_i$ by the language model constructed using method $m$ .

Cross-entropy represents the average number of bits required to encode each word in the test text. Lower cross-entropy corresponds to higher model likelihood. In this domain, a difference of $0.014\text{ bits/token}$ corresponds approximately to a $1\%$ difference in perplexity ( $2^{H(T; P_m)}$ ).
Knowl 10 — Experimental Setup and Parameter Optimization Protocol
experimental setup
Empirical evaluations are conducted on two vocabulary regimes and multiple standard corpora:
1. Brown Corpus: Tagged corpus from the Penn Treebank containing approximately 1,000,000 words, evaluated using a vocabulary of all 53,850 words occurring in Brown.
2. TIPSTER Corpora: Associated Press (123M words), Wall Street Journal (84M words), and San Jose Mercury News (43M words), evaluated using a vocabulary of 65,173 words appearing at least 70 times in TIPSTER.
3. Data Protocol: For each training data size (ranging from 100 to 10,000,000 sentences), three held-out segments of roughly 50,000 words each are used: one segment for final test evaluation and two segments for development parameter optimization.
4. Parameter Search: Free hyperparameters ( $k_n$ , $\delta$ , $c_{\text{min}}$ , $\beta_n$ , $\gamma_n$ , $\lambda_n$ ) are optimized directly on development set cross-entropy using Powell's direction set search method. For training sizes up to 50,000 sentences, results are averaged over 10 independent runs to compute empirical standard deviations.

Coverage note — No substantial contributed material was omitted from the knowls.

References

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.
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.
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.
4.Chen, Stanley F. 1996. Building Probabilistic Models for Natural Language. Ph.D. thesis, Harvard University. In preparation.
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.
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.
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.
8.Gale, William A. and Kenneth W. Church. 1990. Estimation procedures for language context: poor estimates are worse than none. In COMPSTAT, Proceedings in Computational Statistics, 9th Symposium, pages 69–74, Dubrovnik, Yugoslavia, September.
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.
10.Gale, William A. and Geoffrey Sampson. 1995. Good-Turing frequency estimation without tears. Journal of Quantitative Linguistics, 2(3). To appear.
11.Good, I.J. 1953. The population frequencies of species and the estimation of population parameters. Biometrika, 40(3 and 4):237–264.
12.Jeffreys, H. 1948. Theory of Probability. Clarendon Press, Oxford, second edition.
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.
14.Johnson, W.E. 1932. Probability: deductive and inductive problems. Mind, 41:421–423.
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.
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.
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.
18.MacKay, David J. C. and Linda C. Peto. 1995. A hierarchical Dirichlet language model. Natural Language Engineering, 1(3):1–19.
19.Magerman, David M. 1994. Natural Language Parsing as Statistical Pattern Recognition. Ph.D. thesis, Stanford University, February.
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.
21.Press, W.H., B.P. Flannery, S.A. Teukolsky, and W.T. Vetterling. 1988. Numerical Recipes in C. Cambridge University Press, Cambridge.

Citation

MLA

Chen, S. F., and J. Goodman. “An Empirical Study of Smoothing Techniques for Language Modeling”. 34th Annual Meeting of the Association for Computational Linguistics, 1996, pp. 310–18, https://doi.org/10.3115/981863.981904.

APA

Chen, S. F., & Goodman, J. (1996). An Empirical Study of Smoothing Techniques for Language Modeling. 34th Annual Meeting of the Association for Computational Linguistics, 310–318. https://doi.org/10.3115/981863.981904

Chicago

Chen, S. F., and J. Goodman. 1996. “An Empirical Study of Smoothing Techniques for Language Modeling”. 34th Annual Meeting of the Association for Computational Linguistics, 310–18. https://doi.org/10.3115/981863.981904.

Harvard

Chen, S.F. and Goodman, J. (1996) “An Empirical Study of Smoothing Techniques for Language Modeling”, 34th Annual Meeting of the Association for Computational Linguistics. Association for Computational Linguistics, pp. 310–318. Available at: https://doi.org/10.3115/981863.981904.

Vancouver

1. Chen SF, Goodman J (1996) An Empirical Study of Smoothing Techniques for Language Modeling. In: 34th Annual Meeting of the Association for Computational Linguistics. Association for Computational Linguistics, pp 310–318

BibTeX

@inproceedings{chen-goodman-1996-empirical,
    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",
    month = jun,
    year = "1996",
    address = "Santa Cruz, California, USA",
    publisher = "Association for Computational Linguistics",
    url = "https://aclanthology.org/P96-1041/",
    doi = "10.3115/981863.981904",
    pages = "310--318"
}

Metadata:ACL Anthology

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

License: https://creativecommons.org/licenses/by-nc-sa/4.0/

An Empirical Study of Smoothing Techniques for Language Modeling

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — One-Count Smoothing Method

Knowl 2 — Average-Count Bucketing for Jelinek-Mercer Smoothing

Knowl 3 — Trigram Smoothing Performance Across Corpora and Training Set Sizes

Knowl 4 — Bigram Smoothing Performance Across Corpora and Training Set Sizes

Knowl 5 — Parameter Sensitivity and Training Size Dependency in Smoothing Methods

Knowl 6 — Implementation Complexity of Smoothing Techniques

Knowl 7 — Modified Multi-Order Katz Smoothing Implementation

Knowl 8 — Modified Church-Gale Smoothing Implementation

Knowl 9 — Cross-Entropy Metric for Language Model Evaluation

Knowl 10 — Experimental Setup and Parameter Optimization Protocol

References

Citation

BibTeX

Access the Paper