Forward-Backward Selection with Early Dropping
This work addresses the computational bottleneck in feature selection for high-dimensional data, offering a faster alternative to existing methods like LASSO in scenarios where efficient LASSO algorithms are unavailable.
The paper tackles the computational inefficiency of forward-backward selection for feature selection by introducing a heuristic that temporarily discards conditionally independent variables, preserving predictive accuracy. The result shows a two-order-of-magnitude speedup in high-dimensional problems while selecting fewer variables and matching LASSO's performance when restricted to the same number of variables.
Forward-backward selection is one of the most basic and commonly-used feature selection algorithms available. It is also general and conceptually applicable to many different types of data. In this paper, we propose a heuristic that significantly improves its running time, while preserving predictive accuracy. The idea is to temporarily discard the variables that are conditionally independent with the outcome given the selected variable set. Depending on how those variables are reconsidered and reintroduced, this heuristic gives rise to a family of algorithms with increasingly stronger theoretical guarantees. In distributions that can be faithfully represented by Bayesian networks or maximal ancestral graphs, members of this algorithmic family are able to correctly identify the Markov blanket in the sample limit. In experiments we show that the proposed heuristic increases computational efficiency by about two orders of magnitude in high-dimensional problems, while selecting fewer variables and retaining predictive performance. Furthermore, we show that the proposed algorithm and feature selection with LASSO perform similarly when restricted to select the same number of variables, making the proposed algorithm an attractive alternative for problems where no (efficient) algorithm for LASSO exists.