Source-linked AI summary
Feature Selection via Regularized Trees
Houtao Deng, George Runger
TL;DR
Feature selection needs compact, informative subsets, but conventional approaches can require multiple models and tree splits can select redundant features. The paper introduces tree regularization, which penalizes similar-gain new split features and applies the framework to random forests and boosted trees. Experiments report high-quality subsets for strong and weak classifiers, while retaining tree models’ handling of varied data types and nonlinear structure.
Problem
Feature selection seeks compact subsets without significant predictive-information loss, while tree models can select redundant features and some selection methods require multiple models.
Method
The framework penalizes selecting a new split feature unless its gain is substantially larger than the gains of previously selected features, and is implemented in random forests and boosted trees.
Results
RRF and RBoost produce high-quality feature subsets for both strong and weak classifiers.
Takeaways & Limitations
The framework provides an effective and efficient feature-selection solution for practical problems using tree models.
Abstract
from arXiv · showhide
We propose a tree regularization framework, which enables many tree models to perform feature selection efficiently. The key idea of the regularization framework is to penalize selecting a new feature for splitting when its gain (e.g. information gain) is similar to the features used in previous splits. The regularization framework is applied on random forest and boosted trees here, and can be easily applied to other tree models. Experimental studies show that the regularized trees can select high-quality feature subsets with regard to both strong and weak classifiers. Because tree models can naturally deal with categorical and numerical variables, missing values, different scales between variables, interactions and nonlinearities etc., the tree regularization framework provides an effective and efficient feature selection solution for many practical problems.
I. INTRODUCTION
Feature selection seeks compact subsets without significant predictive-information loss, while the paper proposes tree regularization to add this capability efficiently to tree models.
- Feature selection selects compact predictor subsets without significant loss of predictive information about the target.It can address dimensionality, improve time and space efficiency, and facilitate interpretability.
- The proposed framework penalizes a new splitting feature when its gain resembles that of features selected in previous splits.This is intended to produce compact feature subsets.
- The framework requires building a single model and can be added to many tree-based models that split on one feature at a node.
- The framework is implemented on random forest and boosted trees as regularized ensembles.The paper refers to these implementations as RRF and RBoost.
- Experiments evaluate the effectiveness and efficiency of the two regularized tree ensembles.
A. Related work
Existing feature-selection approaches trade off learner specificity and computational cost, motivating a single-model approach that enables tree models to select feature subsets.
- Filters select features independently of a supervised learner, so their performance may not be optimal for a chosen learner.
- Wrappers use a learner to evaluate feature subsets for a given task but tend to be computationally expensive.
- Embedded methods select features using information obtained while training a learner, including variable-importance or node-splitting criteria.
- Wrappers and embedded methods may require multiple models; SVM-RFE may require O(M) models.
- The proposed tree regularization framework selects feature subsets while building many tree models only one time, potentially reducing training time.
B. Information-theoretic measures and issues
Information-theoretic measures quantify relevance, redundancy, and association, but common pairwise measures miss conditional and higher-order interactions that can be computationally expensive to capture.
- Information-theoretic measures, including entropy and information gain, are widely used for feature selection.
- Mutual information is symmetric and measures the degree of association between two variables.
- I(X_i; Y) can evaluate feature relevance for predicting the class, while I(X_i; X_j) can evaluate pairwise predictor redundancy.
- Mutual information and symmetric uncertainty capture two-way relationships but not relationships between variables conditioned on other variables.
- Higher-order interaction measures address some limitations, but handling n-way interactions for n > 3 remains computationally expensive.
C. Tree-based models and issues
Tree models can capture multi-way interactions, but their split-wise optimization ignores redundancy among previously selected features, especially across tree ensembles.
- Decision trees recursively split data into subsets and commonly choose splitting features by optimizing information-theoretic criteria.
- Tree models can capture multi-way interactions among splitting variables, potentially addressing limitations of information-theoretic measures.
- A decision tree selects each split feature without considering redundancy with features chosen in previous splits.
- After splitting on X2, either X1 or X2 can separate the classes, although {X2} is the minimal separating feature set.
- Regularization penalizes selecting a new feature similar to features used in previous splits to eliminate tree feature redundancy.The redundancy problem is more severe in ensembles containing multiple trees.
III. RELATIONSHIP BETWEEN DECISION TREES AND THE MAX-DEPENDENCY SCHEME
The Max-Dependency scheme can be represented as a tree in which feature selection across each level emphasizes non-redundant information, unlike ordinary decision trees that may select multiple redundant features.
- Max-Dependency scheme: The Max-Dependency scheme selects features sequentially using conditional mutual information given the features selected in earlier steps.The initial selected set is empty, and each subsequent step conditions on the previously selected feature set.
- Assumptions: Decision-tree analysis in this section assumes categorical variables, information-gain splitting, and K-way splits, although the later regularization framework is broader.
- Tree representation: A tree node is represented by its level and position, with unsplit nodes assigned imaginary child nodes to preserve the MD-tree structure.The path to a node is represented by feature-value pairs such as Sν.
- MD tree: An MD tree views each selection step as a tree level and selects only one feature at each level.The selected feature maximizes a weighted sum of conditional mutual information across nodes at that level.
- Comparison: Decision trees can select multiple features at the same level, whereas the MD formulation imposes a single-feature constraint and explicitly targets non-redundant information.The weighted level-wise calculation is more computationally expensive than node-wise conditional mutual-information maximization.
IV. REGULARIZED TREES
The tree regularization framework penalizes new splitting features whose gains resemble those of previously selected features, producing compact subsets while requiring only one model build per tree model.
- Regularization principle: The framework penalizes a candidate feature outside F when its gain is not substantially larger than the gain of selected features.Here, F is the feature set used in previous splits, and λ ∈[0, 1] controls the penalty; smaller λ imposes a larger penalty.
- Algorithm: The single-tree algorithm initializes F as empty, repeatedly selects a splitting feature, adds new selected features to F, and stops when the best regularized gain is zero.The algorithm then recursively splits the data into child nodes.
- Regularization principle: A regularized tree sequentially adds features to F only when they provide substantially new predictive information about Y.The resulting F is intended to contain informative, non-redundant features and is directly usable as the selected subset.
- Related work: A related penalized form reduced redundancy only along individual tree paths, whereas this framework targets a compact feature subset across the tree model.
- Regularized random trees: The regularized random tree differs from the original by using gainR, evaluating selected and sampled unselected variables, and requiring a new variable to improve upon all selected-variable gains.The random tree samples K=⌈M⌉ variables at each node in the described implementation.
- Regularized ensembles: The framework extends to ensembles by carrying F across trees, while computational complexity scales linearly with the number of regularized trees.The ensemble procedure uses F for features selected in previous splits from both the current and earlier trees.
V. EVALUATION CRITERIA FOR FEATURE SELECTION
Feature-selection quality is evaluated either theoretically, by identifying a minimal Markov blanket, or empirically, by minimizing a classifier’s expected loss while preferring smaller subsets. The Vehicle experiment illustrates how evaluation can differ across classifiers, with RF continuing to improve as features are added while C4.5 and NB plateau.
- Theoretical criterion: The theoretical criterion defines the optimal subset as a minimal Markov blanket that preserves conditional independence between Y and features outside the blanket.A Markov blanket is minimal and renders Y conditionally independent of any disjoint feature subset.
- Empirical criterion: The empirical criterion seeks the smallest feature subset that minimizes a classifier’s expected loss on data drawn from distribution D.The criterion depends on a training set, classifier induction algorithm, loss function, and data distribution.
- Empirical criterion: When comparing subsets empirically, lower generalization error is preferred, and equal-error subsets are ranked by smaller size.This operationalizes a preference for less predictive-information loss and compactness.
- Comparing criteria: The theoretical criterion is classifier-independent, whereas the empirical criterion measures information loss through a particular classifier.A strong classifier may better capture predictive information than a weak classifier, making strong-classifier evaluation desirable.
- Vehicle illustration: In the Vehicle experiment, RF accuracy keeps improving as randomly added features increase, while C4.5 and NB accuracy stops improving after a certain number of features.The comparison uses training and testing splits and evaluates accuracy against the number of selected features.
VI. EXPERIMENTS
Experiments compare regularized tree ensembles with established feature-selection methods and SVM-RFE across datasets and classifiers. RRF and RBoost generally preserve predictive accuracy while selecting compact subsets, with RRF substantially reducing selection time relative to SVM-RFE.
- Experimental setup: RRF and RBoost were evaluated on UCI, NIPS 2003, and IJCNN 2007 feature-selection benchmark datasets using Weka.The experiments used λ = 0.5 and compared regularized ensembles with CFS, FCBF, and SVM-RFE.
- Comparison with feature selectors: Regularized tree ensembles generally selected more features than CFS and FCBF, while retaining accuracy competitive with using all features under RF.The additional selected features were reported to add predictive information, consistent with the ensembles capturing multi-way interactions.
- Limitations: On datasets with few instances, such as arcene, RRF and RBoost offered no advantage over CFS.The authors suggest that small datasets produce small trees that are less capable of capturing multi-way feature interactions.
- Classifier effects: C4.5 accuracy remained competitive with using all features for every feature-selection method, unlike RF, indicating weaker extraction of predictive information from features.This contrast suggests that classifier strength affects how differences among selected feature subsets appear in evaluation.
- Comparison with SVM-RFE: RRF took 4 seconds on average for musk and 6 seconds on average for arrhythmia, compared with 109 and 442 seconds for SVM-RFE, respectively.These timings are reported for the two datasets used in the direct comparison.
- Comparison with SVM-RFE: For both musk and arrhythmia, RF accuracy using RRF-selected features was competitive with the optimum SVM-RFE point.RRF automatically selected the number of features, whereas SVM-RFE required a cutoff-selection strategy such as cross-validation.
VII. CONCLUSION
The framework adds feature selection to tree models through regularization, with RRF and RBoost producing high-quality feature subsets for both strong and weak classifiers.
- RRF and RBoost extend random forest and boosted trees with the proposed tree regularization framework for feature selection.
- The framework produces high-quality feature subsets for both strong and weak classifiers.
- Tree models’ support for categorical and numerical variables, missing values, different scales, interactions, and nonlinearities makes the framework suitable for many practical problems.