Why These Geometric Classes Are Useful
A hypothesis class can be simple to describe geometrically and still produce many different labelings of a sample. The VC dimension measures the largest sample size on which the class can realize every possible binary labeling. For rectangles, the key restriction is that each coordinate has only a lower and upper boundary. For unions of intervals, each additional interval can create another separated positive region, but cannot skip over a negative point.
These examples make the two parts of a VC-dimension calculation concrete: construct a set that the class shatters, then show that every set one point larger has a labeling the class cannot realize. The resulting dimensions are \(2d\) for axis-aligned rectangles in \(d\) dimensions and \(2k\) for unions of at most \(k\) intervals on the real line.
Definitions and Hypothesis Classes
Equivalently, view membership in \(C\) as a positive label and nonmembership as a negative label. Shattering means that every assignment of positive and negative labels to the sample can be realized by a member of the class. If a class shatters a set, it also shatters each subset of that set, by restricting the possible labelings.
The endpoints of a rectangle are constrained to be parallel to the coordinate axes. This matters: an arbitrary rotation changes the class. In the interval class, the intervals need not have the same length or be equally spaced, but each is a single connected stretch of the real line.
Rectangles in \(d\) Dimensions
For the lower bound, place two points on each coordinate axis, one in each direction from the origin. Write \(e_j\) for the vector whose \(j\)th coordinate is \(1\) and whose other coordinates are \(0\). The \(2d\) points are \(e_1,-e_1,\ldots,e_d,-e_d\). To realize a labeling, choose the interval for coordinate \(j\) according to the labels of \(e_j\) and \(-e_j\). Every point on a different coordinate axis has \(j\)th coordinate \(0\), so the chosen interval must contain \(0\) in every case.
Proof. First we show that the \(2d\) points just described are shattered. For each coordinate \(j\), choose its interval as follows:
| Labels of \(e_j\) and \(-e_j\) | Choose the \(j\)th interval |
|---|---|
| Both positive | \([-1,1]\) |
| Only \(e_j\) positive | \([0,1]\) |
| Only \(-e_j\) positive | \([-1,0]\) |
| Both negative | \([0,0]\) |
The product of these intervals includes every point labeled positive and excludes every point labeled negative. In the last row, for example, the interval in coordinate \(j\) excludes both \(e_j\) and \(-e_j\), while containing coordinate \(0\) for points on all other axes. Thus every labeling is realized, and the VC dimension is at least \(2d\).
For the upper bound, take any \(2d+1\) distinct points. For each coordinate \(j\), choose one sample point attaining the minimum \(j\)th coordinate and one attaining the maximum \(j\)th coordinate. There are at most \(2d\) chosen points in total. Therefore at least one point \(z\) is not among them. Remove \(z\) from the sample. The chosen extrema remain in the remaining sample, so, coordinate by coordinate, its minimum and maximum are unchanged. Consequently \(z\)'s coordinate in every dimension lies between the minimum and maximum among the remaining points.
Now label every remaining point positive and label \(z\) negative. Any axis-aligned rectangle containing all the positive points must contain the full coordinate range of those points in each dimension. Since \(z\) lies in each of those ranges, the rectangle must contain \(z\) as well. This labeling cannot be realized. No set of \(2d+1\) points is shattered, so the VC dimension is at most \(2d\). Together the bounds give \(\operatorname{VC}(\mathcal{C})=2d\). \(\square\)
Worked Example: Constructing a Rectangle for a Labeling in Two Dimensions
Consider the four points \(e_1=(1,0)\), \(-e_1=(-1,0)\), \(e_2=(0,1)\), and \(-e_2=(0,-1)\). Suppose only \(e_1\) and \(-e_2\) are labeled positive.
On the first coordinate axis, only \(e_1\) is positive, so choose the first-coordinate interval \([0,1]\). On the second axis, only \(-e_2\) is positive, so choose the second-coordinate interval \([-1,0]\). The resulting rectangle is
It contains \(e_1=(1,0)\) and \(-e_2=(0,-1)\). It excludes \(-e_1=(-1,0)\) because \(-1\notin[0,1]\), and excludes \(e_2=(0,1)\) because \(1\notin[-1,0]\). The construction works independently for each coordinate, which is why it handles every labeling of these four points.
Unions of Intervals on the Real Line
For the lower bound, take any \(2k\) distinct points in increasing order, \(x_1<\cdots<x_{2k}\). A positive labeling splits into runs of consecutive positive points. There can be at most \(k\) such runs: each run other than a possible first run must be preceded by a negative point, and the alternating pattern beginning with a positive point already has the maximum \(k\) runs. For each run, take the interval from its first point to its last point. That interval includes exactly the positive sample points in the run and no negative sample point. The union of these intervals realizes the labeling.
Proof. The construction above shows that every set of \(2k\) distinct real points is shattered, so the VC dimension is at least \(2k\). For the upper bound, take any \(2k+1\) distinct points and order them as \(x_1<\cdots<x_{2k+1}\). Label the odd-indexed points positive and the even-indexed points negative. There are \(k+1\) positive points, and between each consecutive pair of them lies a negative point.
Any interval containing two of these positive points must also contain every real number between them, including at least one of the intervening negative sample points. A union that realizes the labeling cannot contain any negative point, so each of its intervals can cover at most one positive point. At least \(k+1\) intervals would therefore be needed, which is not allowed. The labeling is unrealizable, so no \(2k+1\) points are shattered and the VC dimension is at most \(2k\). Hence it equals \(2k\). \(\square\)
Worked Example: Realizing a Labeling With Two Intervals
Take four ordered sample points \(1<2<3<4\), and label \(2\) and \(3\) positive while labeling \(1\) and \(4\) negative. The positive points form one consecutive run in the ordered sample. The interval \([2,3]\) contains both positive points and neither negative point, so one interval suffices; it is also a valid union of at most two intervals.
For a labeling with two separated positive runs, label \(1\) and \(3\) positive and \(2\) and \(4\) negative. The intervals \([1,1]\) and \([3,3]\) realize it. Each interval contains its selected positive point, and neither contains either negative point. These examples show how the number of positive runs, rather than the number of positive points alone, determines the intervals needed.
Worked Example: An Explicit Unshatterable Set
For two intervals, consider five ordered points \(1<2<3<4<5\). Label \(1,3,5\) positive and \(2,4\) negative. An interval containing both \(1\) and \(3\) must contain \(2\); an interval containing both \(3\) and \(5\) must contain \(4\). Thus no allowed interval can cover more than one positive point without including a negative point. Covering all three positives requires three intervals, so this labeling cannot be realized with at most two. This directly witnesses why five points cannot be shattered by unions of two intervals.
The same obstruction scales with \(k\): among \(2k+1\) ordered points, the alternating labeling has \(k+1\) isolated positives separated by negatives, requiring \(k+1\) intervals.
How to Use the Bounds—and a Common Pitfall
A lower-bound construction and an upper-bound obstruction answer different questions. Shattering \(m\) points proves only that the VC dimension is at least \(m\); it does not establish equality. Equality requires a separate argument showing that no set of \(m+1\) points can be shattered. In these examples, the upper bounds use structural constraints: coordinate extrema force a rectangle to include an unlabelled point, and intervening negatives prevent one interval from joining separated positives.
A common mistake is to count parameters and assume that this count is the VC dimension. A rectangle has \(2d\) coordinate boundaries, and a union of \(k\) intervals has \(2k\) endpoints, but parameter counting alone does not prove the answer. The endpoint choices must actually realize every labeling of a witness set, and a separate argument must rule out shattering a larger set. The constructions and obstructions above supply both parts.
These dimensions quantify a class's capacity to distinguish finite samples, not the number of parameters in every possible representation. In particular, the proofs rely on the order of points on the real line and on coordinatewise extrema in Euclidean space; changing the geometric class can change those arguments and the resulting dimension.
Check Your Understanding
Use the constructions and upper-bound arguments to answer the following.
- For the rectangle witness in \(\mathbb{R}^d\), what interval is used in coordinate \(j\) when both \(e_j\) and \(-e_j\) are labeled negative, and why does it not exclude points on the other coordinate axes?
- Why does finding at most \(2d\) coordinate-extremal points among \(2d+1\) points leave a point whose removal preserves every coordinate minimum and maximum?
- For \(2k\) ordered points, why can an arbitrary positive labeling have no more than \(k\) positive runs?
- Explain why an interval that covers two positive points in the alternating labeling of \(2k+1\) points must include a negative sample point.
- State both VC dimensions and identify the main geometric obstruction used in each upper-bound proof.