Laplace Add-One Smoothing

The Problem

Without smoothing, any word never seen with class $c$ in training gets $P(w \mid c) = 0$. One unseen word makes the entire Naive Bayes product collapse to zero. Zipf’s Law and Heaps’ Law guarantee that unseen words are ubiquitous.

Laplace (Add-One) Smoothing

Add 1 to every word count and add $\lvert V \rvert$ to the denominator:

$P(w \mid c) = \frac{\text{count}(w, c) + 1}{\sum_{w' \in V} \text{count}(w', c) + \lvert V \rvert}$

• $\lvert V \rvert$: total number of unique word types across all training data (all classes combined)
• Effect: shifts a small amount of probability mass from seen words to unseen ones
• Every word type, even those never seen in training, now has $P(w \mid c) > 0$

General Smoothing Parameter $\omega$

$P(w \mid c) = \frac{\text{count}(w, c) + \omega}{\sum_{w' \in V} \text{count}(w', c) + \omega \times \lvert V \rvert}$

Laplace smoothing is the special case $\omega = 1$. The parameter $\omega$ can be tuned on the development set: try $\omega = 0.1, 0.5, 1.0, 2.0$ and pick the value that maximises dev-set accuracy or F1.

Worked Example

Revisiting the small 2-class problem from the Naive Bayes note.

Training data:

• SPAM documents: “buy now”, “free buy”
• HAM documents: “meeting now”, “free lunch”

Vocabulary $V = \{\text{buy}, \text{now}, \text{free}, \text{meeting}, \text{lunch}\}$, $\lvert V \rvert = 5$.

Smoothed likelihoods:

SPAM class (total tokens = 3):

$P(\text{buy} \mid \text{SPAM}) = \frac{2 + 1}{3 + 5} = \frac{3}{8} = 0.375$

$P(\text{now} \mid \text{SPAM}) = \frac{1 + 1}{3 + 5} = \frac{2}{8} = 0.25$

$P(\text{free} \mid \text{SPAM}) = \frac{1 + 1}{3 + 5} = \frac{2}{8} = 0.25$

$P(\text{meeting} \mid \text{SPAM}) = \frac{0 + 1}{3 + 5} = \frac{1}{8} = 0.125$

$P(\text{lunch} \mid \text{SPAM}) = \frac{0 + 1}{3 + 5} = \frac{1}{8} = 0.125$

HAM class (total tokens = 4):

$P(\text{meeting} \mid \text{HAM}) = \frac{1 + 1}{4 + 5} = \frac{2}{9} \approx 0.222$

$P(\text{now} \mid \text{HAM}) = \frac{1 + 1}{4 + 5} = \frac{2}{9} \approx 0.222$

$P(\text{free} \mid \text{HAM}) = \frac{1 + 1}{4 + 5} = \frac{2}{9} \approx 0.222$

$P(\text{lunch} \mid \text{HAM}) = \frac{1 + 1}{4 + 5} = \frac{2}{9} \approx 0.222$

$P(\text{buy} \mid \text{HAM}) = \frac{0 + 1}{4 + 5} = \frac{1}{9} \approx 0.111$

Classify “buy lunch”:

Priors: $P(\text{SPAM}) = 0.5$, $P(\text{HAM}) = 0.5$.

$P(\text{SPAM} \mid d) \propto 0.5 \times 0.375 \times 0.125 = 0.5 \times 0.046875 = 0.02344$

$P(\text{HAM} \mid d) \propto 0.5 \times 0.111 \times 0.222 = 0.5 \times 0.02464 = 0.01232$

The classifier predicts SPAM. Without smoothing, both products were zero; the classifier could not choose. With Laplace smoothing, every word has non-zero probability, and the classifier works correctly.

Exam Rule

Apply smoothing whenever the question does not explicitly say “without smoothing”. Always state $\lvert V \rvert$ explicitly as the denominator correction.

Summary

Smoothing	Formula	$\omega$
Laplace (add-one)	$(\text{count}+1) / (\text{total}+\lvert V \rvert)$	1
Add-$\omega$ (general)	$(\text{count}+\omega) / (\text{total}+\omega\lvert V \rvert)$	Tuned on dev set

Past paper questions: y2021p3q9(a), y2023p3q8(a), y2024p3q9(a)