Log-Probability and Underflow Mitigation

The Underflow Problem

The Naive Bayes classification rule multiplies many small probabilities:

$P(c) \times \prod_{i=1}^{n} P(w_i \mid c)$

With Laplace smoothing, a typical $P(w \mid c)$ might be ~0.001. For a document with 100 words, the product is roughly $(10^{-3})^{100} = 10^{-300}$. Standard 64-bit floating-point numbers can represent values down to approximately $10^{-308}$ before hitting zero. A 100-word document is close to this boundary; longer documents or smaller probabilities push the product to exactly zero on the computer.

Floating-point underflow turns a mathematically valid (but tiny) number into zero. When this happens, the classifier loses all discriminative information: every class product becomes zero, and the argmax is meaningless.

Solution: Work in Log Space

Since $\log$ is strictly monotonically increasing, the argmax is identical:

$c^* = \underset{c \in C}{\text{argmax}} \ \log\left(P(c) \times \prod_{i=1}^{n} P(w_i \mid c)\right)$

$c^* = \underset{c \in C}{\text{argmax}} \ \left[ \log P(c) + \sum_{i=1}^{n} \log P(w_i \mid c) \right]$

The product becomes a sum of log-probabilities. Each $\log P(w \mid c)$ is a moderate negative number (e.g., $\log(0.001) = -6.91$). For 100 words, the sum is roughly $-691$, which is easily representable.

Why This Works

Logarithms map multiplication to addition:

$\log(a \times b) = \log(a) + \log(b)$

For three probabilities:

$\log(P(c) \times P(w_1 \mid c) \times P(w_2 \mid c)) = \log P(c) + \log P(w_1 \mid c) + \log P(w_2 \mid c)$

Each term is a negative number. The sum grows (becomes more negative) linearly with document length, rather than exponentially shrinking toward zero.

Worked Example

Classify a 10-word document with two classes. Smoothed probabilities:

Word	$P(w \mid \text{Class A})$	$P(w \mid \text{Class B})$
$w_1$	0.001	0.002
$w_2$	0.003	0.001
$w_3$	0.0005	0.004
$w_4$	0.002	0.001
$w_5$	0.001	0.003
$w_6$	0.004	0.0005
$w_7$	0.001	0.002
$w_8$	0.002	0.001
$w_9$	0.003	0.001
$w_{10}$	0.0005	0.002

Priors: $P(\text{A}) = 0.6$, $P(\text{B}) = 0.4$.

In probability space (dangerous):

$P(\text{A} \mid d) \propto 0.6 \times (0.001 \times 0.003 \times 0.0005 \times \dots)$

The product is approximately $10^{-34}$, still representable for 10 words, but for 100 words it would underflow.

In log space (safe):

$\log P(\text{A}) = \log(0.6) = -0.511$

$\sum \log P(w_i \mid \text{A}) = \log(0.001) + \log(0.003) + \log(0.0005) + \dots = -6.908 + (-5.809) + (-7.601) + \dots$

Sum for A: $-0.511 + (-65.2) = -65.7$. Sum for B: $\log(0.4) + (-58.4) = -0.916 + (-58.4) = -59.3$.

Since $-59.3 > -65.7$, the classifier predicts Class B. The log-space computation is numerically stable for documents of any length.

Implementation Note

Always convert to log space immediately after computing smoothed probabilities. Pre-compute $\log P(w \mid c)$ for every word-class pair during training. At classification time, sum the pre-computed log values for the words in the document and add $\log P(c)$. The class with the largest (least negative) sum wins.

Summary

Approach	Operation	Risk
Probability space	Multiply $P(w \mid c)$	Underflow for ~100+ words
Log space	Sum $\log P(w \mid c)$	Safe for any document length

Past paper questions: y2021p3q9(a)