Forward-backward selection with early dropping

DOI10.48550/ARXIV.1705.10770zbMATH Open1483.68279arXiv1705.10770MaRDI QIDQ4633015FDOQ4633015

Authors: Giorgos Borboudakis, Ioannis Tsamardinos, Giorgos Borboudakis, Ioannis Tsamardinos 

Publication date: 2 May 2019

Abstract: 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.

Full work available at URL: https://arxiv.org/abs/1705.10770

Recommendations

• Improved variable selection with forward-lasso adaptive shrinkage
• 10.1162/153244303322753616
• An improvement on floating search algorithms for feature subset selection
• scientific article; zbMATH DE number 1691504
• A greedy feature selection algorithm for big data of high dimensionality

zbMATH Keywords

feature selectionBayesian networksforward selectionmaximal ancestral graphsMarkov blanket discovery

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Probabilistic graphical models (62H22) Ridge regression; shrinkage estimators (Lasso) (62J07) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Cites Work

• Applied Linear Regression
• Causation, prediction, and search
• Estimating the dimension of a model
• Least angle regression. (With discussion)
• Extended Bayesian information criteria for model selection with large model spaces
• Title not available (Why is that?)
• 10.1162/153244303322753616
• Title not available (Why is that?)
• Maximum Likelihood Estimation of Misspecified Models
• Random forests
• Likelihood Ratio Tests for Model Selection and Non-Nested Hypotheses
• Bayesian backfitting. (With comments and a rejoinder).
• Support-vector networks
• Title not available (Why is that?)
• Estimating high-dimensional directed acyclic graphs with the PC-algorithm
• The Group Lasso for Logistic Regression
• Title not available (Why is that?)
• Title not available (Why is that?)
• Variable selection for generalized linear mixed models by \(L_1\)-penalized estimation
• Regression modeling strategies. With applications to linear models, logistic regression and survival analysis
• Ancestral graph Markov models.
• Estimation for high-dimensional linear mixed-effects models using \(\ell_1\)-penalization
• Consistent model selection criteria on high dimensions
• Tuning Parameter Selection in High Dimensional Penalized Likelihood
• Model Selection Principles in Misspecified Models
• Sequential selection procedures and false discovery rate control
• The performance of the likelihood ratio test when the model is incorrect
• Markov Properties for Acyclic Directed Mixed Graphs
• Compressed Sensing and Source Separation
• Title not available (Why is that?)
• Local causal and Markov blanket induction for causal discovery and feature selection for classification. Part I: Algorithms and empirical evaluation
• Orthogonal least squares methods and their application to non-linear system identification
• Adaptive Lasso and group-Lasso for functional Poisson regression
• Conditional likelihood maximisation: a unifying framework for information theoretic feature selection
• A greedy feature selection algorithm for big data of high dimensionality
• Bootstrapping the out-of-sample predictions for efficient and accurate cross-validation
• Model selection procedure for high‐dimensional data
• A stepwise regression algorithm for high-dimensional variable selection
• Adjusting Stepwisep-Values in Generalized Linear Models

Cited In (9)

• dcorVS
• Latent theme dictionary model for finding co-occurrent patterns in process data
• Title not available (Why is that?)
• Extending greedy feature selection algorithms to multiple solutions
• Domain knowledge-enhanced variable selection for biomedical data analysis
• Streamwise feature selection
• Squared error-based shrinkage estimators of discrete probabilities and their application to variable selection
• Features Selection as a Nash-Bargaining Solution: Applications in Online Advertising and Information Systems
• A greedy feature selection algorithm for big data of high dimensionality

Uses Software

• LIBSVM
• CLOP
• MXM

This page was built for publication: Forward-backward selection with early dropping

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4633015)