Number of features vs. number of observations

Question

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?

Answer 1

What you've hit on here is the curse of dimensionality or the p>>n problem (where p is predictors and n is observations). There have been many techniques developed over the years to solve this problem. You can use AIC or BIC to penalize models with more predictors. You can choose random sets of variables and asses their importance using cross-validation. You can use ridge-regression, the lasso, or the elastic net for regularization. Or you can choose a technique, such as a support vector machine or random forest that deals well with a large number of predictors.

Honestly, the solution depends on the specific nature of the problem you are trying to solve.

Answer 2

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).

If you use regularisation, then in principal, (an upper bound on) the generalisation error is independent of the number of features (see Vapnik's work on the support vector machine). However that leaves the problem of finding a good value for the regularisation parameter (cross-validation is handy).

Answer 3

You are probably over impression from the classical modelling, which is vulnerable to the Runge paradox-like problems and thus require some parsimony tuning in post-processing.
However, in case of machine learning, the idea of including robustness as an aim of model optimization is just the core of the whole domain (often expressed as accuracy on unseen data). So, well, as long as you know your model works good (for instance from CV) there is probably no point to bother.

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.

Answer 4

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.