TL;DR
This paper introduces the Tree Augmented Naive Bayes (TAN) classifier, a novel approach that improves upon the simplicity and robustness of naive Bayes by allowing limited correlations between features. Experiments show TAN significantly outperforms naive Bayes and other state-of-the-art classifiers like C4.5 on various benchmark datasets.
What Problem Does This Paper Address?
Supervised learning aims to build models that predict a target variable (class) given a set of input features. While the "naive Bayes" classifier, which assumes all features are independent given the class, is surprisingly effective, its strong independence assumption is often unrealistic. This leads to the question: can we build Bayesian classifiers that relax this assumption and achieve even better predictive performance? Learning unrestricted Bayesian networks is computationally intractable, so the challenge is to find a practical approach that captures useful feature dependencies without sacrificing efficiency.
Methods
The paper proposes and evaluates the Tree Augmented Naive Bayes (TAN) classifier. TAN builds upon the naive Bayes structure by adding at most one "correlation" edge between any two attributes. This means each attribute can have the class variable as a parent, plus at most one other attribute as a parent. This structure is learned efficiently using a method based on Chow and Liu's algorithm for learning maximum likelihood trees, adapted for conditional mutual information. To address potential issues with unreliable parameter estimates due to small sample sizes in certain partitions, the authors also introduce a smoothing operation for TAN models.
Datasets
The experiments were conducted on 22 datasets, primarily from the U. C. Irvine repository. Two artificial datasets ("mofn-3-7-10" and "corral") were also included. The paper notes that instances with missing values were removed, and continuous attributes were pre-discretized.
Key Insights and Ideas
- Naive Bayes' surprising success: The paper highlights that despite its unrealistic independence assumption, naive Bayes performs competitively with more complex classifiers.
- The limitation of unsupervised Bayesian network learning for classification: Learning unrestricted Bayesian networks using standard scoring metrics like MDL doesn't necessarily optimize for classification accuracy. These metrics can favor models that better represent the overall data distribution but might not accurately predict the class variable, especially when there are many attributes.
- TAN as a practical compromise: TAN offers a sweet spot by allowing limited attribute dependencies (captured by a tree structure) while maintaining computational efficiency and robustness similar to naive Bayes.
- The importance of conditional mutual information: For learning TAN structures, the paper uses conditional mutual information to measure the gain in log-likelihood when adding an attribute as a parent, given the class variable is already a parent.
- Smoothing is crucial for TAN: The smoothing operation is essential for TAN to handle potential issues with unreliable parameter estimates, leading to significantly improved performance in practice.
Key Results
- TAN classifiers consistently outperformed naive Bayes across the tested datasets.
- TAN also showed significant improvements over C4.5 and a selective naive Bayes (SNBC) approach.
- The paper provides a table (Table 1) detailing the accuracy of various classifiers (NBC, Unsup, TAN, TAN-smoothed, C4.5, SNBC) on each dataset, showing TAN-smoothed generally achieving the highest accuracies. For instance, on the "australian" dataset, TAN-smoothed achieved 86.67% accuracy compared to naive Bayes' 81.30%.
Limitations and Future Work
- Computational cost of unrestricted Bayesian networks: The paper acknowledges that learning unrestricted Bayesian networks for classification is computationally intractable.
- Modeling complex attribute correlations: While TAN captures some correlations, it might not be sufficient when higher-order conditional probabilities need to be modeled, especially with a large number of training instances. The authors suggest exploring learning unrestricted augmented naive Bayes networks, possibly using cross-validation for scoring.
- Handling missing data and continuous attributes: The current implementation does not handle missing data or continuous attributes directly, relying on preprocessing steps.
- Exploring alternative scoring metrics: The paper suggests that developing specialized scoring metrics for classification tasks could be a promising avenue.
Summary updated