Linear Dependence in R^d

Because of the dependence, there are real coefficients a1 through a(d+1), not all zero, such that the weighted combination of the vectors equals the zero vector.

Programming

Capacity Through Shattering

A classification class is more expressive when it can produce more different labelings of data points. VC dimension measures this capacity by asking how many points the class can shatter. A set of points is shattered when every possible binary labeling of those points can be produced by some classifier in the class.

What does it mean for a classifier to realize every possible binary labeling, and how does the largest such set define VC dimension?

Key point

The central question is not how many labelings one particular classifier produces. It is whether, for every labeling of the chosen points, there exists some classifier in the class that produces it.

Homogeneous Lower Bound

A homogeneous halfspace uses a weight vector w and a decision boundary constrained to pass through the origin. For the lower bound, choose the d standard basis vectors e1 through ed. Each basis vector has a 1 in one coordinate and 0 in every other coordinate.

Worked example

Labeling the Standard Basis

Show that the d standard basis vectors can receive any desired binary labeling under homogeneous halfspaces.

1
Choose a labeling
Let y1 through yd be the desired binary labels for e1 through ed.
2
Build the weight vector
Use those labels as the coordinates of w.
3
Evaluate each point
The dot product w · ei selects the i-th coordinate of w, so w · ei equals yi.
4
Conclude shattering
Because every desired labeling can be obtained by choosing the corresponding weight vector, the d basis vectors are shattered.

Result

Homogeneous halfspaces can shatter at least d points, so their VC dimension is at least d.

The weight vector is doing all the work in this construction. Its i-th coordinate determines the result on ei because the dot product with ei extracts exactly that coordinate. Thus, the d independent coordinate directions provide d independently controllable labeling choices.

Dependence Blocks the Next Point

The lower bound alone is not enough. To prove that the homogeneous VC dimension is exactly d, we must show that no set of d+1 vectors in R^{^d} can be shattered. The key fact is that any d+1 vectors in R^{^d} are linearly dependent.

How does a linear dependence among d+1 points force at least one labeling to be impossible for homogeneous halfspaces?

Because of the dependence, there are real coefficients a1 through a(d+1), not all zero, such that the weighted combination of the vectors equals the zero vector. Separate the indices with positive coefficients from those with negative coefficients. If both groups are nonempty, suppose a homogeneous classifier tried to assign positive dot products to one group and negative dot products to the other. Applying the same weight vector to the dependence relation creates incompatible sign conditions: the contributions from the two groups cannot combine to zero in the required way.

Combining the two parts gives the exact result: homogeneous halfspaces in R^{^d} have VC dimension d. The standard basis supplies the d-point lower bound, while linear dependence prevents any d+1-point set from being shattered.

Adding the Bias Term

A non-homogeneous halfspace includes a bias term in addition to the weight vector. Geometrically, the bias allows the separating hyperplane to be translated instead of requiring it to pass through the origin. In the shattering argument, this adds one more degree of freedom beyond the coordinates of the weight vector.

How does adding a bias term allow d+1 points to be shattered, and what geometric freedom does translating the hyperplane provide?

Worked example

The Zero Vector and the Basis Vectors

Identify a set of d+1 points that non-homogeneous halfspaces can shatter.

1
Choose the points
Take the zero vector together with the d standard basis vectors.
2
Use the extra freedom
The source proof states that the bias term allows this set to be shattered, paralleling the homogeneous construction for the basis vectors.
3
Establish the lower bound
Since a set of d+1 points can be shattered, the non-homogeneous VC dimension is at least d+1.

Result

Non-homogeneous halfspaces can shatter at least d+1 points.

For the upper bound, suppose that d+2 vectors in R^{^d} could be shattered by non-homogeneous halfspaces. The standard reduction in the source converts this situation into d+2 vectors in R^{^d+1} shattered by homogeneous halfspaces. But homogeneous halfspaces in R^{^d+1} have VC dimension d+1, so they cannot shatter d+2 vectors. This contradiction gives the upper bound.

