Should feature selection be performed only on training data (or all data)? Should be feature selection performed only on training data (or all data)? I went through some discussions and papers such as Guyon (2003) and Singhi and Liu (2006), but still not sure about right answer.
My experiment setup is as follows:


*

*Dataset: 50-healthy controls & 50-disease patients  (cca 200 features that can be relevant to disease prediction).

*Task is to diagnose disease based on available features.


What I do is 


*

*Take whole dataset and perform feature selection(FS). I keep only selected features for further processing

*Split to test and train, train classifier using train data and selected features. Then, apply classifier to test data (again using only selected features). Leave-one-out validation is used.

*obtain classification accuracy

*Averaging: repeat 1)-3) N times. $N=50$ (100).


I would agree that doing FS on whole dataset can introduce some bias, but my opinion is that it is "averaged out" during averaging (step 4). Is that correct? (Accuracy variance is $<2\%$)
1 Guyon, I. (2003) "An Introduction to Variable and Feature Selection", The Journal of Machine Learning Research, Vol. 3, pp. 1157-1182
2 Singhi, S.K. and Liu, H. (2006) "Feature Subset Selection Bias for Classification Learning", Proceeding ICML '06 Proceedings of the 23rd international conference on Machine learning, pp. 849-856 
 A: Just as an addendum to the answers here, I've got two links that really helped me understand why this isn't a good procedure:


*

*http://nbviewer.jupyter.org/github/cs109/content/blob/master/lec_10_cross_val.ipynb 

*https://www.youtube.com/watch?v=S06JpVoNaA0
Edit: as requested, a brief explanation of the contents of the links: 
Suppose I'm training a classifier, and I have a dataset of 1000 samples, with 1 million features each. I cannot process them all, so I need less features (say, I can compute 300 features). I also have a held-out test set of 100 samples to accurately estimate my out-of-sample, real-world accuracy.
If I filter my 1 million features down to 300, by selecting those features with a highest correlation to the targets of my whole dataset, I am making a mistake (because I'm introducing overfitting which cannot be detected by Cross Validation later on). My held-out set will show this by spitting back a bad accuracy value.
According to the above links, the correct way to do it is to divide my dataset into a training set and Cross-Validation set, and then tune my model (filtering out features, etc) based on this training set and it's associated CV score. If I'm using K-folds, I must tune from scratch each time I make a split/fold, and then average the results. 
Programatically, you do the following:


*

*Keep aside a part of your dataset as a hold-out set.

*Split the remainder of your dataset (henceforth called T1) into K-folds.

*In a for-loop from i=1 to K, do the following:


*

*select the i'th fold as your CV set, and the remaining samples as your training set (henceforth called Ti).

*Do whatever feature engineering and feature selection you want: filter features, combine them etc. 

*Convert both your CV set (the current fold, called CVi) and your current training set Ti to one with the appropriate features. 

*Train your model on the training set  Ti

*Get the score from the current fold, CVi. Append this score to a list holding all the scores.


*Now, your list has the score of each fold, so you average it, getting the K-folds score. 


It's really important that you perform the feature engineering inside the loop, on the sub-training set, Ti, rather than on the full training set, T1. 
The reason for this is that when you fit/feature engineer for Ti, you test on CVi, which is unseen for that model. Whereas, if you fit/feature engineer on T1, any CV you choose has to be a subset T1, and so you will be optimistically biased, i.e. you will overfit, because you're training and testing on the same data samples. 
A really good StackExchange answer is this one, which really explains it more in depth and with an example of the code. Also see this as an addendum.
A: The Efron-Gong "optimism" bootstrap is very good for this.  The idea is to use all available data for developing the predictive model, and using all data for estimating the likely future performance of that same model.  And your sample size is too small by a factor of 100 for any split-sample approaches to work.
To use the bootstrap correctly you have to program all steps that used $Y$ and have them repeated afresh at each resample.  Except for feature selection, here's a good example: Interpreting a logistic regression model with multiple predictors
A: The procedure you are using will result in optimistically biased performance estimates, because you use the data from the test set used in steps 2 and 3 to decide which features used in step 1.  Repeating the exercise reduces the variance of the performance estimate, not the bias, so the bias will not average out.  To get an unbiased performance estimate, the test data must not be used in any way to make choices about the model, including feature selection.
A better approach is to use nested cross-validation, so that the outer cross-validation provides an estimate of the performance obtainable using a method of constructing the model (including feature selection) and the inner cross-validation is used to select the features independently in each fold of the outer cross-validation.  Then build your final predictive model using all the data.
As you have more features than cases, you are very likely to over-fit the data simply by feature selection.  It is a bit of a myth that feature selection should be expected to improve predictive performance, so if that is what you are interested in (rather than identifying the relevant features as an end in itself) then you are probably better off using ridge regression and not performing any feature selection.  This will probably give better predictive performance than feature selection, provided the ridge parameter is selected carefully (I use minimisation of Allen's PRESS statistic - i.e. the leave-one-out estimate of the mean-squared error).
For further details, see Ambroise and McLachlan, and my answer to this question.
