An introduction to Variable and Feature Selection

The objectives of variable selection are:
- Improving the prediction performance of the predictors. This point implies that with large amount of variables the performance may degrade. Is it only due to noise and overfitting?
- Providing faster and more cost-efficient predictors
- Providing better understanding of the underlying process that generated the data

Has a good summary of how to approach the feature selection problem (use domain knowledge, normalize features, construct conjunctive features or products of features in the case of interdependence, use variable ranking for initial filtering, detect outlier examples by using the top ranked variables, try linear (fast) predictor and use forward or backward selection method, etc…)

Variable ranking is a filtering method, very computation-efficient (scalable). It is robust against over fitting. A correlation (Pearson) based ranking for regression enforces ranking according to goodness of linear fit of individual variables to the output values. The paper presents several ways of extending this idea for classification (use a threshold to differentiate values). Another possible way is Information Theoretic ranking criteria, which is the measure of dependency between the density of a variable and the density of the target.

Noise reduction and consequentially better class separation may be obtained by adding variables that are presumably redundant (i.i.d variables are not truly redundant)

Perfectly correlated variables are truly redundant in the sense that no additional information is gained by adding them.

A variable that is completely useless by itself can provide performance improvement when taken with others. Two variables that are useless by themselves can be useful together.

The variable ranking approaches, although scalable, suffer from non-optimality due to concentration of only one variable without taking into account the content of others. The Variable Subset Selection techniques were developed to tackle this problem. There are three main types of variable subset selection solutions: (a) Wrappers – utilize the learning machine of interest as a black box to score subsets of variables according to their predictive power; (b) Filters – select subset of variables as a pre-processing step, independently of the chosen predictor (learning machine); (c) Embedded methods – perform variable selection in the process of training and are usually specific to given learning machines.

Wrappers (see Kohavi and John, 1997) usually considered a brute force approach, requiring large amounts of computation. However, greedy strategies are particularly computationally advantageous and robust against overfitting (Reunanen, 2003). This can be divided into forward selection and backward elimination. Forward method are more efficient by may produce weaker subsets than those found by the backward elimination method (because in forward selection the importance of variables is not assessed in the context of other variables).

Embedded methods are more efficient that wrappers in several respencts: (a) they make better use of available data by not needing to split the training data into a training and validation set; (b) the reach the solution faster by avoiding retraining a predictor from scratch for every variable subset investigated.

Filters are argued to be faster than wrappers and provide a generic selection of variables, not tuned for/by a given learning machine. Also, filters can be used as a preprocessing step to reduce space dimensionality and overcome overfitting. It may be possible to use wrapper with a linear predictor as a filter and then train with a more complex non-linear predictor. When a number of examples is small compared to the number of variables, one may need to resort to selecting variables with correlation coefficients to avoid overfitting. Another method of filtering is a family of Markov blanket algorithms (a Markov blanket of a variable x, is a set of other variables that render x “unnecessary”).

One way of “stabilize” variable selection is to use several “bootstraps”. The variable selection process is repeated with sub-samples of the training data. The union of the subsets of variables selected in the various bootstraps is taken as the final “stable” subset.