TL;DR
Standard Random Forests select features blindly, but not all features are created equal. This paper introduces LESS (LEverage ScoreS) Trees, an ensemble method that uses linear algebra—specifically statistical leverage scores—to "bias" feature selection toward the most informative attributes, resulting in more accurate, faster, and more interpretable models.
What Problem Does This Paper Address?
In the era of "Big Data," we are often drowning in features, many of which are redundant or pure noise (the "curse of dimensionality"). Standard ensemble methods like Random Forests (RF) handle 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 actually useful, a uniform sampler will frequently pick "weak" features, forcing the ensemble to grow massive (and computationally expensive) to achieve decent accuracy. The authors seek a way to identify "significant" attributes upfront to build leaner, smarter ensembles.
Methods
The authors propose the LESS Tree ensemble algorithm, which operates in two main phases:
- Importance Scoring: Instead of treating every feature as equally likely to be chosen, they compute a probability distribution ($\Pi$) over the features. They evaluate two non-uniform methods:
- Norm-based sampling: Features are weighted by their squared Euclidean norm (magnitude).
- Statistical Leverage Scores: This is the "secret sauce." By performing a Singular Value Decomposition (SVD) on the training matrix, they calculate leverage scores that identify which columns (features) 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.
Datasets
The researchers evaluated their approach on four high-dimensional benchmarks:
- MNIST: The classic dataset of handwritten digits (60,000 training examples).
- ORL: A face recognition dataset with 400 images and 4,096 dimensions.
- PIE: A database of 41,368 facial images across 68 people (1,024 dimensions).
- MADELON: An artificial, highly non-linear dataset from the NIPS 2003 feature selection challenge, specifically designed to test a model's ability to find signal in noise.
Key Insights and Ideas
- Biased is Better: Randomness is useful for generalization, but "judiciously biased" randomness is even better. By favoring features with high leverage scores, the model focuses its "attention" on the most structural parts of the data.
- Interpretability through Sparsity: Because each tree in a LESS ensemble only ever sees $k$ features (often as few as 10 to 50), the resulting trees are much easier for a human to inspect compared to a standard RF tree that might split on any of the hundreds or thousands of available features.
- Efficiency Gains: Training on a restricted subset of features significantly reduces the computational search space for the "best split" at each node, leading to faster training times without sacrificing accuracy.
Key Results
- Accuracy vs. Random Forests: In almost all tests, the LESS algorithm with $k=50$ features either matched or outperformed the standard Random Forest algorithm.
- Performance on Noise: On the "adversarial" MADELON dataset, LESS was significantly superior to both standard RFs and uniform sampling.
- Space Complexity: The authors found that LESS often achieved target accuracy with fewer total nodes. For example, on the MADELON dataset, LESS reached the target accuracy using only 4,003 nodes, while the standard Random Forest required 26,407 nodes.
- Training Speed: LESS trees are generally faster to train because they operate on a reduced feature space from the start.
Limitations and Future Work
- Hyperparameter Tuning: The performance of LESS is sensitive to the choice of $k$ (the number of features sampled). The authors suggest a range of $[\sqrt{d}, 2\sqrt{d}]$, but this still requires empirical tuning.
- Static Selection: Currently, LESS selects the feature subset once per tree. The authors suggest that a future direction could involve applying these non-uniform sampling techniques at the node level (sampling a new "biased" subset for every split), which might further improve performance.
- Generalization: While the paper focuses on decision trees, the authors conjecture that these leverage-score-based selection schemes could be applied to other "weak" learners like linear classifiers or Support Vector Machines, though this wasn't tested in the current study.
Summary updated