Random Forest Density Estimation

Hongwei Wen, Hanyuan HangICML 2022 · OpenReview

Introduction

Density estimation—the task of approximating the underlying probability distribution of a dataset—is a cornerstone of machine learning, utilized in applications ranging from clustering to anomaly detection. However, traditional methods often struggle to balance computational efficiency, dimensionality, and local adaptivity:

  • Kernel Density Estimation (KDE): While popular, KDE lacks local adaptivity, meaning it struggles when a density function exhibits varying properties across different regions of the feature space.
  • Histogram Density Estimation (HDE): Though simple, HDE suffers severely from the "curse of dimensionality." The number of cells grows exponentially ($2^{pd}$), making it computationally infeasible for high-dimensional data.
  • Tree-based Methods: Single-tree methods are efficient but produce discontinuous, "jumpy" density estimates at partition boundaries, which degrades overall accuracy.

To bridge these gaps, researchers have proposed Random Forest Density Estimation (RFDE), a novel tree-based algorithm that overcomes boundary discontinuities and dimensionality curses by ensembling random trees.

Methodology: From Trees to Forests

The core innovation of RFDE lies in its transition from a single Random Tree Density Estimator (RTDE) to an ensemble approach.

1. RTDE Construction: Starting with a hypercube containing the training data, the algorithm recursively partitions the space. At each step, it randomly selects a single dimension and splits the current cell exactly at its midpoint. This recursive splitting continues until a user-defined depth $p$ is reached. The density within each resulting leaf node (cell) is then estimated as a constant, calculated based on the proportion of training samples it contains.

The recursive midpoint splitting process for a single tree.

2. RFDE (The Ensemble): To resolve the boundary discontinuity inherent to a single tree, RFDE trains $T$ different random trees. Because the dimension selection at each split is randomized, the trees produce different partition boundaries. The final density estimate for any given point is simply the uniform average of the estimates from all $T$ trees.

Unlike standard histograms that split every dimension at every level, RFDE's midpoint splitting rule only splits one random dimension at a time. This keeps the total number of cells at $2^p$ regardless of the data dimension $d$, effectively bypassing the $2^{pd}$ cell explosion.

Key Insights and Theoretical Breakthroughs

A single tree inherently produces a step function. However, ensembling multiple trees with varying random boundaries effectively "smooths out" these steps. As the ensemble size $T$ increases, the forest approximates a continuous, smooth density function much more effectively than any individual base estimator.

Visualization of how ensembling smooths the predicted density estimate compared to the true density.

Beyond empirical smoothing, the authors provide a significant theoretical breakthrough: they offer the first mathematical proof that ensembling strictly improves the convergence rate for density estimation in specific function spaces (specifically, $C^{1,\alpha}$). For dimensions $d \ge 2$, the upper bound of the forest's error is proven to be strictly smaller than the lower bound of a single tree's error.

Experimental Evaluation

The researchers evaluated RFDE across a rigorous suite of synthetic and real-world benchmarks:

  • Synthetic Datasets: Tested on mixtures of Beta, Laplace, Exponential, and Uniform distributions across 2, 5, and 7 dimensions. RFDE consistently outperformed both KDE and HDE, with its advantage widening as dimensionality increased.
  • Real-World UCI Datasets: On datasets like Adult, Diabetes, and Abalone, RFDE achieved significantly lower Average Negative Log-Likelihood (ANLL) than baseline methods, indicating a superior fit to the true data distribution.
  • Anomaly Detection: When applied to 20 benchmark outlier detection datasets from the ODDS library, RFDE proved highly robust. It achieved the lowest "rank-sum" score (55), outperforming heavyweights like Isolation Forest (72) and One-Class SVM (82).

The experiments also highlighted the algorithm's parameter sensitivity. There is an optimal tree depth $p$ for any given dimension; a tree that is too shallow fails to capture local structural nuances, while one that is too deep suffers from high variance.

Limitations and Future Directions

While RFDE presents a major step forward, it has a few limitations:

  • Hyperparameter Tuning: Performance is highly sensitive to the tree depth $p$. While cross-validation is recommended, finding the optimal $p$ for massive datasets can be computationally expensive.
  • Fixed Splitting Rule: The current algorithm relies strictly on midpoint splitting. Exploring data-dependent splitting rules—similar to standard Random Forests used in classification—could further improve local adaptivity, though it would complicate the theoretical proofs.
  • Computational Scaling: Although vastly more efficient than histograms, RFDE's memory and time requirements still scale linearly with the number of trees $T$, which may pose constraints for strict real-time applications.

Summary updated

Abstract

We propose a density estimation algorithm called random forest density estimation (RFDE) based on random trees where the split of cell is along the midpoint of the randomly chosen dimension. By combining the efficient random tree density estimation (RTDE) and the ensemble procedure, RFDE can alleviate the problems of boundary discontinuity suffered by partition-based density estimations. From the theoretical perspective, we first prove the fast convergence rates of RFDE if the density function lies in the Hölder space $C^{0,\alpha}$. Moreover, if the target function resides in the subspace $C^{1,\alpha}$, which contains smoother density functions, we for the first time manage to explain the benefits of the ensemble learning in density estimation. To be specific, we show that the upper bound of the ensemble estimator RFDE turns out to be strictly smaller than the lower bound of its base estimator RTDE in terms of convergence rates. In the experiments, we verify the theoretical results and show the promising performance of RFDE on both synthetic and real world datasets. Moreover, we evaluate our RFDE through the problem of anomaly detection as a possible application.
BibTeX
@inproceedings{wen2022random,
  author = {Hongwei Wen and Hanyuan Hang},
  title = {{Random Forest Density Estimation}},
  booktitle = {International Conference on Machine Learning},
  year = {2022},
  url = {https://openreview.net/forum?id=5zDWmwdVye},
}
Figure