Naive Bayes Classifier

Source: Unit 3 §9

The setup

Naive Bayes is a highly practical Bayesian method, with performance comparable to neural nets and decision trees on a lot of real problems.

Each instance is a tuple of attribute values $(a_1, a_2, \dots, a_n)$, and the target $f(x) \in V$ is drawn from a finite set. Assign the most probable value:

$$v_{\text{MAP}} = \arg\max_{v_j \in V} P(v_j \mid a_1, \dots, a_n) = \arg\max_{v_j \in V} P(a_1, \dots, a_n \mid v_j) \cdot P(v_j)$$

⚠GotchaThe second factor is the one that will not estimate

$P(v_j)$ is easy - count how often $v_j$ appears in the training set. But $P(a_1, \dots, a_n \mid v_j)$ needs a huge dataset, because it has one parameter for every combination of attribute values. Most combinations will never appear in your training data at all.

The naive conditional independence assumption

Naive assumption: attribute values are conditionally independent given the target value. The joint probability then becomes a product of individual probabilities:

$$v_{\text{NB}} = \arg\max_{v_j \in V} P(v_j) \prod_i P(a_i \mid v_j)$$

The naive assumption replaces one table indexed by every attribute combination with n small tables indexed by one attribute each. That is the entire trick, and it is why Naive Bayes trains on data a full joint model could never learn from.

≡FactsWhat the assumption buys and costs

• Number of terms to estimate drops to (number of distinct attribute values) × (number of distinct target values), which is far fewer than the joint.
• When the conditional independence assumption actually holds, NB classification equals MAP classification - nothing is lost.
• When it does not hold, the probabilities come out wrong, but the argmax is often still right, which is why the method survives its own bad assumption.

Worked example 1: Play Tennis

The same 14-row dataset as the decision-tree example. Classify:

$$x = (\text{Outlook}=\text{Sunny},\; \text{Temp}=\text{Cool},\; \text{Humidity}=\text{High},\; \text{Wind}=\text{Strong})$$

Prior probabilities: $P(\text{Yes}) = 9/14 = 0.643$ and $P(\text{No}) = 5/14 = 0.357$.

Attribute value	P(· | Yes)	P(· | No)
Outlook = Sunny	2/9 = 0.222	3/5 = 0.60
Temp = Cool	3/9 = 0.333	1/5 = 0.20
Humidity = High	3/9 = 0.333	4/5 = 0.80
Wind = Strong	3/9 = 0.333	3/5 = 0.60

→StepsMultiplying out both classes

1. YES: $0.643 \times 0.222 \times 0.333 \times 0.333 \times 0.333 = \mathbf{0.00529}$.
2. NO: $0.357 \times 0.60 \times 0.20 \times 0.80 \times 0.60 = \mathbf{0.02057}$.
3. NO (0.0206) beats YES (0.0053), so PlayTennis(x) = NO.

⚠GotchaThe slide's YES value is an arithmetic slip

The slide shows YES = 0.0211. The correct value is ≈ 0.0053. The final answer is unaffected - NO is still correct, because NO ≈ 0.0206 dominates either way - but do not reproduce 0.0211 in an exam.

Worked example 2: text classification

Training data:

Sentence	Class
A great game	sports
The election is over	not sports
very clean match	sports
a clean but forgettable game	sports
it was a close election	not sports

Task: classify "A very close game" as sports or not sports.

≡FactsThe bag-of-words idea

Ignore word order and grammar; treat a document as a set of words, with the features being word frequencies. It is simplistic and it works well.

Word independence turns a sentence probability into a product:

$$P(\text{a very close game} \mid \text{sports}) = P(\text{a} \mid s) \cdot P(\text{very} \mid s) \cdot P(\text{close} \mid s) \cdot P(\text{game} \mid s)$$

and we compare $P(\text{sentence} \mid \text{sports}) \cdot P(\text{sports})$ against $P(\text{sentence} \mid \neg\text{sports}) \cdot P(\neg\text{sports})$, dropping the common divisor $P(D)$.

Priors: $P(\text{sports}) = 3/5 = 0.6$ and $P(\neg\text{sports}) = 2/5 = 0.4$.

⚠GotchaThe zero-probability problem

The word "close" never appears in a sports sentence, so $P(\text{close} \mid \text{sports}) = 0$, and one zero factor annihilates the entire product. A single unseen word would veto a class no matter how much evidence the other words provide. The fix is Laplace smoothing.

Laplace smoothing: add 1 to every word count, and add the vocabulary size to the denominator.

$$P(\text{word} \mid \text{class}) = \frac{\text{count} + 1}{\text{words in class} + \lvert \text{vocabulary} \rvert}$$

#NumbersThe counts for this corpus

• Sports has 11 words.
• Not-sports has 9 words.
• The vocabulary is 14 distinct words.

Word	P(word | sports)	P(word | not sports)
a	(2+1)/(11+14) = 3/25	(1+1)/(9+14) = 2/23
very	(1+1)/25 = 2/25	(0+1)/23 = 1/23
close	(0+1)/25 = 1/25	(1+1)/23 = 2/23
game	(2+1)/25 = 3/25	(0+1)/23 = 1/23

→StepsMultiplying, prior included

1. sports: $0.6 \times \tfrac{3}{25} \times \tfrac{2}{25} \times \tfrac{1}{25} \times \tfrac{3}{25} = 0.0000276$, that is $2.76 \times 10^{-5}$.
2. not sports: $0.4 \times \tfrac{2}{23} \times \tfrac{1}{23} \times \tfrac{2}{23} \times \tfrac{1}{23} = 0.0000057$, that is $5.72 \times 10^{-6}$.
3. sports ($2.76 \times 10^{-5}$) beats not sports ($5.72 \times 10^{-6}$), so the sentence is classified as SPORTS.

Note that smoothing did not just avoid a zero product: "close" still gets the smallest numerator in the sports column, so the evidence against sports is preserved, just not made absolute.

Advanced text techniques

≡FactsFour upgrades to the bag of words

• Remove stop words (a, able, the). "a very close game" becomes "very close game".
• Stemming / lemmatisation groups related forms: "election" and "elected" are counted as one.
• n-grams count sequences of words - "clean match", "close election" - instead of single words, recovering a little of the word order the bag threw away.
• TF-IDF (term frequency, inverse document frequency) is a numeric statistic reflecting how important a word is to a document within a corpus.