# Number of features vs. number of observations

Are there any papers/books/ideas about the relationship between the number of features and the number of observations one needs to have to train a "robust" classifier?

For example, assume I have 1000 features and 10 observations from two classes as a training set, and 10 other observations as a testing set. I train some classifier X and it gives me 90% sensitivity and 90% specificity on the testing set. Let's say I am happy with this accuracy and based on that I can say it is a good classifier. On the other hand, I've approximated a function of 1000 variables using 10 points only, which may seem to be not very... robust?

• One of my absolutely most valuable books over the years has been Tinsley and Brown's Handbook. There are many places in the book where this topic is discussed, by different contributing authors. Commented May 8, 2011 at 18:51

I suspect that no such rules of thumb will be generally applicable. Consider a problem with two gaussian classes centered on $\vec{+1}$ and $\vec{-1}$, both with covariance matrix of $0.000001*\vec{I}$. In that case, you only need two samples, one from either class to get perfect classification, almost regardless of the number of features. At the other end of the spectrum if both classes are centered on the origin with covariance $\vec{I}$, no amount of training data is going to give you a useful classifier. At the end of the day, the amount of samples you need for a given number of features depends on how the data are distributed, in general, the more features you have, the more data you will need to adequately describe the distribution of the data (exponential in the number of features if you are unlucky - see the curse of dimensionality mentioned by Zach).
The real problem with $p\gg n$ in case of ML are the irrelevant attributes -- mostly because some set of them may become more usable for regenerating decision than the truly relevant ones due to some random fluctuations. Obviously this issue has nothing to do with parsimony, but, same as in classical case, ends up in terrible loss of generalization power. How to solve it is a different story, called feature selection -- but the general idea is to pre-process the data to kick out the noise rather than putting constrains on the model.