Stracuzzi and Utgoff (2004) propose a form of wrapper method, called randomized variable elimination to avoid the cost of running the learning algorithm several times to evaluate the subset quality. Randomized variable elimination takes large steps through the space of possible input sets. Randomized variable elimination technique uses a cost function to achieve a balance between the probability of failing to select correct subset of variables and the computational cost required to run the algorithm several times.
A hypothesis is first formed on the complete set of 'n' inputs. Then, 'k' random variables are removed and the hypothesis is formed on remaining (n-k) inputs. The accracy of the first formed hypothesis is compared with the accuracy of the second hypothesis. If it is observed that the performance doesn't degrade much the 'k' variables are removed permanently but the perfomance degrades significantly then the 'k' variables are replaced back.
Below is a high level generic algorithm for randomized variable elimination where L is the learning algorithm, n is the number of input variables, r is actual relevant variables.