Naive Bayes Classifiers

The model applies Bayes rule after factorizing class-conditional feature likelihoods.

Everything that follows in this lesson is an argument about the third box. What the factorization costs, when it costs nothing at all, and what it quietly does to the fourth.

The model assumes features are independent of one another after the class is known. Two words can be strongly associated overall and still satisfy the modeling approximation differently within spam and non-spam classes.

Real features violate the assumption, and the classifier still wins. Domingos and Pazzani measured how often, in 1997. They ran the simple Bayesian classifier against C4.5, PEBLS and CN2 on 28 UCI datasets, 20 random 2/3–1/3 splits each. It was more accurate than C4.5 in 19 domains against 9, than PEBLS in 16 against 11, and than CN2 in 20 against 8. Average accuracy 79.1% against 77.2%, 77.6% and 76.2%, and the best average rank of all five learners at 2.43. Then they did the part that decides the question. They measured attribute dependence directly and correlated it with the classifier's accuracy advantage. The correlation was essentially nil: R² = 0.04 against C4.5, 0.0004 against PEBLS, 0.002 against CN2. The classifier was not winning because the independence assumption happened to hold. Their abstract states where the two kinds of success part company: “The region of quadratic-loss optimality of the Bayesian classifier is in fact a second-order infinitesimal fraction of the region of zero-one optimality.” Getting the class right and getting the probability right are different regions. The second is vanishingly smaller than the first.

The other half of the explanation is how little data the simplified factorization needs. Ng and Jordan proved the rate in 2001. Naive Bayes converges to its higher asymptotic error after O(log n) training examples, where logistic regression needs O(n), with n the number of features. Their abstract states the trade in one line — “while discriminative learning has lower asymptotic error, a generative classifier may also approach its (higher) asymptotic error much faster.” They confirmed the resulting two-regime crossover on 15 UCI datasets, 8 continuous and 7 discrete, averaged over 1,000 random train/test splits. Zheng and colleagues generalised the same O(log n) versus O(n) result from the binary case to the multiclass one in 2023. The naive model is not a good approximation of the world. It is a cheap one, and cheapness is worth most when labels are scarce.

The violated assumptions do cost accuracy, and most of that cost can be repaired. On the Industry Sector corpus multinomial Naive Bayes reached 0.582 accuracy. A transformed weight-normalized complement variant reached 0.923, against 0.934 for a support vector machine. On 20 Newsgroups the same three numbers were 0.848, 0.861 and 0.862. Rennie and colleagues published those figures in 2003. What closed most of the gap was not a better probability model. It was a set of corrections to the representation: weights estimated from the data outside each class, normalized document length, damped repeated terms. The authors note that the result “no longer has a generative interpretation”.

Naive Bayes is a family rather than one universal estimator. The choice between its members is measurable rather than aesthetic.

The two text members are not equally good, and the gap has a number on it. McCallum and Nigam put them against each other in 1998, on five corpora. Yahoo Science (13,589 pages, 95 classes, vocabulary 44,383), Industry Sector (6,440 pages, 71 classes, vocabulary 29,964), 20 Newsgroups (about 20,000 articles, 20 groups, vocabulary 62,258), WebKB (4,199 pages, 4 classes, vocabulary 23,830) and the Reuters-21578 ModApte split (12,902 articles, 10 most populous classes, vocabulary 19,371). Their conclusion: “The multinomial model is found to be almost uniformly better than the multi-variate Bernoulli model. In empirical results on five real-world corpora we find that the multinomial model reduces error by an average of 27%, and sometimes by more than 50%.” Picking the wrong member of the family is worth about a quarter of your errors, and sometimes half of them.

The exception is where the useful rule lives. Bernoulli sometimes won at small vocabulary sizes. So the choice is not a default but a function of how many features the representation keeps. Introduction to Information Retrieval records the same division: multinomial “can handle more” features, Bernoulli “works best with fewer”. Wang and Manning report the gap independently in 2012, where multivariate Bernoulli NB “performs up to 10% worse” than multinomial NB. The comparison below is a decision procedure, not a ranking. Match the likelihood to how the features are actually encoded, then measure the choice on your own data.

