Randomized Variable Elimination

Variable selection, or the process of identifying input variables that are relevant to a particular learning problem, has recently received much attention in the learning community. Methods that employ the learning algorithm as a part of the selection process (wrappers) have been shown to outperform methods that select variables independent of the learning algorithm (filters), but only at great computational expense. We present a randomized wrapper algorithm for variable elimination that runs in time only a constant factor greater than that of simply learning in the presence of all input variables, provided that the cost of learning grows at least polynomially with the number of inputs.