Smoothing Techniques › Add-k Smoothing

A natural generalization is to add a fractional amount $k$ instead of 1. This is called add-k smoothing or Lidstone smoothing. Rather than inflating every count by a full unit, we inflate by a fraction $k \in (0, 1]$:

$$P_{\text{add-k}}(w_i \mid w_{i-1}) = \frac{C(w_{i-1}, w_i) + k}{C(w_{i-1}) + k|V|}$$

where:

• $k$: a hyperparameter in the range $(0, 1]$ controlling how much mass to redistribute to unseen events
• $C(w_{i-1}, w_i)$: raw bigram count
• $C(w_{i-1})$: raw unigram count of the context
• $|V|$: vocabulary size

When $k = 1$, this reduces to Laplace smoothing. When $k$ is small (for example, $k = 0.01$), the adjustment is gentler and less mass is stolen from seen bigrams.

The value of $k$ should be tuned on a held-out development set. You train the model on training data, then try different values of $k$ and pick the one that minimizes perplexity on the held-out data. Typical values range from 0.001 to 0.5.

However, even with optimally tuned $k$, add-k smoothing remains a relatively poor performer. The core problem is that it uses the same $k$ for all n-grams, regardless of how often they appear. A word that appears once in the training set and a word that appears 1,000 times receive the same additive adjustment, which isn't what the data suggests. More principled methods use different discount amounts for different n-grams based on their observed counts.

There's a deeper issue too. The add-k family of methods treats the lower-order distribution (what probability to give unseen bigrams) as uniform: every word in the vocabulary gets the same small baseline probability of $k / (C(w_{i-1}) + k|V|)$, regardless of how common the word is. But in reality, some words are much more likely to appear in new contexts than others. A common function word like "the" is far more likely to follow any given word than a rare content word. The lower-order distribution should reflect this, and add-k doesn't.