Forward-Backward Selection with Early Dropping

• DOI: 10.48550/arxiv.1705.10770
• Publication Date: 2017-01-01
• Authors: Giorgos Borboudakis; Ioannis Tsamardinos
• Keywords: Markov blanket; Lasso; Feature (linguistics)

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