Homogeneous and Non-homogeneous Linear Separators

A homogeneous halfspace uses a separating boundary that is required to pass through the origin.

Programming

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.

How do the possible binary labelings of a finite set relate to whether a hypothesis class shatters that set?

Key point

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.

How does requiring the separating boundary to pass through the origin limit labelings, and why does the maximum shattered set have size d?

Worked example

Shattering the standard basis vectors

Show why the d standard basis vectors can receive every binary labeling under homogeneous halfspaces.

1
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.
2
Choose a labeling
Suppose the desired binary labels are y1 through yd.
3
Build the weight vector
Use those desired labels as the coordinates of the weight vector w.
4
Evaluate each point
The dot product of w with ei selects the i-th coordinate of w, so the result equals yi.
5
Conclude shattering
Because the weight vector can be chosen for every desired binary labeling, the d basis vectors are shattered.

Result

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.

1
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.

What additional configurations become possible when the separating boundary can shift away from the origin?

Worked example

The d+1 point construction

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

1
Choose the set
Take the zero vector together with the d standard basis vectors.
2
Count the points
There is one zero vector plus d basis vectors, giving d+1 points.
3
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.
4
Interpret the increase
Allowing the boundary to shift away from the origin makes one additional point available in a shattered set.

Result

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

Which geometric change is controlled by the weight vector, which is controlled by the bias, and how do they jointly determine the decision boundary?

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}.

How does adding the bias term change the separator's position and add one effective degree of freedom?

Common Proof Mistakes

Common mistake
Showing only that d points can be shattered and then stopping.
What it looks like
The standard basis construction proves that the VC dimension is at least d for homogeneous halfspaces.
Why it fails
An exact VC dimension also requires proving that no larger set can be shattered.
Do this instead
Add the linear-dependence upper bound for d+1 vectors.
Common mistake
Treating the homogeneous and non-homogeneous cases as having the same capacity.
What it looks like
Both cases use linear separating boundaries, so they are assumed to have VC dimension d.
Why it fails
The homogeneous boundary must pass through the origin, while the non-homogeneous boundary can shift away from it.
Do this instead
Track the bias term and remember that the non-homogeneous VC dimension is d+1.
Common mistake
Using linear dependence without explaining the sign contradiction.
What it looks like
A set of d+1 vectors is linearly dependent, so it cannot be shattered.
Why it fails
Linear dependence becomes a shattering contradiction only after separating positive and negative coefficients and examining the required dot-product signs.
Do this instead
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.
Common mistake
Describing the bias as another ordinary coordinate without connecting it to geometry.
What it looks like
The bias adds one number, so the VC dimension increases by one automatically.
Why it fails
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.
Do this instead
Relate the added term to the shifted boundary and the R^(d+1) reduction.

Check Your Reasoning

MEDIUM

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.

Your attempt (not saved)

EASY

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?