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