Agnostic learning of conjunctions first cut. In lecture, we saw the Elimination

Question

Agnostic learning of conjunctions first cut. In lecture, we saw the Elimination A- gorithm for learning conjunctions in the standard (realizable) PAC-learning model. In this problem, we will develop and analyze an algorithm for learning conjunctions in the agnostic learning model with some limited tolerance to adversarial noise. Specifically, we will develop a polynomial-time algorithm such that if there is some conjunction such that for the target concept c, P e(1- , then our algorithm produces a conjunction h such that Prze D[c(x-h(z)] 1-0(ne) with confidence 1- where there are n attributes. (a) First, show why the Elimination Algorithm as given does not provide such a guarantee.

Explanation / Answer

Here we are trying to develop a polynomial-time algorithm such that if there is some conjunction c* for hthe given equation and trying to produce a conjunction h.

Now the Elimination algorithm as given won't be providing any guarentee because

a) No errors is present in the equation:- until and unless we can guarentee that there is no error by any means in our example, elimination algorithm can't guarentee.

b) The target concept is included in the hypothesis space H :- This also need to be ensured that the solution or the target result which we trying to get is included(present) in the hypothesis space H which we had defined.

For better explanation please try to put the whole question.

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---