The VC Dimension of Affine Halfspaces

Affine Halfspaces and Their VC Dimension

A linear score $w^\mathsf{T}x+b$ assigns a signed value to a point $x$: the vector $w$ determines the orientation of a separating hyperplane, and $b$ shifts it. The central question here is how many points in $\mathbb{R}^d$ can have every possible assignment of binary labels produced by such a rule. The answer is $d+1$. The lower bound comes from a set with no affine dependence; the upper bound comes from the fact that any $d+2$ points must have one.

Definition: An affine halfspace in $\mathbb{R}^d$ is a set $$ H_{w,b}=\{x\in\mathbb{R}^d:w^\mathsf{T}x+b\geq 0\}, $$ where $w\in\mathbb{R}^d$ and $b\in\mathbb{R}$. Its classifier labels $x$ positive when $w^\mathsf{T}x+b\geq 0$, and negative otherwise. A finite set $S$ is shattered if every subset of $S$ is the intersection of $S$ with some halfspace in the class. The VC dimension is the largest cardinality of a finite shattered set, or infinity if no finite maximum exists.

The boundary convention in this definition assigns points on the hyperplane to the positive class. The proof below uses this convention explicitly. The resulting dimension is unchanged if halfspaces are instead defined with a strict inequality: the lower-bound construction gives strictly positive and negative scores, and the upper-bound obstruction can be written with the corresponding weak and strict inequalities reversed.

Definition: Points $x_1,\ldots,x_m\in\mathbb{R}^d$ are affinely independent if the only coefficients $\alpha_1,\ldots,\alpha_m$ satisfying both $$ \sum_{i=1}^m\alpha_i x_i=0 \quad\text{and}\quad \sum_{i=1}^m\alpha_i=0 $$ are $\alpha_1=\cdots=\alpha_m=0$. Equivalently, the augmented vectors $(x_i,1)\in\mathbb{R}^{d+1}$ are linearly independent.

Why $d+1$ Points Can Be Shattered

Take $d+1$ affinely independent points $x_1,\ldots,x_{d+1}$. Their augmented vectors form a basis of $\mathbb{R}^{d+1}$. To realize a particular labeling, assign each point a target score of $+1$ or $-1$, according to its label, and solve for $w$ and $b$ so that the affine score takes those target values.

Worked Example: Realizing a Labeling of Three Points in the Plane

Consider $x_1=(0,0)$, $x_2=(1,0)$, and $x_3=(0,1)$ in $\mathbb{R}^2$. These points are affinely independent: the augmented vectors $(0,0,1)$, $(1,0,1)$, and $(0,1,1)$ are linearly independent. Label $x_1$ and $x_3$ positive and $x_2$ negative.

Choose target scores $+1,-1,+1$, respectively. Writing $g(x)=w_1x_1+w_2x_2+b$ for a point with coordinates $(x_1,x_2)$, the three equations are

b=1,\qquad w_1+b=-1,\qquad w_2+b=1.

Thus $b=1$, $w_1=-2$, and $w_2=0$. The resulting score is $g(x)=-2x_1+1$. At the three points its values are $1,-1,1$, so this halfspace realizes the requested labeling with no point on the boundary.

Theorem: Any $d+1$ affinely independent points in $\mathbb{R}^d$ are shattered by affine halfspaces.

Proof. Let $x_1,\ldots,x_{d+1}$ be affinely independent and choose any labeling of them. Write $y_i=1$ for a positive label and $y_i=-1$ for a negative label. Since the augmented vectors $(x_i,1)$ form a basis, there is a vector $(w,b)\in\mathbb{R}^{d+1}$ satisfying the $d+1$ linear equations

w^\mathsf{T}x_i+b=y_i,\qquad i=1,\ldots,d+1.

Each positive point then has score $1\geq 0$, and each negative point has score $-1<0$. This constructs a halfspace for the chosen labeling. Since the labeling was arbitrary, every labeling is realized, so the points are shattered. $\square$

Worked Example: All Labelings of Two Points on the Line

In $\mathbb{R}$, take the distinct points $x_1=-1$ and $x_2=2$. They are affinely independent: if $\alpha_1+\alpha_2=0$ and $-\alpha_1+2\alpha_2=0$, then $\alpha_1=-\alpha_2$, so $3\alpha_2=0$, and both coefficients vanish.

For any desired labels $y_1,y_2\in\{-1,1\}$, solve $w(-1)+b=y_1$ and $2w+b=y_2$. Subtracting the first equation from the second gives $3w=y_2-y_1$, hence

w=\frac{y_2-y_1}{3}, \qquad b=\frac{2y_1+y_2}{3}.

For example, the labeling $(+1,-1)$ gives $w=-2/3$ and $b=1/3$; the scores at $-1$ and $2$ are $1$ and $-1$. The formula works for each of the four labelings because it gives the prescribed scores $y_1,y_2$ exactly. Thus two points can be shattered on the line.

Why $d+2$ Points Cannot Be Shattered

The obstruction is dimensional. After adding a final coordinate equal to $1$, each point becomes a vector in $\mathbb{R}^{d+1}$. Any $d+2$ such vectors are linearly dependent, which gives coefficients whose weighted sum of points is zero and whose coefficients also sum to zero. Those two identities force at least one positive and one negative coefficient. Labeling the corresponding points according to these signs creates a contradiction for any affine score.

Worked Example: A Checkerboard Labeling of a Square

