Smoothing Techniques › Comparing Smoothing Methods Empirically

Laplace smoothing performs poorly on realistic corpora. The fundamental problem is that it adds $|V|$ to the denominator, which is enormous for real vocabularies. This effectively discounts all n-gram counts massively and allocates an implausibly large fraction of probability mass to unseen events. Chen and Goodman's 1998 empirical comparison showed Laplace performing worst among all smoothing methods tested, across every corpus and n-gram order they examined.

Add-k with tuned $k$ can perform reasonably well, significantly better than Laplace. But it requires a held-out validation set and still uses the same discount for all count values, which is suboptimal. The sensitivity to $k$ means that a poorly tuned model can be worse than Laplace if $k$ is set too small.

Good-Turing estimation performs better than add-k for low-count n-grams (counts 1-5) but is unreliable for higher counts and requires a separate strategy for those. In practice, Good-Turing is rarely used in isolation but rather as a building block for better methods.

Katz backoff with Good-Turing discounting performs well and was the standard method for many years in speech recognition and machine translation systems. It's computationally efficient and handles the count-dependent discounting better than add-k. Many successful systems from the 1990s and early 2000s used Katz backoff.

Absolute discounting performs comparably to Katz in most settings and is significantly simpler to implement. The estimated discount from $N_1 / (N_1 + 2N_2)$ requires no tuning and works well across corpora.

Kneser-Ney and modified Kneser-Ney consistently outperform all other methods, especially for higher-order n-grams. The improvement comes entirely from the continuation-count lower-order distribution. On the Penn Treebank benchmark, for example, modified Kneser-Ney with trigrams achieves perplexity around 100-120 on standard test splits, while Laplace smoothing achieves perplexity many times higher. On the Wall Street Journal corpus, Kneser-Ney trigram models typically reduce perplexity by 30-40% relative to well-tuned add-k, a substantial difference that translates directly into improved speech recognition word error rates.

The following table summarizes the characteristics of each method:

An important pattern in empirical comparisons is that the performance gap between Kneser-Ney and simpler methods grows as the n-gram order increases. For unigrams, there's no smoothing to be done. For bigrams, the differences are meaningful. For trigrams, Kneser-Ney's advantage is substantial. For 4-grams and 5-grams, it's decisive.

The reason is that higher-order n-grams suffer from more severe data sparsity, which means the lower-order backoff model is consulted more frequently. When you back off from 5-grams to 4-grams to trigrams to bigrams to unigrams, the quality of the unigram distribution matters enormously, because many n-gram probability estimates ultimately depend on it. Kneser-Ney's continuation probability is a much better unigram distribution for this purpose than MLE frequency, and this advantage propagates up through all the higher-order calculations.

This is why modified Kneser-Ney remained the recommended method for n-gram language models for over two decades. Even as corpora grew from millions to billions of words, the continuation probability remained a superior choice for the lower-order distribution. The principle behind it, that a good lower-order distribution should measure contextual diversity rather than raw frequency, is a fundamental insight that doesn't become less true as data increases.