17
$\begingroup$

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?

$\endgroup$
14
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ I find this answer somewhat misleading as a crucial assumption of the Hua paper is missing: The features Hua et al. consider in the linked paper are all informative, which is not what you can expect to have in practice. IMHO this should clearly be stated as the IMHO most common type of uncorrelated "features" are uninformative measurement channels. $\endgroup$ – cbeleites unhappy with SX Mar 23 '18 at 16:09
  • $\begingroup$ Wrt. the learning curves: OP probably won't be able to use them with 2×20 cases, as they cannot be measured with a useful precision from so few cases. Hua briefly mentions this, and we discussed this difficulty rather in detail in the paper I linked in my answer below. $\endgroup$ – cbeleites unhappy with SX Mar 23 '18 at 16:13
8
$\begingroup$

from my own experience: In one case, I have worked with 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.

| improve this answer | |
$\endgroup$
  • $\begingroup$ @Bashar Haddad: Correct me if I'm wrong (as I'm new to both computer vision and ML), isn't HOG feature actually a high dimensional vector(in my case, I was getting 1764 -dimensional HOG features). So when you say 9 features and one of them is HOG, aren't you actually getting a high dimensional feature space for HOG alone? $\endgroup$ – Mathmath Jul 17 '17 at 7:37
  • 1
    $\begingroup$ In literature they use the word feature to either indicate the feature type or the dimension index. So when I say I am using 6 features, this means I am using 6 feature types, each of them is (1 x D) vector. if I am talking about Hog feature type, each dimension can be a feature. $\endgroup$ – Bashar Haddad Jul 17 '17 at 23:44
3
$\begingroup$

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.

| improve this answer | |
$\endgroup$
2
$\begingroup$

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.

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.