Sparse token counts align naturally with a simple generative story and fast updates. That alignment has a measured boundary rather than an open horizon.

Document length is the variable that decides it. On short snippets, multinomial Naive Bayes with bigrams scored 79.0 on RT-s, against 76.2 for a unigram SVM and 77.7 for a bigram SVM. It beat the SVM on every snippet dataset except one: “With the only exception being MPQA, MNB performed better than SVM in all cases”. Wang and Manning mapped the boundary in 2012. On full-length reviews the order reverses. On IMDB, bigram MNB scored 86.59 against 89.16 for the bigram SVM and 91.22 for their NBSVM hybrid. The authors name the cause rather than the symptom: “Compared to the excellent performance of MNB on snippet datasets, the many poor assumptions of MNB pointed out in (Rennie et al., 2003) become more crippling for these longer documents.” NBSVM was later reproduced on IMDB at 91.87% with trigrams, with Wang and Manning's 91.22% cited as the figure to beat. The same classifier that leads on a sentence trails on a review.

Without smoothing, one feature never observed in a class can assign that class zero likelihood for the entire row. Additive smoothing reserves probability mass for unseen events.

That mass has to be taken from somewhere, and the bill is itemised. Jurafsky and Martin work the arithmetic in Speech and Language Processing, on the Berkeley Restaurant Project corpus of 9,332 sentences with a vocabulary of V = 1,446. Add-one smoothing cuts the bigram count C(want to) from 608 to 238, and P(to|want) from 0.66 to 0.26 — a discount of 0.39. On the same corpus the discount for “Chinese food” is 0.10. A factor of ten apart. Their explanation: “The sharp change occurs because too much probability mass is moved to all the zeros.” The same chapter's verdict is that “Laplace smoothing does not perform well enough to be used in modern n-gram models”. Chen and Goodman had reached that verdict empirically in 1996, comparing smoothing methods across corpora, training sizes and n-gram orders: “From these graphs, we see that additive smoothing performs poorly and that methods katz and interp-held-out consistently perform well.”

Too much smoothing washes out genuine differences, and too little produces brittle estimates. The sharper point is that the discount is not applied evenly. Two estimates on one corpus were charged 0.39 and 0.10 for the same repair. Tune the strength within a valid pipeline and data regime. Then look at what it did to the specific estimates your decision depends on, rather than at the average.

Naive Bayes is fast enough to support extensive representation checks.

Each step below has a measured quantity behind it in this lesson. The variant choice was worth an average 27% reduction in error to McCallum and Nigam. The smoothing strength moved P(to|want) from 0.66 to 0.26 in one worked example. And the calibration check is where the false independence assumption becomes visible, because that is the one place the ranking metrics will not show it to you.

Several Naive Bayes variants update sufficient statistics without retaining all past rows. This makes them attractive for streams and large sparse datasets.

That regime has a canonical evaluation, and it is worth knowing what one looks like. The TREC 2005 Spam Track evaluated 53 filters on 8 corpora under a strictly online protocol. Forty-four of those filters were submitted by 12 participating groups. Messages arrive in chronological order, and the filter must classify each one before it is told the answer: “The gold standard for each message is communicated to the filter immediately following classification.” Cormack and Lynam ran the track under NIST's Text REtrieval Conference. The public corpus trec05p-1/full holds 92,189 messages: 39,399 ham and 52,790 spam, 57.3% spam.

The statistics still summarize a historical mixture. Update policies therefore need drift monitoring, decay or windows when old evidence should lose relevance. A chronological stream is exactly where that bites. Counts accumulated over 92,189 messages describe the traffic that has already arrived, and nothing in the update rule notices when the traffic changes underneath them.