Bayes' rule and Naive Bayes

Bayes' rule

How likely is A, once we know B happened? Bayes' rule turns one conditional probability into the other:

P(A | B) = P(B | A) × P(A) / P(B)

P(A) is the prior (what we believed before), and P(A | B) the posterior (what we believe after seeing B).

A disease affects 1% of people. A test finds 90% of sick people, but also says "positive" for 9% of healthy ones. You test positive. How likely are you to be sick?

p_sick = 0.01                     # prior: 1% of people are sick
p_pos_if_sick = 0.90              # the test finds 90% of sick people
p_pos_if_healthy = 0.09           # and says "positive" for 9% of healthy people

p_pos = p_pos_if_sick * p_sick + p_pos_if_healthy * (1 - p_sick)
p_sick_if_pos = p_pos_if_sick * p_sick / p_pos
print(f"P(positive) = {p_pos:.4f}")
print(f"P(sick | positive) = {p_sick_if_pos:.1%}")

Only about 9%. In 1000 people, 10 are sick and 9 of them test positive; but 990 are healthy and about 89 of them test positive too. Most positives are false alarms, because the disease is rare. Ignoring the prior like this is the base-rate fallacy, and doctors, judges and ML engineers all fall for it.

A spam filter

Naive Bayes classifies a message by Bayes' rule. For each class (spam, ham, the word for "not spam"):

P(spam | words) ∝ P(spam) × P(word₁ | spam) × P(word₂ | spam) × ...

The ∝ ("proportional to") means we skip dividing by P(words): it is the same for both classes, so it cannot change which one wins.

It is naive because it assumes the words are independent given the class, which is plainly false ("free" and "offer" tend to appear together). It works well anyway, and it is fast: training is just counting.

from math import log

training = [
    ("win money now", "spam"), ("free money offer", "spam"), ("win a free prize", "spam"),
    ("meeting at noon", "ham"), ("project meeting tomorrow", "ham"), ("lunch at noon tomorrow", "ham"),
]

counts = {"spam": {}, "ham": {}}
messages = {"spam": 0, "ham": 0}
for text, label in training:
    messages[label] += 1
    for word in text.split():
        counts[label][word] = counts[label].get(word, 0) + 1
vocabulary = {w for c in counts.values() for w in c}

def score(text, label):
    total = sum(counts[label].values())
    s = log(messages[label] / len(training))                      # the prior
    for word in text.split():
        s += log((counts[label].get(word, 0) + 1) / (total + len(vocabulary)))   # smoothed
    return s

for text in ["free money", "meeting tomorrow at noon"]:
    spam, ham = score(text, "spam"), score(text, "ham")
    print(f"{text!r}: spam {spam:.2f}, ham {ham:.2f} -> {'spam' if spam > ham else 'ham'}")

• P(word | spam) is the word's count in spam messages divided by the number of words in spam.
• Laplace smoothing: a word never seen in spam would get probability 0 and wipe out the whole product. So add 1 to every count (and the vocabulary size to the total): (count + 1) / (total + V).
• Log probabilities: multiplying hundreds of small probabilities underflows to 0.0 in floating point. Adding logarithms instead (log(a × b) = log a + log b) keeps the numbers usable.

Mark lesson complete