In $\mathbb{R}^2$, consider the four square corners $x_1=(-1,-1)$, $x_2=(1,-1)$, $x_3=(1,1)$, and $x_4=(-1,1)$. They satisfy

$$ x_1+x_3=x_2+x_4. $$

Label $x_1,x_3$ positive and $x_2,x_4$ negative. If an affine score $g(x)=w^\mathsf{T}x+b$ realized these labels, then $g(x_1),g(x_3)\geq 0$, while $g(x_2),g(x_4)<0$. The point relation gives

$$ g(x_1)+g(x_3)-g(x_2)-g(x_4)=0. $$

Indeed, the coefficients sum to $1+1-1-1=0$, so the intercept terms cancel, and the vector relation cancels the terms involving $w$. But the left side must be strictly positive: its first two terms are nonnegative, and each of the last two terms is the negative of a strictly negative score. This contradiction proves that this particular labeling cannot be realized. The four corners are therefore not shattered.

Theorem: No set of $d+2$ points in $\mathbb{R}^d$ is shattered by affine halfspaces.

Proof. Let $x_1,\ldots,x_{d+2}\in\mathbb{R}^d$. Their augmented vectors $(x_i,1)$ lie in a vector space of dimension $d+1$, so there are coefficients $\lambda_1,\ldots,\lambda_{d+2}$, not all zero, such that

\sum_{i=1}^{d+2}\lambda_i x_i=0, \qquad \sum_{i=1}^{d+2}\lambda_i=0.

The coefficients include at least one positive and at least one negative value. Otherwise, since they sum to zero, all would be zero. Label $x_i$ positive when $\lambda_i>0$, and negative when $\lambda_i<0$; assign any label to points with $\lambda_i=0$.

Suppose an affine halfspace realized this labeling, and write $g(x)=w^\mathsf{T}x+b$. For $\lambda_i>0$, the positive label implies $g(x_i)\geq 0$, so $\lambda_i g(x_i)\geq 0$. For $\lambda_i<0$, the negative label implies $g(x_i)<0$, so $\lambda_i g(x_i)>0$. Terms with $\lambda_i=0$ vanish. Since at least one coefficient is negative, it follows that

\sum_{i=1}^{d+2}\lambda_i g(x_i)>0.

On the other hand, the affine form of $g$ and the two dependence identities give

\sum_{i=1}^{d+2}\lambda_i g(x_i) = w^\mathsf{T}\left(\sum_{i=1}^{d+2}\lambda_i x_i\right) +b\left(\sum_{i=1}^{d+2}\lambda_i\right) =0.

This contradiction shows that the specified labeling cannot be realized. Thus no $d+2$ points are shattered. $\square$

Conclusion: The VC dimension of affine halfspaces in $\mathbb{R}^d$ is $d+1$. The lower bound follows from any $d+1$ affinely independent points; the upper bound follows because every $d+2$ points have an affine dependence that obstructs at least one labeling.

Common Pitfall and Why the Result Matters

A common mistake is to argue that $d+2$ points cannot be shattered simply because $d+2$ score equations involve only $d+1$ parameters. Having more equations than parameters does not, by itself, show that some labeling is impossible: some systems of more equations than unknowns are consistent. The correction is to use the affine dependence relation and choose a labeling from its positive and negative coefficients. The resulting weighted sum must be both strictly positive and exactly zero, which is a genuine contradiction.

The count $d+1$ is a statement about affine, not purely linear, separation. The intercept $b$ contributes one additional degree of freedom: after augmenting each point with a coordinate equal to $1$, the score becomes a linear functional in $d+1$ coordinates. This explains why the dimension is one larger than the number of spatial coordinates. In learning theory, the VC dimension measures the class's capacity to realize label patterns; it is a key combinatorial quantity in results about growth and uniform convergence.

For $d=0$, the space $\mathbb{R}^0$ contains a single point. The constant score $b$ realizes either label on that point, so its VC dimension is $1=d+1$, consistent with the result. For positive $d$, the theorem gives both bounds: $d+1$ points can be shattered, and no set of $d+2$ points can be shattered. Therefore the maximum is exactly $d+1$.

Check Your Understanding

Use the constructions and dependence argument above to answer the following questions.

Why does affine independence of $d+1$ points make the target-score equations solvable for every labeling?
For the square-corner example, which identity ensures that the intercept terms cancel when the four scores are combined?
Why must a nonzero set of coefficients summing to zero contain both a positive and a negative coefficient?
In the upper-bound proof, which side of the labeling creates the strictly positive contribution to the weighted sum?
What changes in the lower-bound construction if the halfspace convention assigns boundary points to the negative class?

The VC Dimension of Affine Halfspaces

What You'll Learn

Affine Halfspaces and Their VC Dimension

Why \(d+1\) Points Can Be Shattered

Worked Example: Realizing a Labeling of Three Points in the Plane

Worked Example: All Labelings of Two Points on the Line

Why \(d+2\) Points Cannot Be Shattered

Worked Example: A Checkerboard Labeling of a Square

Common Pitfall and Why the Result Matters

Check Your Understanding

The VC Dimension of Affine Halfspaces

What You'll Learn

Affine Halfspaces and Their VC Dimension

Why \(d+1\) Points Can Be Shattered

Worked Example: Realizing a Labeling of Three Points in the Plane

Worked Example: All Labelings of Two Points on the Line

Why \(d+2\) Points Cannot Be Shattered

Worked Example: A Checkerboard Labeling of a Square

Common Pitfall and Why the Result Matters

Check Your Understanding

Previous

Next