Sparse Projection Oblique Randomer Forests

Tyler M. Tomita, James Browne, Cencheng Shen, Jaewon Chung, Jesse Patsolic, Benjamin Falk, Carey E. Priebe, Jason Yim, Randal C. Burns, Mauro Maggioni, Joshua T. VogelsteinJMLR 2020 · OpenReview

TL;DR

This paper introduces Sparse Projection Oblique Randomer Forests (SPORF), a novel decision forest algorithm that uses sparse random projections for splits. SPORF aims to combine the interpretability and efficiency of traditional Random Forests with the increased expressive power of oblique forests, achieving state-of-the-art performance on a large benchmark suite.

What Problem Does This Paper Address?

Traditional Random Forests (RF) use axis-aligned splits, meaning splits are parallel to the feature axes. While this makes them robust to noise, interpretable, and computationally efficient, it can lead to overly complex trees and suboptimal performance when decision boundaries are not axis-aligned. Oblique decision forests, which use splits along linear combinations of features, offer greater expressive power but often sacrifice interpretability, computational efficiency, and robustness to noise. This paper addresses the challenge of creating a decision forest that retains the desirable properties of RF while also benefiting from the increased flexibility of oblique splits.

Methods

The core innovation of SPORF lies in its splitting mechanism. Instead of axis-aligned splits or dense oblique splits, SPORF uses sparse random projections. At each node, a random projection matrix is sampled, where a significant fraction of its entries are zero. This matrix is then used to project the data into a lower-dimensional space, and splits are searched for in this projected space. This approach is designed to:

  • Maintain interpretability: Sparse projections, especially those with coefficients of ±1, can still be interpreted as linear combinations of original features.
  • Improve computational efficiency: Sparse projections are computationally cheaper than dense ones.
  • Enhance robustness: By using random projections, SPORF can potentially discover informative directions that axis-aligned splits would miss, while still being less sensitive to noise than dense oblique methods.
  • Control sparsity: SPORF allows for control over the sparsity of these projections, offering a tunable parameter that balances performance and computational cost.

The paper also details the training and hyperparameter tuning process, which involves optimizing for out-of-bag error by tuning parameters like d (number of candidate split directions) and λ (average sparsity of projections).

Datasets

The paper evaluates SPORF on:

  • Simulated data sets: Sparse Parity, Orthant, and Trunk. These are specifically constructed to highlight different aspects of algorithm behavior, such as the informativeness of individual dimensions versus combinations of dimensions.
  • UCI Machine Learning Repository: A suite of 105 benchmark classification data sets. This is a standard benchmark used in previous studies to compare machine learning algorithms.
  • Real-world data sets for computational analysis: MNIST, Higgs, and p53. These are used to assess the efficiency and scalability of SPORF.

Key Insights and Ideas

  • Bridging the gap: SPORF effectively bridges the gap between axis-aligned and oblique decision forests by using sparse random projections. This allows it to capture complex decision boundaries without sacrificing the benefits of RF.
  • Robustness to hyperparameter choice: SPORF is shown to be less sensitive to its sparsity hyperparameter (λ) compared to other oblique methods like F-RC, making it easier to tune.
  • Learning interpretable features: SPORF can learn new, interpretable features (sparse linear combinations of original features) that are more informative than the original features themselves, as demonstrated by Gini importance analysis.
  • Consistency on challenging problems: SPORF achieves near-perfect classification accuracy on a problem where RF is theoretically known to be inconsistent, suggesting SPORF can handle a wider range of data distributions.

Key Results

  • Performance: SPORF consistently outperforms RF, XGBOOST, RR-RF, and CCF on a large suite of UCI benchmark data sets, particularly on numeric data. It achieves state-of-the-art classification performance.
  • Efficiency: SPORF's training time is comparable to RF and F-RC, and it exhibits good strong scaling, meaning it can effectively utilize multiple cores. Its prediction times are also competitive, especially with optimizations like "Forest Packing."
  • Robustness to noise: SPORF is robust to the addition of many noise dimensions, maintaining its performance where other oblique methods degrade significantly.
  • Simulated data performance: SPORF performs well across all simulated data settings, whereas other methods excel in specific scenarios (e.g., RF on orthant, F-RC on sparse parity).

Limitations and Future Work

  • Dense combinations: SPORF's reliance on sparse random projections might limit its ability to find informative splits when the signal is contained in dense linear combinations or non-linear combinations of features. The authors suggest that a hybrid approach evaluating both sparse random and dense supervised projections could further improve performance.
  • Theoretical consistency: While SPORF shows empirical consistency on problems where RF is not, a formal proof of SPORF's consistency is still an open question.
  • Regression: The paper mentions a preliminary implementation for regression, suggesting future work to investigate SPORF's behavior and performance on regression tasks.
  • Hyperparameter defaults: While default hyperparameter settings are identified, further research could explore their optimality across a wider range of problems.

Summary updated

Abstract

Decision forests, including Random Forests and Gradient Boosting Trees, have recently demonstrated state-of-the-art performance in a variety of machine learning settings. Decision forests are typically ensembles of axis-aligned decision trees; that is, trees that split only along feature dimensions. In contrast, many recent extensions to decision forests are based on axis-oblique splits. Unfortunately, these extensions forfeit one or more of the favorable properties of decision forests based on axis-aligned splits, such as robustness to many noise dimensions, interpretability, or computational efficiency. We introduce yet another decision forest, called “Sparse Projection Oblique Randomer Forests” (SPORF). SPORF trees recursively split along very sparse random projections. Our method significantly improves accuracy over existing state-of-the-art algorithms on a standard benchmark suite for classification with $>100$ problems of varying dimension, sample size, and number of classes. To illustrate how SPORF addresses the limitations of both axis-aligned and existing oblique decision forest methods, we conduct extensive simulated experiments. SPORF typically yields improved performance over existing decision forest methods, while mitigating computational efficiency and scalability and maintaining interpretability. Very sparse random projections can be incorporated into gradient boosted trees to obtain potentially similar gains.
BibTeX
@article{tomita2020sparse,
  author = {Tyler M. Tomita and James Browne and Cencheng Shen and Jaewon Chung and Jesse Patsolic and Benjamin Falk and Carey E. Priebe and Jason Yim and Randal C. Burns and Mauro Maggioni and Joshua T. Vogelstein},
  title = {{Sparse Projection Oblique Randomer Forests}},
  journal = {J. Mach. Learn. Res.},
  year = {2020},
  url = {https://openreview.net/forum?id=DPR2lUruq_i},
}
Figure