2010-10-22 More on PAC learning

Things we covered in today's class:

• finished proof of PAC learning monotone conjunctions, and PAC learning algorithm for rectangles (see chapter 1 of Introduction to Computational Learning Theory)
  
• definition of alternative PAC learning oracle-based models:
• the sample-based model that in addition receives as input the size of the target concept
• the one-oracle model using random example generator EX()
• the two-oracle model using positive random example generatos EX+() and negative random example generator EX-()
• reduction of online to PAC learning, more information on this in:
• Angluin's 1988 paper Queries and concept learning contains a similar reduction from the query learning model to PAC
• Littlestone's paper From on-line to batch learning

Exercise 5: Generalize the PAC algorithm for rectangles to
n-dimestional hyperrectangle.

Exercise 6: Show that an algorithm that is always able to output
consistent hypotheses is a PAC learning algorithm, given that the
sample size is at least $\frac{1}{\epsilon} \ln \frac{|H|}{\delta}$.

Exercise 7: Show that all four alternative models are indeed equivalent.
You may find the proofs to part of this in the original paper
Equivalence of models for polynomial learnability).