Shattering and VC Dimension
Try it: Shattering and VC Dimension
What it means for a hypothesis class to shatter a set of points: all 2^n labelings are checked exactly, each realizable one with a witness hypothesis drawn, until the first labeling no hypothesis can produce — linked to the VC dimensions of thresholds (1), intervals (2), halfspaces in the plane (3) and axis-aligned rectangles (4).
How it works
- Pick a hypothesis class and place n points.
- Enumerate all 2^n labelings of the points with 0 / 1.
- For each labeling decide exactly whether some hypothesis produces it (thresholds: every 1 left of every 0; intervals: no 0 between the outer 1s; rectangles: no 0 in the bounding box of the 1s; halfspaces: strict linear separability).
- Draw a witness hypothesis for every realizable labeling.
- The set is shattered if every labeling is realized; VCdim is the size of the largest shattered set.
Default run (6 steps): 2 points and the class of intervals on a line (VC dimension 2). Check all 2^2 = 4 labelings: is each one produced by some hypothesis? … All 4 labelings are realized: intervals on a line shatter these 2 points, so VCdim >= 2. Theory: VCdim = 2, so no set of 3 points can be shattered.
Simplified: At most 6 points on a 0–10 board. The lab checks one placement at a time: failing to shatter one set of n points does not by itself show VCdim < n — that needs every placement (the lab states the known VC dimension).
Loading the simulation…