Quite a few results are available on learning miscellaneous concept classes in the PAC learning framework. I would like to know whether any of these results have been extended in the abstaining classifier setting, where the classifier is allowed to refrain from classifying certain examples under various restrictions. In particular, does abstaining improve accuracy in any way, and if so, can this improvement be quantified?


2 Answers 2


There is work on this, and abstaining can sometimes help. You might be looking for this paper: Trading Off Mistakes with Don't Know Predictions by Sayedi et al. from the last NIPS.

  • $\begingroup$ I think this work focused on forcing a limit on the number of mistakes a learner can make and thereby forcing the learner to abstain. $\endgroup$
    – Lev Reyzin
    Commented Jan 11, 2011 at 19:44

The paper Efficiently Learning Typical Finite Automata from Random Walks [Freund et al. '97] considered default mistakes, where a learner defaults (or chooses not to answer), instead of predicting.

From what I remember, they showed that 1) You can learn (w.h.p.) by making only default mistakes, and 2) If the random walk is reset (to the start state of the DFA) on a default mistake, this helps in learning.


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.