Naive Bayes Classifiers

Classification asks: given features $\mathbf{x} = (x_1, \dots, x_d)$, predict a label $y \in \{1, \dots, K\}$. A discriminative classifier (like logistic regression) models $P(y \mid \mathbf{x})$ directly. A generative classifier instead models the joint distribution $P(\mathbf{x}, y) = P(y)\,P(\mathbf{x}\mid y)$, and then uses Bayes' rule to obtain

The denominator $P(\mathbf{x})$ does not depend on $y$, so for classification we only need to compare numerators across classes. The hard part is modeling $P(\mathbf{x} \mid y)$: with $d$ features, even binary features require $2^d - 1$ parameters per class to specify the joint distribution exactly — infeasible for even moderate $d$. The naive Bayes assumption breaks this joint distribution into a product of per-feature conditionals:

This says: once you know the class $y$, the features are statistically independent of one another. It is called "naive" precisely because this is usually false — in a spam email, the words "free" and "prize" are correlated even conditioned on "spam" — but the assumption reduces the parameter count from exponential in $d$ to linear in $d$, and it turns parameter estimation into simple per-feature counting rather than joint density estimation. Combining the two pieces gives the Naive Bayes classification rule:

Different choices of the per-feature model $P(x_j \mid y)$ give different variants: Multinomial Naive Bayes for word counts, Bernoulli Naive Bayes for binary presence/absence features, and Gaussian Naive Bayes for continuous features modeled as $x_j \mid y \sim \mathcal{N}(\mu_{y,j}, \sigma_{y,j}^2)$. All three share the same architecture — factorized likelihood, Bayes' rule, argmax decision — differing only in the parametric family used per feature.

Training a Naive Bayes classifier is estimation, not optimization: every parameter has a closed-form maximum-likelihood estimate obtained by counting frequencies in the training set. This is a direct consequence of Maximum Likelihood and Cross-Entropy Loss: because the joint likelihood factorizes over both examples and (given $y$) over features, the log-likelihood decomposes into independent additive terms, each maximized separately. Concretely, for the class prior:

For Multinomial Naive Bayes on word-count data (vocabulary size $V$), the per-class, per-word probability is

where $\alpha > 0$ is the Laplace/Lidstone smoothing constant (typically $\alpha = 1$), added to avoid assigning zero probability to a word never seen with class $k$ during training — which would otherwise zero out the entire product for any test document containing that word. For Bernoulli Naive Bayes on binary features, $\hat{P}(x_j = 1 \mid y=k)$ is the fraction of class-$k$ training examples with feature $j$ present, again Laplace-smoothed. For Gaussian Naive Bayes, $\hat\mu_{k,j}$ and $\hat\sigma_{k,j}^2$ are the per-class sample mean and variance of feature $j$. At prediction time, we compute the (unnormalized) posterior score for each class and take the argmax. Because probabilities multiply into vanishingly small numbers for high-dimensional data (numerical underflow), all real implementations work in log-space, converting products into sums:

``` ALGORITHM: TrainNaiveBayes (Multinomial variant, word-count features) INPUT: training set {(x_i, y_i)}_{i=1..N}, x_i a length-V count vector, vocabulary size V, classes {1..K}, smoothing constant alpha > 0 OUTPUT: log-prior logP[k], log-likelihood table logL[k][w] 1. for k in 1..K: 2. N_k <- count of training examples with label k 3. logP[k] <- log(N_k / N) 4. 5. for k in 1..K: 6. total[k] <- 0 7. wordcount[k][w] <- 0 for all w in 1..V 8. for each (x_i, y_i) with y_i == k: 9. for w in 1..V: 10. wordcount[k][w] += x_i[w] 11. total[k] += x_i[w] 12. for w in 1..V: 13. logL[k][w] <- log( (wordcount[k][w] + alpha) / (total[k] + alpha * V) ) 14. return logP, logL

ALGORITHM: PredictNaiveBayes INPUT: test vector x (length-V counts), logP, logL, classes {1..K} OUTPUT: predicted class y_hat 1. for k in 1..K: 2. score[k] <- logP[k] 3. for w in 1..V: 4. if x[w] > 0: 5. score[k] <- score[k] + x[w] logL[k][w] 6. y_hat <- argmax_k score[k] 7. return y_hat ``` Line 4–5 of `PredictNaiveBayes` shows the practical shortcut: with sparse features (most word counts are zero), the inner loop touches only the nonzero entries of $x$, so prediction cost scales with the number of present* features, not the full vocabulary size $V$.

Training complexity. Let $N$ be the number of training examples, $d$ the number of nonzero features per example on average (for sparse text, $d \ll V$), and $K$ the number of classes. Training requires one pass over the data to accumulate per-class counts: $O(N \bar d)$ time, where $\bar d$ is the average number of nonzero features per example, plus $O(KV)$ to finalize the smoothed probability table. Space is $O(KV)$ for the count/probability tables. This is dramatically cheaper than iterative methods like logistic regression or SVMs, which require multiple passes over the data and gradient computations; Naive Bayes needs exactly one pass and closed-form arithmetic.

