Why the Naive Bayes approximation is not as Naive as it appears

The Naive Bayes approximation and associated classifier is widely used in machine learning and data mining and offers very robust performance across a large spectrum of problem domains. As it depends on a very strong assumption - independence among features - this has been somewhat puzzling. Various hypotheses have been put forward to explain its success and moreover many generalizations have been proposed. In this paper we propose a set of "local" error measures - associated with the likelihood functions for particular subsets of attributes and for each class - and show explicitly how these local errors combine to give a "global" error associated to the full attribute set. By so doing we formulate a framework within which the phenomenon of error cancelation, or augmentation, can be quantitatively evaluated and its impact on classifier performance estimated and predicted a priori. These diagnostics also allow us to develop a deeper and more quantitative understanding of why the Naive Bayes approximation is so robust and under what circumstances one expects it to break down.