Lab 08 — Naive Bayes Classifier

Overview of the lab

Bayesian statistics & Bayes' theorem
Naive Bayes classifier
Conditional independence assumption
Zero-probability problem & Laplace smoothing
Practical implementation
Gaussian Naive Bayes

Introduction to Naive Bayes

The Naive Bayes classifier is a probabilistic machine learning algorithm based on Bayes' theorem. It is called "naive" because it makes a strong assumption that all features are conditionally independent given the class label.

Where does it fit in machine learning?

Supervised learning: uses labeled training data in the format <input data, true label>.
Classification: predicts the class / category of new examples.
Probabilistic approach: unlike KNN (which uses distance), Naive Bayes uses probability theory.

Common applications

Spam email detection
Sentiment analysis
Document classification
Medical diagnosis
Real-time prediction (fast training and prediction)

Machine learning recap: data terminology

Training data: data used to train the algorithm.
Validation data: data used to tune hyperparameters.
Test data: previously unseen data used to test how well the algorithm generalizes predictions.
k-cross validation: method for finding the best results (typically k = 5 or k = 10).
Bias: the model's inability to capture the relationship between data.
Variance: difference in prediction on unseen data.

Foundation

Bayes' theorem

Bayes' theorem is the foundation of the Naive Bayes classifier. It allows us to calculate the probability of an event based on prior knowledge of conditions related to that event.

Probability basics

For two events A and B:

P(A \mid B) = \frac{P(A \cap B)}{P(B)} \qquad P(B \mid A) = \frac{P(A \cap B)}{P(A)}

From these, we get:

P(A \cap B) = P(B \mid A) \cdot P(A) = P(A \mid B) \cdot P(B)

📐 Bayes' theorem

Rearranging the equation above gives us Bayes' theorem:

\[ P(A \mid B) = \frac{P(B \mid A) \cdot P(A)}{P(B)} \]

$P(A \mid B)$ = posterior probability: probability of A given B
$P(B \mid A)$ = likelihood: probability of B given A
$P(A)$ = prior probability: probability of A
$P(B)$ = evidence: probability of B

See it with 100 emails

Let A = "the email is spam" and B = "the email contains the word free". Each envelope below is one email; the ones with a dot contain "free". Bayes' theorem just asks: of all the emails that contain "free", what fraction are spam?

Prior $P(\text{spam})$0.40 Likelihood $P(\text{free} \mid \text{spam})$0.30 $P(\text{free} \mid \text{ham})$0.05

Classifier

Naive Bayes classifier — general formula

For classes $C_1, C_2, \dots, C_K$ and attributes / features $\vec{x} = (x_1, x_2, \dots, x_n)$, Bayes' theorem gives:

P(C_i \mid x_1, x_2, \dots, x_n) = \frac{P(x_1, x_2, \dots, x_n \mid C_i) \cdot P(C_i)}{P(x_1, x_2, \dots, x_n)}, \quad i = 1, \dots, K

What does this mean? $P(C_i \mid x_1, \dots, x_n)$ represents: "Given that we observe features $x_1, x_2, \dots, x_n$, what is the probability that the example belongs to class $C_i$?"

Example: medical diagnosis

We want to diagnose whether a patient has a disease based on symptoms. Classes: $C_1$ = has disease, $C_2$ = healthy. Features: $x_1$ = fever (yes / no), $x_2$ = cough (yes / no), $x_3$ = fatigue (yes / no). For a patient with $\vec{x}$ = (fever = yes, cough = yes, fatigue = no):

$P(C_1 \mid \vec{x})$ = "what is the probability the patient has the disease, given these symptoms?"
$P(C_2 \mid \vec{x})$ = "what is the probability the patient is healthy, given these symptoms?"

We classify the patient into whichever class has the higher probability. Goal: for a new example with features $\vec{x}$, find the class $C_i$ that maximizes $P(C_i \mid \vec{x})$.

The problem

Computing $P(x_1, x_2, \dots, x_n \mid C_i)$ directly is computationally expensive: we need the joint probability of all features, which requires exponentially many combinations — for $n$ features with $d$ values each, we need $d^n$ probabilities. With 10 binary features, that is already $2^{10} = 1024$ probability values per class.

The "naive" part

The naive assumption — conditional independence

📐 Conditional independence assumption

All features are conditionally independent given the class. Mathematically, for a given class $C_i$:

\[ P(x_j \mid x_{j+1}, x_{j+2}, \dots, x_n, C_i) = P(x_j \mid C_i) \]

This means: given we know the class, knowing one feature tells us nothing about another feature.

Why is this "naive"?

This assumption is often not true in reality. In spam detection, feature 1 = the email contains "free" and feature 2 = the email contains "money" are actually correlated (they often appear together in spam), but Naive Bayes assumes they are independent given the class.

