A geometric classifier can have infinitely many possible boundaries and still have finite VC dimension. The question is not how many boundaries exist, but how independently they can label finitely many points. Two complementary arguments are needed: construct one set on which every labeling is possible, then prove that no larger set can have that property.
Throughout, is an integer and the domain is .
Definition 2.2.1
(Shattering and VC dimension)
A finite set is shattered by a class if every assignment of binary labels to its points is realized by some classifier in that class. The VC dimension of the class is the largest integer for which some set of distinct points is shattered, and if arbitrarily large finite sets are shattered.
Every subset of a shattered set is also shattered: extend a labeling of the subset arbitrarily to the whole set. Consequently, ruling out shattering at one size also rules it out at every larger size. Coordinates and thresholds are real, and all geometric sets below include their boundaries.
Affine halfspaces
Consider
We allow ; constant zero and one classifiers are included. The offset allows a boundary to move rather than forcing it through the origin.
Theorem 2.2.2
(Affine halfspaces have VC dimension )
For the class above, .
Proof
(Affine score construction and dependence)
Lower bound. The points are affinely independent. For any prescribed signs , choose and . Then the affine score is exactly at the origin and at . Thus it realizes the desired labels with a strict margin from zero. All labelings are possible.
Upper bound. Take any distinct points . Their augmented vectors are linearly dependent. Hence there are real coefficients, not all zero, satisfying
Some coefficients are positive and some are negative. Label each point with by 1 and each point with by 0; assign labels to zero-coefficient points arbitrarily. If an affine halfspace realized this labeling, its scores would satisfy for positive coefficients and for negative coefficients. Therefore
The strict inequality comes from at least one negative coefficient multiplying a strictly negative score. But affine dependence gives , a contradiction. Thus no points can be shattered. Together with the lower bound, this proves the theorem.
Proof X-ray
The boundary convention matters
The proof does not assume that all labeled points have strictly separated scores. Because a boundary point is labeled 1, a proposed realization gives on the positive side and on the negative side. The negative-coefficient terms alone force strict positivity of the weighted sum. This handles boundary points without a general-position assumption.
Worked example 2.2.3
(Three points in the plane)
In the plane, the origin and the two coordinate unit vectors can be labeled in all eight ways. For labels 0 at the origin, 1 at , and 0 at , take and : the three scores are . The theorem says no four planar points are shattered by affine halfspaces, regardless of their arrangement.
Worked example 2.2.4
(Extracting the impossible labeling from an affine dependence)
Take the four points in the plane. With we have and . The positive coefficients sit at and , so the proof labels them 1 and labels by 0. Suppose scores realized this: then , , and . Adding the last two gives , while adding the first two gives , a contradiction. This is the familiar exclusive-or labeling, and it shows the weighted sum is the quantity that is forced to be positive.
Concept lensGeometric
The affine dependence as two convex hulls that meet
Put . The dependence says the two points and coincide. So the positive and negative groups have convex hulls with a common point. An affine score cannot be on one hull and on the other. In the square example this point is .
Worked example 2.2.5
(A zero coefficient and collinear points)
Take the four points . The coefficients satisfy and . The point has coefficient zero, so its label is arbitrary and plays no role. The proof labels and by 1 and by 0, which is the collinear pattern 1, 0, 1: the middle score is , so it cannot be negative. The same dependence also explains why the boundary convention explained in the proof X-ray above matters, because may equal zero.
Counterexample mode
A dimension statement is not a statement about every set
Three collinear points in the plane, ordered along their line, cannot be labeled 1, 0, 1 by an affine halfspace. The score at the middle point is a convex combination of the two endpoint scores, so if both endpoints are nonnegative, the middle score is nonnegative as well. The planar VC dimension is still 3 because a noncollinear triple can be shattered. Existence of one shattered set is enough for a lower bound.
Axis-aligned boxes
Let consist of indicators of bounded closed boxes
The bounds in different coordinates can be chosen separately, but each positive point must satisfy all coordinate constraints simultaneously. No empty-box hypothesis is needed for the result.
Theorem 2.2.6
(Axis-aligned boxes have VC dimension 2d)
For , .
Proof
(Extreme points and strict extrema)
Lower bound. Consider the points . For each coordinate , choose if is to be positive and otherwise. Choose if is to be positive and otherwise. Every interval contains zero, so other coordinates impose no restriction on . The chosen endpoints include exactly the points assigned label 1. Even the all-zero labeling is realized by .
Upper bound. Suppose a set of distinct points were shattered. For each point , choose a box containing every other point but excluding . Some coordinate of must lie outside that box. If it is below the lower endpoint, is a strict minimum in that coordinate among the whole set; if above the upper endpoint, it is a strict maximum. A coordinate has at most one strict minimum and one strict maximum, so there are at most points that can serve as such an extremum. This contradicts the points, each of which would need to be one.
The argument is robust to tied coordinates: a point excluded while all others are included must be a strict extremum in some coordinate. A tie cannot provide the necessary witness for that coordinate.
Worked example 2.2.7
(Four points shattered by rectangles)
In two dimensions the four points and are shattered. To include and only, use . The other two points fall outside. No set of five planar points can be shattered by axis-aligned rectangles, even though the four boundary coordinates are real-valued.
Worked example 2.2.8
(One dimension and a point that cannot be excluded)
For the boxes are closed intervals and the theorem gives . The points are shattered: selects both, selects only , selects only , and selects neither. For the three points the middle point is neither a strict minimum nor a strict maximum, so no interval can contain and but exclude . The labeling 1, 0, 1 is impossible, matching the upper-bound argument with .
Common mistake
(Dropping the offset)
If the offset is removed, the class has VC dimension , not . For it contains the indicators of , and the constant one. A single point is shattered, but two points never are: for the points the labeling would need and , and for the labeling would need and . The offset is exactly what gives the extra dimension in the theorem.
Common mistake
(Taking a tie as an extremum witness)
In the box upper bound, a point that is excluded while all others are included must be a strict minimum or strict maximum in some coordinate. Equal coordinates do not count. In the plane, let and let the other points be . In the first coordinate lies strictly between and , and in the second between and , so every box containing the other four contains . This can never be excluded, and the same reasoning shows how strictness is used to count at most witnesses.
Capacity and learning claims
The theorem counts possible labelings on finite sets; it does not supply a specific efficient learning algorithm or an exact sample size. VC generalization results use this capacity together with assumptions about independent sampling, confidence and the learning rule. Nor can a number of adjustable parameters by itself replace a shattering proof: the class definition, domain and permitted boundaries all matter.
Practice with solutions
Quick check
(Give that label as 1, 0, 1 respectively using .)
Choose from the score at the origin.
Solution · Answer
Take , , giving scores .
Quick check
(Why can three ordered points on the real line not be shattered by closed intervals?)
Which labeling is impossible?
Solution · Answer
The interval containing both endpoints also contains the middle point, so the labeling 1, 0, 1 is impossible.
Quick check
(For the four planar points , give a box that selects exactly and .)
Bound each coordinate separately.
Solution · Answer
.
Quick check
(Does VC dimension mean every set of points is shattered by affine halfspaces?)
Recall the definition: existence of a shattered set.
Solution · Answer
No. The definition requires existence of a shattered set of that size; for example, a collinear triple in the plane cannot realize 1, 0, 1 in order.