I would like to compare 2 text classifiers C1 and C2, which can be trained with "unlimited" noisy training datasets, meaning that you can use as much data as you want for training, such data being very noisy. I am thinking of the 2 options below. Which one would be better?

1) Set up a datasize size interval 0-z, z being a very large number. Identify dataset size x at which C1 scores maximum accuracy (eg using a learning curve). Then train C2 with such dataset size x.

2) Identify dataset size y at which C1 stops learning (eg very small slope of the learning curve). Then train C2 with such dataset size y.

Please not that I am not asking about method for comparing classifiers, but how to decide the training dataset size at which 2 classifiers should be compared.

Edit: Below is the learning curve for one classifier. X axis is training dataset size, Y axis is accuracy. For the purpose of comparing two classifiers, should I pick the size at which highest accuracy has been found (red), or the size at which the accuracy remains (more or less) stable (green)?

enter image description here

Edit2: @cbeleites @Dikran Marsupial I am sorry for the lack of information:

  • I have 3 classes in my problem.
  • The above learning curve was generated by increasing training dataset size, starting from 1,000 examples/class(3,000 in total) until 140,000 examples/class(420,000 in total); for each increase step 1,000 new examples/class(3,000 in total) are being added, and the trained model is tested for every iteration with the same test dataset, composed of 350 examples/class (1,050 examples in total)
  • Training dataset samples were automatically labeled, test samples were manually labeled
  • I'd not call the graph the learning curve: it is just one instance. First of all, you need to tell us how exactly it was generated: is it a "growing" data set, i.e. one sample after the other is added and the model is recalculated and re-evaluated after each additional (bunch of) sample(s)? Is an independent set of $n$ samples for each point of this curve? Next, you need to estimate the variance: how much do new data sets differ? Also, how many classes does your model distinguish? You should also indicate the number of test samples you used for measuring accuracy. – cbeleites Nov 12 '12 at 11:08
  • 1
    Definitely don't pick a point after looking at the results as this is essentially cherry-picking, which will result in an optimistically biased performance estimate. It would be interesting to see the curves you get from multiple runs of the algorithm with independent samples of data. If they all look like that (including the mean), it would suggest that there is something wrong with the method. – Dikran Marsupial Nov 12 '12 at 12:25
  • 1
    yes, with different test and training sets. Essentially the question is what is the expected shape of the curve, when the expectation is taken over the random sampling of the data to form test and training sets. I suspect that the shape of the curve is due to the sampling of the data and is not meaningful. – Dikran Marsupial Nov 12 '12 at 13:00
  • 2
    @kanzen_master: different test sets allow you to judge the variance due to finite test sample size. Different training sets show the variance of (true) accuracy around the average accuracy for training sample size $n$. – cbeleites Nov 12 '12 at 13:00
  • 1
    @cbeleites I see... So, there are 2 causes for variances, one due to the finit training and one for the finit test set... – kanzen_master Nov 12 '12 at 13:45
up vote 8 down vote accepted

Do I understand you correctly that you want to measure whether C1 is a faster/slower learner than C2?

With unlimited training data, I'd definitively construct (measure) the learning curves. That allows you to discuss both questions you pose.

As Dikran already hints, the learning curve does have a variance as well as a bias component: training on smaller data gives systematically worse models but there is also higher variance between different models trained with smaller $n_{train}$ which I'd also include in a discussion which classifier is better.

Make sure you test with large enough test sample size: proportions of counts (such as classifier accuracy) suffer from high variance which can mess up your conclusions. As you have an unlimited data source, you are in the very comfortable situation that it is actually possible to measure the learning curves without too much additional testing error on them.

I just got a paper accepted that summarizes some thoughts and findings about Sample Size Planning for Classification Models. The DOI does not yet function, but anyways here's the accepted manuscript at arXiv.

Of course computation time is your consideration now. Some thoughts on this

  • how much computer time you are willing to spend will depend on what you need your comparison for.

  • if it's just about finding a practically working set-up, I'd be pragmatic also about the time to get to a decision.

  • if it's a scientific question, I'd quote my old supervisor " Computer time is not a scientific argument". This is meant in the sense that saving a couple of days or even a few weeks of server time by compromising the conclusions you can draw is not a good idea*.
    The more so, as having better calculations doesn't necessarily require more of your time here: your time to set up the calculations will take roughly the same time whether you calculate on a fine grid of training sample sizes or a rough one, or whether you measure variance by 1000 iterations or just by 10. This means that you can do calculations in an order that allows to get a "sneak-preview" on the results quite fast, then you can sketch the results, and at the end pull in the fine-grained numbers.

