VC dimension
Infinitely many thresholds are easy to learn; one innocent-looking sine family is impossible. Counting hypotheses and counting parameters both give the wrong answer. Shattering gives the right one — and leads to the fundamental theorem of statistical learning.
45 min
After this lesson you can
- Define the restriction of a class to a sample, shattering and the VC dimension
- Prove that thresholds have VC dimension 1, intervals 2 and lines in the plane 3
- State the Sauer–Shelah lemma and explain why polynomial growth is what makes learning possible
- State the fundamental theorem of statistical learning, including its sample-complexity rates
- Explain why the VC dimension is not the number of parameters
In this lesson
- Only the labellings matter
- Three worked examples
- Why shattering is the obstacle
- The growth function and the Sauer–Shelah lemma
- From counting to generalisation
- The VC dimension is not the number of parameters
- In code
- Limits, and what came next
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.