38
$\begingroup$

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?

$\endgroup$
23
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ Qualitatively, that makes sense. Dependent features are going to result in weighting - so an even distribution or a distribution that cancels out, will cancel this weighting. However, "lop-sided" dependencies are probably going to perform poorly still? I guess for the spam example, we should expect a lot of dependencies for +spam features, but not necessarily -spam features in the general case. However, a person might receive lots of legitimate email on a specific topic, so in that case there would be a lot of dependent features - which would balance the +spam features. $\endgroup$ – winwaed Feb 8 '12 at 21:04
  • 3
    $\begingroup$ I also recommend this paper: cs.stanford.edu/people/ang/papers/… $\endgroup$ – Dov Feb 8 '12 at 21:16
25
$\begingroup$

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".

$\endgroup$
  • $\begingroup$ I think "easy" is perhaps relative, but yes spam classification is 'easier' than I think most people assumed 12 years or so ago. Kernel Methods might be an approach to producing a fast and simple classifier, but "How do I design an effective kernel function for my data" seems like some of the machine learning becomes "human learning" (ie. finding better understanding of the data and its inter-relationships)? $\endgroup$ – winwaed Feb 9 '12 at 15:09
  • 1
    $\begingroup$ Yes it is relative, and also there are a lot of problems, so there are still plenty of hard ones out there! And I think the boundary between ML and human learning is always blurry ... if you're creating some super-fancy probabilistic model you're doing the same thing. The good old NFLT tells us that one method can't solve all problems, however intricate that method is, so we'll always need humans to design models/kernels/algorithms or whatever is needed to get more out of your data. $\endgroup$ – tdc Feb 9 '12 at 15:21
  • $\begingroup$ true - definitely a blurry line! $\endgroup$ – winwaed Feb 9 '12 at 15:26
  • 1
    $\begingroup$ Why the downvote? Care to comment? $\endgroup$ – tdc Nov 19 '14 at 16:19
7
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.