VC dimension — worked examples (a capacity ladder)
Parent: vc-dimension
Read the children as a ladder: when the simpler class can't express the pattern you need, climb to the next — that climb is raising VC. Each is counted by hand (exhibit shatterable points, then prove the next size can't be shattered).
| class | VC | breaks on |
|---|---|---|
| threshold | 1 | − + − (non-monotone) |
| interval | 2 | + − + (needs two bands) |
| union-of-intervals | 2k | more than k alternations |
| linear-separators | 3 | 4 points in XOR |
| rectangles | 4 | 5 points |
| vc-sin | ∞ | nothing — fits everything (so learns nothing) |
The price of every step up is in price-of-capacity.