Is there a simple method to calculate the minimum number of datalines needed for a machine learning algorithm with x variables?

Question

Here is the problem: I am making a machine learning algorithm that takes the inputs and outputs of some software I've written, and I don't know how many datalines to produce to get results that are a 'good' fit. I realize the answer is 'the more the better' but I'm looking for any sort of minimum requirement. I also realize that the greater the number of variables the greater the number of datalines required.

So I'm looking for a rule of thumb for number of variables to number of datalines.

Answer 1

When you choose the sample number for training, you may consider the trade-off between bias and variance.

One purpose (among many) of training is to estimate the out-of-sample error Eout given the obtained in-sample error Ein. There is such generalization in VC analysis: Eout <= Ein + Omega (also known as Hoeding inequality written in a probability format). So people tend to experimentally observe the changes of Eout and Ein. What they found is: as the sample number increases, the Eout would finally converged to Ein with a simple model; while Eout also converges from a huge value to a relatively constant value as well with a complex model, but still larger enough than Ein. Such VC analysis curve can be equivalently viewed as a bias-variance trade-off curve which indicates the variance decreases as the sample number increases. You can refer this slide for more details. On the other hand, the target complexity also influences on the generalization error. This slide shows a overfit measure as the number of data points changes. You can observe that if the target is complicated, increasing the sample number may not necessarily reduce the overfitting any more (the red region in the figures), yet it is still effective in reducing the overfitting if the target is not complicated.

As analyzed above, the training sample size is usually related to model complexity (number of variates) and target complexity, whereas test sample size can be estimated based on a required accuracy performance. Like @Dikran suggested, you need to try the effects by observing your own learning curve.

Answer 2

in addition to Dikran Marsupial's excellent advise:

While there is no hard minimum requirement for the training data you need,

• There is a rule of thumb that says that with 5* cases per variate in each class you can usually have a stable linear classifier. Now, stable doesn't guarantee good, but unstable will always be bad. Note however, that in many disciplines with very wide data, good models are trained with far less samples.
  * I've also seen 3 and 6, but that's the same order of magnitude.
• you can calculate minimum sample sizes required for testing: usually, building a good model is not sufficient. You also need to show that the model performs well. For relatively easy problems for which, however, only small sample sizes are available, this can actually be the harder part of the problem.
  Not sure whether it applies to your scenario, though: you may be able to generate enough independent rows that this is not the concern.
  Note also that classification performance measures that are proportions of test cases (overall accuracy, sensitivity, specificity, predictive values, precision, recall, etc.) are subject to very high variance and thus need large test sample sizes. This can also cause considerable difficulties with the learning curve (see the paper below for illustrations). Frank Harrell will tell you that better measures, e.g. Brier's score, should be used (see e.g. the discussion linked below). However, depending on your field, you may have to report the proportions.

Here's a paper we wrote about this: 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

See also: How large a training set is needed?

Answer 3

There are no useful rules of thumb for this as the number of patterns required strongly depends on the nature of the problem, in particular the more complex the form of underlying relationship between the variables, the more data you will need to estimate it, the more noise corrupting the data, the more data you are likely to need to average out the effects of the noise. There is also a fairly strong dependence on the nature of the machine learning algorithm as well, if the technique is well suited to the problem you will need less data, if it is not well suited, you will need more data.

At the end of the day, there is no minimum amount of data that you need to perform inference, the more data you have the more confident you can be of your inference, but it is generally a smooth relationship.

I would advise generating a learning curve - a plot of the test set error as a function of the number of training patterns. This will give you a good indication of the amount of data you will need to train your model, and whether you have already reached the point of diminishing returns.