<p>In PAC learning, there is the "Occam razor" principle, which says that learning is qualitatively equivalent finding a succinct hypothesis that is consistent with the training samples.</p>

<p>My question is whether there is a similar principle in Angluin's model in exact learning with membership and equivalence queries. In this model, the learner can either ask for the label of a sample of her choice, or ask for a counterexample for a hypothesis of her choice (if no counter-example exists, the verifier is told that the hypothesis is correct).</p>

<p>I am not sure how an "Occam razor" for Angluin's model could even be defined, but ideally it would say that learning is equivalent to the ability to find a succinct hypothesis that is consistent with training samples, in some sense.</p>

CC BY-SA 3.0
2013-06-15T04:00:05.427Z
For readers not working in the area (like me), could you give a reference to the precise theorem whose analog you're looking for in Angluin's model?
Robin Kothari
CC BY-SA 3.0
2013-06-16T06:53:11.623Z
I am not fluent enough myself in the area to know what the best reference is, but many lecture notes of courses on computational theory contain some variant of this theorem, usually called "Occam's razor".
Personally, I read it in the book "Computational learning theory" of Kearns.
Or Meir
CC BY-SA 3.0
2015-12-03T17:42:46.443Z
Isn't choosing a representation with the minimum size of the target function is kind of application to Occam razor principle?
seteropere
<machine-learning>
Occam razor for exact learning with membership/equivalence queries
Or Meir
# Occam razor for exact learning with membership/equivalence queries

(Asked by: username_0 on 2013-06-14)

In PAC learning, there is the "Occam razor" principle, which says that learning is qualitatively equivalent finding a succinct hypothesis that is consistent with the training samples.

My question is whether there is a similar principle in Angluin's model in exact learning with membership and equivalence queries. In this model, the learner can either ask for the label of a sample of her choice, or ask for a counterexample for a hypothesis of her choice (if no counter-example exists, the verifier is told that the hypothesis is correct).

I am not sure how an "Occam razor" for Angluin's model could even be defined, but ideally it would say that learning is equivalent to the ability to find a succinct hypothesis that is consistent with training samples, in some sense.

**Tags:** machine-learning

> **Comments:**
> **username_1**: For readers not working in the area (like me), could you give a reference to the precise theorem whose analog you're looking for in Angluin's model?  
> **username_0**: I am not fluent enough myself in the area to know what the best reference is, but many lecture notes of courses on computational theory contain some variant of this theorem, usually called "Occam's razor". Personally, I read it in the book "Computational learning theory" of Kearns.  
> **username_2**: Isn't choosing a representation with the minimum size of the target function is kind of application to Occam razor principle?  

---

## 0 answers

