Can I perform an exhaustive search with cross-validation for feature selection?

I have been reading some of the posts about feature selection and cross-validation but I still have questions about the correct procedure.

Suppose I have a dataset with 10 features and I want to select the best features. Also suppose I am using one-nearest neighbor classifier. Can I perform an exhaustive search using cross-validation to estimate the error rate as guide to choose the best features? Something like the following pseudo code

for i=1:( 2^10 -1)
error(i)= crossval(1-nn, selected_fetures(i))
end

i=find(erro(i)==min(error(i));
selected_fetures= selected_features(i);


What I'm trying to explain in this pseudo code is that I'm running the cross validation for all possible combinations of features and choose the combination that gives the minimum error.

I think that this procedure is correct because I am performing an exhaustive search. The choice of the features was not based on the entire dataset, but on the average error on each partition. Am I overfitting the model with such feature selection?

Yes, you are likely to end up with over-fitting in this case, see my answer to this previous question. The important thing to remember is that cross-validation is an estimate of generalisation performance based on a finite sample of data. As it is based on a finite sample of data, the estimator has a non-zero variance, so to some extent reducing the cross-validation error will result in a combination of model choices that genuinely improve generalisation error and model choices that simply exploit the random peculiarities of the particular sample of data on which it is evaluated. The latter type of model choice is likely to make generalisation performance worse rather than better.

Over-fitting is a potential problem whenever you minimise any statistic based on a finite sample of data, cross-validation is no different.

• Maybe but cross-validation is a big step above resubstitutin as it evaluates the classifier on a set of data not used in the fitted model. – Michael R. Chernick Sep 26 '12 at 16:33
• yes, it is less prone to over-fitting than the resubstitution estimator, but in my experience it is still generally a big enough problem that exhaustive search is likely to be a bad idea. Millar in his monograph on "subset selection in regression" advises to use regularisation rather than feature selection if predictive performance is the important criterion and identifying features is not a primary goal (paraphrasing somewhat). – Dikran Marsupial Sep 26 '12 at 16:55
• @Michael It is not CV that is wrong, it is the idea of strictly minimizing error on a used-features space (or on parameter space, which is a related trap). Even the whole train set is a random subset of reality, thus this optimization is simply stochastic and must be treated accordingly, or you will certainly end up in a non-significant fluctuation -- this is clearly visible when you bootstrap the whole analysis. IMO this way the only option for a better accuracy is a robust modelling technique (regularized or randomized) and for explanatory fs some is-attribute-better-than-noise testing. – user88 Sep 26 '12 at 23:56
• I wasn't blaming CV. The problem is exhaustive searching, I think.. – Michael R. Chernick Sep 27 '12 at 0:08
• yes, it was well worth pointing out that CV is way better than resubstitution for feature selection, as that is still sometimes used, but it is the over-optimisation that is the problem. – Dikran Marsupial Sep 27 '12 at 7:57

I think this is a valid procedure for feature selection which is no more prone to overfitting than other feature selection procedures. The problem with this procedure is that it has large computational complexity and barely can be used for real data sets.

• I don't think this is correct. If sparsity is achieved via regularisation e.g. a LASSO approach, then the set of feature subsets that can be generated is likely to be much smaller than the number investigated by an exhaustive search. This means there is less opportunity for over-fitting as the "model space" is more highly constrained. I wouldn't recommend exhaustive search unless the data set is very large and the number of features is very small (of course it quickly becomes computationally infeasible with the number of features anyway). – Dikran Marsupial Sep 26 '12 at 16:59
• I agree about the issues Dikran raises on exhaustive search. – Michael R. Chernick Sep 26 '12 at 17:13

I think if you do feature selection inside each fold of the cross validation you'll be fine. As posters above state you will overfit in any model using the selected features obtained from the procedure outlined above. This is because all data had some influence on the feature selection routine.

• Sadly this is also incorrect, the problem of over-fitting is likely to arise whenever you minimise a statistic over a finite sample of data. If the statistic has a non-zero variance, some degree of over-fitting is inevitable if the statistic is minimised fully. If you perform feature selection independently in each fold, the resulting cross-validation estimate is (almost) unbiased, but that doesn't mean the model won't be over-fit, just that the performance estimate accounts for the effects of the over-fitting. – Dikran Marsupial Sep 26 '12 at 19:15