77
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I should say for full disclosure that I have already posted this to the bioconductor list $\endgroup$ – danielsbrewer Sep 2 '10 at 10:26
  • $\begingroup$ Please summarize any bioconductor results back here? $\endgroup$ – Shane Sep 2 '10 at 16:01
39
$\begingroup$

This is a very good question that I faced myself when working with SNPs data... And I didn't find any obvious answer through the literature.

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.

$\endgroup$
  • $\begingroup$ Thanks for that. I'm not particular sold on SVM, just using that as an example. So if you used random trees, you don't have to do cross-validation? Is that right. $\endgroup$ – danielsbrewer Sep 2 '10 at 11:13
  • 7
    $\begingroup$ yes, RFs include a random sampling of variables (typically $\sqrt{p}$) when growing a tree and each tree is based on a boostraped sample of the individuals; variable importance is computed on so-called out-of-bag samples (those not used for building the decision tree) using a permutation technique. The algorithm is repeated for m trees (default m=500) and results are averaged to compensate uncertainty at the tree level (boosting). $\endgroup$ – chl Sep 2 '10 at 11:34
  • 3
    $\begingroup$ It is important that it is called Random Forest not Random Trees; you may have problems with Google. $\endgroup$ – user88 Sep 2 '10 at 11:52
  • 1
    $\begingroup$ +1, good answer and serendipitous for me -- much thanks for the paper references, especially the review. $\endgroup$ – ars Sep 12 '10 at 18:36
  • $\begingroup$ With enough data, wouldn't it be best to hold out a test set, perform loocv on the training set to optimize model parameters, fit the entire train set (and call that the "final" classifier), and then evaluate the final model on the test set? $\endgroup$ – user0 Dec 15 '16 at 2:53
41
$\begingroup$

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)

$\endgroup$
17
$\begingroup$

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

$\endgroup$
9
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I think there's still a generalization issue when using the same sample (1) to assess the classifier classification/prediction performance while tuning its parameters (eventually, with feature selection) and (2) use in turn its predictions on the whole data set. In fact, you are breaking the control exerted on overfitting that was elaborated using cross-validation. Hastie et al. provide a nice illustration of CV pitfalls, esp. wrt. feature selection, in their ESL book, § 7.10.2 in the 2nd edition. $\endgroup$ – chl Sep 2 '10 at 17:16
  • $\begingroup$ @chl: who said anything about tuning parameters? If additional things are performed, they should be repeated during cross-validation as well. Clearly modifying your algorithm until you get good cross-validated error rates is "cheating". BTW, I agree that cross-validation, especially leave-one-out, is not all that great. $\endgroup$ – Aniko Sep 2 '10 at 20:39
  • $\begingroup$ not it is not cheating, since CV shows you the approximation how algorithm will perform on new data. You only need to be sure that you haven't settled on something based on the whole set (this is a leak of information about the structure of the full set, so it can immediately bias all train parts). $\endgroup$ – user88 Sep 3 '10 at 7:15
  • $\begingroup$ @mbq - Ankino is correct, tuning your model to minimise a CV statistic is "cheating" and the CV statistic of the final model will have a substantial optimistic bias. The reason for this is that the CV statistic has a non-negligible variance (as it is evaluated on a finite set of data) and thus if you directly optimise the CV statistic you can over-fit it and you can end up with a model that generalises less well than the one you started with. For a demonstration of this, in a machine learning context, see jmlr.csail.mit.edu/papers/v11/cawley10a.html Solution: Use nested XVAL $\endgroup$ – Dikran Marsupial Sep 3 '10 at 7:40
1
$\begingroup$

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.

$\endgroup$
-1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Oh my, yet again; have you read the title of this article? $\endgroup$ – user88 Sep 2 '10 at 23:49
  • 2
    $\begingroup$ Ok, to be clear -- I'm not saying LOOCV is a good idea for a big number of objects; obviously it is not, but Shao is not applicable here. Indeed in most of cases rules for LMs does not hold for ML. $\endgroup$ – user88 Sep 3 '10 at 0:17
  • 2
    $\begingroup$ It is also questionable whether assymptotic results are of practical use when looking at datasets with a large number of features and comparatively few patterns. In that case the variance of the procedure is likely to be of greater practical importance than bias or consistency. The main value of LOOCV is that for many models it can be implemented at negligible computational expense, so while it has a higher variance than say bootstrapping, it may be the only feasible approach within the computaional budget available. That is why I use it, but I use something else for performance evaluation! $\endgroup$ – Dikran Marsupial Aug 25 '11 at 13:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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