"Stability" of error estimates with cross validated SVMs

Question

I have a small data set (about 120 rows) with a large number of features (about 600). I'm attempting to train a linear support vector machine and using the following approach:

1) Apply recursive feature elimination with 10-fold cross-validation to reduce the number of features 2) Fit the SVM on the reduced feature space and test with 10-fold cross-validation again.

I'm slightly concerned because the outputs of these steps seem somewhat unstable. Step 1) can produce an "optimal" feature space with anywhere from 6 to 300 features, and seems to produce the best CV scores when it settles on a feature space with about 100 features. The variation is due to the random partitions of the training data during cross-validation, of course.

The best CV scores are in the neighborhood of 0.9, and the worst around 0.6-0.7.

I have read a fair bit about over-fitting during the model selection step, eg http://jmlr.org/papers/v11/cawley10a.html

My question is, should I be concerned? Can I safely accept the better models, or am I subtly overfitting to my dataset? All of the research I've read suggests that overfitting during model selection is attributable to hyperparameter tuning, but I am not tuning anything here. Yet, I feel like the feature selection step may have a similar effect.

Answer 1

Feature selection on 120 data points with 600 features does seem like a regime where concerns about overfitting the validation set could be justified. Because you're doing nested cross validation, you can compare the validation set error to the test set error over iterations of feature selection, similar to the paper you mentioned. This could give a hint about how concerned you should be.

All of the research I've read suggests that overfitting during model selection is attributable to hyperparameter tuning, but I am not tuning anything here. Yet, I feel like the feature selection step may have a similar effect.

Feature selection (as you're implementing it) is a model selection procedure, just like tuning other hyperparameters on the validation set. So, the concerns are identical. You could think of the included features as hyperparameters, e.g. a vector $s$ where $s_i = 1$ if feature $i$ is included, otherwise $0$. The issue is not that hyperparameters are tuned per se. It's that choices about the model are made from a large set of possibilities, by optimizing performance on a small set of data (the validation set, in this case).

As an alternative to recursive feature elimination / wrapper-based feature selection, you might consider an approach that incorporates feature selection directly into the base learning algorithm. For example, $\ell_1$ regularized logistic regression gives sparse weights. During learning, many weights are driven to zero, corresponding to non-selected features. Model selection (e.g. using cross validation) then consists of setting only a single hyperparameter: the penalty strength, which determines the number of selected features. This reduces the risk of overfitting the validation set, and is also less greedy than stepwise feature selection (greedy strategies are more prone to suboptimal choices). Along similar lines, check out Cawley & Talbot (2014) for a nice discussion of the underlying issues. They do feature selection for SVMs using automatic relevance determination (ARD) kernels, and reduce overfitting during model selection by tuning kernel parameters as part of the base learning procedure.

Cawley and Talbot (2014). Kernel learning at the first level of inference.