2010-11-02 Query Learning

We have introduced the model of exact learning from equivalence and membership queries, and the following algorithms:

• learning monotone conjunctions with Equivalence Queries
• learning monotone conjunctions with Membership Queries
• learning monotone DNFs with EQ + MQs

Finally, we have introduced the class of Horn CNFs, together with some observations on its behavior. The algorithm and its proof are left for next class.

The algorithm for monotone DNFs has been explained in several classical papers, for example, Valiant's A theory of the learnable or Angluin's Queries and concept learning. The algorithm for Horn CNF is a classic result by Angluin et al. Learning conjunctions of Horn clauses.

Exercise 11: Show that learnability in the query learning model using EQs implies learnability in the PAC learning model. Hint: simulate the EQ oracle with a sample of size $\frac{1}{\epsilon} \ln \frac{1}{\delta}$ and use the union bound appropriately.

Exercise 12: Complete the proof of learnability of monotone DNF formulas from Membership and Equivalence Queries.