Naive Bayes and Generative Classifiers

A spam filter over a 50,000-word vocabulary faces a counting problem. Modelling the joint distribution of which words appear together, per class, needs on the order of \(2^{50{,}000}\) probabilities. Naive Bayes needs about 100,000: one per word per class. It gets there by assuming words are independent given the class, which anyone who has read an email knows is false. Filters built this way were nonetheless effective for years, and the reason they work says a lot about the difference between classifying and estimating probabilities.

The model

A generative classifier models how data arise: a class prior \(p(y)\) and a class-conditional density \(p(x \mid y)\). Prediction then goes through Bayes' rule, \(p(y \mid x) \propto p(y)\,p(x \mid y)\). Naive Bayes factorises the class-conditional over the \(D\) features:

For two classes, taking logs turns this into an additive score,

a prior log-odds plus one evidence term per feature. The per-feature distributions are chosen to match the data: Bernoulli for word presence, multinomial for word counts, Gaussian for continuous measurements. Fitting is counting. For multinomial naive Bayes with vocabulary size \(V\), the smoothed estimate of word \(w\)'s probability in class \(c\) is \((N_{wc} + \alpha)/(N_c + \alpha V)\), where \(N_{wc}\) counts occurrences of \(w\) in class \(c\) and \(N_c\) counts all words in that class. Training is one pass over the data, and the model updates online by incrementing counts.

The smoothing term \(\alpha\) is not optional. Without it, a word that never appeared in the training spam gets probability zero, its log is \(-\infty\), and one unseen word vetoes every other piece of evidence in the email.

Generative versus discriminative

Logistic regression models \(p(y \mid x)\) directly and never models \(x\) at all (logistic regression and the log-odds). Gaussian naive Bayes with class-shared variances produces exactly the same functional form, a linear log-odds, but fits its coefficients by estimating means and variances rather than by maximising conditional likelihood.

Ng and Jordan made the trade-off precise. The discriminative model reaches a lower asymptotic error, because it is not constrained by a wrong independence assumption. The generative model can approach its own higher asymptote with a number of examples logarithmic, rather than linear, in the number of features, so there are often two regimes: naive Bayes ahead with little data, logistic regression ahead with a lot. Experiments on 15 UCI datasets showed the crossover on many of them (Ng & Jordan, 2001, On Discriminative vs. Generative Classifiers, NeurIPS 14). The empirical claim has been contested: Xue and Titterington reran comparisons and argued that the two-regime pattern is less reliable than the original paper suggested (Xue & Titterington, 2008, Neural Processing Letters 28).

Generative models also have structural advantages beyond sample efficiency. A missing feature is handled by simply dropping its factor, which is exact marginalisation. New classes can be added without refitting the others.

Why a wrong model classifies well

Domingos and Pazzani showed that naive Bayes can be optimal under zero-one loss even when the independence assumption is violated by a wide margin, because classification only needs the correct class to have the highest score, not the correct score (Domingos & Pazzani, 1997, On the Optimality of the Simple Bayesian Classifier under Zero-One Loss, Machine Learning 29). Dependence distorts the magnitudes of the posterior far more often than it flips the ordering.

The magnitudes are where the damage shows. Suppose one feature carries a likelihood ratio of 3 for spam, and nine near-duplicate features (say "free", "FREE", "Free!") carry the same information. Naive Bayes counts the evidence ten times, multiplying the odds by \(3^{10} = 59{,}049\) rather than 3. The ranking of emails may survive; the probability does not. This is why naive Bayes posteriors pile up near 0 and 1.

When it breaks

Probabilities are overconfident by construction. Niculescu-Mizil and Caruana found naive Bayes pushes predictions toward 0 and 1, producing an inverted-sigmoid reliability curve, and that isotonic regression corrects it better than a sigmoid (2005, ICML). Any use of the score as a probability, such as expected cost or a risk threshold, needs recalibration.

Text violates the multinomial model in specific ways. Word counts are burstier than a multinomial allows, long documents dominate the estimates, and imbalanced classes bias the weights. Rennie and colleagues fixed each with simple transforms, including log-scaled counts, length normalisation and complement-class estimation, and reported a fast classifier competitive with support vector machines on text (Rennie et al., 2003, Tackling the Poor Assumptions of Naive Bayes Text Classifiers, ICML).

The per-feature density is another assumption. Gaussian naive Bayes on a bimodal or heavily skewed feature assigns likelihoods that bear little relation to the data. Discretising the feature or using a kernel density per class is often better than the default.

Correlated feature engineering hurts it most. Adding interaction terms, polynomial features, or several encodings of the same variable helps a discriminative model and actively damages naive Bayes, because every copy is counted as fresh evidence.