Naive Bayes and generative vs discriminative models

Two routes to a classifier

A discriminative model learns $p(y\mid\mathbf{x})$ — or just the boundary — directly from inputs to labels; logistic regression (3.3 Logistic regression and softmax classification) and every neural-network classifier are discriminative. A generative model learns how each class produces inputs, $p(\mathbf{x}\mid y)$, plus how common each class is, $p(y)$, and classifies by Bayes' theorem (1.7 Probability II: Bayes, independence, MLE and MAP):

The denominator $p(\mathbf{x}) = \sum_{c'} p(\mathbf{x}\mid c')p(c')$ is the same for every class, so the $\arg\max$ ignores it; you only need it when you want the actual posterior probabilities. The prior $p(y=c)=\pi_c$ is estimated by class frequencies. The hard part is $p(\mathbf{x}\mid y=c)$: a joint distribution over all $d$ features, per class.

The naive assumption

With $d$ binary features, the exact class-conditional distribution has $2^d - 1$ free parameters per class — $10^{300}$ for a 1,000-word vocabulary. Naive Bayes assumes the features are conditionally independent given the class:

reducing the count to $d$ parameters per class. The assumption is almost always false — "free" and "offer" co-occur in spam far more than independence predicts — yet the classifier often works, because it only needs the ranking of the classes to be right, not the probabilities. Dependencies tend to inflate the winning class's score and the losers' scores by similar factors, so the $\arg\max$ survives even when the posteriors are wildly over-confident (Domingos & Pazzani, 1997). This is also why Naive Bayes probabilities should never be read as calibrated (3.3 Logistic regression and softmax classification).

Three flavours

Multinomial Naive Bayes with word counts is the classic text classifier and the one we will compute by hand. Gaussian Naive Bayes is a diagonal-covariance special case of Gaussian discriminant analysis (GDA); with a shared covariance across classes, GDA's log-odds are linear in $\mathbf{x}$ — the same functional form as logistic regression, reached by a different route.

Smoothing and logs

A word never seen in spam during training has $\theta_{\text{spam},j}=0$, and one zero factor annihilates the whole product no matter how spammy the rest of the message is. Laplace (add-$\alpha$) smoothing pretends every word was seen $\alpha$ extra times in every class:

with $V$ the vocabulary size and $\alpha=1$ the default ($\alpha<1$ often works better; tune it by cross-validation, 3.5 Evaluating models: metrics, validation and the bias–variance trade-off). The same trick, under the name add-$k$ smoothing, rescues n-gram language models (6.2 Classical NLP and n-gram language models). Products of hundreds of probabilities underflow to zero in floating point, so compute everything in log space:

That expression is linear in the feature counts $x_j$ with weights $\log\hat\theta_{cj}$ and bias $\log\pi_c$ — Naive Bayes is a linear classifier whose weights are set by counting rather than by gradient descent (3.3 Logistic regression and softmax classification). To recover posteriors, exponentiate after subtracting the maximum log-score (the log-sum-exp trick of 2.2 NumPy and vectorized thinking).

Worked example: a five-word spam filter

Vocabulary $V=5$: {free, win, meeting, report, the}. Training data: 5 spam documents with 10 tokens in total (free 4, win 3, the 3) and 5 ham documents with 10 tokens (meeting 4, report 3, the 3). Priors $\pi_{\text{spam}}=\pi_{\text{ham}}=0.5$. With $\alpha=1$, every estimate is $(N_{cj}+1)/(10+5)$:

Classify the message "free win meeting":

Posterior $p(\text{spam}\mid\mathbf{x}) = 10/(10+2.5) = 0.8$. In log space: $\log\text{score}_{\text{spam}} = \ln 0.5 + \ln\frac{5}{15}+\ln\frac{4}{15}+\ln\frac{1}{15}\approx -5.82$, $\log\text{score}_{\text{ham}}\approx -7.21$; the difference $1.39 = \ln 4$ matches the 4:1 odds. Without smoothing, $\hat\theta_{\text{spam},\text{meeting}}=0$ would have forced the spam score to zero and the message to ham on the strength of one word — the failure smoothing exists to prevent.

import numpy as np
class MultinomialNB:
    def fit(self, X, y, alpha=1.0):               # X: (n, V) counts, y: (n,) ints
        self.classes = np.unique(y)
        self.log_prior = np.log(np.array([(y == c).mean() for c in self.classes]))
        counts = np.stack([X[y == c].sum(0) for c in self.classes])      # (C, V)
        self.log_theta = np.log((counts + alpha) / (counts.sum(1, keepdims=True) + alpha * X.shape[1]))
        return self
    def predict_log_proba(self, X):
        s = self.log_prior + X @ self.log_theta.T                         # (n, C) — linear in counts
        return s - np.logaddexp.reduce(s, axis=1, keepdims=True)         # normalize in log space

Generative versus discriminative, precisely

Ng and Jordan (2001) made the middle rows precise: Naive Bayes converges to its asymptotic error with a number of examples logarithmic in $d$, logistic regression needs linearly many — so Naive Bayes often wins with little data and loses with a lot. The practical rule: a small labelled set with many features (early-stage text classification) favours Naive Bayes; abundant data favours discriminative models. Naive Bayes is also an excellent baseline: if a neural network cannot beat counting words, something is wrong with the pipeline (3.1 What is learning? ERM, generalization and the ML workflow).

Why "generative AI" is the same word

A language model is a generative model of text: it defines $p(x_1,\dots,x_T)$ over token sequences and can sample from it (6.2 Classical NLP and n-gram language models, 7.6 Decoder-only: GPT and autoregressive generation). Naive Bayes, n-gram models and GPT are on one continuum of increasingly expressive $p(\mathbf{x})$: the multinomial model treats a document as a bag of independent draws, an n-gram model conditions each token on the previous $n-1$, a transformer conditions on everything. Smoothing, log-space computation and perplexity all start here. And the generative route to classification survives at the frontier: zero-shot classification by comparing $p(\text{text}\mid\text{"this is about sports"})$ across candidate labels is Bayes' rule with a language model as the likelihood.

Where this shows up later

• Add-$k$ smoothing, log-space scoring and perplexity reappear for n-gram language models — 6.2 Classical NLP and n-gram language models; "generative model of text" is the definition of an LLM — 7.6 Decoder-only: GPT and autoregressive generation, 8.1 The LLM lifecycle and model landscape.
• Gaussian class-conditionals with shared covariance give linear boundaries — the same form as 3.3 Logistic regression and softmax classification — and relate to LDA, a cousin of PCA — 3.12 Dimensionality reduction: PCA, t-SNE and UMAP.
• Generative modelling of $p(\mathbf{x})$ becomes VAEs, GANs and diffusion — 8.8 Generative models I: VAEs and GANs, 8.9 Generative models II: Diffusion and flow matching; the Bayesian classifier idea underlies classifier guidance in diffusion — 8.9 Generative models II: Diffusion and flow matching.
• Naive Bayes as a counting baseline is the first model to try in the tabular and text projects — 3.14 Project: end-to-end tabular ML with scikit-learn.