ConceptDBISAI-written · not yet proofread

Laplace Smoothing

Also Additive Smoothing · Add-One Smoothing · Add-Epsilon Smoothing

Additive smoothing replaces the relative frequencies n_wc / n_c by (n_wc + α) / (n_c + α|V|) for some α > 0, so that every word gets a non-zero probability while the estimates stay a probability distribution.

Know these firstNaive Bayes Classifier

Formula#

Smoothing given probabilities (exam WS 19/20, Task 4.2). If only the learned $p_{wc}$ are available, add $\varepsilon > 0$ to each of them and renormalize per class:

p'_{wc} = \frac{p_{wc} + \varepsilon}{\sum_{v \in V} (p_{vc} + \varepsilon)} = \frac{p_{wc} + \varepsilon}{1 + \varepsilon \cdot |V|}.

With $p_{wc} = n_{wc}/n_c$ this is additive smoothing with $\alpha = \varepsilon \cdot n_c$ :

\frac{n_{wc}/n_c + \varepsilon}{1 + \varepsilon |V|} = \frac{n_{wc} + \varepsilon n_c}{n_c + \varepsilon n_c |V|}.

Properties#

The three properties asked in exam WS 19/20, Task 4.2, hold for every $\alpha > 0$ (resp. $\varepsilon > 0$ ):

Non-zero: $n_{wc} + \alpha \ge \alpha > 0$ , and the denominator is positive, so $p_{wc} > 0$ for every word, also for unseen ones.
Order preserved within a class: $n_{wc} < n_{vc} \iff n_{wc} + \alpha < n_{vc} + \alpha$ , and dividing by the same positive number keeps the strict inequality.
Still a distribution: $\sum_{w \in V} (n_{wc} + \alpha) = n_c + \alpha |V|$ , so the $p_{wc}$ of each class sum to $1$ .

Further:

Why it is needed in Naive Bayes: a single word of $d$ that was never seen in class $c$ makes $p_{wc} = 0$ and the whole score of $c$ zero; in log space $\log 0$ is undefined.
Effect of $\alpha$ : $\alpha \to 0$ gives the unsmoothed relative frequencies; $\alpha \to \infty$ pushes every $p_{wc}$ towards the uniform $1/|V|$ . Smoothing helps rare classes and short training sets most, where $n_c$ is small compared to $\alpha |V|$ .

Example#

ExampleSmoothing removes zero scores

Training data from Naive Bayes Classifier > Example: $S$ : “ball goal”, “ball ball”; $P$ : “vote law”, “vote ball”; $V = \{\text{ball}, \text{goal}, \text{vote}, \text{law}\}$ , $n_S = n_P = 4$ , $p_S = p_P = 1/2$ . With $\alpha = 1$ the denominators are $4 + 4 = 8$ :

	ball	goal	vote	law
$p_{wS}$	$4/8$	$2/8$	$1/8$	$1/8$
$p_{wP}$	$2/8$	$1/8$	$3/8$	$2/8$

Document “ball goal vote” (both scores were $0$ without smoothing): score $S$ $= \frac12 \cdot \frac48 \cdot \frac28 \cdot \frac18 = \frac{8}{1024}$ , score $P$ $= \frac12 \cdot \frac28 \cdot \frac18 \cdot \frac38 = \frac{6}{1024}$ , so $\hat c = S$ .

Sources#

Not covered by a WS 25/26 lecture. Source: the former Information Retrieval exams.
Exam WS 19/20, Task 4.2 (not published) (smooth(pwc, eps) with the three properties)

Connections

Mentioned in inline links2

Naive Bayes Classifier
Zero probabilities. If a word $w$ of $d$ never occurs in the training documents of class $c$ , then $p_{wc} = 0$ and the score of $c$ is $0$ , whatever the other words say. If every class has such a word, all scores are $0$ . Smoothing fixes… §
Document “ball goal vote”: both scores are $0$ (goal is unseen in $P$ , vote is unseen in $S$ ). See Laplace Smoothing for the smoothed version. §
Naive Bayes Classification
Laplace Smoothing — avoids zero probabilities for unseen words §
Where things go wrong: a word never seen in class $c$ zeroes its score. Laplace Smoothing repairs this; the log-space implementation needs it, and avoids underflow of long products. §

Search in these mentions →