Interactive demo · Nonparametric Statistical Inference · Chapter 2

Shattering and the VC dimension

A class of sets picks out a subset of the points R if some set in the class contains exactly those points. If every one of the 2n subsets can be picked out, R is shattered. The VC dimension is the size of the largest shattered set; by Sauer's lemma the number of subsets picked out from n points is then at most a polynomial of degree v in n, which is what makes the uniform bound (2.42) useful. Click in the square to add a point (click a point to remove it), choose a class, and look at the grid of all subsets: green tiles are picked out, red tiles are not.

Class of sets

Random points

Try these

The 1-D classes use the horizontal coordinates only (the points are projected onto the axis). The counts are exact for points in general position (no three on a line, no four on a circle): half-planes and discs are enumerated from the lines through two points and the circles through one, two or three points, as proved in the notes. Random point sets use the seeded generator with seed 1000 + the seed slider, coordinates 0.1 + 0.8U.

In the lecture notes