2010-11-26 Reductions

We covered reductions in the PAC prediction model. The lecture was based on chapter 7 of Kearns and Vazirani's book, but you can find the original definitions in Pitt and Warmuth's paper Prediction-preserving reducibility.

Then, we generalized the notion of reduction for algorithms that are allowed to ask MQs. This can be found in Angluin and Kharitonov's paper When won't membership queries help?

Exercise 19: Show that CNF pwm-reduces to 2-Horn CNF, where a 2-Horn CNF formula is a CNF formula for which every clause contains at most 2 positive literals. Hint: use a reduction similar to the reduction from general to monotone DNF seen in class, and add trailing clauses to guarantee the answers to the membership query oracle.

Exercise 20: Define a suitable notion of reducibility for the model of learning from membership and equivalence queries, and prove the corresponding theorem: if C eq+mq reduces to C' and C' is eq+mq learnable, then so is C.