Source-linked AI summary
Multiple decision trees
Suk Wah Kwok, Chris Carter
TL;DR
Selecting one decision tree may be suboptimal, while averaging over all possible models is computationally infeasible. The paper averages predictions from a small set of modified-ID3 decision trees and finds that structurally different trees generally improve performance over individual trees.
Problem
The paper investigates whether averaging predictions from multiple decision trees can improve on selecting a single classification model.
Method
The authors use a modified ID3 algorithm to construct a small set of high-probability decision trees and average their predictions.
Results
Using multiple trees improved performance by 3.6% for weather and 2.2% for student with unpruned trees, and by 2.9% and 4.2% with pruned trees.
Takeaways & Limitations
Averaging a small number of structurally different decision trees usually outperformed each constituent tree, including the ID3 tree.
Takeaways & Limitations
The approach is restricted to models and probabilities that facilitate the calculations because considering all models may be computationally infeasible.
Abstract
from arXiv · showhide
This paper describes experiments, on two domains, to investigate the effect of averaging over predictions of multiple decision trees, instead of using a single tree. Other authors have pointed out theoretical and commonsense reasons for preferring the multiple tree approach. Ideally, we would like to consider predictions from all trees, weighted by their probability. However, there is a vast number of different trees, and it is difficult to estimate the probability of each tree. We sidestep the estimation problem by using a modified version of the ID3 algorithm to build good trees, and average over only these trees. Our results are encouraging. For each domain, we managed to produce a small number of good trees. We find that it is best to average across sets of trees with different structure; this usually gives better performance than any of the constituent trees, including the ID3 tree.
1. Introduction
The paper contrasts selecting a single model with averaging predictions across models, aiming to retain computational feasibility while gaining benefits of model averaging. It applies this hybrid strategy to decision trees and reports improved performance using very few models.
- Many classification systems use abduction: selecting one model from a model class and using it for prediction.
- Abduction may mislead when little data provide insufficient grounds for preferring one model over others.
- Transduction would average predictions from all possible models weighted by their probabilities, but considering and estimating those models may be computationally infeasible.
- The paper uses decision trees and averages over a small number of high-probability models as a hybrid approach intended to combine benefits of transduction with complex abductive models.
- The results report improved performance with a very small number of models across a variety of domains.
2. Overview of ID3
ID3 constructs a decision tree from classified training data described by predictive attributes. The tree tests attribute values at internal nodes and assigns classes at its leaves, typically yielding a single model for future predictions.
- Model selection: ID3 is normally used to select a single model from data for predicting the classes of future data.
- Input representation: The data is represented by a fixed set of attributes chosen for their predictive relationship to the class.The example attributes include academic results, programming experience, and temperament.
- Tree construction: ID3 uses classified training data to construct a decision tree.Each internal node tests an attribute value, while each leaf is assigned a class.
I I high school maths result< 82.5%: fail (2)
The section describes how ID3 constructs decision trees and how pruning converts them into class probability trees. Pruning collapses subtrees into leaves, whose class proportions estimate class probabilities.
- Tree construction: ID3 builds trees top-down, selecting tests with maximum information gain until the training set is correctly classified.The algorithm chooses a root test first and then proceeds downward.
- Pruning: Pruning collapses subtrees into leaves and has generally been shown to improve performance.After pruning, leaves may contain training objects from different classes.
- Class probability trees: Class probability trees estimate each class probability from the proportion of training-set objects assigned to that class within a leaf.This approach is identified as a class probability tree.
3. Background theory
Because decision-tree posterior probabilities are difficult to calculate, the paper adopts a hybrid strategy: generate a few high-posterior rules and average across them. The section frames this strategy around the posterior distribution’s shape and the performance effects of combining rules.
- Motivation and Bayesian analysis: Calculating posterior probabilities for decision-tree models is difficult, particularly because choosing the prior probability is problematic.Buntine identifies difficulties in specifying a prior that reflects correlations among data and favors simple trees.
- Hybrid approach: The paper therefore follows Buntine’s hybrid approach: generate several high-posterior classification rules instead of calculating every rule’s posterior probability, then average across them.This is intended to obtain some of the averaging effect associated with transduction.
- Posterior distribution: The study examines the shape of the posterior distribution over classification rules, distinguishing a fairly flat distribution from one with a sharp peak.A flat distribution may make choosing one rule perform poorly, whereas a sharp peak may make single-rule selection adequate.
- Combining rules: It also investigates whether combining classification rules outperforms single rules and how the number of combined rules affects performance.These questions concern the effect of combining a small number of high-posterior rules.
4. Experiments
The experiments use an interactive version of ID3 to build alternative decision trees and test whether averaging comparable trees improves classification accuracy. Trees are evaluated independently and combined either by voting or by averaging class-probability estimates.
- The interactive ID3 algorithm lets the user select tests while retaining information-gain rankings for guidance.Experiments override default tests only at the top tree levels to produce substantially different trees.
- The experiments ask whether trees other than the ID3 tree can achieve competitive performance, whether averaging good trees improves accuracy, and how accuracy changes as more trees are added.
- Near-maximum information-gain tests produce trees that do not perform significantly worse than the default, and some perform better.
- Each tree independently classifies data points, after which the trees’ categorical or probability estimates are averaged.Categorical interpretation selects the class with the highest averaged estimate, called the voting method; retaining the average gives the class probability method.
- Performance is measured as percentage error for categorical results and as the Half-Brier score for probability estimates.The Half-Brier score is one-half the mean square error over a test set.
5. Results
Across the Weather and Student domains, the modified tree-building method found multiple competitive trees, with several outperforming the ID3 tree. Averaging structurally different trees generally improved performance, although adding trees beyond the optimum slightly degraded voting accuracy while probability-based error continued to decrease.
- Individual trees: The method found 8 competitive trees for Weather and 7 for Student, and ID3 was not the best tree in either domain.There were 2 better Weather trees and 4 better Student trees than ID3.
- Individual trees: Student produced a larger group of good trees because 6 or 7 attributes had good information gain near the top, versus only 2 or 3 in Weather.Among pruned trees, 4 Student trees outperformed the pruned ID3 tree, with trees 2, 3, and 5 significantly better.
- Tree combinations: Combinations of different trees outperformed combinations of similar trees with common roots or common second-level nodes, for both unpruned and pruned trees.The Weather experiments combined three trees using their individual results as probability estimates and voting to produce categorical predictions.
- Number of trees: 3.6% for Weather and 2.2% for Student were the improvements from using multiple unpruned trees.Increasing the number of trees initially improved performance, but after a few trees the error reached an optimum and then slightly increased.
6. Conclusion
The experiments tested whether averaging predictions from a limited set of good decision trees could improve classification accuracy. Across both domains, averaging structurally different trees usually outperformed each constituent tree, including ID3, although too few trees limited further investigation.
- Conclusion: The experiments used a limited form of transduction that retained only good trees because tree posterior probabilities could not be accurately calculated.This approach focused on averaging predictions from a manageable subset rather than estimating probabilities for all possible trees.
- Conclusion: Across each domain, the method produced a small number of trees with competitive size and performance relative to ID3.The resulting trees were suitable candidates for comparison and averaging.
- Conclusion: Averaging sets of different trees usually performed better than any constituent tree, including the ID3 tree.The benefit came from combining trees with different structures rather than relying on a single tree.
- Conclusion: The limited number of different trees prevented a thorough investigation of how performance changes as more trees are added.Future work should develop a tree-building algorithm that produces more good trees or investigate approximate weighting of individual trees.