2010-10-19 PAC learning model

We finished the proof of the Weighted Majority Algorithm.

Exercise 4: Re-do analysis for WMA but instead of predicting according to the weighted majority, predict as follows: choose an expert at random according to probability w_i/W, and predict according to the chosen expert. You should get a better constant in the bound.

Then, we covered the definitions of representation class and PAC learning. The model was originally introduced in the classic 1984 paper by Valiant A theory of the learnable. We also saw one example of a learning algorithm that works in the PAC model: the elimination algorithm for learning monotone conjunctions. The proof is left for next class.

This material is well covered in the first chapter of the Kearns and Vazirani's textbook An Introduction to Computational Learning Theory.