Learning Theory

The part of the course that asks what learning is, rather than how to do it. How large is the space of hypotheses, how many examples does a learner need before it can be trusted, and how do you measure the capacity of a model class without ever training it?

The pages

• Concept Learning - hypothesis spaces, general-to-specific ordering, and version spaces.
• PAC Learning - probably approximately correct, and the sample complexity bound.
• VC Dimension - shattering, capacity, and the bound that does not depend on the size of the hypothesis space.
• Cheat Sheet - the whole topic on one page.