Abstract
We study the effectiveness of non-uniform randomized feature selection in decision tree classification. We experimentally evaluate two feature selection methodologies based on information extracted from the dataset: (i) leverage scores-based and (ii) norm-based feature selection. Experimental evaluation of the proposed techniques indicates that such approaches can be more effective than naive uniform feature selection while maintaining performance comparable to the standard Random Forest algorithm.
Introduction
In the era of "Big Data," datasets often contain a vast number of features, many of which are redundant or represent pure noise—a phenomenon known as the "curse of dimensionality." Standard ensemble methods, such as Random Forests (RF), mitigate this by selecting a random subset of features at every node. However, uniform random selection is a "blind" strategy. If a dataset has 1,000 features but only 10 are informative, a uniform sampler will frequently select "weak" features. This forces the ensemble to grow significantly in size and computational cost to achieve acceptable accuracy. This paper introduces LESS (LEverage ScoreS) Trees, an ensemble method that uses statistical leverage scores to bias feature selection toward the most informative attributes, creating leaner and more accurate models.
Methods
The LESS Tree ensemble algorithm operates in two primary phases: importance scoring and ensemble construction.
- Importance Scoring: Instead of treating all features as equally likely, the algorithm computes a probability distribution ($\Pi$) over the features. Two non-uniform methods are evaluated:
- Norm-based sampling: Features are weighted by their squared Euclidean norm (magnitude).
- Statistical Leverage Scores: By performing a Singular Value Decomposition (SVD) on the training matrix, leverage scores are calculated to identify features that are most influential in defining the data's structure.
- Ensemble Construction: For each tree in the ensemble, the algorithm samples $k$ features according to the distribution $\Pi$. Unlike a standard Random Forest, which samples features at every node, a LESS tree is trained in its entirety using only that fixed subset of $k$ features.
Experimental Evaluation
The proposed approach was evaluated on four high-dimensional benchmark datasets:
- MNIST: Handwritten digits (60,000 examples).
- ORL: Face recognition (400 images, 4,096 dimensions).
- PIE: Facial images (41,368 images, 1,024 dimensions).
- MADELON: An artificial, highly non-linear dataset designed to test signal detection in noise.
Key Results
The experimental results demonstrate that "judiciously biased" randomness outperforms blind uniform sampling. By favoring high-leverage features, the model focuses on the most structural parts of the data.
- Accuracy vs. Random Forests: In most tests, LESS with $k=50$ features matched or outperformed standard Random Forests. As shown in the performance plots, leverage score-based sampling often converges to lower error rates faster than uniform sampling.
- Robustness to Noise: On the adversarial MADELON dataset, LESS was significantly superior to both standard RFs and uniform sampling, effectively identifying the signal within the noise.
- Space Complexity: LESS achieved target accuracy with fewer total nodes. For instance, on the MADELON dataset, LESS reached the target accuracy using only 4,003 nodes, while the standard Random Forest required 26,407 nodes.
- Efficiency: Training on a reduced feature space from the start leads to faster training times as the search space for optimal splits is minimized.
Conclusion and Future Work
LESS Trees provide a more interpretable and efficient alternative to standard Random Forests by leveraging the underlying structure of the data for feature selection. Because each tree only sees a small subset of features, the resulting models are easier for humans to inspect. Future work could explore applying these non-uniform sampling techniques at the node level or extending them to other learners like linear classifiers or Support Vector Machines.
Summary updated