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.
 A: 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).
If you've divided your test set into training, validation and testing already, then there's no particular reason to do cross-validation unless you have so little data that your test set is too small to draw strong conclusions from. Many researchers have a dislike of cross validation because if used to drive model development (by which I mean, you tweak things, then run cross validation to see how they do, then tweak them some more etc.) you effectively have access to your test data and this can lead you to overestimate your performance on truly unseen data. If your data is so small that you have no choice but to do cross validation, the correct way to do this with training, dev and test sets is to explicitly split your data into three parts for each fold---the majority should be used for training, some for development (feature selection in your case, plus any other free parameters that need fitting) and finally you should test on the test portion. You can then average scores across these test portions to get an estimate of model performance: however, as I said, beware that if these scores are used to guide you to approaches you want to use for your problem, you shouldn't expect to get the same score on unseen data that you did from your cross validation.
A: 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). 
A: 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. 
A: 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.
A: 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).
A: 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).
