TL;DR
This paper reveals that decision tree size often grows linearly with training data size, even when accuracy plateaus. This suggests that many data reduction techniques achieve smaller trees primarily by reducing the training set size, rather than by intelligently selecting "bad" instances. The authors propose random data reduction as a crucial baseline for evaluating more sophisticated methods.
What Problem Does This Paper Address?
Decision trees are powerful machine learning models, but their complexity (size) can be a concern. Larger trees are harder to interpret, slower to build, and can sometimes overfit the training data. Data reduction techniques aim to improve decision tree performance by removing training instances before building the tree. However, it's unclear how much of the observed tree size reduction is due to the method of selecting instances to remove versus simply reducing the number of instances used. This paper investigates this question, aiming to understand the true impact of sophisticated data reduction methods.
Methods
The core of the paper involves extensive empirical evaluation. The authors:
- Investigated the relationship between training set size and tree size/accuracy: They built decision trees using C4.5 with five different pruning algorithms (error-based, reduced error, minimum description length, cost-complexity with and without the 1SE rule) on various training set sizes. They plotted tree size and accuracy against the number of training instances.
- Performed linear regression: For points where accuracy had plateaued, they regressed tree size against training set size to quantify the linear relationship.
- Decomposed data reduction effects: For a specific technique (John's ROBUST-c4.5), they compared the tree size achieved by the method to the tree size achieved by randomly removing the same number of instances. This allowed them to isolate the effect of instance selection versus simple data reduction.
- Used cross-validation: To ensure robust estimates, they employed k-fold cross-validation (specifically 10-fold) and averaged results over multiple data permutations.
Datasets
The experiments were conducted on 19 datasets from the UC Irvine repository. The paper notes two exceptions from a previous study (John 1995): the 'crx' dataset was omitted as it was similar to 'australian', and the 'horse-colic' dataset was omitted due to ambiguity in its class label. A 'vote1' dataset was created by removing an attribute from the 'vote' dataset. No new benchmarks were introduced.
Key Insights and Ideas
- Tree size grows with data, even without accuracy gains: A striking finding is that tree size often continues to increase linearly with training set size long after classification accuracy has peaked. This indicates that many pruning methods fail to adequately limit tree growth when presented with more data, leading to overfitting.
- Random data reduction is a powerful baseline: Simply removing random instances from the training set consistently leads to smaller trees with minimal loss in accuracy. This suggests that a significant portion of the tree size reduction seen with any data reduction technique is simply due to the reduction in the number of training instances.
- Sophisticated methods might not be as "smart" as they seem: The decomposition analysis for ROBUST-c4.5 shows that a substantial part of its tree size reduction comes from simply reducing the training set size, not necessarily from intelligently identifying and removing "bad" instances. This implies that the "intelligence" of instance selection might be less impactful than initially assumed.
- Cost-complexity pruning is more robust: Among the tested pruning methods, cost-complexity pruning (both with and without the 1SE rule) was found to be less susceptible to the pathology of growing tree size without accuracy improvements.
Key Results
- For error-based pruning (EBP), on average, random data reduction achieved 38.29% smaller trees with only a -0.14% average accuracy difference across datasets where tree size and training set size had a significant relationship after accuracy peaked.
- Across 16 datasets where accuracy peaked before 100% of data was used, the average r² value was 0.90 for EBP, indicating that training set size strongly predicted tree size.
- For ROBUST-c4.5, on average, 41.67% of the decrease in tree size was attributable to simply reducing the training set size, while the remaining 58.33% was due to the method's specific instance selection strategy.
- In some cases, ROBUST-c4.5's effect was almost entirely due to training set reduction (e.g., 100% for lymphography and tic-tac-toe), while in others, it was minimal or even negative (e.g., -9.92% for hepatitis).
Limitations and Future Work
- Generalizability of ROBUST-c4.5 decomposition: The paper acknowledges that the decomposition analysis was performed for only one data reduction technique (ROBUST-c4.5). Further experiments are needed to compare other sophisticated data reduction techniques against the random data reduction baseline.
- Understanding overfitting: The paper identifies that three of the pruning methods (EBP, REP, MDL) often fail to limit tree growth appropriately as training set size increases. Future work will investigate the causes of this overfitting, with one author exploring "multiple testing in tree construction and pruning" as a potential solution.
- Beyond decision trees: The authors plan to investigate whether other model construction algorithms exhibit similar pathological relationships between model complexity and data size.
- Estimating "right" tree size: Random data reduction can be used to estimate the smallest tree size that achieves accuracy equivalent to the full dataset, providing a benchmark for the "right" tree size.
Summary updated