An Empirical Map of Feature Selection Algorithms

Executive summary

Feature selection is not flashy and tends to attract less attention than the sophisticated estimation techniques that it is often no more than a prelude to. Nonetheless, the problem of selecting the best subset of features remains hugely complex with an exponential search space and a vast number of potential solution algorithms to choose from. The multitude of feature selection algorithms that have been proposed in various statistical sub-domains is reflective of a variety of philosophical approaches that can be taken when solving the problem. Some approaches emphasize speed, some aim for asymptotic consistency, some emphasize tests of statistical significance, others predictive performance. I’ve taken a set of 23 algorithms from different domains and representing distinct approaches to feature selection and apply them to an empirical problem. An overview of the methods is provided here, while Fig. 1 visualizes an approximate relative popularity score for (a subset of) methods across different statistical domains:

Figure 1: Popularity of feature selection algorithms

Fig. 1 is based on the number of mentions in document titles on Google Scholar. The most popular feature selection algorithms are genetic algorithms (GA), lasso, correlation, random forest importance and information gain. However, the result varies across fields. While the lasso is hugely popular in econometrics, for instance, the field also favors some less well-known methods such as Bayesian model averaging (BMA) or general-to-specific (GETS). Partial least squares (PLSR) enjoys significant popularity in chemometrics, while social sciences in general tend to make use of a broader set of algorithms than core statistical disciplines.

In this analysis, each of the 23 algorithms is used to select features from 100 bootstrap samples of the publicly available FRED-MD US macroeconomic data set , with the objective of identifying leading indicators for 4 different target variables from a set of 134 candidate features. Based on the resulting models, I measure the proximity in the selection behavior of the algorithms using a metric that can account for the correlated nature of the underlying data (see below). Then I project the result onto a two-dimensional graph (upper left panel Fig. 2), with each point (node) in the graph representing one bootstrap realization of the respective algorithm, and with adjacent nodes selecting similar information.

Figure 2: Feature Selection Map with target variable: US CPI inflation (CPIAUCSL), and \(k\leq 30\)

The selection map broadly comprises 4 clusters of algorithms that can be observed again and again across different target variables and model sizes (\(k\)):

1. Penalized regressions, including (adaptive) lasso, elastic net and gradient boosting regressions (correlation, MRMR and random forest importance (RF) sometimes hover in the vicinity);
2. Model sampling methods, including the three Bayesian techniques, forward selection and the genetic algorithm (GA);
3. Backward selection, including recursive feature elimination (RFE), GETS, and — somewhat less intuitively — PLSR;
4. Peripheral methods that produce very different models including, for instance, RReliefF and the unsupervised (Laplacian, FOS-MOD) or semi-supervised (PCR) algorithms.

Grouping along these 4 clusters appears to be highly robust and suggests a type of fundamental affinity between these methods that is not always obvious.

Fig. 2 displays two additional metrics: the out-of-bootstrap performance rank and the diversity of selected information. The latter measures the effective percentage of principal components contained in the selected model (i.e. how many orthogonal information sources the model taps into). For both measures, a higher value is favorable. Two important observations are (i) that the penalized regression methods perform consistently well on both metrics, and (ii) that there is a distinct positive correlation between the measures. If a feature selection algorithm selects features that represent a wide variety of distinct information sources, it is more likely to rank higher on out-of-sample performance.

Reproducing the above plots for different target variables and different model sizes (\(k\)) reveals remarkable robustness of the results, as shown in the results section. For the economically interested reader, that section also discusses which leading indicators are ultimately identified as the most predictive features for each target. Before examining these results, however, the following sections provide an overview of the algorithms, methodology and data used in this analysis.

Feature selection algorithms

Feature selection is a much discussed topic in several statistical domains and the landscape of available methods is accordingly complex and multifaceted (see Li et al. (2018) for a decent overview). Generally speaking, feature selection aims to strike a balance between the desire to build a parsimonious model for prediction or inference and the desire to leverage as much of the available information as possible. The data set used in this analysis, for instance contains 134 monthly time series of which we would like to select the \(k \leq 30\) features with the highest predictive power. This selection problem can be solved using a wide variety of algorithms leading to a variety of competing candidate models.

In order to develop a sense of the relative popularity of different feature selection algorithms, I decided to count the number of publications available on Google Scholar based on queries that use keywords relating to different algorithms in the context of feature selection as well as the statistical domain.² Fig. 3 plots the result in the form of an approximate popularity score:

Figure 3: Popularity of feature selection algorithms

The plot reveals some similarities and some disparities. The most popular methods (genetic algorithms, correlation, information gain, lasso, random forest) are consistently applied across many domains. Conversely, some fields, such as econometrics or chemometrics chart a slightly different course. Of the categories of feature selection algorithms discussed below, none seems to dominate outright.

Apart from research domains, algorithms can be grouped along several additional axes, as summarized in the tables below. One of the most generally accepted classifications distinguishes between filter, wrapper and embedded methods (Kumar 2014; Galli 2022). However, as with most statistical learning techniques, there are distinctions between supervised and unsupervised methods, between different types of objective functions, asymptotic properties, complexity and many other attributes.

install.packages(tidyfit)
library(tidyfit)

# This is useful to show progress bars
# progressr::handlers(global = TRUE)

# Usage example for tidyfit::regress
data %>% 
  group_by(target_variable_name)
  regress(target_variable_value ~ .,   # Model specification
          m("lasso"),                  # Lasso regression (default hyperparameter grid)
          m("cor"),                    # Correlation
          m("relief"),                 # RReliefF
          .cv = "vfold_cv")

