Linear Multiclass Predictors
The Natarajan dimension is a complexity measure for a hypothesis class.
The Multiclass Prediction Problem
Multiclass prediction means choosing one class from several possible target classes. The important object is the mapping from an input to a selected output. A classifier may organize this task through binary subproblems, or it may compare all candidate classes directly.
Class-Sensitive Features
A linear multiclass predictor begins with a class-sensitive feature mapping called Ψ. Its input has two parts: an example x from the input space X and a class label from the finite label set [k]. Its output is a vector in R^d. Because the class label is included in the input, the representation can distinguish the same example when it is paired with different classes.
The vector w in R^d controls one complete hypothesis in HΨ. The predictor uses the same w when comparing the candidate classes for an input. Thus, changing w changes the hypothesis, while evaluating different class labels changes which class-sensitive feature vector is being scored. The representation and the parameter vector work together: Ψ describes the input-label pair, and w determines the particular predictor chosen from the class.
Reading a class-sensitive representation
Suppose the same input x is considered with two different candidate labels, a and b. What changes in the representation?
Pair the input with a label: The mapping receives (x, a), not x alone, so it can produce a feature vector specific to the input-label pair.
Change the candidate label: The mapping can instead receive (x, b). The two representations may differ because the class label is part of the input.
Use one hypothesis: The same vector w controls the scores used to compare the candidate labels for x.
Class-sensitive features let the representation distinguish different labels attached to the same example, while w specifies the complete hypothesis used for the comparison.
Why the Dimension Is at Most d
The Natarajan dimension is a complexity measure for a hypothesis class. It asks how large a set of inputs can be multiclass-shattered when each input has two competing class choices.
To analyze a candidate shattered set C, the proof uses two functions, f0 and f1, which provide the two class choices for every x in C. It then converts each multiclass comparison into a difference vector: ρ(x) = Ψ(x, f0(x)) − Ψ(x, f1(x)). This step turns the multiclass structure into geometry in R^d.
The transformed set ρ(C) lies in R^d and is shattered by homogeneous linear separators. A shattered set of this kind cannot contain more than d elements. The mapping ρ preserves the number of elements in the candidate set, so |C| is also at most d. Since every candidate shattered set satisfies this limit, the result is Ndim(HΨ) ≤ d.
Ndim(HΨ) ≤ d
Applying the bound when d = 5
A linear multiclass class HΨ uses a feature mapping into R^5. What upper bound does the theorem give for its Natarajan dimension?
Identify d: The feature vectors live in R^5, so the parameter dimension is d = 5.
Apply the theorem: The general result is Ndim(HΨ) ≤ d.
Substitute the dimension: Replacing d with 5 gives Ndim(HΨ) ≤ 5.
Interpret the result: No candidate multiclass-shattered set for this class can contain more than five inputs under the supplied theorem.
Ndim(HΨ) ≤ 5. This is an upper bound, not a proof that a five-element set is actually shattered.
Choosing the Greatest Class Score
A direct linear multiclass predictor compares one linear score for each candidate class. For an input x, it evaluates the class-sensitive representation for the possible labels and uses the same parameter vector w to produce the competing scores. The prediction is the class whose score is greatest.
Following the argmax decision
For one input, suppose the direct predictor produces three class scores: class A has 1.2, class B has 0.7, and class C has 1.8. Which class is selected?
List the candidates: The predictor has one score for each of the three possible classes.
Compare the scores: The values are 1.2, 0.7, and 1.8.
Select the greatest: The greatest value is 1.8, associated with class C.
The direct linear predictor selects class C.
Binary Reduction Strategies
One-versus-All and All-Pairs both reuse binary classification, but they create different binary learning problems. One-versus-All separates each named class from all remaining classes. All-Pairs trains a binary classifier for each particular pair of classes.
| Method | Binary training problem | Decision procedure |
|---|---|---|
| One-versus-All | Recognize one named class against the rest | Combine the binary outputs across the class-specific classifiers |
| All-Pairs | Choose between one particular pair of classes | Combine the pairwise outputs across the class-pair classifiers |
| Direct linear multiclass | Compare all candidate classes within one multiclass predictor | Select the class with the greatest score |
When Reduction Misaligns
A reduction method can perform poorly even when a good direct multiclass predictor exists because the independently created binary problems or their aggregation rule may not preserve the useful multiclass decision structure. A binary learner may receive a problem that is poorly matched to the original multiclass boundaries, or the separate outputs may disagree when they are recombined.
When a multiclass result disagrees with expectations, locate the disagreement in the pipeline. First check whether the original examples entered the intended binary training sets. Next inspect the binary predictor outputs. Finally verify how those outputs were combined and whether the rule used scores, positive labels, votes, or a tie-break.
Assuming that multiclass prediction is defined as one binary classifier per class.
Multiclass prediction is the task of selecting one class from several possible classes. One-versus-All is only one reduction method.
Fix:
Distinguish the prediction task from the method used to organize candidate classes.Assuming that a good multiclass predictor guarantees a good reduction.
The reduced binary problems and the aggregation rule may not preserve the original multiclass decision structure.
Fix:
Evaluate both the reduced problems and the final combination rule.Treating Ndim(HΨ) ≤ d as proof that the dimension equals d.
The theorem supplies a ceiling. A matching lower bound requires evidence that a set of that size is actually shattered.
Fix:
Report the result as an upper bound unless shattering has also been established.
Check Your Understanding
A linear multiclass predictor uses a class-sensitive mapping into R^d. Explain why the Natarajan dimension is at most d, naming the transformed vector used in the proof and the type of separators applied to the transformed set.
Hints
- Start by assuming that a set C is shattered.
- Use the two class-choice functions f0 and f1.
- Write the difference vector ρ(x) for each x in C.
- Explain why the transformed set cannot have more than d elements.
For a problem with four classes, describe the binary training questions asked by One-versus-All and by All-Pairs. Then explain one reason the final predictions of a reduction method might disagree with a good direct multiclass predictor.
Hints
- One-versus-All uses one named class against the rest.
- All-Pairs uses one particular class pair at a time.
- Consider how independent outputs are combined.
Key Takeaways
- The Natarajan dimension measures the multiclass shattering capacity of a hypothesis class.
- A class-sensitive mapping Ψ represents each input-label pair as a vector in R^d, while one vector w in R^d controls an entire hypothesis.
- The proof transforms two competing class choices into difference vectors ρ(x), then uses homogeneous linear separators to show Ndim(HΨ) ≤ d.
- One-versus-All separates each class from the rest, whereas All-Pairs compares classes two at a time.
- A direct linear multiclass predictor chooses the class with the greatest score, while a reduction method can lose useful structure through its binary problems or aggregation rule.
Key Takeaways
- The Natarajan dimension is a measure of how large a multiclass-shattered set a hypothesis class can support.
- For linear multiclass predictors using a mapping into R^d, the difference-vector proof gives Ndim(HΨ) ≤ d.
- The vector w in R^d determines one complete hypothesis and controls the class comparisons for every input.
- One-versus-All and All-Pairs reduce multiclass prediction to different collections of binary problems.
- Direct predictors choose the greatest class score, while reductions can fail when their independent binary decisions or aggregation rule misrepresent the multiclass structure.