Concept - Zero Probability Problem

Definition

In Concept - Naive Bayes, a class score is the product $p(c){\prod }_{i}p(w_i\mid c)$. If any word $w_i$ of the message never occurred in training messages of class $c$, then $p(w_i\mid c)=0$ and the entire product becomes 0 for that class, whatever the other factors are (s.107-115, 03 Text Classification - Chunk 04 (s.91-120)).

Slide example (s.97-120)

• Message: “Lunch Money Money Money Money”.
• Normal: $0.67\times 0.18\times 0.06^4=0.000002$ (s.106).
• Spam: $p(S)\times p(\text{Lunch}\mid S)\times p(\text{Money}\mid S{)}^4=0$, because $p(\text{Lunch}\mid S)=0.00$: “it was not in the Training Data” (s.108-109).
• It “doesn’t matter” what $p(S)=0.33$ or $p(\text{Money}\mid S)=0.57$ is: “anything times 0 is 0” (s.112-115).
• Consequence: any message containing Lunch will always be classified as normal, no matter how many times Money occurs (s.116-118). “And that’s a problem.” (s.119)

Intuition

A zero count means “not observed in the training sample”, not “impossible”. Treating it as impossible lets a single unseen word veto a class.

Fix

Add 1 count (a “black box”) to every word in every class histogram: Concept - Laplace Smoothing (s.120).

Related

Concept - Naive Bayes | Concept - Likelihood | Concept - Prior Probability | Concept - Laplace Smoothing | Concept - Underflow