The benefit

Despite being unrealistic, the assumption allows us to decompose the joint probability:

P(x_1, x_2, \dots, x_n \mid C_i) = P(x_1 \mid C_i) \cdot P(x_2 \mid C_i) \cdots P(x_n \mid C_i) = \prod_{j=1}^{n} P(x_j \mid C_i)

This reduces the complexity from $d^n$ to just $n \cdot d$ probability values per class.

Number of features $n$10

Values per feature $d$2

Naive Bayes — final formula

Combining Bayes' theorem with the conditional independence assumption:

P(C_i \mid x_1, \dots, x_n) \propto P(C_i) \cdot \prod_{j=1}^{n} P(x_j \mid C_i)

Note: we ignore the denominator $P(x_1, \dots, x_n)$ because it is the same for all classes $C_i$, we only care about which class has the highest probability, and we can compare classes without computing it.

📐 Classification decision

To classify a new example $\vec{x} = (x_1, \dots, x_n)$, choose the class that maximizes:

\[ \hat{C} = \arg\max_{C_i} \; P(C_i) \cdot \prod_{j=1}^{n} P(x_j \mid C_i) \]

What we need to learn from the training data:

Prior probabilities $P(C_i)$ for each class — simply count: $P(C_i) = \frac{\text{count of examples in class } C_i}{\text{total count of examples}}$
Conditional probabilities $P(x_j \mid C_i)$ for each feature value given each class — count: $P(x_j \mid C_i) = \frac{\text{count of times feature } x_j \text{ appears in class } C_i}{\text{count of examples in class } C_i}$

Example: email spam classification

Classes: $C_1$ = spam, $C_2$ = not spam (ham). Features (words in the email): $x_1$ = contains "free", $x_2$ = contains "money", $x_3$ = contains "meeting". Suppose we have 100 training emails: 40 are spam and 60 are ham, so the priors are $P(\text{Spam}) = 40/100 = 0.4$ and $P(\text{Ham}) = 60/100 = 0.6$. The conditional probabilities counted from the training data:

Word	P(word \| Spam)	P(word \| Ham)
"free"	0.30	0.05
"money"	0.25	0.10
"meeting"	0.05	0.40

Classification task: a new email contains the words "free" and "money" (but not "meeting").

P(\text{Spam} \mid \text{free, money}) \propto P(\text{Spam}) \cdot P(\text{free} \mid \text{Spam}) \cdot P(\text{money} \mid \text{Spam}) = 0.4 \times 0.30 \times 0.25 = 0.03

P(\text{Ham} \mid \text{free, money}) \propto P(\text{Ham}) \cdot P(\text{free} \mid \text{Ham}) \cdot P(\text{money} \mid \text{Ham}) = 0.6 \times 0.05 \times 0.10 = 0.003

Decision: since $0.03 > 0.003$, classify as Spam ✉️.

Try it: build the email

Click the words to put them in (or take them out of) the new email. By default, as in the example above, only the words that appear in the email are multiplied. The second mode also uses the words that are missing, multiplying $1 - P(\text{word} \mid C)$ for each of them (the Bernoulli variant of Naive Bayes).

Pitfall

Zero-probability problem

What happens if a feature value never appears in the training data for a particular class? Suppose the word "discount" never appeared in any spam email in the training data: $P(\text{"discount"} \mid \text{Spam}) = 0/40 = 0$. Then

P(\text{Spam} \mid \text{contains "discount"}) \propto P(\text{Spam}) \cdot P(\text{"discount"} \mid \text{Spam}) \cdots = 0.4 \times \mathbf{0} \times \dots = \mathbf{0}

The entire probability becomes zero, regardless of the other features — this is catastrophic. It is called the zero-probability problem (or zero-frequency problem). Why is it a problem?

Lack of training data: just because we didn't see "discount" in spam during training doesn't mean it can never appear in spam.
Probability multiplication: a single zero makes the entire product zero.
Loss of information: all other features are ignored.

Solution: Laplace smoothing

Laplace smoothing (also called additive smoothing) solves the zero-probability problem by adding a small constant to all counts. Instead of

P(x_j \mid C_i) = \frac{\text{Count}(x_j, C_i)}{\text{Count}(C_i)}

we use

📐 Laplace (additive) smoothing

\[ P(x_j \mid C_i) = \frac{\text{Count}(x_j, C_i) + \alpha}{\text{Count}(C_i) + \alpha \cdot V} \]

$\alpha$ = smoothing parameter (typically $\alpha = 1$, called Laplace smoothing or add-one smoothing)
$V$ = number of different possible values for the feature (vocabulary size)
$\text{Count}(x_j, C_i)$ = number of times feature value $x_j$ appears in class $C_i$
$\text{Count}(C_i)$ = total count of all feature values in class $C_i$

