Naive Bayes Classification

Core Idea

Given a document $d$ and a set of classes $C$, find the class with the highest posterior probability:

$c^* = \underset{c \in C}{\text{argmax}} \ P(c \mid d)$

By Bayes’ Theorem:

$P(c \mid d) = \frac{P(c) \times P(d \mid c)}{P(d)}$

Since $P(d)$ is constant across all classes for a given document, we drop it:

$c^* = \underset{c \in C}{\text{argmax}} \ P(c) \times P(d \mid c)$

The Naive Assumption

The “naive” part: all features (words) are independent given the class. This lets us decompose the document probability into a product:

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

where $w_1, w_2, \dots, w_n$ are the words in the document. The full classification rule:

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

Parameter Estimation (Unsmoothed MLE)

Prior:

$P(c) = \frac{N_c}{N_{\text{total}}}$

where $N_c$ is the number of training documents of class $c$.

Likelihood (Maximum Likelihood Estimate, no smoothing):

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

where $\text{count}(w, c)$ is the number of times word $w$ appears in documents of class $c$, and $V$ is the vocabulary.

The Zero-Probability Problem

If any word $w$ in the test document never appeared with class $c$ in training, then $\text{count}(w, c) = 0$, so $P(w \mid c) = 0$. The product $\prod P(w_i \mid c)$ becomes zero. If this happens for all classes, the classifier cannot decide.

Even one unseen word kills the entire product. This is not a rare edge case: Zipf’s Law and Heaps’ Law guarantee that test documents will contain unseen words.

Worked Example (Small 3-Word Problem)

Training data (2 classes, SPAM and HAM):

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$.

Token counts per class:

• SPAM: buy=2, now=1, free=1 (3 tokens total)
• HAM: meeting=1, now=1, free=1, lunch=1 (4 tokens total)

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

Likelihoods (unsmoothed):

• $P(\text{buy} \mid \text{SPAM}) = 2/3 \approx 0.667$
• $P(\text{buy} \mid \text{HAM}) = 0/4 = 0$ (never seen with HAM)

Classify test document “buy lunch”:

$P(\text{SPAM} \mid \text{"buy lunch"}) \propto 0.5 \times (2/3) \times P(\text{lunch} \mid \text{SPAM})$

$P(\text{lunch} \mid \text{SPAM}) = 0/3 = 0$ (never seen with SPAM).

$P(\text{HAM} \mid \text{"buy lunch"}) \propto 0.5 \times P(\text{buy} \mid \text{HAM}) \times (1/4)$

$P(\text{buy} \mid \text{HAM}) = 0/4 = 0$ (never seen with HAM).

Both products collapse to zero. The classifier cannot choose. This is exactly what Laplace smoothing prevents.

Interpretability

Naive Bayes is interpretable: every parameter $P(w \mid c)$ is directly inspectable. If a feature value appears only with one class in training, you can identify the bias mathematically (e.g., $P(\text{Gender=F} \mid \text{Success}) = 0$ means the classifier can never predict Success for Female applicants). This property is invaluable for fairness auditing and is not available in black-box models.

Summary

Component	Formula	Notes
Prior	$P(c) = N_c / N_{\text{total}}$	Fraction of training docs in class $c$
Likelihood (MLE)	$P(w \mid c) = \text{count}(w,c) / \sum \text{count}(w',c)$	Zero for unseen words
Classification rule	$c^* = \text{argmax}_c \ P(c) \prod P(w_i \mid c)$	Product collapses if any $P(w_i \mid c) = 0$

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