<p>There is work on this, and abstaining can sometimes help. You might be looking for this paper: <a href="http://www.cs.cmu.edu/~avrim/Papers/kwikmb.pdf">Trading Off Mistakes with Don't Know Predictions</a> by Sayedi et al. from the last NIPS. </p>

CC BY-SA 2.5
2011-01-11T19:44:03.117Z
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.
Lev Reyzin
CC BY-SA 2.5
2011-01-11T18:50:31.167Z
2011-01-11T18:50:31.167Z
Aaron Roth
<p>The paper <a href="http://people.csail.mit.edu/ronitt/papers/dfa.ps" rel="nofollow">Efficiently Learning Typical Finite Automata from Random Walks</a> [Freund et al. '97] considered <em>default mistakes</em>, where a learner defaults (or chooses not to answer), instead of predicting.  </p>

<p>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.</p>

CC BY-SA 2.5
2011-01-11T19:51:13.107Z
2011-01-11T19:51:13.107Z
Lev Reyzin
<p>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?</p>

<lg.learning>
Relating PAC learning results and abstaining classifiers
Anthony Labarre
# Relating PAC learning results and abstaining classifiers

(Asked by: username_0 on 2011-01-11)

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?

**Tags:** lg.learning


---

## 2 answers

### Answer by username_1 on 2011-01-11. Score: 6 | Accepted answer

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](http://www.cs.cmu.edu/~avrim/Papers/kwikmb.pdf) by Sayedi et al. from the last NIPS.

> **Comments:**
> **username_2**: 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.  

---

### Answer by username_2 on 2011-01-11. Score: 4

The paper [Efficiently Learning Typical Finite Automata from Random Walks](http://people.csail.mit.edu/ronitt/papers/dfa.ps) [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.


---

