What is the origin of the rule of thumb for the number of samples needed machine learning? I've heard that as a rule of thumb, the number of samples needed for a machine learning algorithm to get accurate results is ten times the number of degrees of freedom. For example, classifying an 8x8 bitmap as being a digit between 0 to 9 would require (8 * 8) * 10 = 640 training examples for accuracy.
If this is correct, where is the origin of this rule of thumb (sources would be appreciated). If it is not correct, what is an accurate method of determining the minimum number of training examples needed for accurate predictions? (again, citations would be appreciated)
Many Thanks,
Michael
 A: The origin is that you have to be worried about overfitting with generalized linear models when you have too many predictors per record (or per case in the most rare class in case of time-to-event, logistic regression or softmax-regression). An initial rule of thumb was 10 or more cases per record, but for some situations that may be too much of a requirement. The point is that below some point point estimates are substantially exagerrated, standard errors do not do what you hope etc. and that predictions might be less reliable as a result.
However, this rule of thumb primarily serves as a warning for when you may be entering dangerous territory with a (non-pentalized) GLM fit using maximum likelihood. To overcome that, you can of course use regularization and still GLMs (e.g. LASSO logistic regression, elastic net etc.) in such situations (especially if you are primarily after predictions), as long as you tune your hyperparameters sensibly (e.g. cross-validation).
Of course, there are plenty of other methods (such as Bayesian methods, gradient boosting, neural networks and so on) that all have their particular ways of achieving some form of regularization (e.g. priors, tuning the number of trees, dropout etc.), which - when used approrpiately - allow us to do useful things with sparse (relative to the amount of predictors) data.
A: The rule of thump is more like a joke and not a rule. Imagine these two cases: (1) digit recognition with hand written data (2) digit recognition based on machine printed digits using a handful of fonts. So what do you think? Clearly, you need more data to capture the variety of input data in the former case.
The only correct rule-of-thump is to test your classification method on your data to see how it performs. It totally depends on the complexity of your data and the power of your classifier.
