Homogeneous Linear Separators
The Natarajan dimension is a complexity measure for a hypothesis class.
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.
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.
Keeping the candidate label visible
Describe what changes when the same example x is paired with two different candidate labels.
Start with the example: Use one input x from X.
Pair with a first label: The mapping receives (x, f₀(x)) and produces Ψ(x, f₀(x)) in R^d.
Pair with a second label: The mapping receives (x, f₁(x)) and produces Ψ(x, f₁(x)) in R^d.
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.
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.
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)).
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
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Ψ?
Set the parameter dimension: Here d = 5, so every hypothesis in HΨ is controlled by a vector w in R^5.
Assume a shattered set: Let C be any candidate set that is shattered, with two label-choice functions f₀ and f₁.
Transform each example: For every x in C, form ρ(x) = Ψ(x, f₀(x)) − Ψ(x, f₁(x)).
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.
Transfer the limit back: Because ρ preserves the number of elements in C, the original shattered set also has at most 5 elements.
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
Treating Ndim(HΨ) ≤ d as if it meant Ndim(HΨ) = d.
The theorem supplies an upper bound only. It does not construct a shattered set.
Fix:
State that no shattered set can contain more than d elements; a matching lower bound needs separate evidence.Ignoring the candidate class label in the feature mapping.
The mapping receives both x and a class label from [k], so it can distinguish the same example paired with different classes.
Fix:
Write the inputs as Ψ(x, label) and keep both parts visible when explaining the proof.Trying to apply the homogeneous-separator bound directly to the original examples.
The proof first converts the two multiclass choices into difference vectors in R^d.
Fix:
For each x in C, form ρ(x) = Ψ(x, f₀(x)) − Ψ(x, f₁(x)) before invoking the separator argument.Treating each example as if it had an independent parameter vector.
Each hypothesis in HΨ is determined by one shared vector w in R^d.
Fix:
Explain that the same w controls the comparisons for all example-label pairs.
Check Your Understanding
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.
What do you think happens?
If d = 8, what upper bound should you predict for Ndim(HΨ)?
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
- The Natarajan dimension measures the multiclass shattering complexity of a hypothesis class.
- The class-sensitive mapping Ψ represents an example together with a candidate class label and outputs a vector in R^d.
- Every hypothesis in HΨ is controlled by one shared parameter vector w in R^d.
- For a shattered set C, the proof forms ρ(x) = Ψ(x, f₀(x)) − Ψ(x, f₁(x)) for each x in C.
- 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.