I have an iterative document classification task, corpus size = 300,000 documents. The labels are binary valued (yes/no). I wanted to know whether the following methodology is valid. The assumption is that there is an oracle to label the documents.

Randomly select 500 documents and label them using an oracle, lets call this the hold out set H. Set H is never used for training purposes.

Select another 500 document set, Tr, label them using an oracle, train a SVM classifier and evaluate the accuracy of the resulting model on set H. Sample another 100 documents, get them labeled from the oracle, add them to Tr, train a SVM classifier and evaluate the accuracy on set H. Repeat the procedure until you reach the desired accuracy level and stop.

Personally I feel that a hold-out set so small may not be able to account for all the variation in the corpus in order to determine whether to stop the iterative learning process. But I am not able to quantify this. Would also appreciate some pointers to research papers.


2 Answers 2


It sounds like you're trying to create an active learning algorithm, if I interpreted the setting correctly. If so, have you already looked at other active learning methods and found them unsatisfactory for some reason?

Whether 500 documents is too small a set or not of course depends on the problem, but there are other issues too. First, your stopping criterion can't simply be a threshold of the accuracy on the set H, since you don't know the Bayes-optimal error for the problem at hand (unless you do...). Worse, if H happens to be a bad sample (not representative), then you could be stuck getting more and more labels from the oracle (which I'm guessing is expensive, which is why you're trying to avoid it).

EDIT: on second thought, it's not really active learning since you're not focusing on how to pick which samples to give to the oracle. It's more of a stopping criterion problem for online/active learning, e.g.:

Zhu et al. "Confidence-based stopping criteria for active learning for data annotation"

Schuurmans, Dale, and Russell Greiner. "Sequential PAC learning."

Fu et al. "How Many Samples Are Needed to Build A Classifier: A General Sequential Approach"

  • $\begingroup$ Thanks, I agree its an active learning algorithm. My concern is not so much about which samples to give to the oracle. But I am more concerned about the stopping criteria. How do I quantify the variation in the accuracy resulting from the sampling errors in the holdout set? I will also look at the paper you referred to. $\endgroup$
    – ryk
    Commented Feb 11, 2014 at 16:28
  • $\begingroup$ Uh, yeah, not really active learning... I found another old paper that might be of interest, updating my post now. $\endgroup$
    – martin
    Commented Feb 11, 2014 at 17:52
  • $\begingroup$ Found another potentially relevant paper. Added to edit. $\endgroup$
    – martin
    Commented Feb 11, 2014 at 18:01

Using an independent estimate of generalization performance (such as a hold-out set) to decide when to stop collecting data is a reasonable thing to do, provided that the variance of the estimate is sufficiently low to be reliable. I am presuming that you will be looking at the difference in performance on H between iterations rather than aiming for a particular value? I would be tempted to use k-fold cross-validation rather than a single hold-out set, so that your performance estimate is based on all of the data that you have submitted to the oracle so far, and so will likely have a lower variance. This will be a little more computationally expensive, but this is iften less expensive than obtaining labels from the oracle, so it wins the cost-benefit analysis.

This paper on "What size test set gives good error rate estimates" ought to be equally applicable to deciding how bit to make the validation set for early stopping.

Remember that the hold-out set will give a slightly optimistically biased performance estimate as it has been used to tune one aspect of the classifier, namely how much labelled training data was used, but I suspect this bias is likely to be fairly minimal.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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