ML6.3 · LESSON 3 OF 6

Naive Bayes

Compare nearest-neighbor, naive Bayes and margin-based predictions using their actual assumptions.

THE IDEA

Counting words, then multiplying

Bayes' rule says P(class | message) is proportional to P(class) × P(message | class). The hard part is P(message | class): the number of possible messages is astronomical, so you will never see most of them. Naive Bayes makes one bold assumption: given the class, the words are independent. Then P(message | class) is just the product of one-word probabilities, and each of those can be estimated by counting.

Our tiny training set has 4 spam and 4 ham messages. Spam messages contain 13 words in total and ham messages 10. The word free appears 3 times in spam and never in ham. To score a message, start from the prior (each class is 4 of 8, so 0.5) and multiply in the probability of each word given that class.

smoothing alpha = 1

Click a word to add one more copy to the message. Message: free meeting. Training: 4 spam and 4 ham messages, 13 spam words, 10 ham words, 8 different words.

word	in message	count in ham	count in spam	P(word \| ham)	P(word \| spam)
free	1	0	3	0.0556	0.1905
lunch	0	2	0	0.1667	0.0476
meeting	1	3	0	0.2222	0.0476
now	0	1	3	0.1111	0.1905
prize	0	0	3	0.0556	0.1905
report	0	2	0	0.1667	0.0476
today	0	2	1	0.1667	0.0952
win	0	0	3	0.0556	0.1905
prior		4 of 8 each		0.5	0.5
product		prior times the likelihoods		0.0062	0.0045
sum of logs		log prior plus log likelihoods		-5.0876	-5.3959

Posterior: ham 57.6%, spam 42.4%. Prediction: ham.

Click words to build a message. Watch the product row and the sum-of-logs row. Then drag alpha down to 0 and try the message free meeting.

Why logs, and why smoothing

Real messages have hundreds of words, and a product of hundreds of probabilities such as 0.01 shrinks to 0 in floating point. Taking logs turns the product into a sum, and the larger total still marks the likelier class: log P(c) + Σ log P(wordⱼ | c). (A product of 70 numbers of size 0.00001 is already exactly 0 in 64-bit floats, while its log is -805.9048.)

The bigger problem is a word that never appeared in a class during training. Its estimated probability is 0/total = 0, and a single zero multiplies the entire product to 0, however much other evidence there is. Try the message free meeting with alpha = 0: free kills ham, meeting kills spam, and nothing is left. Laplace (additive) smoothing adds alpha to every count and alpha × (vocabulary size) to the class total: P(w | c) = (count + alpha) / (total + alpha·V). With alpha = 1, free in ham gets 1/18 = 0.0556 instead of 0, and the message becomes 57.6% ham, 42.4% spam.

Predict first. With alpha = 0, the word prize never appears in ham, and the message is prize now. What happens to the ham score?

Predict first. A word that appears in a new message but not anywhere in the training vocabulary. What should the model do?

The common mistake: what independence assumes

Chapter context

Different model families turn different notions of similarity into predictions. A geometric distance, a conditional-independence assumption and a kernel are distinct modeling decisions rather than variations of the same formula.

TRY IT YOURSELF

Part 1. Do it on the plot

Build messages from the word buttons and set alpha. Every task is checked against the real counts in the table.

smoothing alpha = 1

Click a word to add one more copy to the message. Message: (empty). Training: 4 spam and 4 ham messages, 13 spam words, 10 ham words, 8 different words.

word	in message	count in ham	count in spam	P(word \| ham)	P(word \| spam)
free	0	0	3	0.0556	0.1905
lunch	0	2	0	0.1667	0.0476
meeting	0	3	0	0.2222	0.0476
now	0	1	3	0.1111	0.1905
prize	0	0	3	0.0556	0.1905
report	0	2	0	0.1667	0.0476
today	0	2	1	0.1667	0.0952
win	0	0	3	0.0556	0.1905
prior		4 of 8 each		0.5	0.5
product		prior times the likelihoods		0.5	0.5
sum of logs		log prior plus log likelihoods		-0.6931	-0.6931

Posterior: ham 50%, spam 50%. Prediction: ham.

To do: Turn smoothing off (alpha = 0) and build a message where both classes get probability 0
To do: With alpha = 1, build a message containing free that is still classified ham
To do: With alpha = 1, build a message containing meeting that is classified spam
To do: Use the message free alone and push alpha up until spam is below 62%

Part 2. Do it in code

nb_fit(docs, labels, alpha=1.0) learns a multinomial naive Bayes model from lists of words. The model may be any object you like.
Likelihood of word w in class c: (count of w in class c + alpha) / (total word count in c + alpha * vocabulary size). Prior: share of documents in class c.
nb_scores(model, doc) returns a dict {class: log prior + sum of log likelihoods of the words}. Skip words that are not in the training vocabulary. A likelihood of exactly 0 gives a score of -inf (no crash).
nb_predict(model, doc) returns the class with the highest score. If scores are equal, return the alphabetically first class.

import math
import numpy as np

def nb_fit(docs, labels, alpha=1.0):
    # return a model (any structure you like)
    pass

def nb_scores(model, doc):
    # {class: log score}
    pass

def nb_predict(model, doc):
    pass

Ctrl/⌘ + Enter runs it

Stuck, or something not working? You can come back to it any time.

CHECK YOUR UNDERSTANDING

Does conditional independence imply features are unconditionally independent?

ANoBYes

Chapter reference: math, worked example & code

This section belongs to the whole chapter, so it is the same on every lesson in it and may cover a different lesson's topic. The code for the experiment you just ran is inside the experiment itself.

Math and notation

\|x-y\|_2^2=\sum_j(x_j-y_j)^2,\quad K(x,y)=\exp(-\gamma\|x-y\|^2),\;\gamma>0.

For SVM canonical boundary planes $w^Tx+b=\pm1$ , their separation is $2/\|w\|$ . A naive-Bayes posterior is proportional to $P(c)\prod_jP(x_j\mid c)$ .

A numerically convenient naive-Bayes decision rule is

\hat c=\arg\max_c\left[\log P(c)+\sum_j\log P(x_j\mid c)\right].

This avoids multiplying many small probabilities, but it does not remove the need to handle zero likelihoods or choose an appropriate feature distribution.

Worked example

For query [1,1], squared distances to [0,0], [2,1] and [3,3] are 2, 1 and 8. The nearest point is [2,1]. Separately, a canonical SVM with w=[3,4] has norm 5 and margin width 2/5=0.4.

Reference code

The following example uses the Python standard library and does not call a remote service.

from math import sqrt, isclose
q = [1,1]
points = [[0,0],[2,1],[3,3]]
distances = [sum((a-b)**2 for a,b in zip(q,p)) for p in points]
assert distances == [2,1,8]
assert distances.index(min(distances)) == 1
assert isclose(2/sqrt(3**2+4**2), .4)

Python examples are provided for study and local execution; this page does not execute Python.

Common mistakes

Changing feature scale can change neighbors. Kernel similarity is not automatically calibrated probability. The SVM margin formula assumes a particular normalization of the separating planes.