Smoothing Techniques › Absolute Discounting

Before introducing Kneser-Ney, we need to understand absolute discounting, which supports Kneser-Ney's most useful idea.

Absolute discounting is based on a remarkable empirical observation made by Church and Gale (1991): when you subtract a constant $d$ from every non-zero bigram count, the resulting adjusted counts closely match the Good-Turing adjusted counts across the whole count spectrum. In other words, Good-Turing's sophisticated per-count calculation can be approximated simply by subtracting a fixed discount $d$ from every non-zero count, using the same $d$ regardless of the count value.

This is surprising. You might expect that a bigram seen 2 times needs a different proportional discount than one seen 20 times. But Church and Gale found empirically that subtracting the same constant $d \approx 0.75$ from both cases produces adjusted counts very close to what Good-Turing would give. The reason is that the ratio $N_{c+1}/N_c$ turns out to be approximately constant for small values of $c$ in most natural language distributions, which means the Good-Turing adjustment is approximately linear in $c$ for small counts, which in turn means subtracting a constant works well.

The absolute discounting formula combines a discounted seen-bigram term with a lower-order interpolation term:

$$P_{\text{abs}}(w_i \mid w_{i-1}) = \frac{\max\bigl(C(w_{i-1}, w_i) - d,\ 0\bigr)}{C(w_{i-1})} + \lambda(w_{i-1}) \cdot P_{\text{lower}}(w_i)$$

where:

• $d$: the discount parameter, typically between 0 and 1 (often around 0.75), subtracted from every non-zero bigram count
• $\lambda(w_{i-1})$: a normalization constant ensuring all conditional probabilities sum to 1
• $P_{\text{lower}}(w_i)$: a lower-order (backoff or interpolation) probability for $w_i$

The $\max(\cdot, 0)$ ensures we never give a negative probability to seen n-grams. For very rare n-grams (count = 1 or 2), $C - d$ is still positive (since $d < 1$), so this clamp is usually not triggered unless $d > 1$.

The normalization constant $\lambda$ captures the total probability mass that was removed from the seen bigrams:

$$\lambda(w_{i-1}) = \frac{d \cdot \bigl|\{w : C(w_{i-1}, w) > 0\}\bigr|}{C(w_{i-1})}$$

where:

• $\bigl|\{w : C(w_{i-1}, w) > 0\}\bigr|$: the number of distinct words that follow $w_{i-1}$ in the training corpus (the number of distinct bigram completions)
• $C(w_{i-1})$: the total count of $w_{i-1}$

The numerator $d \cdot \bigl|\{w : C > 0\}\bigr|$ equals the total probability mass removed from seen bigrams (each of the distinct continuations loses $d / C(w_{i-1})$ in probability). The denominator normalizes this so that $\lambda$ represents the fraction of mass to be redistributed.

Church and Gale estimated the optimal discount as:

$$d \approx \frac{N_1}{N_1 + 2 N_2}$$

where:

• $N_1$: the number of distinct bigrams seen exactly once
• $N_2$: the number of distinct bigrams seen exactly twice

This formula is surprisingly accurate: in most real corpora, $d$ ends up close to 0.75. The intuition behind the formula is that it minimizes the average squared error between the absolute-discounting adjusted counts and the Good-Turing adjusted counts, given the observed frequency-of-frequency distribution.

The key insight from absolute discounting is that the same discount works well across a wide range of counts. Whether a bigram appeared 2 times or 200 times, subtracting $d \approx 0.75$ gives a good adjusted count. This is much simpler than Good-Turing's per-count estimation, and it performs nearly as well because the Good-Turing adjustments are themselves nearly constant for typical natural language count distributions.