Why does this work?

Guarantees non-zero probabilities: even if $\text{Count}(x_j, C_i) = 0$, we get $P(x_j \mid C_i) = \frac{\alpha}{\text{Count}(C_i) + \alpha V} > 0$.
Maintains a probability distribution: the probabilities still sum to 1.
Minimal impact on frequent features: for features that appear often, adding $\alpha$ has a negligible effect.

Example: "discount" never appeared in 40 spam emails, the vocabulary size is $V = 1000$ words, and $\alpha = 1$:

\text{without smoothing: } \frac{0}{40} = 0 \qquad \text{with Laplace smoothing: } \frac{0 + 1}{40 + 1 \times 1000} = \frac{1}{1040} \approx 0.00096

Now the probability is small but not zero.

Try it: train a spam filter

Below is a tiny training set of 11 labelled emails. The classifier counts every word per class and scores a new email with the smoothed formula above. Start with $\alpha = 0$ and the email "free money meeting": "meeting" never occurs in spam, so the spam score is 0 — however spammy "free" and "money" are. And "free" and "money" never occur in ham, so the ham score is 0 too: the classifier cannot decide at all. Then raise $\alpha$.

New email

$\alpha$0.0

Try:

Practical implementation

Two details matter when you implement Naive Bayes on real text:

Multiply small numbers → sum logarithms. An email has many words, and a product of many probabilities smaller than 1 quickly becomes too small for the computer to represent (numerical underflow). Because the logarithm is increasing, the arg max does not change, so we compare $\log P(C_i) + \sum_j \log P(x_j \mid C_i)$ instead. The spam filter above shows both.
Words never seen in training have no count in any class, so they are usually simply ignored.

naive_bayes.py Python

import math
from collections import Counter

def train(emails, labels, alpha=1.0):
    classes = set(labels)
    priors = {c: labels.count(c) / len(labels) for c in classes}
    counts = {c: Counter() for c in classes}           # word counts per class
    for text, c in zip(emails, labels):
        counts[c].update(text.lower().split())
    vocab = set(w for c in classes for w in counts[c])
    return priors, counts, vocab, alpha

def predict(model, text):
    priors, counts, vocab, alpha = model
    V = len(vocab)
    scores = {}
    for c in priors:
        total = sum(counts[c].values())
        score = math.log(priors[c])                    # log P(C)
        for w in text.lower().split():
            if w not in vocab:                         # unseen word: ignore
                continue
            p = (counts[c][w] + alpha) / (total + alpha * V)   # Laplace smoothing
            score += math.log(p)                       # + log P(word | C)
        scores[c] = score
    return max(scores, key=scores.get)

emails = ["win free money now", "meeting tomorrow at ten"]
labels = ["spam", "ham"]
model = train(emails, labels, alpha=1)
print(predict(model, "free money"))   # spam

sklearn_naive_bayes.py Python

from sklearn.feature_extraction.text import CountVectorizer
from sklearn.naive_bayes import MultinomialNB, GaussianNB

# word counts -> multinomial Naive Bayes with Laplace smoothing (alpha)
vectorizer = CountVectorizer()
X = vectorizer.fit_transform(emails)
clf = MultinomialNB(alpha=1.0).fit(X, labels)
print(clf.predict(vectorizer.transform(["free money"])))

# continuous features -> Gaussian Naive Bayes
X_num = [[35, 6], [10, 1]]   # e.g. % capital letters, number of links
gnb = GaussianNB().fit(X_num, ["spam", "ham"])
print(gnb.predict([[30, 5]]))

Advantages and disadvantages

Advantages ✅	Disadvantages ❌
Fast training and prediction: only needs to count frequencies	Naive independence assumption: assumes features are independent, which is often unrealistic
Simple to implement: easy to understand and code	Zero-frequency problem: requires smoothing techniques
Works well with high-dimensional data: scales well with the number of features	Poor probability estimates: the actual probability values can be inaccurate (though classification can still be good)
Requires a small amount of training data: can work with limited data	Sensitive to irrelevant features: irrelevant features can affect predictions
Handles missing values well: can easily skip missing features	Cannot learn feature interactions: misses relationships between features
Probabilistic predictions: provides probability estimates for classes	Continuous features: requires assumptions about the distribution (e.g., Gaussian — see below)

When to use Naive Bayes?

Good for:

Text classification (spam detection, sentiment analysis, document categorization)
Real-time prediction (very fast)
Multi-class prediction
When features are relatively independent
When you have limited training data

Not ideal for:

