PAC learning
When can a finite sample promise anything about data you have never seen? Set up the problem formally, derive how many examples a finite hypothesis class needs — first when a perfect rule exists, then when none does — and see exactly what the two little numbers ε and δ promise.
45 min
After this lesson you can
- Define true risk, empirical risk, a hypothesis class and empirical risk minimisation (ERM)
- State the PAC definition and say in words what and guarantee
- Derive the realizable sample complexity with the union bound
- Derive the agnostic sample complexity for a finite class from Hoeffding's inequality and the union bound
- Explain why you cannot apply Hoeffding's inequality directly to the hypothesis ERM picked
In this lesson
- A formal model of learning
- The picture: learning a threshold
- The realizable case: a derivation you could have invented
- What ε and δ promise
- When nothing is perfect: the agnostic case
- In code
- Limits of the model
This lesson is part of Descent Pro
Descent Pro unlocks every lesson on the route, from base camp to the summit. Every plan starts with a free trial.