We know that language models face a major hurdle: data sparsity. Most word combinations will never appear in a training corpus, no matter how large. Simple smoothing methods like add-one (Laplace) smoothing solve this by giving a little probability to everything, but they often go too far, taking too much probability from things we've seen and giving it to things we haven't.

More advanced techniques offer a smarter way to redistribute probability. They don't treat all unseen events as equally likely. Instead, they use information from lower-order n-grams to make more nuanced guesses.

A more sophisticated approach starts with a simple, powerful idea: subtract a small, fixed discount from the counts of every n-gram you've seen. This is called absolute discounting. The name is a bit of a misnomer; it's not the count that's discounted, but rather the probability mass derived from it.

Imagine you have a small bucket of probability for each word context. For every bigram you've seen, you take a small, fixed amount of probability out of its bucket. You then collect all this discounted probability and distribute it among the bigrams you haven't seen. This ensures that frequent n-grams contribute more to the unseen probability pool than rare ones, which is a more sensible arrangement than what Laplace smoothing does.

The discount $d$ is a hyperparameter, typically a value between 0 and 1. A common choice is $d = 0.75$. The key takeaway is that we've separated the probability calculation: one part for seen n-grams and another for unseen ones, funded by a discount on the seen ones.

Absolute discounting is good, but its backoff model can be improved. A simple unigram model estimates $P_{backoff}(w_i)$ based on how frequently $w_i$ appears overall. But is raw frequency really what we want? Consider the bigram "San Francisco". The word "Francisco" appears frequently in a corpus, but almost always after "San". It's not a very versatile word. The word "cat", however, might appear after many different words: "the", "a", "my", "your", "that", etc.

Kneser-Ney (KN) smoothing's core insight is that for a backoff model, we care more about how many different contexts a word appears in than its raw frequency. A word that completes many different bigrams is a better candidate to complete a new, unseen one. This is called its continuation probability.

The continuation probability is calculated based on the number of unique preceding words.

This seemingly small change makes Kneser-Ney smoothing dramatically more effective than other methods, and it's long been considered the state-of-the-art for n-gram language models.

One final tweak improves the model even further. The original formulation uses a single discount parameter $d$. However, research has shown that using different discounts for n-grams with different counts can yield better results. For example, you might want to discount a bigram with a count of 1 differently than a bigram with a count of 10.

Modified Kneser-Ney smoothing introduces separate discounts for n-grams with counts of 1, counts of 2, and counts of 3 or more. While mathematically more complex, this adjustment provides a more fine-grained and accurate redistribution of probability mass.

The choice of smoothing technique has a direct and significant impact on model performance, typically measured by perplexity. A lower perplexity score indicates that the model is less surprised by the test data, meaning its probability distributions are a better match for the real-world language.

For any serious application of n-gram models, Kneser-Ney or its modified version is the standard choice. It intelligently handles data sparsity by considering the diversity of contexts a word appears in, leading to more accurate probability estimates and better overall model performance.

While neural language models have largely replaced n-gram models in many state-of-the-art applications, understanding these classical smoothing techniques provides a strong foundation in the core challenges of language modeling.