Problems with strong feature dependencies
When you need accurate probability estimates
Regression problems (it's a classifier)

Continuous features

Gaussian Naive Bayes

Counting works for words and other categorical features. But many features are continuous — e.g. the percentage of capital letters in an email, its length, or a patient's temperature. We cannot count how often "exactly 23.7 % capital letters" appeared in spam. Gaussian Naive Bayes instead assumes that, within each class, each feature follows a normal (Gaussian) distribution, and uses its density as $P(x_j \mid C_i)$:

📐 Gaussian likelihood

\[ P(x_j \mid C_i) = \frac{1}{\sqrt{2\pi\sigma_{ij}^2}} \exp\!\left( -\frac{(x_j - \mu_{ij})^2}{2\sigma_{ij}^2} \right) \]

$\mu_{ij}$ and $\sigma_{ij}^2$ are the mean and variance of feature $j$ among the training examples of class $C_i$.

Training no longer counts — it estimates, for every class and every feature:

\mu_{ij} = \frac{1}{N_i} \sum_{x \in C_i} x_j \qquad \sigma_{ij}^2 = \frac{1}{N_i} \sum_{x \in C_i} (x_j - \mu_{ij})^2

where $N_i$ is the number of training examples in class $C_i$. Prediction is exactly the same Naive Bayes rule, with the densities plugged in:

\hat{C} = \arg\max_{C_i} \; P(C_i) \cdot \prod_{j=1}^{n} \mathcal{N}(x_j;\, \mu_{ij}, \sigma_{ij}^2)

A density can be larger than 1 — it is not a probability. That is fine: we only compare the scores of the classes, just as before. The naive assumption still applies: each feature has its own 1-D Gaussian per class, so there is no correlation between features within a class.

Worked example: % capital letters

One continuous feature — the percentage of capital letters in an email — with the priors from the spam example, $P(\text{Spam}) = 0.4$ and $P(\text{Ham}) = 0.6$. Training values:

Class	Training values (%)	Mean $\mu$	Variance $\sigma^2$	Std. dev. $\sigma$
Spam	30, 42, 35, 28, 40	35	29.6	5.44
Ham	8, 12, 5, 15, 10	10	11.6	3.41

A new email has 20 % capital letters:

P(\text{Spam}) \cdot \mathcal{N}(20;\, 35, 29.6) = 0.4 \times 0.00164 = 0.000656

P(\text{Ham}) \cdot \mathcal{N}(20;\, 10, 11.6) = 0.6 \times 0.00157 = 0.000944

Decision: Ham, with $P(\text{Spam} \mid 20\%) = \frac{0.000656}{0.000656 + 0.000944} \approx 0.41$. The two likelihoods are almost equal — 20 % is roughly as far from both means, measured in standard deviations — so the prior tips the decision towards ham. At 25 % the spam likelihood dominates and $P(\text{Spam} \mid 25\%) \approx 0.999$.

Try it: one feature

The two curves are $P(C) \cdot \mathcal{N}(x;\, \mu, \sigma^2)$ for spam and ham from the table above; the dashed line is the posterior $P(\text{Spam} \mid x)$. Move $x$ and the prior.

% capital letters $x$20

$P(\text{Spam})$0.40

Try it: two features

Now each email has two continuous features: % capital letters and number of links. Gaussian NB fits one Gaussian per feature per class, so each class's density contours are ellipses aligned with the axes (the naive assumption: no correlation inside a class). The shading is $P(\text{Spam} \mid x)$; click anywhere to classify a new email.

Summary: key takeaways

Naive Bayes is a probabilistic classifier based on Bayes' theorem.
The "naive" assumption: all features are conditionally independent given the class. This is usually not true in reality, but it makes computation tractable and often works well in practice.
Classification formula: $\hat{C} = \arg\max_{C_i} P(C_i) \cdot \prod_{j=1}^{n} P(x_j \mid C_i)$
Training: just count frequencies — $P(C_i)$ = fraction of training examples in class $C_i$; $P(x_j \mid C_i)$ = fraction of times feature $x_j$ appears in class $C_i$. For continuous features, Gaussian Naive Bayes estimates a mean and variance instead.
Zero-probability problem: solved by Laplace smoothing, $P(x_j \mid C_i) = \frac{\text{Count}(x_j, C_i) + \alpha}{\text{Count}(C_i) + \alpha V}$.

Why Naive Bayes works despite being "naive"

Even though the independence assumption is often violated:

it simplifies computation dramatically;
the classification decision often remains correct even if the probability estimates are wrong;
it works surprisingly well in many real-world applications (especially text classification).

Test yourselfLab 08 quiz

19 auto-graded tasks, 100 points: prior, likelihood and posterior, computing class scores, the independence assumption, Laplace smoothing, Gaussian Naive Bayes and Naive Bayes vs KNN.

Start the quiz →