8

My question is about cross validation when there are many more variables than observations. To fix ideas, I propose to restrict to the classification framework in very high dimension (more features than observation).

Problem: Assume that for each variable $i=1,\dots,p$ you have a measure of importance $T[i]$ than exactly measure the interest of feature $i$ for the classification problem. The problem of selecting a subset of feature to reduce optimally the classification error is then reduced to that of finding the number of features.

Question: What is the most efficient way to run cross validation in this case (cross validation scheme)? My question is not about how to write the code but on the version of cross validation to use when trying to find the number of selected feature (to minimize the classification error) but how to deal with the high dimension when doing cross validation (hence the problem above may be a bit like a 'toy problem' to discuss CV in high dimension).

Notations: $n$ is the size of the learning set, p the number of features (i.e. the dimension of the feature space). By very high dimension I mean p>>n (for example $p=10000$ and $n=100$).

robin girard
  • 6,335
  • 6
  • 46
  • 60
  • But still, what do you want to measure with CV and in what purpose? To get a cutoff of attribute number? –  Jul 28 '10 at 11:15
  • @mbq: thanks for the advice. I have edited the question accordingly, hope it is more clear now ! – robin girard Jul 28 '10 at 11:26

2 Answers2

6

You miss one important issue -- there is almost never such thing as T[i]. Think of a simple problem in which the sum of two attributes (of a similar amplitude) is important; if you'd remove one of them the importance of the other will suddenly drop. Also, big amount of irrelevant attributes is the accuracy of most classifiers, so along their ability to assess importance. Last but not least, stochastic algorithms will return stochastic results, and so even the T[i] ranking can be unstable. So in principle you should at least recalculate T[i] after each (or at least after each non trivially redundant) attribute is removed.

Going back to the topic, the question which CV to choose is mostly problem dependent; with very small number of cases LOO may be the best choice because all other start to reduce to it; still small is rather n=10 not n=100. So I would just recommend random subsampling (which I use most) or K-fold (then with recreating splits on each step). Still, you should also collect not only mean but also the standard deviation of error estimates; this can be used to (approximately) judge which changes of mean are significant ans so help you decide when to cease the process.

  • said "You miss one important issue -- there is almost never such thing as T[i]" I wanted the answer to focus on the problem of selecting the number of variables. Construction (which I agree are not perfect) of T[i] are discussed here http://stats.stackexchange.com/questions/490/variable-selection-procedure-for-binary-classification Sometime, it is also usefull to discuss problem separatly. – robin girard Jul 28 '10 at 15:21
  • 1
    @robin But here you can't tear those apart. The most of algorithms mentions in that question were created to address this issue -- forward selection is to remove correlated features, backward elimination is to stabilize the importance measure, mcmc is to include correlated features... –  Jul 28 '10 at 15:37
  • @robin the idea of making some exact importance measure was a base for so-called filter algorithms which are now mainly abandoned since they were just too weak. They have the advantage that they are computationally cheap, still this is not worth it. –  Jul 28 '10 at 15:42
0

That's a good question, and that tends to hit more of what's referred to ensemble learners and model averaging (I'll provide links below):

When you're in high dimensional settings, the stability of your solution (i.e., what features/variables are selected) may be lacking because individual models may choose 1 among many collinear, exchangeable variables that by-and-large carry the same signal (among one of many reasons). Below are a couple of strategies on how to address this.

In bayesian model averaging for example,

Hoeting, Jennifer A., et al. "Bayesian model averaging: a tutorial." Statistical science (1999): 382-401.

you construct many models (say 100), and each of which is constructed with a subset of the original features. Then, each individual model determines which of the variables it saw was significant, and each model is weighed by data likelihood, giving you a nice summary of how to "judge" the effectiveness of variables in 'cross-validation" sort of way. If you know a-priori that some features are highly correlated, you can induce a sampling scheme such that they're never selected together (or if you have a block-correlation structure then you choose elements of different blocks in your variance-covariance matrix)

In a machine learning type setting: look at "ensemble feature selection". This paper (one example)

Neumann, Ursula, Nikita Genze, and Dominik Heider. "EFS: an ensemble feature selection tool implemented as R-package and web-application." BioData mining 10.1 (2017): 21.

determines feature significance across of a variety of "importance" metrics to make the final feature selection.

I would say that the machine learning route might be better b/c linear models (w/ feature selection) saturate at p = n b/c of their optimization re-formulation (see this post If p > n, the lasso selects at most n variables). But as long as you can define and justify a good objective criterion on how you 'cross-validate' the feature selection, then you're off to a good start.

Hope this helps!

Samir Rachid Zaim
  • 746
  • 3
  • 15