Naive Bayes: Algorithm Deep Dive

Overview#

Naive Bayes is the only genuinely probabilistic classifier in this supervised algorithms series — rather than finding a decision boundary geometrically, it computes actual probabilities using Bayes' theorem, under one deliberately simplifying assumption. This notebook derives Bayes' theorem from first principles, works through the full math of how class probabilities are computed and combined, walks through a complete worked example by hand, and examines precisely why the "naive" independence assumption doesn't prevent the classifier from working well in practice.

1. Deriving Bayes' Theorem#

Architecture & Data Flow
Copy
Bayes' theorem follows directly from the definition of conditional
probability. Starting from:

  P(A and B) = P(A|B) * P(B) = P(B|A) * P(A)

Rearranging the right two expressions:

  P(A|B) * P(B) = P(B|A) * P(A)

Dividing both sides by P(B):

  P(A|B) = [P(B|A) * P(A)] / P(B)

This IS Bayes' theorem. Applied to classification, with A = "class" and
B = "observed features":

  P(class | features) = [P(features | class) * P(class)] / P(features)

Architecture & Data Flow
Copy
Each term has a name:
  P(class | features)  → POSTERIOR — what we want to compute
  P(features | class)   → LIKELIHOOD — how likely these features are, given the class
  P(class)                → PRIOR — how common this class is, overall, before seeing any features
  P(features)               → EVIDENCE — how likely these features are, overall (across all classes)

2. Why the Denominator Can Be Ignored for Classification#

