10-601 PAC

This a lecture used in the Syllabus for Machine Learning 10-601B in Spring 2016

Slides

• William's lecture: Slides in pdf, Slides in Powerpoint,

Readings

• Mitchell Chapter 7

What you should remember

• Definition of pac-learnability.
• Definition of sample complexity vs time complexity
• How sample complexity grows with 1/epsilon, 1/delta, and |H|
  • in the noise-free case.
  • in the "agnostic" setting, where noise is present and the learner outputs the smallest-error-rate hypothesis.
• The definition of VC-dimension and shattering
• How VC dimension relates to sample complexity