Repeatedly measuring accuracy against the hold out set

Question

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.

Answer 1

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"

Answer 2

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.