Source-linked AI summary
Narrowing the Gap: Random Forests In Theory and In Practice
Misha Denil, David Matheson, Nando de Freitas
TL;DR
Random forests are highly successful but their theoretical properties remain insufficiently understood, especially for the original practical algorithm. The paper develops a tractable random regression forest, proves consistency, and compares it empirically with practical and theoretical variants. Its study identifies how design simplifications affect performance while focusing on consistency and leaving broader theoretical analyses for future work.
Problem
Theoretical properties of widely used random forests remain poorly understood, and consistency had not been established even for Breiman’s original algorithm.
Method
The paper introduces a theoretically tractable random regression forest that relaxes two prior simplifying assumptions and empirically compares it with practical and theoretical models.
Results
The proposed algorithm is consistent and achieves the closest match to practical random forests among theoretically tractable models in algorithmic similarity and empirical performance.
Takeaways & Limitations
Comparing practical and theoretical variants provides insight into how different design choices and theoretical simplifications affect performance.
Takeaways & Limitations
The paper focuses on consistency, leaving finite-sample complexity bounds, asymptotic convergence rates, and consistency beyond regression for future analysis.
Abstract
from arXiv · showhide
Despite widespread interest and practical use, the theoretical properties of random forests are still not well understood. In this paper we contribute to this understanding in two ways. We present a new theoretically tractable variant of random regression forests and prove that our algorithm is consistent. We also provide an empirical evaluation, comparing our algorithm and other theoretically tractable random forest models to the random forest algorithm used in practice. Our experiments provide insight into the relative importance of different simplifications that theoreticians have made to obtain tractable models for analysis.
1. Introduction
Random forests are widely successful, but their practical algorithms remain difficult to analyze theoretically. This paper narrows that gap by introducing a tractable variant and empirically comparing it with practical and theoretical models.
- Random forests have achieved broad success as a general-purpose classification and regression method.
- Theoretical understanding remains limited because widely used random forest algorithms are difficult to analyze, including the original variant.
- The literature has polarized between elaborate empirical extensions without guarantees and simplified theoretical models chosen for tractability.
- The paper introduces a tractable random regression forest that relaxes two simplifying assumptions from previous theoretical work.
- It empirically compares standard random forests with several theoretically analyzed models to assess the relative importance of their simplifying assumptions.
2. Related work
Prior work established consistency for several simplified or specialized forest models, while the mathematical basis of practical random forests remained incompletely understood. This paper focuses on consistency as a central unresolved property and studies models that trade realism for tractability.
- Random forests evolved into a broad framework of models applied successfully across many fields.
- The mathematical forces underlying practical random forests remain poorly understood, and early theoretical intuition was only recently formalized rigorously.
- Consistency asks whether an estimator converges to an optimal estimator as the data set grows, while convergence rates are a further theoretical interest.
- This paper focuses on consistency, which had not been established even for Breiman’s original algorithm.
- Theoretical analyses commonly study stylized algorithms because simplification provides tractability, with the intended insight extending to more sophisticated counterparts.
- Earlier work proved consistency for randomized classifiers, quantile regression forests, survival forests, and an online random forest variant.
- Biau’s analyzed model differs from Breiman’s algorithm in candidate split selection and by requiring an independent data set for leaf predictors.
3. Random Forests
Random forests combine independently trained decision trees by averaging their predictions. Their construction involves choices about splitting, leaf prediction, and randomness injection, with this paper restricting leaf predictors to simple averages.
- Random forest predictions average the outputs of several independently trained trees.
- Constructing a random tree requires choices about leaf splitting, leaf predictors, and how randomness enters the tree.
- Splits may be axis-aligned or linear, with thresholds selected randomly or by optimizing a function of the data in the leaves.
- Candidate splits can be selected uniformly at random or by optimizing purity criteria such as information gain or Gini gain.
- The common regression leaf predictor is the average response of training points in the leaf.
- This paper considers only simple averaging predictors rather than generalized leaf predictors.
- Randomness can enter through candidate dimensions, feature-combination coefficients, threshold selection, or bootstrapped or subsampled training data.
4. Algorithm
The proposed forest builds independent trees using separate structure and estimation points, restricted split searches, squared-error selection, and averaged leaf predictions. These design choices make the algorithm tractable while approximating practical random forests.
- 4. Algorithm: Each tree is constructed independently without the bootstrapping used by Breiman’s random forests.
- 4.1. Tree construction: Each tree randomly partitions the data into structure points for tree shape and estimation points for fitting leaf predictors.
- 4.1. Tree construction: The structure-estimation partition is required for consistency, while an additional ignored subset is possible but not pursued because subsampling generally hurts performance.
- 4.2. Leaf expansion: At each expansion step, the algorithm selects min(1+Poisson(λ), D) distinct candidate dimensions and searches candidate split points within them.
- 4.2. Leaf expansion: Unlike standard forests, it selects m structure points to restrict each candidate dimension’s split search range, producing approximately balanced trees.
- 4.2. Leaf expansion: Candidate split points are scored by squared-error reduction and the maximizing candidate is chosen subject to a minimum of k_n estimation points per child.
- 4.3. Prediction: For a new query point, each tree predicts from the estimation points in its containing leaf, and the forest averages the tree predictions.
5. Consistency
The paper proves consistency for its random regression forest by reducing the analysis to consistent trees and controlling their cell geometry under explicit assumptions. Averaging finitely many consistent trees preserves consistency.
- Consistency framework: The forest is treated as an empirical averaging estimator built by averaging randomized base estimators.This structure lets the proof connect forest consistency to consistency of its constituent trees.
- Consistency framework: Consistency of the trees implies consistency of the resulting empirical averaging forest.The paper states this implication as Proposition 3 and notes that the regression case is straightforward.
- Consistency framework: A finite average of copies of the tree estimator with different randomizing variables is also consistent.This extends the single-tree result to the empirical forest estimator.
- Proof strategy: The proof conditions on the structure–estimation partition, making tree shape independent of leaf predictions, then transfers conditional consistency to unconditional consistency.The transfer uses boundedness and a dominated-convergence argument.
- Main theorem: Under bounded-density and bounded-regression assumptions, consistency holds when k_n →∞ and k_n/n →0 as n →∞.The proof verifies that leaf-cell diameters shrink while the number of estimation points in the relevant cell grows.
- Geometric argument: The geometric argument bounds cell dimensions after successive splits and establishes that the number of splits tends to infinity in probability.This yields shrinking cell diameters, completing the consistency conditions.
6. Discussion
The discussion compares the paper’s model and two theoretically analyzed alternatives with Breiman’s practical random forest by varying split-point selection and data splitting. The experiments examine how these choices affect regression performance across several datasets.
- Compared models: Biau08 and Biau12 are theoretically analyzed random forest models adapted from classification to regression.Biau08 uses random leaf, dimension, and rank-based split selection, whereas Biau12 grows breadth-first with random candidate dimensions and split candidates.
- Results: Across four UCI datasets, Breiman’s algorithm outperforms the paper’s algorithm, which outperforms both Biau algorithms.Figure 2 reports mean squared error for the compared variants.
- Data splitting: Biau12 uses one shared structure–estimation partition across all trees, while the paper’s algorithm chooses the partition independently for each tree.The two partition parts serve the same structural and leaf-estimation roles in both models.
- Experimental factors: The comparison isolates two algorithmic differences: how candidate split points are chosen and whether, and how, data splitting occurs.The experiments vary these factors across several regression problems.
7. Experiments
The experiments compare the proposed forest with theoretically analyzed variants and Breiman’s algorithm on UCI regression datasets and Kinect joint prediction. Across these tasks, the proposed method generally narrows the empirical gap to Breiman’s model, while split selection and data splitting have different effects.
- Experimental design: The study compares the proposed algorithm, Biau08, Biau12, and Breiman on several regression datasets, including UCI tasks and challenging Kinect joint prediction.The experiments aim to assess the impact of simplifications used to make random forests theoretically tractable.
- UCI datasets: The UCI experiments show the performance ordering Breiman, the proposed algorithm, Biau12, then Biau08.Biau12 outperforms Biau08 except on the wine quality dataset, where the order is reversed.
- UCI datasets: Changing data splitting has little effect with sufficient data, but tree-level splitting significantly improves performance on the comparatively small Diabetes dataset.The comparison includes forest-level and tree-level splitting variants.
- UCI datasets: The gap between Biau12 and the proposed algorithm exceeds the effect of changing data splitting, implicating split selection as the larger difference between these methods.Removing data splitting makes the proposed algorithm very competitive with Breiman, indicating that splitting accounts for most of its remaining performance gap.
- UCI datasets: The relative results remain consistent across a wide range of forest sizes, although Figure 3 presents this analysis only for the CT slice dataset.The figure plots mean squared error against number of trees, with error bars showing one standard deviation over five runs.
- Kinect Pose Estimation: On Kinect joint prediction, the dominant test-error ordering is Biau08, Biau12, the proposed algorithm, then Breiman.Mean squared error is reported directly in pixel units for each joint; left-side joints are shown and right-side results are similar.
8. Conclusion
The paper narrows the gap between theoretical and practical regression forests by deriving and analyzing a new algorithm and comparing it empirically with prior theoretical variants. It proves consistency and finds that the new method is empirically closer to Breiman’s model, while emphasizing consistency as the current theoretical focus.
- The paper derives a new regression forest algorithm, proves it is consistent, and shows that its empirical performance is closer to Breiman’s model than previous theoretical variants.
- The empirical study compares the practically used algorithm with recent theoretical variants for the first time and examines how design choices and simplifications affect performance.
- The study focuses on consistency, leaving finite-sample complexity bounds, convergence rates, and consistency beyond regression as directions for further analysis.
A. Technical results
The technical results show that sufficiently deep branches contain positive-measure regions and enough estimation points with arbitrarily high probability, implying that every cell is eventually split infinitely often in probability.
- Proposition 7: Proposition 7 establishes that, for sufficiently large n, every cell is cut infinitely often in probability.Formally, if K is the root-to-leaf distance, then P(K < t) → 0 for every fixed t as n → ∞.
- Geometric control: At depth K, every cell contains a hypercube with side length δ with probability at least (2(1 −δ1/K) −1)Km.The bound assumes the same dimension is cut at every level; varying dimensions only increases the probability.
- Geometric control: Because each depth-K leaf contains a positive-measure hypercube, the minimum leaf probability p is strictly positive.The minimum is taken over finitely many leaves, each containing a set of positive measure under µX.
- Estimation-point counts: For a set with probability p, the number of estimation points is Binomial(n, p/2), since each data point becomes an estimation point with probability 1/2.Hoeffding’s inequality is then used to control the probability that this count falls below kn.
- Estimation-point counts: As n grows, the probability that every branch reaches depth K becomes arbitrarily high because leaves at that depth contain at least kn estimation points.The argument applies for any K, while kn/n → 0, so sufficiently large samples prevent premature leaf termination with high probability.