Probabilistic Modeling & Naive Bayes | AI & Machine Learning Engineering

While discriminative algorithms like Logistic Regression model the posterior boundary $P(y | x)$ directly, Generative Classifiers model the joint probability distribution $P(x, y) = P(x | y) P(y)$ .

By modeling how the data was generated within each target class, Bayes' theorem allows us to invert the conditional likelihoods to determine the most probable class label for novel inputs.

Linear Parameter GrowthGenerative AI

O(d)

The conditional independence assumption collapses the exponential parameter space from O(C^d) to O(d * C).

1. First-Principles Derivation of Bayes' Theorem#

To understand the mechanics of Bayesian classification, we begin with the definition of conditional probability across events $A$ and $B$ .

Architecture Diagram

Rendering diagram...

Step 1: Definition of Conditional Probability

For two events $A$ and $B$ where $P(B) > 0$ , the probability of $A$ given that $B$ has occurred is defined as:

P(A | B) = \frac{P(A \cap B)}{P(B)}

Similarly, the conditional probability of $B$ given $A$ is:

P(B | A) = \frac{P(A \cap B)}{P(A)}

Step 2: Equate the Joint Intersection

Multiply both equations by their respective denominators to isolate the joint probability $P(A \cap B)$ :

P(A \cap B) = P(A | B) P(B)

P(A \cap B) = P(B | A) P(A)

Because the joint event $A \cap B$ is symmetric, we equate both expressions:

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

Step 3: Isolate the Posterior Probability

Dividing both sides by the evidence $P(B)$ yields Bayes' Theorem:

P(A | B) = \frac{P(B | A) P(A)}{P(B)}

Step 4: Marginalize the Evidence Denominator

In classification, let $y \in \{c_1, \dots, c_K\}$ denote the target class and $x \in \mathbb{R}^d$ denote the feature vector. By the Law of Total Probability:

P(x) = \sum_{k=1}^K P(x \cap y = c_k) = \sum_{k=1}^K P(x | y = c_k) P(y = c_k)

Substituting this into Bayes' Theorem gives:

P(y = c | x) = \frac{P(x | y = c) P(y = c)}{\sum_{k=1}^K P(x | y = c_k) P(y = c_k)}

2. The Conditional Independence Assumption#

Evaluating the full joint likelihood $P(x_1, x_2, \dots, x_d | y = c)$ requires estimating interactions among all $d$ features simultaneously. If features are binary, this requires estimating $2^d - 1$ parameters per class, creating an intractable curse of dimensionality.

The Naive Bayes Assumption posits that all feature attributes are conditionally independent given the class label $y$ :

P(x_1, x_2, \dots, x_d | y = c) = \prod_{j=1}^d P(x_j | y = c)

Maximum A Posteriori (MAP) Classification Rule#

To assign a new observation $x$ to the most probable class $\hat{y}$ :

\hat{y} = \arg\max_{c \in \{1, \dots, K\}} P(y = c | x) = \arg\max_c \frac{P(y = c) \prod_{j=1}^d P(x_j | y = c)}{P(x)}

Because the denominator $P(x)$ is constant across all candidate classes $c$ , it can be dropped:

\hat{y} = \arg\max_{c \in \{1, \dots, K\}} P(y = c) \prod_{j=1}^d P(x_j | y = c)

Taking the natural logarithm transforms the product of small probabilities into a numerically stable sum of log-likelihoods:

\hat{y} = \arg\max_{c \in \{1, \dots, K\}} \left[ \ln P(y = c) + \sum_{j=1}^d \ln P(x_j | y = c) \right]

3. Likelihood Models: Gaussian Naive Bayes#

When features $x_j \in \mathbb{R}$ are continuous, we model each feature within class $c$ as a one-dimensional Gaussian normal distribution:

P(x_j | y = c) = \frac{1}{\sqrt{2\pi \sigma_{c,j}^2}} \exp\left( -\frac{(x_j - \mu_{c,j})^2}{2\sigma_{c,j}^2} \right)

Where parameters are estimated via Maximum Likelihood from training samples in class $c$ :

\mu_{c,j} = \frac{1}{N_c} \sum_{i: y_i = c} x_{i,j}, \qquad \sigma_{c,j}^2 = \frac{1}{N_c} \sum_{i: y_i = c} (x_{i,j} - \mu_{c,j})^2 + \epsilon

Log-Likelihood Expansion#

Taking the logarithm of the Gaussian density yields:

