Source-linked AI summary
Random forests and kernel methods
Erwan Scornet
TL;DR
Random forests have strong practical performance, but important mathematical properties remain unexplained, especially for procedures depending on the whole training set. The paper slightly modifies forest procedures into KeRF kernel estimates, derives explicit forms and consistency-rate bounds, and reports favorable empirical comparisons with random forests.
Problem
Random forests’ mathematical properties remain incompletely understood, and simplified-model consistency results do not directly extend to Breiman’s data-dependent forests.
Method
The paper modifies random-forest procedures into KeRF estimates, whose kernels are forest connection functions, and analyzes selected models theoretically and empirically.
Results
The paper derives explicit KeRF expressions, proves upper bounds on their consistency rates, and finds KeRF estimates empirically as accurate as or more accurate than corresponding random-forest estimates.
Takeaways & Limitations
KeRF provides a more interpretable kernel representation of random forests that is more amenable to mathematical analysis.
Takeaways & Limitations
Controlling cell occupancy while retaining simple partition shapes is difficult: data-dependent trees complicate connection probabilities, whereas data-independent trees make cell populations hard to control.
Abstract
from arXiv · showhide
Random forests are ensemble methods which grow trees as base learners and combine their predictions by averaging. Random forests are known for their good practical performance, particularly in high dimensional set-tings. On the theoretical side, several studies highlight the potentially fruitful connection between random forests and kernel methods. In this paper, we work out in full details this connection. In particular, we show that by slightly modifying their definition, random forests can be rewrit-ten as kernel methods (called KeRF for Kernel based on Random Forests) which are more interpretable and easier to analyze. Explicit expressions of KeRF estimates for some specific random forest models are given, together with upper bounds on their rate of consistency. We also show empirically that KeRF estimates compare favourably to random forest estimates.
1 Introduction
Random forests perform well in high-dimensional settings, but their mathematical properties remain incompletely understood. This paper studies their connection to kernel methods through a modified procedure called KeRF.
- 1 Introduction: Random forests combine predictions from many randomized trees, with variants differing in how trees are built and randomness is introduced.Breiman’s forests randomize both training sets and splitting directions.
- 1 Introduction: Existing consistency results for simplified forests do not directly adapt to Breiman’s forests because their construction depends strongly on the whole training set.Later work established asymptotic normality or consistency only under appropriate assumptions.
- 1 Introduction: The paper uses the connection between forests and kernel estimates to seek a clearer understanding of random-forest mechanisms.Kernel estimates use training observations, kernel functions, and a tunable parameter.
- 1 Introduction: A slight modification rewrites random-forest procedures as KeRF estimates with explicit kernel interpretations that are more amenable to mathematical analysis.The paper also gives explicit expressions, consistency-rate upper bounds, and empirical comparisons with random-forest estimates.
- 1 Introduction: The paper develops definitions, formalizes the relation to random forests, proves consistency rates for two KeRF models, and evaluates them experimentally.Proofs are presented in a separate section after the experiments.
2 Notations and first definitions
The paper defines finite and infinite random forests and modifies their weighting into KeRF estimates. KeRF kernels are forest connection functions, representing the probability that two points share a tree cell.
- 2 Notations and first definitions: An infinite random forest estimates the regression function m(x)=E[Y|X=x] from an independent training sample using randomized regression trees.The finite forest averages predictions from M trees whose randomization is independent of the training sample.
- 2 Notations and first definitions: By the law of large numbers, the finite forest estimate converges almost surely to the infinite forest estimate.This convergence is stated pointwise for every x in the domain.
- 2 Notations and first definitions: Random-forest construction may be independent of the data, depend on predictors, or depend on the whole training set; the paper studies Breiman’s, centred, and uniform forests.Breiman’s splits minimize within-cell variances and stop when cells contain fewer than a small prescribed number of points.
- 2 Notations and first definitions: Random-forest weights divide each observation’s contribution by the number of observations in the cell containing the prediction point.This makes observations in densely populated cells contribute less than observations in sparse cells.
- 2 Notations and first definitions: KeRF estimates instead weight observations according to how often they appear in cells containing the prediction point, so empty cells do not contribute.The construction is introduced to compensate for misestimation induced by random-forest weights.
- 2 Notations and first definitions: For a finite forest, the connection function is the empirical probability that two points occupy the same cell, yielding an interpretable positive semi-definite kernel.The connection function also gives a geometrical characterization of forest cells.
- 2 Notations and first definitions: Infinite KeRF and random-forest estimates generally require Monte Carlo approximation, although centred KeRF and approximated uniform KeRF have explicit expressions.These expressions can be computed directly using the paper’s equation (7).
- 2 Notations and first definitions: For infinite discrete or continuous forests, the infinite KeRF estimate is a kernel estimate whose kernel is the connection function K_n.K_n(x,z) is the probability that x and z are connected in the infinite forest.
3 Relation between KeRF and random forests
The paper characterizes when KeRF estimates approximate random-forest estimates, showing that cell-occupancy control is central to their closeness. The relationship holds for several forest models under specific conditions, but simple partitions and controlled cell sizes are difficult to obtain simultaneously.
- Finite forest and KeRF estimates are close when the number of observations in each cell is bounded above and below.This is formalized through assumption (H1.1) and Proposition 3.
- For centred forests, choosing k = (log2 n)/3 makes centred KeRF estimates asymptotically equivalent to centred forest estimates as n →∞.The result also extends to densities bounded between positive constants, while the uniform assumption is crucial for the stated equivalence in the centred case.
- For Breiman forests, KeRF and forest estimates are equal when each cell contains exactly one point, while occupancies between 1 and 5 yield a controlled approximation.The exact equality is stated for the one-point-per-cell setting; the broader 1-to-5 setting invokes Proposition 3.
- For median forests, each cell contains the same number of points ±2, and median KeRF estimates are equivalent to median forest estimates when that occupancy grows with n.The level k must be chosen so that the lower occupancy sequence a_n tends to infinity.
- Infinite KeRF and random-forest estimates are close when cell occupancies are bounded through sequences controlling their lower and upper limits.Proposition 4 extends the finite-forest relationship to infinite forests under (H1.2).
- Controlling cell occupancy while retaining a simple partition is difficult: adaptive stopping can match estimates but complicates the connection function, whereas non-adaptive partitions complicate occupancy control.Therefore, an explicit KeRF expression does not generally provide an explicit expression for the corresponding random-forest estimate.
4 Two particular KeRF estimates
The paper analyzes centred and uniform KeRF estimates by expressing their connection functions explicitly and establishing consistency rates under stated assumptions. It also compares their theoretical and practical behavior, including computational limits and differences between the two constructions.
- General framework: Infinite KeRF estimates depend only on the forest connection function, making them more tractable than estimates tied to particular finite trees.The paper focuses on infinite forests because their expressions are more amenable to analysis and may provide better prediction accuracy than finite forests.
- Centred KeRF: Centred KeRF uses centred forest partitions and a connection function determined by the training-set size through the level parameter k.Its construction is closely related to centred forests, which approximate Breiman forests in a linear regression setting.
- Centred KeRF: Under (H2), centred KeRF is consistent when k →∞ and n/2^k →∞, with an explicit upper bound on its consistency rate.The assumptions include Gaussian noise with finite variance, uniformly distributed covariates on [0, 1]^d, and a Lipschitz regression function.
- Centred KeRF: For d ≥9, the centred KeRF upper bound is sharper than the corresponding centred random-forest bound, although it does not attain the Lipschitz minimax rate n^-2/(d+2).The paper states that simulations support better performance for centred KeRF than for centred random forests.
- Uniform KeRF: Uniform KeRF has an explicit connection-function expression, but its general connection probability depends on point positions as well as distance, complicating analysis.A translation-invariant approximation is used for uniform KeRF; simulations report similar prediction accuracy for estimates built with the two kernels.
- Uniform KeRF: Uniform KeRF is consistent under the same k and n conditions, but its rate is worse than centred KeRF’s in every dimension and does not reach the Lipschitz minimax rate.The paper also reports better performance for centred KeRF than for uniform KeRF in simulations.
5 Experiments
Experiments compare KeRF estimates with their random-forest counterparts across Breiman, uniform, and centred models, including bootstrap and finite-versus-infinite settings. KeRF accuracy is generally similar, while centred KeRF can outperform centred forests and infinite estimates are approached as the forest size grows.
- Breiman forests: Breiman KeRF estimates behave similarly to Breiman forest estimates in empirical risk, and bootstrapping does not change either algorithm’s performance.The comparison uses two regression models, with similar conclusions reported for the remaining models.
- Uniform forests: Uniform KeRF accuracy is close to uniform forest accuracy when both use complete binary trees of level k = ⌊log2 n⌋.Under this construction, each cell contains on average n/2^k ≃ 1 observation.
- Centred forests: Centred KeRF estimates are comparable to or more accurate than centred forest estimates across the reported models.The paper attributes this pattern partly to equal observation weights in KeRF, which avoid errors from unbalanced cells in non-adaptive centred forests.
- Bootstrap comparisons: Bootstrap experiments produce results similar to the corresponding non-bootstrap comparisons for KeRF and random forests.Figures 6 and 7 report the bootstrap versions for selected regression frameworks.
- Finite and infinite KeRF: Finite centred KeRF accuracy tends toward infinite centred KeRF accuracy as M tends to infinity.The same qualitative observation holds for uniform KeRF, strengthening the approximation used for infinite uniform KeRF.
- Computation: Infinite KeRF estimates are computationally burdensome, requiring thirty minutes to 3 hours in the reported examples and serving mainly as theoretical tools.The multinomial formulation limits their evaluation to low-dimensional data sets and small sample sizes.
6 Proofs
The proofs establish the forest–KeRF connection, characterize connection functions for finite and infinite forests, and derive consistency bounds for centred and uniform KeRF. They also analyze convergence of finite estimates to infinite estimates under stated assumptions.
- Approximation: For continuous random forests, the proofs establish uniform control of connection-function differences over [0, 1]^2.The argument extends to discrete random forests, completing the corresponding approximation result.
- Prediction definition: If no training point is connected to x in any tree, the KeRF prediction is set to zero by convention.The proof notes that both finite and infinite KeRF estimates then equal zero.
- Centred KeRF: The centred KeRF consistency proof controls bias for Lipschitz functions before deriving an upper bound on its convergence rate.The bias analysis is supplied by Theorem 6.1.
- Uniform KeRF: The uniform KeRF consistency proof likewise controls Lipschitz-function bias and then derives a rate bound.Theorem 6.2 provides the corresponding bias control.