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? 
 A: 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.
A: 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.
A: 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.
