Is using the same data for feature selection and cross-validation biased or not?

We have a small dataset (about 250 samples * 100 features) on which we want to build a binary classifier after selecting the best feature subset. Lets say that we partition the data into:

Training, Validation and Testing

For feature selection, we apply a wrapper model based on selecting features optimizing performance of classifiers X, Y and Z, separately. In this pre-processing step, we use training data for training the classifiers and validation data for evaluating every candidate feature subset.

At the end, we want to compare the different classifiers (X, Y and Z). Of course, we can use the testing part of the data to have a fair comparison and evaluation. However in my case, the testing data would be really small (around 10 to 20 samples) and thus, I want to apply cross-validation for evaluating the models.

The distribution of the positive and negative examples is highly ill-balanced (about 8:2). So, a cross-validation could miss-lead us in evaluating the performance. To overcome this, we plan to have the testing portion (10-20 samples) as a second comparison method and to validate the cross-validation.

In summary, we are partitioning data into training, validation and testing. Training and validation parts are to be used for feature selection. Then, cross-validation over the same data is to be applied to estimate the models. Finally, testing is used to validate the cross-validation given the imbalance of the data.

The question is: If we use the same data (training+validation) used in selecting the features optimizing the performance of classifiers X, Y and Z, can we apply cross-validation over the same data (training+validation) used for feature selection to measure the final performance and compare the classifiers?

I do not know if this setting could lead to a biased cross-validation measure and result in un-justified comparison or not.

• Crossvalidated.com deals with exactly this types of questions. I suggest this Q be moved there. – Roman Luštrik Oct 16 '12 at 8:03
• One suggestion is to apply bootstrapping (from training+validation only) on the data instead of cross-validation. Would this solve the bias problem stated in the question? Still not sure !! – soufanom Oct 17 '12 at 8:48
• Yes, it is biased -- browse Qs in the feature-selection tag on this site, especially this one, or even Wikipedia page about CV. – user88 Oct 17 '12 at 10:13
• Agreed. You can apply the design to randomly simulated data sets and estimate how much bias there is. But I would recommend LOOCV as one answer suggests. – Steve P Oct 17 '12 at 13:25

i think it is biased. What about applying FS in N-1 partition and test on last partition. and combine the features from all fold in some way(union/intersection/ or some problem specific way).

• Leaving a part for testing has been explained in the post. Also, as explained cross-validation is needed for comparing the models. Thus, it is not possible to apply it for feature selection unless we use the nested-cross-validation idea. However, the data set is so small and it is difficult to apply the nested-cross-validation. – soufanom Oct 17 '12 at 10:33

The simple answer is that you should do feature selection on a different dataset than you train on (you're doing this already, so don't change this)---the effect of not doing this is you will overfit your training data. You must also not do feature selection on your test set, as this will inflate estimates of your models' performance (I think you already realise this as well, but I found it a little hard to understand the question precisely).

• finally you should test on the test portion. You can then average scores across these test portions to get an estimate of model performance To make some sense of a classifier performance it should be used on test data that has not been seen or used before. The way I see it if you make any decision based on algorithm performance on some data set then this data set is either training or cross validation, under no circumstances should it be called test data set. – Ivan Oct 15 '12 at 13:21
• Note that I did not say that you should do feature selection on your test data---for each fold, you create training, development and test portions. You train on your training, set free parameters and do feature selection on your development, and then apply final learned models to the test data. As I discussed above, this practice isn't ideal, but you're not explicitly using the test data to set parameters (for each fold the test data is blind until models are fixed, you just get creep across folds) – Ben Allison Oct 15 '12 at 14:53
• I think we agree on the same thing, I just wanted to make clear the distinction between test and C/V data. Model selection is akin to parameter selection so it's best if test data is put aside and not used at all. Having done that you'd be able to safely report on expected performance of the chosen model on any new unseen data. – Ivan Oct 16 '12 at 7:57

Did you try LOOCV? I think it's apt to train, when you have very less training data. To answer your question, that would not give you the best of results simply because it could overfit and give you misleading results, such that your classifier would not perform great on other data, that it has not seen.

• LOOCV at the end is just a kind of cross-validation. We need a solution for the problem in which we have a small data, we want to select good features and finally have a representative measure to evaluate performance. – soufanom Oct 17 '12 at 10:52

You could do the following to compare the performance of the classifiers

Take your training set and train it on every possible feature set. For each feature set, minimize the parameters and build the model such that it fits the training set well. Now, once the models are built for all the feature sets, i.e. you have a model for every feature set, validate the models (built on different feature sets) on the validation set and select that model (built for a particular subset of feature set) that gives the minimum error on the validation set. This way, you ensure that the model built has fit well not just the training set but also the validation set.

Now, take this built model and test it on the testing set. This will tell you how well the classifier performs once it runs on a data set that was neither used for training nor for validation. Also, you have selected that feature set that fits the training set and also the validation set well.

• For the wrapper model of feature selection, both training and validation datasets should be supported. In the wrapper model, we are training and testing a classifier given a candidate feature subset. Thus, giving only a training set to this model is not sufficient. The question is: if the same data used for feature selection is used for comparison but using CV, are we still biased and by which degree? – soufanom Oct 14 '12 at 20:05

If possible it is best to hold back some data for additional cross validation. For example you can use it to validate your algorithms by building learning curves. These curves must be build on data set that has not been used before.

Even if you want to simply select an algorithm that gives you highest F1 score, you'd need to use extra cross validation data set to do that. Test set must be reserved to report final accuracy of your solution (expected performance of the chosen classifier on unseen data).

• You answer is stated in my question as a technique I am aware about. The question is about using the same data for feature selection and cross-validation !! – soufanom Oct 16 '12 at 9:00
• @soufanom I wrote that you need an extra cross validation data set to select best performing classifier, otherwise your results will not be reliable. How can you judge performance of a model by running it on a data set that was used to either train the model or to select parameters. IMHO the only reliable way to judge performance of any classifier is to run it on previously unseen data. I hope this answers your question, if not please refine it and add more information. – Ivan Oct 16 '12 at 10:01

It can be super grossly biased, refer to the chapter of model validation in "Elements of Statistical Learning", It can make model cv accuracy above 70% while the true error rate of any model should be 50% (features are independent of the class).