Smoothing: Laplace and Good-Turing Discounting
On this page
Smoothing: Laplace and Good-Turing Discounting
Recall first
Why does an unsmoothed bigram model fail catastrophically after seeing one unseen continuation? What should smoothing preserve as well as non-zero coverage?
First principles
Smoothing reallocates some probability mass from seen events to unseen or rare events while keeping a valid distribution. It combats sparse counts; it cannot repair bad tokenization or domain mismatch.
Laplace/add-one smoothing adds one to every possible continuation:
P_L(w|h) = (count(h,w)+1)/(count(h)+V)
where V is vocabulary size. For a bigram with count(h)=3, count(h,w)=0, and V=5, the unseen probability is 1/8; without smoothing it is zero. Add-one is simple and easy to derive, but often over-discounts frequent events, especially when V is large. Add-k uses a smaller k and reduces that distortion.
Good-Turing discounting estimates how much probability belongs to events with count c by looking at the frequency of frequencies. Let N_c be the number of n-gram types seen exactly c times. The adjusted count is approximately
c* = (c+1) N_{c+1}/N_c.
The idea is that a large population of singletons signals substantial unseen mass. It is more data-sensitive than blindly adding one, but raw N_c values become noisy at high counts; practical systems smooth the frequency-of-frequency curve and combine discounting with backoff/interpolation. For c=0, unseen mass is estimated indirectly from N_1/N, not by putting a literal count in the numerator.
Worked comparison. If a context has 3 observed continuations and V=5, add-one gives every possible continuation a denominator 8, including two unseen types. Good-Turing instead asks how many types occurred once, twice, etc., and discounts each seen count according to that evidence. Thus it can allocate unseen mass without treating a frequent event as if it were only one count.
Exercise — reveal after answering
Using raw Good-Turing counts N₁=20, N₂=5, what adjusted count is suggested for a count-1 event?
Answer: c* = 2×5/20 = 0.5. In practice, smooth N_c estimates and check reliability before using the raw value.
Exam lens
Write Laplace’s formula with V, explain its over-discounting, then state Good-Turing’s N_c idea and c* formula. Distinguish smoothing from merely deleting rare events.
Rapid revision checklist
- Define smoothing and probability-mass reallocation.
- Compute add-one probability.
- Define
N_cand Good-Turing adjusted count. - State why raw Good-Turing estimates need care.
Key takeaways
- Add-one prevents zeroes but is usually crude.
- Good-Turing uses frequency-of-frequencies to estimate unseen mass.
- Smoothing must maintain normalization and match the model’s vocabulary/context policy.