Spectrum of Variable-Random Trees

Fei Tony Liu, Kai Ming Ting, Yang Yu, Zhi-Hua Zhou

Introduction

Ensemble learning relies heavily on the diversity of its base learners. Traditionally, randomization in decision trees has been approached as a binary choice: either start with a deterministic heuristic (like C4.5) and add minor perturbations via techniques like Bagging, or build trees that are entirely random. This paper proposes that these approaches represent the extreme ends of a continuous spectrum. By introducing Variable-Random Trees (VR-Trees), the authors explore the "middle ground" of this spectrum, demonstrating that intermediate levels of randomness often yield superior predictive power, particularly in noisy environments.

The VR-Tree Framework

The core of this approach is the VR-Tree, a base learner whose level of randomization is controlled by a parameter $\alpha \in [0, 1]$. During construction, each node split is determined by a weighted coin flip:

  1. With probability $\alpha$, the algorithm employs a deterministic heuristic (such as Gain Ratio) to select the optimal split.
  2. With probability $1-\alpha$, the algorithm selects a feature and split point entirely at random.

This mechanism allows for a smooth transition from purely random trees ($\alpha = 0$) to standard deterministic trees ($\alpha = 1$). The authors also extend this to subspace methods, as detailed in the algorithm below.

The Subspace.VR-Trees algorithm, combining feature subspace selection with variable randomization.

Analysis of the Randomization Spectrum

Empirical results across 45 UCI datasets reveal a distinct "phase transition" around $\alpha = 0.5$. The "random-heavy" half of the spectrum ($0 \leq \alpha \leq 0.5$) tends to produce larger, highly diverse trees capable of approximating complex, non-axis-parallel decision boundaries. Conversely, the "deterministic-heavy" half ($0.5 < \alpha \leq 1$) produces more accurate individual trees that suffer from high correlation within an ensemble.

Average error rates across the randomization spectrum (alpha). The U-shaped curves indicate that optimal performance often occurs at intermediate levels of randomness.

As shown in the figure above, the relationship between error and $\alpha$ is often U-shaped. This confirms that neither extreme is typically optimal; the best performance is found in the previously unexplored middle of the spectrum. A key insight is that Random Forests (RF) are "constrained" to a narrow range of this spectrum because they always select the best feature from a subset, tethering them to deterministic heuristics. VR-Trees, by contrast, can explore regions of high diversity that RF cannot reach.

Coalescence: Automating Randomness

Since the optimal $\alpha$ varies by dataset, the authors introduce Coalescence. Instead of tuning for a single $\alpha$, Coalescence builds an ensemble by sampling multiple $\alpha$ values from the random-heavy range $[0, 0.5]$. This creates a "committee of experts" with varying degrees of diversity and accuracy, providing robustness without the need for exhaustive cross-validation.

Key Results and Comparative Performance

In head-to-head comparisons using the Friedman test, Coalescence consistently outperformed established methods:

  • Ranking: Coalescence achieved the top rank against Random Forests, Random Subspace, and C5 Boosting.
  • Statistical Significance: Coalescence was found to be significantly better than traditional Bagging and Max-Diverse Ensembles.
  • Win Conditions: Coalescence is particularly effective on datasets with non-axis-parallel boundaries or significant class noise. In contrast, Random Forests maintain an edge on very small datasets or those with a high proportion of irrelevant "noise" features.

Conclusion

The VR-Tree framework demonstrates that the diversity-accuracy trade-off in ensemble learning is best managed by exploring the full spectrum of randomization. While VR-Trees can be sensitive to irrelevant attributes at low $\alpha$ values, the Coalescence method provides a powerful, automated way to leverage high-diversity models. Future research will focus on integrating more robust feature selection into the random split process to further mitigate the impact of noise features.

Summary updated

Abstract

In this paper, we show that a continuous spectrum of randomisation exists, in which most existing tree randomisations are only operating around the two ends of the spectrum. That leaves a huge part of the spectrum largely unexplored. We propose a base learner VR-Tree which generates trees with variable-randomness. VR-Trees are able to span from the conventional deterministic trees to the complete-random trees using a probabilistic parameter. Using VR-Trees as the base models, we explore the entire spectrum of randomised ensembles, together with Bagging and Random Subspace. We discover that the two halves of the spectrum have their distinct characteristics; and the understanding of which allows us to propose a new approach in building better decision tree ensembles. We name this approach Coalescence, which coalesces a number of points in the random-half of the spectrum. Coalescence acts as a committee of ``experts'' to cater for unforeseeable conditions presented in training data. Coalescence is found to perform better than any single operating point in the spectrum, without the need to tune to a specific level of randomness. In our empirical study, Coalescence ranks top among the benchmarking ensemble methods including Random Forests, Random Subspace and C5 Boosting; and only Coalescence is significantly better than Bagging and Max-Diverse Ensemble among all the methods in the comparison. Although Coalescence is not significantly better than Random Forests, we have identified conditions under which one will perform better than the other.
BibTeX
@article{liu2008spectrum,
  author = {Fei Tony Liu and Kai Ming Ting and Yang Yu and Zhi-Hua Zhou},
  title = {{Spectrum of Variable-Random Trees}},
  journal = {J. Artif. Intell. Res.},
  year = {2008},
  doi = {10.1613/jair.2470},
}

Loading related content...

Figure