Feature selection for "final" model when performing cross-validation in machine learning

Question

I am getting a bit confused about feature selection and machine learning and I was wondering if you could help me out. I have a microarray dataset that is classified into two groups and has 1000s of features. My aim is to get a small number of genes (my features) (10-20) in a signature that I will in theory be able to apply to other datasets to optimally classify those samples. As I do not have that many samples (<100), I am not using a test and training set but using Leave-one-out cross-validation to help determine the robustness. I have read that one should perform feature selection for each split of the samples i.e.

1. Select one sample as the test set
2. On the remaining samples perform feature selection
3. Apply machine learning algorithm to remaining samples using the features selected
4. Test whether the test set is correctly classified
5. Go to 1.

If you do this, you might get different genes each time, so how do you get your "final" optimal gene classifier? i.e. what is step 6.

What I mean by optimal is the collection of genes that any further studies should use. For example, say I have a cancer/normal dataset and I want to find the top 10 genes that will classify the tumour type according to an SVM. I would like to know the set of genes plus SVM parameters that could be used in further experiments to see if it could be used as a diagnostic test.

Answer 1

Whether you use LOO or K-fold CV, you'll end up with different features since the cross-validation iteration must be the most outer loop, as you said. You can think of some kind of voting scheme which would rate the n-vectors of features you got from your LOO-CV (can't remember the paper but it is worth checking the work of Harald Binder or Antoine Cornuéjols). In the absence of a new test sample, what is usually done is to re-apply the ML algorithm to the whole sample once you have found its optimal cross-validated parameters. But proceeding this way, you cannot ensure that there is no overfitting (since the sample was already used for model optimization).

Or, alternatively, you can use embedded methods which provide you with features ranking through a measure of variable importance, e.g. like in Random Forests (RF). As cross-validation is included in RFs, you don't have to worry about the $n\ll p$ case or curse of dimensionality. Here are nice papers of their applications in gene expression studies:

1. Cutler, A., Cutler, D.R., and Stevens, J.R. (2009). Tree-Based Methods, in High-Dimensional Data Analysis in Cancer Research, Li, X. and Xu, R. (eds.), pp. 83-101, Springer.
2. Saeys, Y., Inza, I., and Larrañaga, P. (2007). A review of feature selection techniques in bioinformatics. Bioinformatics, 23(19): 2507-2517.
3. Díaz-Uriarte, R., Alvarez de Andrés, S. (2006). Gene selection and classification of microarray data using random forest. BMC Bioinformatics, 7:3.
4. Diaz-Uriarte, R. (2007). GeneSrF and varSelRF: a web-based tool and R package for gene selection and classification using random forest. BMC Bioinformatics, 8: 328

Since you are talking of SVM, you can look for penalized SVM.

Answer 2

In principle:

Make your predictions using a single model trained on the entire dataset (so there is only one set of features). The cross-validation is only used to estimate the predictive performance of the single model trained on the whole dataset. It is VITAL in using cross-validation that in each fold you repeat the entire procedure used to fit the primary model, as otherwise you can end up with a substantial optimistic bias in performance.

To see why this happens, consider a binary classification problem with 1000 binary features but only 100 cases, where the cases and features are all purely random, so there is no statistical relationship between the features and the cases whatsoever. If we train a primary model on the full dataset, we can always achieve zero error on the training set as there are more features than cases. We can even find a subset of "informative" features (that happen to be correlated by chance). If we then perform cross-validation using only those features, we will get an estimate of performance that is better than random guessing. The reason is that in each fold of the cross-validation procedure there is some information about the held-out cases used for testing as the features were chosen because they were good for predicting, all of them, including those held out. Of course the true error rate will be 0.5.

If we adopt the proper procedure, and perform feature selection in each fold, there is no longer any information about the held out cases in the choice of features used in that fold. If you use the proper procedure, in this case, you will get an error rate of about 0.5 (although it will vary a bit for different realisations of the dataset).

Good papers to read are:

Christophe Ambroise, Geoffrey J. McLachlan, "Selection bias in gene extraction on the basis of microarray gene-expression data", PNAS http://www.pnas.org/content/99/10/6562.abstract

which is highly relevant to the OP and

Gavin C. Cawley, Nicola L. C. Talbot, "On Over-fitting in Model Selection and Subsequent Selection Bias in Performance Evaluation", JMLR 11(Jul):2079−2107, 2010 http://jmlr.csail.mit.edu/papers/v11/cawley10a.html

which demonstrates that the same thing can easily ocurr in model selection (e.g. tuning the hyper-parameters of an SVM, which also need to be repeated in each iteration of the CV procedure).

In practice:

I would recommend using Bagging, and using the out-of-bag error for estimating performance. You will get a committee model using many features, but that is actually a good thing. If you only use a single model, it will be likely that you will over-fit the feature selection criterion, and end up with a model that gives poorer predictions than a model that uses a larger number of features.

Alan Millers book on subset selection in regression (Chapman and Hall monographs on statistics and applied probability, volume 95) gives the good bit of advice (page 221) that if predictive performance is the most important thing, then don't do any feature selection, just use ridge regression instead. And that is in a book on subset selection!!! ;o)

Answer 3

To add to chl: When using support vector machines, a highly recommended penalization method is the elastic net. This method will shrink coefficients towards zero, and in theory retains the most stable coefficients in the model. Initially it was used in a regression framework, but it is easily extended for use with support vector machines.

The original publication : Zou and Hastie (2005) : Regularization and variable selection via the elastic net. J.R.Statist.Soc. B, 67-2,pp.301-320

Elastic net for SVM : Zhu & Zou (2007): Variable Selection for the Support Vector Machine : Trends in Neural Computation, chapter 2 (Editors: Chen and Wang)

improvements on the elastic net Jun-Tao and Ying-Min(2010): An Improved Elastic Net for Cancer Classification and Gene Selection : Acta Automatica Sinica, 36-7,pp.976-981

Answer 4

As step 6 (or 0) you run the feature detection algorithm on the entire data set.

The logic is the following: you have to think of cross-validation as a method for finding out the properties of the procedure you are using to select the features. It answers the question: "if I have some data and perform this procedure, then what is the error rate for classifying a new sample?". Once you know the answer, you can use the procedure (feature selection + classification rule development) on the entire data set. People like leave-one-out because the predictive properties usually depend on the sample size, and $n-1$ is usually close enough to $n$ not to matter much.

Answer 5

This is how I select features. Suppose based on certain knowledge, there are 2 models to be compared. Model A uses features no.1 to no. 10. Model B uses no.11 to no. 20. I will apply LOO CV to model A to get its out-of-sample performance. Do the same to model B and then compare them.

Answer 6

I'm not sure about classification problems, but in the case of feature selection for regression problems, Jun Shao showed that Leave-One-Out CV is asymptotically inconsistent, i.e. the probability of selecting the proper subset of features does not converge to 1 as the number of samples increases. From a practical point of view, Shao recommends a Monte-Carlo cross-validation, or leave-many-out procedure.