# Decision trees as partitioning machines to characterize their generalization properties

arXiv: https://arxiv.org/abs/2010.07374 · HTML: https://mlsanity.com/paper/2010.07374/

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 14 Oct 2020.

## Built on by (most cited first, 12 of 12)

- [An Axiomatic Theory of Provably-Fair Welfare-Centric Machine Learning](https://mlsanity.com/paper/2104.14504/) (2021)
- [Learning Prediction Intervals for Regression: Generalization and Calibration](https://mlsanity.com/paper/2102.13625/) (2021)
- [Estimating and Improving Dynamic Treatment Regimes With a Time-Varying Instrumental Variable](https://mlsanity.com/paper/2104.07822/) (2021)
- [Gradient-Boosted Decision Tree for Listwise Context Model in Multimodal Review Helpfulness Prediction](https://mlsanity.com/paper/2305.12678/) (2023)
- [There is no Double-Descent in Random Forests](https://mlsanity.com/paper/2111.04409/) (2021)
- [Learning Capacity: A Measure of the Effective Dimensionality of a Model](https://mlsanity.com/paper/2305.17332/) (2023)
- [Generalization Properties of Decision Trees on Real-valued and Categorical Features](https://mlsanity.com/paper/2210.10781/) (2022)
- [Active Learning for Decision Trees with Provable Guarantees](https://mlsanity.com/paper/2601.20775/) (2026)
- [Transfer Learning Through Conditional Quantile Matching](https://mlsanity.com/paper/2602.02358/) (2026)
- [Improving Generalization Bounds for VC Classes Using the Hypergeometric Tail Inversion](https://mlsanity.com/paper/2111.00062/) (2021)
- [Dataset Representativeness and Downstream Task Fairness](https://mlsanity.com/paper/2407.00170/) (2024)
- [Gradient boosting for extremes: sampling theory and application to insurance](https://mlsanity.com/paper/2606.14268/) (2026)

## Abstract (arXiv)

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ℓ ≥ binomdleftlfloorfracd2rightrfloor, where ℓ 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ℓ). 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.