Naive Bayes

Overview

The naive Bayesian classifier is known to be optimal when attributes are independent given the class. This project explores whether other sufficient conditions for its optimality exist. Empirical results showing that it performs surprisingly well in many domains containing clear attribute dependences suggest that the answer to this question may be positive. In this project we show that, although the Bayesian classifier's probability estimates are only optimal under quadratic loss if the independence assumption holds, the classifier itself can be optimal under zero-one loss (misclassification rate) even when this assumption is violated by a wide margin. 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. This implies that the Bayesian classifier has a much greater range of applicability than previously thought. For example, naive Bayes is optimal for learning conjunctions and disjunctions, even though they violate the independence assumption. Further, studies in artificial domains show that it will often outperform more powerful classifiers for common training set sizes and numbers of attributes, even if its bias is "a priori" much less appropriate to the domain.

Publications

• Domingos and Pazzani. On the Optimality of the Simple Bayesian Classifier under Zero-One Loss. In Machine Learning. 1997.
• Domingos and Pazzani. Beyond Independence: Conditions for the Optimality of the Simple Bayesian Classifier. In Proceedings of the Thirteenth International Conference on Machine Learning (ICML). 1996