Homogeneous and Non-homogeneous Linear Separators
VC dimension is a measure of classification capacity based on shattering.
Capacity Through Shattering
A classification class is more expressive when it can realize more different labelings of data points. VC dimension measures this capacity. It is the largest number of points that the class can shatter, where shattering means that every possible binary labeling of those points can be produced by some classifier in the class.
The central question is not how many classifiers exist. It is how many different binary labelings the class can realize on one fixed set of points.
The Homogeneous Constraint
A homogeneous halfspace uses a separating boundary that is required to pass through the origin. Its classification choices are controlled by a weight vector. The VC dimension of homogeneous halfspaces in R^d is d.
Shattering the standard basis vectors
Show why the d standard basis vectors can receive every binary labeling under homogeneous halfspaces.
Choose the points: Take the d standard basis vectors e1 through ed. Each basis vector has a 1 in one coordinate and 0 in all the others.
Choose a labeling: Suppose the desired binary labels are y1 through yd.
Build the weight vector: Use those desired labels as the coordinates of the weight vector w.
Evaluate each point: The dot product of w with ei selects the i-th coordinate of w, so the result equals yi.
Conclude shattering: Because the weight vector can be chosen for every desired binary labeling, the d basis vectors are shattered.
At least d points can be shattered, so the homogeneous VC dimension is at least d.
The lower bound alone is not enough. It shows that d points can be shattered, but an exact VC dimension also requires an upper bound showing that d+1 points cannot be shattered.
Why Homogeneous Capacity Stops at d
Take any d+1 vectors in R^d. They are linearly dependent, so there are real coefficients a1 through a(d+1), not all zero, whose 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, shattering would require a weight vector whose dot products are positive on one group and negative on the other. Applying that weight vector to the dependence relation creates incompatible sign conditions. If one group is empty, the corresponding side becomes an equality, and the contradiction still follows.
- The two bounds meet: d basis vectors establish a shattered set of size d, while linear dependence rules out shattering any set of size d+1. Therefore, homogeneous halfspaces in R^d have VC dimension d.
Adding a Shift
A non-homogeneous halfspace removes the requirement that the separating boundary pass through the origin. The boundary can shift away from the origin. This additional freedom increases the VC dimension from d to d+1.
The d+1 point construction
Identify a set of d+1 points that non-homogeneous halfspaces can shatter.
Choose the set: Take the zero vector together with the d standard basis vectors.
Count the points: There is one zero vector plus d basis vectors, giving d+1 points.
Use non-homogeneous separators: The source construction states that this set is shattered by non-homogeneous halfspaces, paralleling the homogeneous construction for the basis vectors.
Interpret the increase: Allowing the boundary to shift away from the origin makes one additional point available in a shattered set.
Non-homogeneous halfspaces can shatter at least d+1 points.
To obtain the exact value, the upper bound considers d+2 vectors in R^d. The standard reduction converts this situation into d+2 vectors in R^(d+1) shattered by homogeneous halfspaces. That would contradict the homogeneous result, because homogeneous halfspaces in R^(d+1) have VC dimension d+1 and cannot shatter d+2 vectors. Therefore, non-homogeneous halfspaces in R^d have VC dimension exactly d+1.
Weight and Bias Roles
The weight vector is the object used directly in the homogeneous shattering construction: its coordinates are chosen to match the desired labels of the standard basis vectors. The homogeneous boundary must still pass through the origin. The non-homogeneous setting adds a bias term, allowing the boundary to move away from the origin. In the shattering proof, that added term is represented by a standard reduction that turns the problem into homogeneous halfspaces in one higher dimension, R^(d+1).
Common Proof Mistakes
Showing only that d points can be shattered and then stopping.
An exact VC dimension also requires proving that no larger set can be shattered.
Fix:
Add the linear-dependence upper bound for d+1 vectors.Treating the homogeneous and non-homogeneous cases as having the same capacity.
The homogeneous boundary must pass through the origin, while the non-homogeneous boundary can shift away from it.
Fix:
Track the bias term and remember that the non-homogeneous VC dimension is d+1.Using linear dependence without explaining the sign contradiction.
Linear dependence becomes a shattering contradiction only after separating positive and negative coefficients and examining the required dot-product signs.
Fix:
Explain that the dependence relation cannot coexist with the requested positive and negative dot products, including the equality case when one coefficient group is empty.Describing the bias as another ordinary coordinate without connecting it to geometry.
The important change is that the boundary can move away from the origin, and the proof expresses this through a reduction to one higher-dimensional homogeneous problem.
Fix:
Relate the added term to the shifted boundary and the R^(d+1) reduction.
Check Your Reasoning
Explain, in your own words, why the standard basis vectors establish the homogeneous lower bound, and why a linearly dependent set of d+1 vectors prevents the homogeneous upper bound from failing.
Hints
- For the lower bound, ask what the dot product with a standard basis vector selects.
- For the upper bound, separate the coefficients in a dependence relation into positive and negative groups.
- Remember that shattering requires every binary labeling, not merely several labelings.
Compare the point sets used in the two lower-bound arguments: the d standard basis vectors for homogeneous halfspaces and the zero vector together with those basis vectors for non-homogeneous halfspaces. What changed, and what does that change say about the role of the bias term?
Hints
- Count the points in each construction.
- Ask whether the boundary is required to pass through the origin.
- Connect the extra point to the increase from d to d+1.
Key Takeaways
- VC dimension is the largest number of points that a classification class can shatter, meaning it can realize every binary labeling of those points.
- Homogeneous halfspaces in R^d have VC dimension d: the standard basis vectors give the lower bound, and linear dependence of any d+1 vectors gives the upper bound.
- Non-homogeneous halfspaces in R^d have VC dimension d+1: the zero vector together with the d basis vectors gives the lower bound, while reduction to homogeneous halfspaces in R^(d+1) gives the upper bound.
- The bias term allows the separating boundary to shift away from the origin, adding one effective degree of freedom compared with the homogeneous setting.
Key Takeaways
- VC dimension measures classification capacity through shattering.
- Homogeneous halfspaces in R^d have VC dimension d.
- The homogeneous lower bound uses the d standard basis vectors.
- The homogeneous upper bound follows from linear dependence among any d+1 vectors.
- Allowing a bias shifts the boundary away from the origin and raises the non-homogeneous VC dimension to d+1.