Prediction complexity. For a test example with $m$ nonzero features, scoring all $K$ classes costs $O(Km)$ time — a dot product between the sparse feature vector and each class's log-probability vector. This is independent of $V$ (vocabulary size) and $N$ (training set size), which is why Naive Bayes scales to real-time filtering of large streams.

Why maximum likelihood reduces to counting. The log-likelihood of the training data under the naive Bayes model factorizes as

Each term $P(y=k)$ and each $P(x_j \mid y=k)$ appears in disjoint groups of summands (grouped by class $k$), so maximizing $\ell(\theta)$ over all parameters simultaneously is equivalent to maximizing each group separately. For categorical/multinomial features this is a constrained optimization (probabilities sum to 1 per class), solved by Lagrange multipliers, and the solution is exactly the empirical relative frequency — hence "counting is maximum likelihood" for this model family.

Correctness of the classification rule. Given the true generative model $P(y)P(\mathbf{x}\mid y) = P(y)\prod_j P(x_j\mid y)$, the argmax rule is provably Bayes-optimal: it minimizes expected 0/1 classification loss, because $\arg\max_y P(y\mid \mathbf{x})$ is by definition the minimum-error decision when the posterior is exact. The catch is the conditional independence assumption is almost always violated in real data, so the fitted $\hat P(\mathbf{x}\mid y)$ is a misspecified approximation to the true class-conditional density. What is remarkable — and provable in certain regimes — is that Naive Bayes can still produce the correct ranking of posterior probabilities (hence the correct argmax decision) even when the estimated probabilities themselves are badly calibrated, because errors from ignoring correlations often bias all classes' scores in similar directions, preserving relative order. This explains the folklore observation that Naive Bayes classification accuracy is often much better than its probability calibration.

Tradeoffs. The independence assumption is a strong bias that trades variance for parameter efficiency: with only $O(Kd)$ parameters instead of $O(K \cdot 2^d)$, the model is far less prone to overfitting on small datasets, at the cost of being unable to represent feature interactions (e.g., "New York" as a phrase carries different information than "New" and "York" independently). Smoothing similarly trades a small bias (probabilities pulled toward uniform) for a large reduction in variance (avoiding catastrophic zero-probability failures on unseen words).

Consider a tiny spam filter trained on four short "documents" over a vocabulary of 6 words: `{free, money, meeting, report, prize, hello}`.

Step 1 — Priors. $N = 4$, $N_\text{spam} = 2$, $N_\text{ham} = 2$.

Step 2 — Word counts per class (spam docs: 1,2; ham docs: 3,4):

Total words in spam class: $2+1+3 = 6$. Total words in ham class: $2+2+1 = 5$. Vocabulary size $V=6$.

Step 3 — Smoothed likelihoods with $\alpha = 1$:

Step 4 — Classify a new document: `"free prize meeting"`. Using the multinomial log-score $\log P(k) + \sum_w \text{count}(w)\log P(w\mid k)$ (each word appears once here): Spam score:

Ham score:

Since $-5.663 > -6.788$, the classifier predicts spam — driven mainly by "prize" and "free," which are strongly associated with spam, outweighing "meeting"'s pull toward ham. Note the raw probabilities (exponentiating and normalizing) would give $P(\text{spam}\mid\mathbf{x}) \approx \frac{e^{-5.663}}{e^{-5.663}+e^{-6.788}} \approx 0.755$, illustrating that the model is fairly confident despite the ambiguous mixed content — a useful sanity check on calibration, not just the argmax decision.

The probabilistic backbone of Naive Bayes traces to Reverend Thomas Bayes, whose posthumously published theorem on inverse probability underlies the entire generative-classification framework. The "naive" independence trick that makes the method computationally tractable, however, emerged from 20th-century statistics and early machine learning, converging from two directions: statisticians studying discriminant analysis with independent features, and computer scientists building practical text classifiers where full joint modeling was computationally impossible.

Naive Bayes remains embedded in production systems precisely where speed and simplicity outweigh the cost of the independence assumption. Early spam filters (and many lightweight filters still in use) use multinomial or Bernoulli Naive Bayes over word features, because training is a single pass over millions of emails and classification of a new message takes microseconds. Sentiment analysis pipelines use it as a fast baseline before deploying heavier neural models, since it establishes an accuracy floor with almost no engineering cost. Medical diagnosis support tools use Gaussian or categorical Naive Bayes to combine independent test results (e.g., independent lab markers) into a risk estimate, valuing interpretability — each feature's contribution to the log-score is directly inspectable — over marginal accuracy gains from more complex models. In recommender systems and real-time content moderation, Naive Bayes variants serve as a cheap first-pass filter ahead of more expensive downstream models, exploiting its $O(Kd)$ prediction cost to triage traffic at scale. It also serves a pedagogical role: because its assumptions are explicit and its parameters are literally counts, it is the natural bridge from probability theory to the broader family of generative classifiers, including Linear Discriminant Analysis, which relaxes the independence assumption by modeling a full (shared) covariance structure across features while retaining the same Bayes'-rule decision framework. Understanding Naive Bayes deeply — where it succeeds despite a false assumption, and where that assumption actively hurts — is essential grounding before tackling models that attempt to capture the correlations Naive Bayes deliberately ignores.

Ask the tutor: Why can Naive Bayes still produce correct classifications even when its independence assumption is clearly violated by the data?