Decision trees have been a staple of machine learning for half a century, prized for their interpretability and effectiveness on tabular data. However, they are notoriously prone to overfitting. To combat this, practitioners usually rely on pruning techniques like those found in the CART (Classification and Regression Trees) algorithm, which uses cross-validation to find the right balance between tree depth and error.
The problem? Cross-validation is computationally expensive and can be unreliable when training data is scarce. Theoretically, we could avoid cross-validation by using mathematical "generalization bounds"—guarantees on how well a model will perform on unseen data. But to use these bounds, we need a precise measure of a model's expressive power, typically quantified by the VC (Vapnik-Chervonenkis) dimension or the growth function. For decision trees with real-valued features, these properties have remained surprisingly weakly bounded or unknown—until now.
Researchers have finally cracked the exact VC dimension for decision stumps on real-valued features and provided a tighter recursive bound for general binary decision trees. By viewing trees as "partitioning machines" rather than just classifiers, they developed a pruning algorithm that is nearly 20 times faster than the industry-standard CART—and often more accurate—because it eliminates the need for cross-validation.
The "Partitioning" Perspective
The authors introduce a fundamental shift in perspective: instead of looking at how a tree labels data, they look at how it partitions it. They define a partitioning function, which counts the number of ways a tree structure can split a sample into disjoint sets. By focusing on the structure of the data split rather than the specific labels assigned to the leaves, the authors created a framework that naturally extends to multi-class problems.
Key methodological highlights include:
- Graph Theory for Stumps: The authors used graph-theoretical arguments to find the exact VC dimension for decision stumps (trees with only one split). They proved that the exact VC dimension for a decision stump on $\ell$ real-valued features is the largest integer $d$ such that $2\ell \ge \binom{d}{\lfloor d/2 \rfloor}$. This settles a long-standing gap in the literature where only lower bounds or approximations previously existed.
- Recursive Decomposition & Scaling: They developed a recursive formula that bounds the partitioning function of a complex tree by combining the partitioning functions of its left and right subtrees. They demonstrated that the VC dimension of a binary tree with $N$ internal nodes scales as $O(N \log(N \ell))$, providing a clear mathematical relationship between tree size, feature count, and generalization.
- Structural Risk Minimization (SRM): Using these new bounds, they implemented a pruning algorithm based on the Shawe-Taylor et al. (1998) framework. Instead of checking performance on a validation set, the algorithm prunes nodes by minimizing a theoretical upper bound on the true risk. While standard CART makes pruning decisions based on local subtree performance, the authors’ approach is more "global"—it considers the growth function of the entire tree structure.
Empirical Results
The authors evaluated their approach on 19 datasets from the UCI Machine Learning Repository, including well-known benchmarks like Iris, Spambase, Wine, Ionosphere, and Breast Cancer (BCWD). The selection was limited to datasets with exclusively real-valued features and 10 or fewer classes to keep the growth function calculations computationally manageable.
The empirical evaluation yielded several compelling insights:
- Superior Accuracy: The proposed pruning algorithm performed better than or similarly to CART on 16 out of the 19 datasets. On average, it provided a 2.02% accuracy gain over CART.
- Massive Speedup: Because the algorithm uses a mathematical bound instead of 10-fold cross-validation, it was 19.5 times faster on average than the CART pruning process.
- Less Aggressive Pruning: Interestingly, the authors found that CART tends to prune trees much more aggressively (resulting in trees with 3x fewer leaves) than their bound-based method. This suggests CART might sometimes "underfit" by being overly cautious.
Limitations and Future Work
While a significant theoretical leap, the current framework is strictly limited to real-valued features. Categorical features (like "Color" or "Zip Code") require a different combinatorial analysis because they can be split in multiple ways (e.g., one-vs-all, binary encoding, or multi-way splits).
Additionally, while the pruning itself is fast, calculating the growth function for trees with a very large number of classes or leaves can become computationally expensive due to the recursive nature of the formulas. Finally, like many VC-based bounds, the actual numerical value of the risk bound is often "uninformative" (greater than 1). While it works perfectly for ranking which pruned tree is best, it cannot yet be used to predict the exact error rate of a model.
The authors plan to extend this partitioning framework to categorical features in future work, potentially creating a universal theoretical foundation for all decision tree variants.
Summary updated