Improving Random Forests by Smoothing

Technical Summary: Improving Random Forests by Smoothing

Problem Statement
Random forest regression is a robust non-parametric method that adapts to local data characteristics through data-driven partitioning. However, its predictions are inherently piecewise constant, resulting in discontinuities at partition boundaries. This lack of smoothness is particularly problematic in small data regimes, where the inability to share information across the input space can lead to suboptimal performance. While classical smoothing methods (e.g., kernel estimators) and soft-tree variants exist, they often struggle with high-dimensional scalability, increased computational complexity, or a loss of the efficient tree-growing algorithms that make random forests attractive. The core challenge is to introduce smoothness and differentiability to random forest predictions without sacrificing their spatial adaptivity or computational efficiency.

Methodology
The authors propose a post-learning, kernel-based smoothing mechanism that operates on the output of a trained random forest rather than altering the tree construction process itself.

1. Probabilistic Smoothing: The method defines a smoothed prediction $\tilde{f}(x_0)$ as the expectation of the original piecewise constant prediction function $f(z)$ over a latent variable $z$ distributed according to a probability kernel $k(\cdot | x_0, \lambda)$. Mathematically, $\tilde{f}(x_0) = \mathbb{E}_{z \sim k}[f(z)]$.
2. Piecewise Constant Implementation: For decision trees and forests, where the domain is partitioned into axis-parallel hyper-rectangles, this expectation simplifies to a weighted sum of the constant values in each region. The weights are the probabilities that the latent variable falls into each region, computed efficiently using the cumulative distribution functions (CDFs) of the chosen kernel.
3. Kernel Selection: The authors utilize product kernels, specifically the Gaussian and the hyperbolic secant (Hypsec) distributions. These are chosen to ensure the resulting prediction function is differentiable everywhere. The hyperbolic secant is noted for its exponential tail decay, which mimics the asymptotic behavior of the Laplace distribution derived from the theoretical analysis of tree split-point variability.
4. Theoretical Justification: The paper demonstrates that this smoothing procedure can be interpreted as capturing the variability or uncertainty in tree cut points under resampling of the training inputs. Specifically, the limiting distribution of a tree's break-point estimate under resampling follows a Laplace distribution; the proposed smoothing mimics this by convolving the prediction with a kernel that approximates this variability.
5. Ensemble Application: Since random forests are additive ensembles, the smoothing operator (being linear) can be applied to individual trees and then averaged, avoiding the computational intractability of smoothing the exponentially complex region structure of the full ensemble.
6. Model Selection: The smoothing parameters (scale $\lambda$) and affine re-calibration parameters ($\beta_0, \beta_1$) are selected by minimizing the Out-of-Bag (OOB) loss. The authors employ gradient-based optimization (e.g., L-BFGS, AdamW) to handle the non-convex nature of the OOB loss landscape.

Key Contributions

• Post-Learning Smoothing Framework: Introduces a general, probabilistic approach to equip any learned piecewise constant function with arbitrary smoothness while retaining the spatial adaptivity of the original model.
• Theoretical Interpretation: Provides a theoretical link between kernel smoothing and the uncertainty of tree split points under data resampling, justifying the use of specific kernel shapes.
• Efficient Implementation: Demonstrates that smoothing can be applied to random forests efficiently by leveraging the linearity of the ensemble, reducing complexity from exponential (in terms of regions) to linear (in terms of individual tree regions).
• Empirical Validation: Shows that a smoothed random forest with a small number of trees (e.g., 10) can outperform standard random forests with significantly larger ensembles (up to 100 trees) and Gaussian Process regression across diverse datasets.

Experimental Results
The approach was evaluated on 10 UCI datasets with training sizes ranging from 50 to 500 observations.

• Performance: The proposed "Ensemble of Smoothed Trees with Per-Dimension parameters" (EST-PD) using either Gaussian or hyperbolic secant kernels consistently outperformed the baseline random forest (10 trees) in 93–94% of cases.
• Comparison to Baselines: EST-PD variants outperformed standard random forests with 20, 50, and 100 trees in 81%, 69%, and 64% of cases, respectively. They also substantially outperformed Gaussian Process regression (winning 88% of cases).
• Statistical Significance: Non-parametric statistical tests (Friedman and Nemenyi) confirmed that the smoothed variants form a statistically superior equivalence group compared to standard random forests and Gaussian processes.
• Small Data Regime: The method showed particular strength in data-scarce settings (e.g., $n=50$), where it achieved significant percentage improvements in Mean Squared Error (MSE) over standard baselines.
• Kernel Choice: The Gaussian and hyperbolic secant kernels yielded remarkably similar performance profiles, suggesting the choice of kernel has minimal practical impact on effectiveness.

Significance and Claims
The paper claims that post-hoc smoothing offers a computationally tractable way to improve the predictive accuracy of random forests, particularly when data is limited. By combining the adaptability of tree-based methods with the smoothness assumptions of kernel methods, the approach addresses the discontinuity issue inherent in standard forests without requiring the complex fitting schemes of soft-trees. The authors note that while the framework focuses on regression (conditional mean estimation), the concept could potentially extend to uncertainty quantification (conditional variance) and classification tasks, though these remain topics for future research. The work also highlights that while the method is theoretically extendable to gradient boosting, the sequential nature of boosting trees presents challenges for the global calibration approach used here.