Decision trees as partitioning machines to characterize their generalization properties

Jean-Samuel Leboeuf, Frédéric Leblanc, Mario Marchand

Decision trees remain a cornerstone of machine learning due to their interpretability and ease of implementation. Despite their ubiquity, the theoretical bounds governing their generalization error have historically been weak or incomplete. In the paper "Decision trees as partitioning machines to characterize their generalization properties," researchers revisit binary decision trees on real-valued features, reframing them as "partitioning machines" to derive tight complexity bounds and a more efficient pruning methodology.

The Problem: The Cost of Pruning

Decision trees are notoriously susceptible to overfitting, often memorizing training data rather than learning underlying patterns. To mitigate this, practitioners use pruning. The industry standard, Classification and Regression Trees (CART), employs cost-complexity pruning. This method relies on a hyperparameter ($\alpha$) typically tuned via cross-validation.

However, cross-validation introduces two significant bottlenecks:

  1. Computational Overhead: The model must be trained multiple times on various data subsets.
  2. Data Inefficiency: In scenarios with limited data, partitioning the set for validation further reduces the information available for training, often leading to suboptimal models.

Structural Risk Minimization (SRM) offers an alternative by pruning based on theoretical generalization bounds. However, SRM requires an accurate measure of the model's complexity, known as the Vapnik-Chervonenkis (VC) dimension. For decades, the exact VC dimension for decision trees with real-valued features remained unknown, rendering SRM-based pruning impractical for these models.

Theoretical Foundations: Partitioning Machines

The authors bridge this gap by introducing the concept of a partitioning function. Rather than counting the number of distinct functions a tree can represent, they count the number of ways a specific tree structure can partition a set of data points into disjoint leaves.

The "Stump" Formula

By mapping the problem to graph theory—specifically "Odd Graphs" and matching theory—the authors derived the exact VC dimension ($d$) for a decision stump (a tree with a single split) with $\ell$ features. It is defined as the largest integer $d$ such that:

$$2\ell \ge \binom{d}{\lfloor d/2 \rfloor}$$

This provides a much tighter and more mathematically precise result than previous heuristic estimates.

Logarithmic Complexity for Deep Trees

For more complex structures, the authors developed a recursive expression to bound the partitioning function. They proved that the VC dimension of a binary tree with $N$ internal nodes is of the order $O(N \log(N\ell))$. This confirms that while complexity grows linearly with the number of nodes, it only grows logarithmically with the number of features, providing a theoretical justification for the robustness of trees in high-dimensional spaces.

The SRM Pruning Algorithm

Leveraging these new bounds, the authors implemented a pruning algorithm based on Structural Risk Minimization. Unlike CART, which makes pruning decisions based on local subtree performance and empirical validation, this SRM algorithm calculates a theoretical penalty for the tree's global complexity. It prunes nodes that do not provide enough "accuracy profit" to justify their mathematical complexity cost.

Because this process is based on a direct formula rather than iterative testing, it eliminates the need for cross-validation entirely.

Experimental Results

The algorithm was benchmarked against CART across 19 datasets from the UCI Machine Learning Repository (e.g., Breast Cancer, Iris, Spambase). The results demonstrated significant improvements in both efficiency and performance:

  • Accuracy: The SRM-based algorithm outperformed or matched CART on 13 out of 19 datasets. On average, it provided a 2.02% mean accuracy improvement over standard CART.
  • Speed: The new pruning process was 19.5 times faster than CART on average, as it bypassed the computational burden of cross-validation loops.
  • Model Depth: Interestingly, CART tended to prune much more aggressively, often resulting in trees with three times fewer leaves. This suggests that standard cross-validation may be "over-pruning" and sacrificing accuracy for simplicity.

Limitations and Future Outlook

While the framework provides a breakthrough for real-valued features, it does not yet account for categorical features, which present different combinatorial challenges due to multi-way or binary grouping splits. Additionally, while the bounds are excellent for ranking trees during pruning, the literal numerical value of the bound ($\epsilon$) can sometimes exceed 1, making it an "uninformative" guarantee of absolute error rates.

Despite these limitations, the transition from empirical cross-validation to theoretical pruning marks a significant step forward in making decision tree training both faster and more robust.

Summary updated

Abstract

Decision trees are popular machine learning models that are simple to build and easy to interpret. Even though algorithms to learn decision trees date back to almost 50 years, key properties affecting their generalization error are still weakly bounded. Hence, we revisit binary decision trees on real-valued features from the perspective of partitions of the data. We introduce the notion of partitioning function, and we relate it to the growth function and to the VC dimension. Using this new concept, we are able to find the exact VC dimension of decision stumps, which is given by the largest integer $d$ such that $2\ell \ge \binom{d}{\left\lfloor\frac{d}{2}\right\rfloor}$, where $\ell$ is the number of real-valued features. We provide a recursive expression to bound the partitioning functions, resulting in a upper bound on the growth function of any decision tree structure. This allows us to show that the VC dimension of a binary tree structure with $N$ internal nodes is of order $N \log(N\ell)$. Finally, we elaborate a pruning algorithm based on these results that performs better than the CART algorithm on a number of datasets, with the advantage that no cross-validation is required.
BibTeX
@inproceedings{leboeuf2020decision,
  author = {Jean-Samuel Leboeuf and Frédéric Leblanc and Mario Marchand},
  title = {{Decision trees as partitioning machines to characterize their generalization properties}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2020},
  url = {https://openreview.net/forum?id=YeDnJ8JS3Tt},
}
Figure