Architecture & Data Flow
Copy
To classify a new example, we compute P(class | features) for EVERY
possible class, and pick whichever is largest. Since P(features) — the
denominator — is the SAME for every class (it doesn't depend on which
class we're evaluating), it can be dropped entirely without changing
which class wins:

  predicted_class = argmax over classes of [P(features | class) * P(class)]

Python
CopyAsk AI
# This is why Naive Bayes implementations compute UNNORMALIZED scores
# and simply pick the largest one, rather than computing true
# probabilities that sum to 1 across classes (though predict_proba()
# does the extra normalization work when actual probability VALUES,
# not just the argmax, are needed)

3. The "Naive" Independence Assumption, Precisely#

Architecture & Data Flow
Copy
Computing P(features | class) directly, for features = (x_1, x_2, ..., x_n),
would require knowing the FULL joint probability distribution of all
features together, given the class — which requires an amount of data
that grows EXPONENTIALLY with the number of features, and is completely
impractical to estimate from any real, finite dataset.

The "naive" assumption: ASSUME every feature is conditionally
independent of every other feature, GIVEN the class:

  P(x_1, x_2, ..., x_n | class) ≈ P(x_1|class) * P(x_2|class) * ... * P(x_n|class)

This reduces the problem from estimating one impossibly complex joint
distribution to estimating n simple, independent, one-dimensional
distributions — each easily estimated from even a modest amount of data.

Python
CopyAsk AI
# Putting it together, the full Naive Bayes classification rule:
#
# predicted_class = argmax over classes of:
#     P(class) * P(x_1|class) * P(x_2|class) * ... * P(x_n|class)

4. A Complete Worked Example, By Hand#

Python
CopyAsk AI
import numpy as np

# Classic example: classify whether an email is spam based on whether it
# contains the words "free" and "meeting"
# Training data: (contains_free, contains_meeting, is_spam)
training_data = [
    (1, 0, 1), (1, 0, 1), (1, 1, 1), (0, 0, 1),   # 4 spam emails
    (0, 1, 0), (0, 1, 0), (0, 0, 0), (1, 1, 0), (0, 0, 0),   # 5 ham emails
]

spam = [d for d in training_data if d[2] == 1]
ham = [d for d in training_data if d[2] == 0]

# Step 1: Priors
p_spam = len(spam) / len(training_data)
p_ham = len(ham) / len(training_data)
print(f"P(spam) = {p_spam:.3f}, P(ham) = {p_ham:.3f}")

# Step 2: Likelihoods — P(feature | class) for each feature
p_free_given_spam = sum(d[0] for d in spam) / len(spam)
p_meeting_given_spam = sum(d[1] for d in spam) / len(spam)
p_free_given_ham = sum(d[0] for d in ham) / len(ham)
p_meeting_given_ham = sum(d[1] for d in ham) / len(ham)

print(f"P(free|spam)={p_free_given_spam:.3f}, P(meeting|spam)={p_meeting_given_spam:.3f}")
print(f"P(free|ham)={p_free_given_ham:.3f}, P(meeting|ham)={p_meeting_given_ham:.3f}")

# Step 3: Classify a NEW email that contains "free" but NOT "meeting"
new_email = (1, 0)   # contains_free=1, contains_meeting=0

score_spam = p_spam * p_free_given_spam * (1 - p_meeting_given_spam)
score_ham = p_ham * p_free_given_ham * (1 - p_meeting_given_ham)

print(f"Spam score: {score_spam:.4f}")
print(f"Ham score:  {score_ham:.4f}")
print(f"Prediction: {'spam' if score_spam > score_ham else 'ham'}")

# Normalizing to get actual probabilities (optional, for interpretation)
total = score_spam + score_ham
print(f"P(spam|email) = {score_spam/total:.3f}, P(ham|email) = {score_ham/total:.3f}")

text
Ask AICopy
P(spam) = 0.444, P(ham) = 0.556
P(free|spam)=0.750, P(meeting|spam)=0.250
P(free|ham)=0.200, P(meeting|ham)=0.400
Spam score: 0.2500
Ham score:  0.0667
Prediction: spam
P(spam|email) = 0.789, P(ham|email) = 0.211

This is literally the entire algorithm — every scikit-learn Naive Bayes variant is doing exactly this calculation, just with more sophisticated ways of estimating each P(feature | class) term depending on the feature type (continuous vs discrete vs binary).

5. The Zero-Frequency Problem and Laplace Smoothing#

Python
CopyAsk AI
# What happens if a word NEVER appeared in the training data for a given
# class? Its estimated probability would be exactly 0 — and since Naive
# Bayes MULTIPLIES probabilities together, a single zero would force the
# ENTIRE product to zero, regardless of how strong the evidence from
# every other feature is.

# Example: "lottery" never appeared in ANY spam email in training
p_lottery_given_spam = 0 / len(spam)   # exactly 0.0

# If a new spam-like email contains "lottery", the spam score becomes
# EXACTLY ZERO no matter what else it contains — clearly wrong, since
# absence of evidence during training shouldn't be treated as absolute
# proof of impossibility

Python
CopyAsk AI
def laplace_smoothed_probability(count, total, n_categories, alpha=1.0):
    """Adds a small pseudo-count (alpha) to every category, preventing
    exact zero probabilities from a feature that simply never appeared
    in the limited training sample."""
    return (count + alpha) / (total + alpha * n_categories)

# Without smoothing: exactly 0
raw = 0 / 4
# With Laplace (add-1) smoothing: small but nonzero
smoothed = laplace_smoothed_probability(count=0, total=4, n_categories=2, alpha=1.0)
print(f"Raw: {raw:.3f}, Smoothed: {smoothed:.3f}")

›Raw: 0.000, Smoothed: 0.167

Python
CopyAsk AI
from sklearn.naive_bayes import MultinomialNB

# scikit-learn applies Laplace (Lidstone) smoothing automatically via
# the alpha parameter — alpha=1.0 (the default) is standard "add-one"
# smoothing; smaller alpha trusts the raw data more, larger alpha
# smooths more aggressively toward the uniform distribution
mnb = MultinomialNB(alpha=1.0)

This is not an optional implementation detail — without smoothing, Naive Bayes would be completely unusable in practice on any real dataset with enough distinct feature values that some combination inevitably never appears in training.

6. The Three Distributional Assumptions, Mathematically#

Gaussian Naive Bayes#

Architecture & Data Flow
Copy
Assumes each continuous feature, WITHIN each class, follows a Normal
(Gaussian) distribution:

  P(x_i | class) = (1 / sqrt(2*pi*variance)) * exp(-(x_i - mean)² / (2*variance))

where mean and variance are estimated SEPARATELY for each (feature, class)
combination, directly from the training data.

Python
CopyAsk AI
import numpy as np

def gaussian_probability(x, mean, variance):
    coefficient = 1 / np.sqrt(2 * np.pi * variance)
    exponent = np.exp(-((x - mean) ** 2) / (2 * variance))
    return coefficient * exponent

# Example: a feature with mean=50, variance=100 within the "positive" class
prob_at_45 = gaussian_probability(45, mean=50, variance=100)
prob_at_90 = gaussian_probability(90, mean=50, variance=100)
print(f"P(x=45|class) = {prob_at_45:.5f}")   # relatively high — close to the mean
print(f"P(x=90|class) = {prob_at_90:.5f}")    # much lower — far from the mean

Multinomial Naive Bayes#

Architecture & Data Flow
Copy
Assumes features represent COUNTS (e.g. word frequencies in a document),
modeled with a multinomial distribution. The probability of a feature
value is estimated as a simple frequency ratio (with smoothing):

  P(word_i | class) = (count of word_i in class + alpha) /
                        (total word count in class + alpha * vocabulary_size)

Bernoulli Naive Bayes#

Architecture & Data Flow
Copy
Assumes features are BINARY (present/absent), and — critically — unlike
Multinomial NB, it explicitly models the ABSENCE of a feature as
informative too, not just its presence:

  P(x_i | class) = p^x_i * (1-p)^(1-x_i)

  where p = P(feature i is present | class), and x_i is 0 or 1

This means Bernoulli NB penalizes the ABSENCE of expected words, while
Multinomial NB simply ignores words that don't appear — a subtle but
real difference that can matter for short documents where the absence
of certain expected terms is itself informative.

Python
CopyAsk AI
from sklearn.naive_bayes import GaussianNB, MultinomialNB, BernoulliNB

# Choosing the right variant depends entirely on what the features
# actually represent — this is a modeling decision, not a hyperparameter
# to tune via cross-validation
gnb = GaussianNB()          # continuous features
mnb = MultinomialNB()        # count/frequency features
bnb = BernoulliNB()           # binary presence/absence features

7. Log-Space Computation: A Critical Implementation Detail#

Python
CopyAsk AI
# Multiplying many small probabilities together (one per feature) causes
# NUMERICAL UNDERFLOW for datasets with many features — the product can
# become smaller than the smallest number a computer can represent,
# rounding to exactly 0.0

# The standard fix: work in LOG SPACE, where multiplication becomes
# addition (much more numerically stable)

import numpy as np

probabilities = [0.001, 0.002, 0.0015, 0.003, 0.0008] * 20   # 100 small probabilities

# Naive approach: underflows to exactly 0 for enough features
naive_product = np.prod(probabilities)
print(f"Naive product: {naive_product}")   # likely 0.0 due to underflow

# Log-space approach: numerically stable
log_sum = np.sum(np.log(probabilities))
print(f"Log-space sum: {log_sum:.3f}")
print(f"Converted back: {np.exp(log_sum)}")   # only converted back at the VERY end, if needed at all

Architecture & Data Flow
Copy
predicted_class = argmax over classes of:
    log(P(class)) + sum over features of log(P(x_i | class))

This is mathematically IDENTICAL to the original multiplicative formula
(since log is a monotonically increasing function, argmax is preserved),
but numerically robust even with hundreds or thousands of features —
exactly what real text classification problems require. Every serious
Naive Bayes implementation, including scikit-learn's, works internally
in log space for this reason.

8. Why "Naive" Independence Doesn't Doom the Classifier#

text
Ask AICopy
The independence assumption is essentially always technically FALSE for
real data — in text, word co-occurrence and order clearly matter (e.g.
"not good" vs "good"), directly violating independence.

But classification only requires getting the RELATIVE ORDERING between
classes correct — not accurate absolute probability values. Even when
correlated features cause the estimated probabilities to be
systematically biased (often OVERCONFIDENT, since correlated evidence
gets "double-counted" as if it were independent), this bias frequently
affects all classes SIMILARLY enough that the class with the truly
highest probability often still comes out on top after the (flawed)
calculation.

Python
CopyAsk AI
# This means Naive Bayes's predicted PROBABILITIES (predict_proba) are
# often poorly CALIBRATED — don't trust the exact probability VALUES
# too literally — even when the actual class PREDICTIONS remain quite
# accurate

from sklearn.calibration import CalibratedClassifierCV

mnb = MultinomialNB()
calibrated_mnb = CalibratedClassifierCV(mnb, method="isotonic", cv=5)
# CalibratedClassifierCV can correct poorly-calibrated probability
# outputs after the fact, when the actual probability VALUES (not just
# the predicted class) matter for a downstream decision

Notes#

• Bayes' theorem, and by extension Naive Bayes, follows directly and rigorously from the basic definition of conditional probability — it is not a heuristic, even though the independence assumption within it is a simplification.
• The independence assumption exists purely for computational tractability — without it, estimating the required joint probability distribution would need an infeasible amount of training data.
• Laplace smoothing is not optional in practice — without it, any single unseen feature-class combination would zero out an entire class's score, regardless of all other evidence.
• Real implementations work in log space to avoid numerical underflow from multiplying many small probabilities — mathematically identical to the raw multiplicative formula, but numerically robust.
• Naive Bayes's predicted class labels tend to remain accurate even when the underlying probability values are poorly calibrated (often overconfident) due to violated independence — calibration methods can correct this when exact probability values matter.

Best Practices Checklist#

• Choose the Naive Bayes variant (Gaussian/Multinomial/Bernoulli) based on what the features actually represent, not by trial and error
• Always use Laplace/Lidstone smoothing (alpha > 0) rather than disabling it
• Don't fully trust predict_proba() output values at face value — consider calibration if exact probabilities drive downstream decisions
• Remember the independence assumption is about computational tractability, not an empirical claim that features are truly unrelated
• Use log-space reasoning to understand why Naive Bayes remains numerically stable even with hundreds of features
• Treat Naive Bayes as a fast, strong baseline for text classification specifically, given its long track record there
• Recognize that correlated features can bias probability estimates, even when final class predictions remain accurate