2010-11-19 End of learning WA, Hardness of PAC learning

In the first half of the lecture, the algorithm and proof for learning Weighted Automata was presented. We also showed that this algorithm implies learnabilty of u unambiguous automata, probabilistic automata (where a MQ returns the probability that the target accepts x), decision trees, and polynomials over finite fields.

Exercise 16 (extra credit): Show how to use the WA algorithm to learn polynomials over the real numbers; should be polynomial in the number of variables, number of terms, and the degree of the polynomial.

Exercise 17: Prove that satisfy-k DNF is learnable from EQ+MQ for every fixed k. Hint: Construct a WA equivalent to any such formula. You can describe a direct construction or, alternatively, you can show that if f and g have WA of size s, then f $\lor$ g, f $\land$ g have WA of size s^2 approx, and deduce the result from here.

In the second half of the lecture, we started with negative results for PAC learning. In particular, we proved that proper PAC-learning 3-term-DNF implies RP=NP. This result can be found in chapter 1 of the book by Kearns and Vazirani  An Introduction to Computational Learning Theory.

Exercise 18: Show that a graph G is 3-colorable iff there is a consistent 3-term DNF for the sample S_G as defined in class.