Therefore, non-homogeneous halfspaces in R^{^d} have VC dimension d+1. The extra one comes from the bias term: the weight vector controls the orientation of the boundary, while the bias supplies additional positional freedom.

Weight Versus Bias

What changes when the weight vector controls orientation while the bias controls position, and how does that extra parameter increase VC dimension?

Classifier class	Boundary restriction	Lower-bound construction	Upper-bound idea	VC dimension
Homogeneous halfspaces in R^{^d}	Boundary passes through the origin	d standard basis vectors	Every d+1 vectors are linearly dependent	d
Non-homogeneous halfspaces in R^{^d}	Bias permits translation of the boundary	Zero vector plus d standard basis vectors	Reduce to homogeneous halfspaces in R^{^d+1}	d+1

The difference between the two VC dimensions is the additional freedom supplied by the bias term.

Key point

Do not treat the bias as merely a notational change. In the shattering proof, it changes the available parameter count and removes the requirement that the boundary pass through the origin.

Common Proof Mistakes

Common mistake
Showing only that d points can be shattered and then stopping.
What it looks like
Using the standard basis vectors establishes only the lower bound for homogeneous halfspaces.
Why it fails
A VC dimension claim requires both a lower bound and an upper bound.
Do this instead
Also show that every d+1-point set fails to be shattered by using linear dependence.
Common mistake
Using the homogeneous result for a non-homogeneous class without adjustment.
What it looks like
Claiming that non-homogeneous halfspaces in R^d have VC dimension d because the weight vector has d coordinates.
Why it fails
The bias term supplies an additional parameter and allows the boundary to translate.
Do this instead
Use the zero vector plus the d basis vectors for the lower bound and the reduction to homogeneous halfspaces in R^(d+1) for the upper bound.
Common mistake
Ignoring the coefficient signs in the dependence argument.
What it looks like
Mentioning linear dependence without separating positive and negative coefficients.
Why it fails
The contradiction depends on comparing the sign requirements on the two coefficient groups.
Do this instead
Split the nonzero dependence coefficients into positive and negative groups, then apply the proposed weight vector to the dependence relation.
Common mistake
Confusing a single successful labeling with shattering.
What it looks like
Finding one weight vector that labels the basis vectors in one desired way.
Why it fails
Shattering requires every possible binary labeling.
Do this instead
Explain how choosing the coordinates of w to match an arbitrary labeling realizes all labelings.

Practice Check

MEDIUM

Explain in your own words why the standard basis vectors prove the lower bound for homogeneous halfspaces, and why linear dependence proves the upper bound. Then state what changes when a bias term is added.

Hints

For the lower bound, track what the dot product with a standard basis vector selects.
For the upper bound, begin with the fact that d+1 vectors in R^{^d} are linearly dependent.
For the non-homogeneous case, identify the role of the zero vector and the extra bias parameter.

Your attempt (not saved)

What do you think happens?

Suppose a classification class can shatter d points but cannot shatter any set of d+1 points. What is its VC dimension?

d-1
d
d+1
It cannot be determined

Reveal answer

Answer:

VC dimension is the largest number of points that the class can shatter.

Summary

1
VC dimension is the largest number of points that a classification class can shatter.
2
Homogeneous halfspaces in R^{^d} shatter the d standard basis vectors, giving a lower bound of d.
3
Any d+1 vectors in R^{^d} are linearly dependent, which prevents homogeneous halfspaces from shattering every d+1-point set.
4
Non-homogeneous halfspaces can shatter the zero vector together with the d standard basis vectors.
5
The bias term adds positional freedom, and the resulting VC dimension is d+1.

At a glance

VC dimension measures classification capacity through shattering.
Homogeneous halfspaces in R^{^d} have VC dimension d.
The homogeneous upper bound follows because every d+1 vectors in R^{^d} are linearly dependent.
Non-homogeneous halfspaces in R^{^d} have VC dimension d+1 because the bias term adds one extra degree of freedom.
The weight vector controls the boundary's orientation, while the bias permits its position to change.

Related concepts

More concepts starting with L