8
$\begingroup$

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?

Improve this question
$\endgroup$

3 Answers 3

Reset to default
10
$\begingroup$

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.

Improve this answer
$\endgroup$
5
  • 1
    $\begingroup$ 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. $\endgroup$
    – Michael R. Chernick
    Sep 26, 2012 at 16:33
  • 2
    $\begingroup$ 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). $\endgroup$
    – Dikran Marsupial
    Sep 26, 2012 at 16:55
  • 1
    $\begingroup$ @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. $\endgroup$
    – user88
    Sep 26, 2012 at 23:56
  • 1
    $\begingroup$ I wasn't blaming CV. The problem is exhaustive searching, I think.. $\endgroup$
    – Michael R. Chernick
    Sep 27, 2012 at 0:08
  • $\begingroup$ 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. $\endgroup$
    – Dikran Marsupial
    Sep 27, 2012 at 7:57
0
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • 2
    $\begingroup$ 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). $\endgroup$
    – Dikran Marsupial
    Sep 26, 2012 at 16:59
  • $\begingroup$ I agree about the issues Dikran raises on exhaustive search. $\endgroup$
    – Michael R. Chernick
    Sep 26, 2012 at 17:13
0
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$
    – Dikran Marsupial
    Sep 26, 2012 at 19:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.