Model comparison with correlated features

Up to this point, I have discussed how models are selected from a large number of potential feature candidates using a variety of different algorithms. Statements about the relative behavior of models, however, are only possible if a systematic framework of model comparison is available. Model comparisons could be done indirectly (e.g. examining the out-of-sample performance of the models) or directly (e.g. counting the number of overlapping features selected). Direct comparisons are arguably more informative (two models could perform equally poorly for vastly different reasons), but are complicated by correlation in the underlying data set.

To understand this, let’s begin by formalizing a notation for direct comparisons of candidate models. Suppose feature selection algorithm \(a \in \mathcal{A}\) generates a selection vector \(\mathbf{m}_a = \{m^{i}_a\}_{i\in 1,...,p}\), where

\[ m^i_a = \begin{cases} 1 \;\; \text{when feature $i$ is selected}\\ 0 \;\; \text{otherwise} \end{cases}, \] and \(p\) is the total number of available features.

We’ll measure the correlation of two selection vectors \(\mathbf{m}_a\) and \(\mathbf{m}_b\), with \(a,b\in\mathcal{A}\), using the percentage overlap \(\mathcal{J}(a,b)\) (Jaccard index) which ranges between 0 and 1 and can be defined as

\[ \mathcal{J}(a, b) = \frac{\sum \mathbf{m}_{a} \mathbf{m}_{b}}{\sqrt{\sum \mathbf{m}_{a} \sum \mathbf{m}_{b}}}. \]

When features are correlated, however, this measure begins to deteriorate, since different algorithms deal differently with multicollinearity.

Suppose the case of two highly correlated features \(x_1\) and \(x_2\). A lasso regression may (somewhat arbitrarily) select \(x_1\), while a correlation filtering approach may select both \(x_1\) and \(x_2\). Both algorithms have selected virtually the same information, but have an unjustifiably low value for \(\mathcal{J}(\cdot)\). To address this issue, I cluster the features and transform \(\mathbf{m}_a\) so that

\[ m^i_a = \begin{cases} 1 \;\; \text{when any feature from the same cluster as $i$ is selected}\\ 0 \;\; \text{otherwise} \end{cases}. \]

Calculating \(\mathcal{J}_g(a,b)\) using the revised definition of \(\mathbf{m}_a\) and \(\mathbf{m}_b\) leads to a similarity curve over the number of clusters (\(g\)). I use complete-linkage hierarchical clustering of the correlation matrix to generate \(p-1\) potential cluster vectors, and then calculate \(\mathcal{J}_g(a,b)\) for all \(g\in 1,...,p-1, p\) (here \(g=p\) is simply the unclustered case).

Fig. 4 illustrates the concept by plotting \(\mathcal{J}_g(\text{Lasso}, \text{Grad. Boost})\) (left) and \(\mathcal{J}_g(\text{Lasso}, \text{RReliefF})\) (right) over the number of clusters. Lasso and gradient boosting select similar models leading to high scores even when the number of clusters is high. The RReliefF algorithm, conversely, selects a highly distinct model. However as the granularity of the clustering is decreased, the selection profile of the algorithms converges.

Figure 4: Similarity between Lasso regression and alternative feature selection algorithms

The total similarity between two methods is now defined as the area under the above Jaccard index curve, \(\sum_g\mathcal{J}_g(a,b)\). This ensures that while RReliefF has a comparatively low similarity, the overall score is increased by the informational overlap revealed when examining clusters of correlated features in a joint manner.

Results

Perhaps unsurprisingly, feature selection is very much an art as well as a science, with the 23 algorithms producing as many distinct (often substantially so) models. Nonetheless, I attempt to distill some robust facts from the feature selection maps produced for all four target variables and three different settings of \(k\), in this section. I look at a direct comparison of the algorithms using feature selection maps, indirect comparisons of the performance and informational diversity, and finally at the actual leading indicators selected by the models.

Performance and diversity

The plots above include two additional metrics of indirect model comparison. The first is the out-of-bootstrap performance rank, which is the inverse rank of the mean squared error (MSE) over the observations not included in each bootstrap sample. The second is the diversity of selected information which is the effective percentage of principal components contained in the selected model (i.e. how many orthogonal information sources the model taps into). The metric is calculated by multiplying the selection vector with the PCA rotation matrix and calculating an entropy score of the resulting rotated vector, which is equal to zero when only one principal component is loaded and equal to one when all principal components have the same absolute loading.

Fig. 5 summarizes the results for these two indirect metrics across all targets and model sizes. The result is a striking positive relationship: a higher degree of information diversity is associated with better out-of-sample performance. Furthermore, algorithms generally performing best on both metrics are those contained in the cluster of penalized regressions, while those contained in the backward selection cluster perform worst.

Figure 5: Relationship between performance and information diversity

Conclusion

The topic of feature selection is vast — not only in the landscape of available methods, but also in approaches to analyzing them. Academic studies often focus (with good reason) on simulations and comparisons across a relatively specialized subset of algorithms. The aim of this analysis has been more practical and has comprised a set of algorithms that is as diverse as possible (or feasible under reasonable constraints).

If one accounts for the poor signal-to-noise ratio of the prediction problem, the results are surprisingly consistent and allow a few broad conclusions to be drawn about the behavior of the feature selection algorithms. Algorithms that select more diverse models (i.e. that draw on more uncorrelated information) tend to perform better. Furthermore, algorithms seem to fall naturally into 4 distinct clusters — a result that may be helpful when considering trade-offs between different methods or when examining model robustness.

References