\ln P(x_j | y = c) = -\frac{1}{2} \ln(2\pi) - \frac{1}{2} \ln(\sigma_{c,j}^2) - \frac{(x_j - \mu_{c,j})^2}{2\sigma_{c,j}^2}

The constant term $-\frac{1}{2}\ln(2\pi)$ can be omitted during classification comparisons.

4. Laplace (Additive) Smoothing for Discrete Models#

In text classification using Multinomial Naive Bayes, word counts $N_{c,j}$ represent term occurrences. If a specific word never appeared in class $c$ during training, its empirical probability evaluates to zero:

\hat{\theta}_{c,j} = \frac{N_{c,j}}{N_c} = 0

A single zero probability nullifies the entire product $\prod_{j} P(x_j | y = c) = 0$ , completely blinding the model to all other strong evidentiary features.

To resolve this, we apply Laplace Smoothing ( $\alpha = 1$ ) or Lidstone Smoothing ( $0 < \alpha < 1$ ):

\hat{\theta}_{c,j} = \frac{N_{c,j} + \alpha}{N_c + \alpha \cdot |V|}

Where $|V|$ is the total vocabulary size (number of distinct features). This guarantees all probabilities remain strictly positive.

5. From-Scratch Implementation: Zero Dependencies#

The following implementations build a full Gaussian Naive Bayes classifier from scratch in Python and Rust using only built-in math and standard collections.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
import math
from typing import List, Dict, Tuple

class GaussianNaiveBayesFromScratch:
    def __init__(self, epsilon: float = 1e-9):
        self.epsilon = epsilon
        self.class_priors: Dict[int, float] = {}
        # Stores (mean, variance) per feature for each class
        self.class_stats: Dict[int, List[Tuple[float, float]]] = {}

    def fit(self, X: List[List[float]], y: List[int]) -> None:
        num_samples = len(X)
        num_features = len(X[0])
        
        # Partition data points by class label
        grouped: Dict[int, List[List[float]]] = {}
        for sample, label in zip(X, y):
            if label not in grouped:
                grouped[label] = []
            grouped[label].append(sample)

        # Estimate Gaussian parameters per class
        for label, samples in grouped.items():
            count = len(samples)
            self.class_priors[label] = count / num_samples
            
            stats = []
            for j in range(num_features):
                mean_j = sum(row[j] for row in samples) / count
                var_j = sum((row[j] - mean_j) ** 2 for row in samples) / count + self.epsilon
                stats.append((mean_j, var_j))
            self.class_stats[label] = stats

    @staticmethod
    def _calculate_gaussian_log_pdf(x: float, mean: float, var: float) -> float:
        # ln( 1 / sqrt(2 * pi * var) * exp(-(x - mean)^2 / (2 * var)) )
        # = -0.5 * ln(2 * pi * var) - ((x - mean)^2 / (2 * var))
        coeff = -0.5 * math.log(2.0 * math.pi * var)
        exponent = -((x - mean) ** 2) / (2.0 * var)
        return coeff + exponent

    def predict_single(self, sample: List[float]) -> int:
        best_label = None
        highest_log_posterior = -float("inf")

        for label, prior in self.class_priors.items():
            # Start with log prior: ln P(y = c)
            log_posterior = math.log(prior)
            
            # Accumulate sum of log likelihoods: sum ln P(x_j | y = c)
            for j, (mean_j, var_j) in enumerate(self.class_stats[label]):
                log_posterior += self._calculate_gaussian_log_pdf(sample[j], mean_j, var_j)

            if log_posterior > highest_log_posterior:
                highest_log_posterior = log_posterior
                best_label = label

        return best_label

    def predict(self, X_test: List[List[float]]) -> List[int]:
        return [self.predict_single(row) for row in X_test]

if __name__ == "__main__":
    X_train = [
        [1.2, 0.7], [0.8, 1.1], [1.5, 1.3],  # Class 0
        [5.2, 4.8], [4.9, 5.5], [6.1, 5.2]   # Class 1
    ]
    y_train = [0, 0, 0, 1, 1, 1]

    gnb = GaussianNaiveBayesFromScratch()
    gnb.fit(X_train, y_train)

    X_test = [[1.0, 1.0], [5.5, 5.0]]
    preds = gnb.predict(X_test)
    print(f"Predictions: {preds}")

6. Active Knowledge Checks#

Concept check

In Bayesian classification, what is the fundamental mathematical reason that allows practitioners to drop the denominator P(x) when computing the MAP class assignment?

Concept check

What fatal failure occurs in an un-smoothed Multinomial Naive Bayes model if a single word in a test email never appeared in the spam class training set?