Linear Dependence in R^d
VC dimension is a measure of classification capacity based on shattering.
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.
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.
Labeling the Standard Basis
Show that the d standard basis vectors can receive any desired binary labeling under homogeneous halfspaces.
Choose a labeling: Let y1 through yd be the desired binary labels for e1 through ed.
Build the weight vector: Use those labels as the coordinates of w.
Evaluate each point: The dot product w · ei selects the i-th coordinate of w, so w · ei equals yi.
Conclude shattering: Because every desired labeling can be obtained by choosing the corresponding weight vector, the d basis vectors are shattered.
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.
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.
The Zero Vector and the Basis Vectors
Identify a set of d+1 points that non-homogeneous halfspaces can shatter.
Choose the points: Take the zero vector together with the d standard basis vectors.
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.
Establish the lower bound: Since a set of d+1 points can be shattered, the non-homogeneous VC dimension is at least d+1.
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
| 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 |
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
Showing only that d points can be shattered and then stopping.
A VC dimension claim requires both a lower bound and an upper bound.
Fix:
Also show that every d+1-point set fails to be shattered by using linear dependence.Using the homogeneous result for a non-homogeneous class without adjustment.
The bias term supplies an additional parameter and allows the boundary to translate.
Fix:
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.Ignoring the coefficient signs in the dependence argument.
The contradiction depends on comparing the sign requirements on the two coefficient groups.
Fix:
Split the nonzero dependence coefficients into positive and negative groups, then apply the proposed weight vector to the dependence relation.Confusing a single successful labeling with shattering.
Shattering requires every possible binary labeling.
Fix:
Explain how choosing the coordinates of w to match an arbitrary labeling realizes all labelings.
Practice Check
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.
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?
Reveal answer
Answer: d
VC dimension is the largest number of points that the class can shatter.
Summary
- VC dimension is the largest number of points that a classification class can shatter.
- Homogeneous halfspaces in R^d shatter the d standard basis vectors, giving a lower bound of d.
- Any d+1 vectors in R^d are linearly dependent, which prevents homogeneous halfspaces from shattering every d+1-point set.
- Non-homogeneous halfspaces can shatter the zero vector together with the d standard basis vectors.
- The bias term adds positional freedom, and the resulting VC dimension is d+1.
Key Takeaways
- 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.