Source-linked AI summary
Gradient Boosted Feature Selection
Zhixiang Eddie Xu, Gao Huang, Kilian Q. Weinberger, Alice X. Zheng
TL;DR
Feature selection must identify relevant features and nonlinear interactions while scaling to large data sets and incorporating known sparsity structure. GBFS modifies gradient-boosted trees to select features sparsely, integrate selection with classification, and use side information. Across real-world data sets it tends to match or outperform Random Forest Feature Selection, while a biological example reaches competing methods’ best accuracy with one feature bag.
Problem
Existing feature-selection methods face a trade-off between nonlinear interaction discovery, scalability, and structured sparsity.
Method
GBFS uses gradient-boosted regression trees with a penalty on new features, no additional penalty for reused features, and support for feature-side information.
Results
GBFS tends to match or outperform Random Forest Feature Selection on accuracy and feature-selection trade-offs across real-world data sets.
Takeaways & Limitations
GBFS combines nonlinear classification and feature selection, scales as O(dn), and can select structured feature bags using domain side information.
Takeaways & Limitations
CART exploration has O(dn) complexity and may become problematic with millions of features; the paper primarily focuses on n ≫d.
Abstract
from arXiv · showhide
A feature selection algorithm should ideally satisfy four conditions: reliably extract relevant features; be able to identify non-linear feature interactions; scale linearly with the number of features and dimensions; allow the incorporation of known sparsity structure. In this work we propose a novel feature selection algorithm, Gradient Boosted Feature Selection (GBFS), which satisfies all four of these requirements. The algorithm is flexible, scalable, and surprisingly straight-forward to implement as it is based on a modification of Gradient Boosted Trees. We evaluate GBFS on several real world data sets and show that it matches or out-performs other state of the art feature selection algorithms. Yet it scales to larger data set sizes and naturally allows for domain-specific side information.
1. INTRODUCTION
Feature selection must balance relevance, nonlinear interaction discovery, scalability, and structured sparsity. GBFS modifies gradient-boosted trees to meet these goals and matches or outperforms Random Forest Feature Selection while supporting feature-group side information.
- Effective feature selection can improve interpretability, reduce classifier memory and training costs, lower feature extraction costs, and improve generalization.
- Linear methods discover linear dependencies but fail on nonlinear interactions, while nonlinear methods often scale super-linearly with training-set size.
- GBFS targets efficient feature selection when the number of data points greatly exceeds the number of features, using greedy gradient-boosted regression trees.
- GBFS penalizes splitting on new features while imposing no additional penalty when previously selected features are reused.
- As a tree ensemble, GBFS discovers nonlinear interactions and unifies feature selection with classification in one optimization.
- GBFS has O(dn) time and memory complexity and can incorporate feature costs, feature bags, or regions of interest as side information.
- Across real-world data sets, GBFS tends to match or outperform Random Forest Feature Selection on accuracy and feature-selection trade-offs.
- On a biological task with nine feature bags, GBFS matched competing methods’ best accuracy using only a single feature bag.
2. RELATED WORK
Prior feature-selection methods trade off linearity, nonlinear modeling, computational cost, and scalability. The related work includes mutual-information, kernel, neural-network, boosted-tree, and Random Forest approaches.
- Lasso scales to very large data sets but models only linear correlations and cannot discover nonlinear feature dependencies.
- mRMR selects responsive, nonredundant features using mutual information, but computing mutual information is intractable for large numbers of instances.
- Other nonlinear approaches include Grafting, boosted-tree ranking, Random Forest methods, and Gradient Boosted Trees used for classifier cascades.
3. BACKGROUND
The paper frames feature selection through sparse regularization and classification data assumptions. Capped l1 regularization better approximates feature-count penalties but introduces a non-convex optimization challenge.
- The paper represents data as input vectors x_1,...,x_n in R^d with corresponding labels drawn from an unknown distribution.
- Although labels may be binary, categorical, or real-valued, the paper focuses on binary classification and notes extensions to multi-class and regression.
- Lasso combines linear classification with l1 regularization, which encourages sparse solutions.
- In binary classification, the paper uses log-loss instead of squared loss for feature selection.
- l1 regularization both controls overfitting and induces sparsity, tying these effects together so their impacts cannot be regulated independently.
- 3.2 The capped l1 norm: The capped l1 norm limits each coefficient’s penalty, so extracted features incur no further use penalty and weights are not pushed toward small values.
- 3.2 The capped l1 norm: When epsilon is sufficiently small, q_epsilon(w)/epsilon gives the exact number of extracted features; however, the capped l1 norm is non-convex.
- 3.2 The capped l1 norm: Combining capped l1 with l1 or l2 regularization allows separate control of feature extraction and regularization through mu and lambda.
4. GRADIENT BOOSTED FEATURE SELECTION
GBFS modifies gradient-boosted regression trees so feature selection penalizes newly extracted features while retaining nonlinear modeling and efficient greedy optimization. The framework also supports structured feature costs and, on a simulated task, outperforms l1-regularized logistic regression.
- Properties: GBFS naturally captures nonlinear feature interactions and unifies feature selection with classification in one optimization.These properties distinguish the approach from linear selection and separate feature-importance procedures.
- Optimization: The sparse tree representation makes the high-dimensional optimization tractable, while the l1 penalty can be replaced by early stopping after T iterations.After T fixed-step updates, the coefficient l1 norm equals αT.
- Gradient Boosted Feature Selection: GBFS learns a sparse ensemble of regression trees, using a feature penalty that charges new features while allowing previously selected features to be reused.The feature-selection penalty is implemented through a binary feature–tree matrix and feature weights.
- Optimization: Gradient boosting minimizes the non-convex objective by coordinate descent, selecting a steepest-gradient tree and approximating the search with greedy CART.The resulting impurity function is a penalized squared loss whose first term matches negative gradients and whose second term rewards feature reuse.
- Structured Feature Selection: The feature-cost function can encode structured sparsity, including grouped features and staged extraction where nearby or related features become cheaper.For medical-image features, costs can encourage locally focused selections around already extracted pixels.
- Empirical Illustration: On the simulated data set, GBFS outperforms l1-regularized logistic regression by capturing nonlinear relations between labels and features.The figure caption states the comparison outcome; the supplied passages do not provide GBFS's numerical test error.
5. RESULTS
Across synthetic, structured, benchmark, and high-dimensional data sets, GBFS captures nonlinear feature relationships, incorporates sparsity structure, and achieves competitive or better feature-selection accuracy with scalable training.
- 5.2 Structured feature selection: On the structured Colon data, GBFS selects features from a single biologically meaningful bag and ties Random Forest for the lowest test error at 15.38%.L1-LR and HSIC Lasso select scattered features, while Group Lasso reaches 36.15% error.
- 5.3 Benchmark data sets: GBFS, RF-FS, and L1-LR scale across the small and medium data sets, while GBFS and RF-FS outperform L1-LR in accuracy by capturing nonlinear feature-label relationships.HSIC Lasso is sensitive to both training-instance count and feature count.
- 5.3 Benchmark data sets: With an SVM-RBF classifier on uspst feature subsets, GBFS has the lowest error rates when only a few features are selected, while methods converge as more features are added.L1-LR slightly outperforms most nonlinear methods when enough features are provided.
- SMK-CAN-187: On SMK-CAN-187, a d ≫n benchmark, GBFS outperforms L1-LR, HSIC-Lasso, and RF-FS, although the margin is small in some regions.The benchmark contains 187 data points and 19,993 features.
- 5.4 Computational complexity: GBFS has O(dn) computation for limited-depth trees, and its iteration count T is independent of the number of input features d.Empirically, GBFS is significantly faster than Random Forest on data sets with many instances, though the implementation comparison is not fully balanced.
6. DISCUSSION
GBFS combines nonlinear feature selection with classifier learning in one scalable, gradient-boosted-tree-based procedure that can incorporate feature dependencies. The authors report promising accuracy and feature-selection quality, while identifying feature dimensionality as a bottleneck.
- 6. DISCUSSION: GBFS performs nonlinear feature selection using gradient boosting of limited-depth trees.The approach combines learning a classifier and selecting features in a single step.
- 6. DISCUSSION: GBFS scales naturally to large data sets and can incorporate known feature dependencies as side-information.The paper highlights applications including biomedical research, medical imaging, and computer vision.
- 6. DISCUSSION: GBFS quickly trains accurate classifiers while selecting high-quality features.The authors describe the method as flexible across application domains and promising for feature discovery.
- 6. DISCUSSION: O(dn) CART feature exploration is a bottleneck when the number of features reaches millions.The paper focuses primarily on the n ≫ d setting and proposes restricting new-feature searches as future work.
A. SUPPLEMENTARY RESULTS
Supplementary MNIST experiments compare GBFS with L1-regularized logistic regression and Random Forest feature selection across six randomly selected one-vs-one task pairs. GBFS consistently matches Random Forest feature selection and outperforms L1-regularized logistic regression.
- A. SUPPLEMENTARY RESULTS: Six randomly selected one-vs-one MNIST task pairs were used to compare GBFS with L1-LR and Random Forest feature selection.Regularization and feature counts were varied to examine error rates under different settings.
- A. SUPPLEMENTARY RESULTS: GBFS consistently matches Random Forest feature selection across the evaluated MNIST task pairs.The comparison examines classification error rates against feature-selection performance.
- A. SUPPLEMENTARY RESULTS: GBFS clearly outperforms l1-regularized logistic regression in the supplementary MNIST comparison.The result is reported across the six randomly chosen binary classification task pairs.