Why do naive Bayesian classifiers perform so well?

Question

Naive Bayes classifiers are a popular choice for classification problems. There are many reasons for this, including:

• "Zeitgeist" - widespread awareness after the success of spam filters about ten years ago
• Easy to write
• The classifier model is fast to build
• The model can be modified with new training data without having to rebuild the model

However, they are 'naive' - i.e. they assume the features are independent - this contrasts with other classifiers such as Maximum Entropy classifiers (which are slow to compute).

The independence assumption cannot usually be assumed, and in many (most?) cases, including the spam filter example, it is simply wrong.

So why does the Naive Bayes Classifier still perform very well in such applications, even when the features are not independent of each other?

Answer 1

This paper seems to prove (I can't follow the math) that bayes is good not only when features are independent, but also when dependencies of features from each other are similar between features:

In this paper, we propose a novel explanation on the superb classification performance of naive Bayes. We show that, essentially, the dependence distribution; i.e., how the local dependence of a node distributes in each class, evenly or unevenly, and how the local dependencies of all nodes work together, consistently (supporting a certain classification) or inconsistently (canceling each other out), plays a crucial role. Therefore, no matter how strong the dependences among attributes are, naive Bayes can still be optimal if the dependences distribute evenly in classes, or if the dependences cancel each other out

Answer 2

Most Machine Learning problems are easy!

See for example at John Langford's blog. What he's really saying is that ML makes problems easy, and this presents a problem for researchers in terms of whether they should try to apply methods to a wide range of simple problems or attack more difficult problems. However the by-product is that for many problems the data is Linearly Separable (or at least nearly), in which case any linear classifier will work well! It just so happens that the authors of the original spam filter paper chose to use Naive Bayes, but had they used a Perceptron, SVM, Fisher Discriminant Analysis, Logistic Regression, AdaBoost, or pretty much anything else it probably would have worked as well.

The fact that it is relatively easy to code the algorithm helps. For example to code up the SVM you either need to have a QP Solver, or you need to code up the SMO algorithm which is not a trivial task. You could of course download libsvm but in the early days that option wasn't available. However there are many other simple algorithms (including the Perceptron mentioned above) that are just as easy to code (and allows incremental updates as the question mentions).

For tough nonlinear problems methods that can deal with nonlinearites are needed of course. But even this can be a relatively simple task when Kernel Methods are employed. The question often then becomes "How do I design an effective kernel function for my data" rather than "Which classifier should I use".

Answer 3

Having used Naive Bayesian Classifiers extensively in segmentation classification tools, my experience is consistent with published papers showing NBC to be comparable in accuracy to linear discriminant and CART/CHAID when all of the predictor variables are available.

(By accuracy both "hit rate" in predicting the correct solution as the most likely one, as well as calibration, meaning a, say, 75% membership estimate is right in 70%-80% of cases.)

My two cents is that NBC works so well because:

• Inter-correlation among predictor variables is not as strong as one might think (mutual information scores of 0.05 to 0.15 are typical)
• NBC can handle discrete polytomous variables well, not requiring us to crudely dichotomize them or treat ordinal variables as cardinal.
• NBC uses all the variables simultaneously whereas CART/CHAID use just a few

And that's when all the variables are observed. What makes NBC really pull away from the pack is that it gracefully degrades when one or more predictor variables are missing or not observed. CART/CHAID and linear discriminant analysis stop flat in that case.