TL;DR
This paper presents an efficient algorithm for computing Bayes optimal predictions using decision trees, overcoming the computational intractability that previously limited its practical application. By reformulating the problem as finding weighted rules derived from frequent itemsets, they enable exact Bayes optimal classification, demonstrating its superiority over MAP-based approaches in experiments.
What Problem Does This Paper Address?
The paper tackles the challenge of achieving truly optimal classification using decision trees. While the Bayesian approach suggests averaging predictions across all possible trees (Bayes optimal classification) is theoretically superior to selecting a single best tree (Maximum A Posteriori or MAP), this averaging has been computationally prohibitive. Previous work claimed that ensembles of decision trees, even when weighted by posterior probabilities, might not outperform single trees due to the dominance of overfitted models. However, this claim couldn't be rigorously tested due to the impracticality of exact Bayes optimal prediction. This paper aims to bridge this gap by providing an efficient algorithm to compute exact Bayes optimal predictions, allowing for a fair comparison and investigation of the benefits of Bayesian averaging in practice.
Methods
The core contribution is an algorithm that efficiently computes Bayes optimal predictions by transforming the problem into finding weighted rules. This is achieved by:
- Reformulating Bayes Optimal Prediction: The paper shows how to express Bayes optimal prediction as a sum over all possible decision trees and their parameters.
- Connecting to Itemset Mining: They leverage the link between decision tree paths and itemsets, a concept from data mining. This allows them to represent tree structures and paths as itemsets.
- Dynamic Programming on Itemset Lattices: The algorithm uses a two-phase dynamic programming approach (bottom-up and top-down) on an itemset lattice. This efficiently computes the necessary weights for the rules.
- Weighted Rule-Based Classifier: The final classifier is a set of rules (itemsets) with associated weights, where the prediction for a new example is determined by a weighted vote of these rules. This approach is computationally feasible, with a complexity that is linear in the size of the itemset lattice.
Datasets
The paper evaluates its approach on two types of data:
- Artificial Data: Generated data was used to test the influence of priors and the ability of the Bayes optimal classifier to recognize when an ensemble of trees is superior.
- UCI Datasets: Standard benchmark datasets from the UCI repository were used for evaluation, employing ten-fold cross-validation. Numeric attributes were discretized into equifrequency bins (typically 4 bins).
Key Insights and Ideas
- Exact Bayes Optimal Classification is Feasible: The most significant insight is that exact Bayes optimal classification, previously considered intractable, can be computed efficiently by reformulating it as a weighted rule-based classification problem derived from itemset mining.
- Bayes Optimal Outperforms MAP: Experiments consistently show that the Bayes optimal approach is significantly more accurate than the MAP approach, especially when hard constraints are relaxed.
- Priors Matter, But Constraints Can Dominate: The choice of prior (e.g., favoring smaller trees) has an impact, but strong hard constraints (like minimum leaf size or maximum depth) can significantly influence the results, sometimes making the optimal and MAP approaches perform similarly.
- Interpretability Through Rules: The weighted rule-based representation offers a degree of interpretability, allowing one to identify the itemsets (rules) that contribute most to a prediction.
Key Results
- Accuracy Improvement: The Bayes optimal classifier consistently outperformed the MAP classifier across various datasets, with significant differences observed in many cases.
- Efficiency: The proposed algorithm allows for exact Bayes optimal prediction without significantly increasing the complexity of building the underlying itemset lattice, making it practical.
- Prior Influence: Experiments suggest that a uniform prior might perform slightly better than a size-biased prior in the Bayes optimal setting, though the differences are often not significant.
- Constraint Impact: Hard constraints can make the search infeasible, and when they are applied, the Bayes optimal and MAP approaches can yield similar results.
Limitations and Future Work
- Computational Complexity: While efficient, the algorithm's complexity is still exponential in the number of attributes, limiting its direct application to datasets with a very large number of features.
- Discretization: The need to discretize numeric attributes can influence performance, and the paper notes that different discretization strategies might yield varying results.
- Future Work: The authors suggest exploring more sophisticated priors and investigating the impact of different discretization strategies. They also implicitly point towards further research in understanding the trade-offs between constraint tightness and computational feasibility.
Summary updated