(*) I may add that I come from an experimental field where you easily spend months or years on sample collection and weeks or months measurements which don't do themselves in the way a simulation runs on a server, neither.


Update about bootstapping / cross validation

It is certainly possible to use (iterated/repeated) cross validation or out-of-bootrap testing to measure the learning curve. Using resampling schemes instead of a proper independent test set is sensible if you are in a small sample size situation, i.e. you do not have enough independent samples for training of a good classifier and properly measuring its performance. According to the question, this is not the case here.

Data-driven model optimization

One more general point: choosing a "working point" (i.e. training sample size here) from the learning curve is a data-driven decision. This means that you need to do another independent validation of the "final" model (trained with that samples size) with another independen test set. However, if your test data for measuring the learining curve was independent and had huge (really large) sample size, then your risk to overfit to that test set is minute. I.e. if you find a drop in performance for the final test data, that indicates either too small test sample size for determining the learning curve or a problem in your data analysis set up (data not independent, training data leaking into test data).


Update 2: limited test sample size
is a real problem. Comparing many classifiers (each $n_{train}$ you evaluate ultimately leads to one classifier!) is a multiple testing problem from a statistics point of view. That means, judging by the same test set "skims" the variance uncertainty of the testing. This leads to overfitting.
(This is just another way to express the danger of cherry-picking Dikran commented about)

You really need to reserve an independent test set for final evaluation, if you want to be able to state the accuracy of the finally chosen model.
While it is hard to overfit to a test set of millions of instances, it it much easier to overfit to 350 samples per class.

Therefore, the paper I linked above may be of more interest for you than I initially thought: it also shows how to calculate how much test samples you need to show e.g. superioriority of one classifier (with fixed hyperparameters) over another. As you can test all models with the same test set, you may be lucky so that you are able to somewhat reduce the required test sample size by doing paired tests here. For paired comparison of 2 classifiers, McNemar test would be a keyword.

  • Yes, I also think that learning curves are definitely a must for comparing the classifiers in my problem. However, would that be enough ? Apart from learning curves I think that a more thorough analysis (ie crossvalidation, bootstraping, etc) at a particular dataset size might be needed to assess/confirm the results found in the learning curve... – kanzen_master Nov 12 '12 at 9:25
  • @kanzen_master: What benefits do you expect from resampling that you cannot have with a large independent test set? – cbeleites Nov 12 '12 at 10:56
  • 1
    +1 for suggestion of learning curves. State of the art classifiers are likely to reach the same accuracy given enough data, but some are likely to get there sooner than others. Trying to estimate the variance of the learning curves is also a good idea (which is straightforward to do if there are unlimited training examples as then there is no need for resampling) – Dikran Marsupial Nov 12 '12 at 12:18
  • Just a last question, how can I know if the variance is low ? (visual inspection? compare to some threshold?). * By the way, related research only collects an arbitrary amount of training data (ie 100,000/class) and compares using k-fold cross-validation/heldout evaluation ... – kanzen_master Nov 13 '12 at 0:30
  • Wow, nice paper topic, and thanks for putting it on arXiv! – bright-star May 28 '14 at 1:46

If you have unlimited training data, then the optimal training set size depends on computational considerations, rather than statistical ones. From a statistical point of view, there are many classifiers based on universal approximations, so if you trained on an infinite dataset you would get a classifier that approached the Bayes error and could do no better.

If the classifier performs worse a size of the training set increases, that would be a rather worrying sign. If it still does this if you average over multiple random samples of training data, I would suspect there is something wrong with the implementation.

  • You mean that I should choose the training dataset size based on the training time? For comparing two classifiers, shouldn't it be better to pick up the size for which the highest accuracy/stable accuracy has been found? Regarding the second part, I think that a decrease of performance while increasing the size of the training dataset can perfectly happen if such training data is noisy. – kanzen_master Nov 12 '12 at 8:49
  • 1
    @kanzen_master: Sure you may observe decrease of performance with more training samples: there is a variance aspect as well as a systematic (bias) one to the learning curve. That's why Dikran talks about multiple random samples. Pls. see also my answer. – cbeleites Nov 12 '12 at 9:21
  • 2
    If a noisy dataset results in accuracy going down as the dataset gets larger, then assuming that the data are i.i.d. etc. it means that the dataset you have so far is too small to adequately represent the distribution of the data, and you need more data. If you collect enough data, the noise will average out and performance will improve. If variance is an issue, that means that more data is needed to reduce the variance. – Dikran Marsupial Nov 12 '12 at 12:22

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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