Homogeneous Linear Separators

For the linear multiclass predictor class HΨ, the central result is an upper bound: Ndim(HΨ) is at most d.

Programming

A Complexity Question

The Natarajan dimension is a complexity measure for a hypothesis class. It asks how large a set of examples can be while still allowing the class to realize every possible choice between two competing labels for those examples. For the linear multiclass predictor class HΨ, the central result is an upper bound: Ndim(HΨ) is at most d.

How can a set of examples be shattered when every pattern of two competing label choices is realized by some hypothesis?

Class-Sensitive Features

The predictor class begins with a class-sensitive feature mapping Ψ. Its input contains an example x from the input space X together with a candidate class label from [k]. Its output is a vector in R^d. Because the label is part of the input to Ψ, the same example can receive different feature representations when it is paired with different candidate classes.

How does Ψ represent an input together with a candidate class label?

Worked example

Keeping the candidate label visible

Describe what changes when the same example x is paired with two different candidate labels.

1
Start with the example
Use one input x from X.
2
Pair with a first label
The mapping receives (x, f₀(x)) and produces Ψ(x, f₀(x)) in R^{^d}.
3
Pair with a second label
The mapping receives (x, f₁(x)) and produces Ψ(x, f₁(x)) in R^{^d}.
4
Compare the representations
The two vectors represent the same example under two different candidate classes, which allows the proof to compare the two label choices.

Result

The class label is part of the feature-mapping input, so Ψ can distinguish an example-label pair from the same example paired with another label.

One Vector Controls HΨ

Every hypothesis in HΨ is determined by one parameter vector w in R^d. This means the entire multiclass predictor is controlled by d parameters collected into w. The class-sensitive mapping supplies a vector for each example-label pair, while w supplies the common parameterization used across those pairs. Consequently, the comparisons that determine multiclass behavior are all governed by the same d-dimensional parameter vector.

How does one vector w determine the behavior of a complete multiclass hypothesis?

Key point

The important complexity fact is not merely that w has d coordinates. It is that every hypothesis in HΨ must use one such vector, so all label comparisons must be supported by the same d-dimensional parameterization.

The Difference-Vector Proof

The proof begins by assuming that a set C has been shattered. Shattering supplies two functions, f₀ and f₁, which specify the two competing class choices for every example in C. For each x in C, the proof forms one difference vector: ρ(x) = Ψ(x, f₀(x)) − Ψ(x, f₁(x)).

How does shattering force a transformed set of difference vectors, and why does that limit the size of C?

The transformed set ρ(C) lies in R^{^d}. The proof shows that ρ(C) is shattered by homogeneous linear separators. A homogeneous separator is the separator model used here to analyze the difference vectors, and the relevant fact is that a set shattered by such separators cannot contain more than d elements. Because the mapping from C to ρ(C) preserves the number of elements, the original set also satisfies |C| ≤ d.

Applying the Bound at d = 5

Worked example

A five-dimensional feature space

Suppose the feature mapping produces vectors in R^{^5}. What upper bound does the theorem give for the Natarajan dimension of HΨ?

1
Set the parameter dimension
Here d = 5, so every hypothesis in HΨ is controlled by a vector w in R^{^5}.
2
Assume a shattered set
Let C be any candidate set that is shattered, with two label-choice functions f₀ and f₁.
3
Transform each example
For every x in C, form ρ(x) = Ψ(x, f₀(x)) − Ψ(x, f₁(x)).
4
Use the separator result
The resulting set ρ(C) lies in R^{^5} and is shattered by homogeneous linear separators, so it cannot contain more than 5 elements.
5
Transfer the limit back
Because ρ preserves the number of elements in C, the original shattered set also has at most 5 elements.

Result

Ndim(HΨ) ≤ 5.

This calculation demonstrates how to use the theorem: the dimension d supplies the ceiling immediately. It does not demonstrate that five examples can actually be shattered. Establishing that lower bound would require additional information about the feature mapping and the hypothesis class.

Common Reasoning Errors

Common mistake
Treating Ndim(HΨ) ≤ d as if it meant Ndim(HΨ) = d.
What it looks like
For d = 5, concluding that the class must shatter a five-element set.
Why it fails
The theorem supplies an upper bound only. It does not construct a shattered set.
Do this instead
State that no shattered set can contain more than d elements; a matching lower bound needs separate evidence.
Common mistake
Ignoring the candidate class label in the feature mapping.
What it looks like
Thinking that Ψ receives only x.
Why it fails
The mapping receives both x and a class label from [k], so it can distinguish the same example paired with different classes.
Do this instead
Write the inputs as Ψ(x, label) and keep both parts visible when explaining the proof.
Common mistake
Trying to apply the homogeneous-separator bound directly to the original examples.
What it looks like
Skipping the construction of ρ(x).
Why it fails
The proof first converts the two multiclass choices into difference vectors in R^{^d}.
Do this instead
For each x in C, form ρ(x) = Ψ(x, f₀(x)) − Ψ(x, f₁(x)) before invoking the separator argument.
Common mistake
Treating each example as if it had an independent parameter vector.
What it looks like
Assigning a new vector to w for every x.
Why it fails
Each hypothesis in HΨ is determined by one shared vector w in R^{^d}.
Do this instead
Explain that the same w controls the comparisons for all example-label pairs.

Check Your Understanding

MEDIUM

A class-sensitive mapping Ψ outputs vectors in R^8. Suppose C is shattered using two label-choice functions f₀ and f₁. Describe the transformed vector assigned to each x in C and give the strongest conclusion supplied by the theorem.

Hints

Use the difference between the two feature vectors associated with the competing labels.
The transformed set lies in R^{^8}.
The separator bound limits the size of every shattered set.

Your attempt (not saved)

What do you think happens?

If d = 8, what upper bound should you predict for Ndim(HΨ)?

At most 4
At most 8
Exactly 8
There is no bound from d

Reveal answer

Answer:

At most 8

The proof transforms any shattered set into a set of difference vectors in R^{^d}, and the homogeneous-separator result limits that transformed set to at most d elements. The result is an upper bound, not a claim of equality.

What the Bound Tells You

1
The Natarajan dimension measures the multiclass shattering complexity of a hypothesis class.
2
The class-sensitive mapping Ψ represents an example together with a candidate class label and outputs a vector in R^d.
3
Every hypothesis in HΨ is controlled by one shared parameter vector w in R^{^d}.
4
For a shattered set C, the proof forms ρ(x) = Ψ(x, f₀(x)) − Ψ(x, f₁(x)) for each x in C.
5
The transformed set ρ(C) is shattered by homogeneous linear separators in R^{^d}, so Ndim(HΨ) is at most d.

Key Takeaways

Natarajan dimension measures how many examples a multiclass hypothesis class can shatter using two competing label choices.
The mapping Ψ includes both an example and a candidate class label, producing a vector in R^d.
A single vector w in R^{^d} determines each hypothesis in HΨ and controls all of its multiclass comparisons.
The proof converts each pair of label choices into a difference vector ρ(x) and studies the transformed set with homogeneous linear separators.
Since the transformed shattered set cannot exceed d elements, Ndim(HΨ) ≤ d.

Related concepts

More concepts starting with H