A Fundamental Issue of Naive Bayes

Naive Bayes is one of the most efficient and effective inductive learning algorithms for machine learning and data mining. But the conditional independence assumption on which it is based, is rarely true in real-world applications. Researchers extended naive Bayes to represent dependence explicitly, and proposed related learning algorithms based on dependence. In this paper, we argue that, from the classification point of view, dependence distribution plays a crucial role, rather than dependence. We propose a novel explanation on the superb classification performance of naive Bayes. To verify our idea, we design and conduct experiments by extending the Chow-Liu algorithm to use the dependence distribution to construct TAN, instead of using mutual information that only reflects the dependencies among attributes. The empirical results provide evidences to support our new explanation