Any "rules of thumb" on number of features versus number of instances? (small data sets)

Question

I am wondering, if there are any heuristics on number of features versus number of observations. Obviously, if a number of features is equal to the number of observations, the model will overfit. By using sparse methods (LASSO, elastic net) we can remove several features to reduce the model.

My question is (theoretically): before we use metrics to assess the model selection are there any empirical observations which relate the optimal number of features to the number of observations?

For example: for a binary classification problem with 20 instances in each class, is there any upper limit on the number of features to use?

Answer 1

Multiple papers have opined that

only in rare cases is there a known distribution of the error as a function of the number of features and sample size.

The error surface for a given set of instances, and features, is a function of the correlation (or lack of) between features.

This paper suggests the following:

• For uncorrelated features, the optimal feature size is $ N-1 $ (where $ N $ is sample size)
• As feature correlation increases, and the optimal feature size becomes proportional to $ \sqrt N $ for highly correlated features.

Another (empirical) approach that could be taken, is to draw the learning curves for different sample sizes from the same dataset, and use that to predict classifier performance at different sample sizes. Here's the link to the paper.

Answer 2

From my own experience:In one case, I worked with a real database that is very small (300 images) with many classes, severe data imbalance problem and I ended up with using 9 features: SIFT, HOG, Shape context, SSIM, GM and 4 DNN-based features. In another case, I worked with very large database (> 1 M images) and ended up with using only HOG feature. I think there is no direct relation between the number of instances and the number of features required to achieve high accuracy. BUT: the number of classes, the similarity between classes and variation within the same class (these three parameters) may affect the number of features. when having larger database with many classes and large similarity between classes and large variation within the same class you need more features to achieve high accuracy. REMEMBER: the quality of used features is more important than the number of used features.

Answer 3

It depends... but of course that answer gets you nowhere.

He is some rule of thumb for model complexity: Learning from data - VC dimension

"Very roughly" you need 10 data points for each model parameter. And number of model parameters can be similar to number of features.

Answer 4

Bit late to the party, but here are some heuristics.

binary classification problem with 20 instances in each class, is there any upper limit on the number of features to use?

• For training of linear classifiers, 3 - 5 independent cases per class and feature are recommended. This limit gives you reliably stable models, it doesn't guarantee a good model (this is not possible: you could have uninformative data where no model could achieve good generalization performance)

• However, for sample sizes as small as your scenario, verification (validation) rather than training is the bottleneck, and verification depends on absolute number of test cases rather than cases relative to model complexity: as a rule of thumb, you need ≈ 100 test cases in the denominator to estimate a proportion with a confidence interval that is not more than 10 %points wide.

  Unfortunately this also means that you basically cannot get the empirical learning curve for your application: you cannot measure it precisely enough, and in practice you'd anyways have huge difficulties extrapolating it because for training you react to the small sample size by restricting your model complexity - and you'd relax this with increasing sample size.

  See our paper for details: Beleites, C. and Neugebauer, U. and Bocklitz, T. and Krafft, C. and Popp, J.: Sample size planning for classification models. Anal Chim Acta, 2013, 760, 25-33.
  DOI: 10.1016/j.aca.2012.11.007
  accepted manuscript on arXiv: 1211.1323

• I've never had anything close to these recommendations (spectroscopy data, also for medical applications). What I do then is: I very closely measure model stability as part of the modeling and the verification process.