Introduction
Decision trees, particularly those constructed using the Classification and Regression Trees (CART) methodology, are fundamental to modern machine learning. They serve as the building blocks for powerful ensemble methods like Random Forests and Gradient Boosted Trees. Despite their widespread use, a rigorous mathematical explanation for their effectiveness—specifically how their data-dependent splitting logic reduces bias and adapts to complex structures—has remained elusive.
In the paper "Analyzing CART" (also titled "Best Split Nodes for Regression Trees"), Jason M. Klusowski provides a theoretical bridge between a tree's internal splitting mechanics and its global predictive performance. By shifting the analysis to an asymptotic framework, Klusowski demonstrates that CART is not merely a heuristic tool but a mathematically sound algorithm that naturally optimizes for signal density.
The Challenge of Data-Dependency
While practitioners have long observed that deeply grown trees exhibit remarkably small bias and high local adaptivity, proving these properties is difficult. The primary obstacle is that CART is inherently data-dependent: the algorithm's recursive partitioning of the feature space depends entirely on the specific values of the input and output data. This creates a complex, non-linear structure that resists standard statistical proofs.
Klusowski addresses this by analyzing an "oracle" CART tree in a population-level setting. This approach allows for an examination of how the algorithm would behave with infinite data, revealing the underlying dynamics of the splitting process without the noise of finite-sample fluctuations.
Theoretical Framework and Methodology
The paper introduces several key methodological innovations to characterize the behavior of CART nodes:
- Node Probability Content: The author derives an exact characterization of the likelihood of a data point falling into a specific node based on the reduction in impurity and the Partial Dependence Function.
- Node Balancedness: A new metric, $\lambda_j(t)$, is introduced to measure how evenly a split divides the data across a specific variable $X_j$ at node $t$.
- The MDI-Bias Bound: The central contribution is Theorem 1, which establishes an exponential bound relating the size of a terminal node to the Mean Decrease in Impurity (MDI) of the variables used to reach it.
Key Insights: MDI as a Measure of Granularity
One of the most significant findings is that MDI is more than just a feature importance ranking. The paper proves that MDI is a direct measure of granularity. When a variable exhibits high MDI, the tree mathematically "squeezes" the probability content of that variable's range, creating a much finer partition in the feature space.
This relationship is exponential: the probability content of a terminal subnode for a variable $X_j$ is bounded by $\exp(-\frac{\eta}{4} MDI(X_j; t))$. This explains why trees can reduce bias so rapidly as they grow deeper; they are not splitting randomly but are aggressively narrowing the window on high-signal variables.
Local Adaptivity and "Lazy" Splitting
CART demonstrates a property known as local adaptivity. In regions where the regression surface is relatively flat (low signal), the algorithm is "lazy," avoiding unnecessary splits. Conversely, in complex regions with high signal, it increases granularity. This allows trees to remain effective in high-dimensional settings where only a small subset of variables may be locally relevant, effectively bypassing the "curse of dimensionality" in sparse regions.
Furthermore, the paper provides a theoretical basis for "end-cut preference." This is the observed tendency of CART to split near the edges of a variable's range when the signal is weak, a behavior that previously lacked a rigorous explanation.
Consistency of Random Forests
By applying these individual tree bounds to ensembles, Klusowski proves the asymptotic consistency of Breiman’s Random Forests. Crucially, this proof extends to general multivariable functions. This is a major step forward, as previous consistency proofs were often limited to simpler, additive models. The research shows that the bias-reduction properties of individual CART trees, when combined with the variance-reduction of averaging, ensure that Random Forests converge to the true underlying function for a wide range of complex, non-additive data structures.
Empirical Validation
The theoretical results were validated using synthetic benchmarks and real-world datasets from the UC Irvine Machine Learning Repository, including:
- Airfoil Self-Noise and Concrete Compressive Strength.
- Friedman #1: A classic non-additive regression function used to test model adaptivity.
- Polynomial and Trigonometric functions: Used to test how trees handle varying degrees of smoothness and periodicity.
In these tests, a clear inverse relationship was observed: as MDI increased, the median length of the terminal subnodes decreased, confirming the theoretical link between impurity reduction and spatial granularity.
Conclusion and Future Directions
While this paper provides a breakthrough in understanding the bias component of CART, it primarily focuses on the asymptotic, population-level setting. Future work remains to fully bridge the gap between these "oracle" splits and the noisy splits found in finite, small datasets. Additionally, while the paper addresses "totally nonadaptive" forests (where splits are independent of training labels but based on the underlying distribution), extending these proofs to fully data-dependent forests remains a challenging frontier in machine learning theory.
Summary updated