Linear Multiclass Predictors
Multiclass prediction means choosing one class from several possible target classes.
Try it: Multiclass: One-vs-All, All-Pairs, Direct
How One-vs-All trains one binary classifier per class and All-Pairs one per pair of classes, how their outputs are combined (largest score, binary labels, or pairwise votes) into one class, and where a reduction fails although a direct linear multiclass predictor (argmax of k class scores) succeeds.
How it works
- One-vs-All: for each class i, relabel its points +1 and every other class −1, and train a binary linear classifier (logistic regression by gradient descent).
- All-Pairs: for each pair i < j, keep only the points of classes i and j, label i as +1 and j as −1, and train — classifiers.
- Combine: One-vs-All predicts the class with the largest score , or (binary labels only) a class whose says +1; All-Pairs gives each pairwise winner one vote and predicts the class with the most wins. Ties go to the smallest class and are reported.
- Direct: one linear multiclass predictor h(x) = argmax_y ⟨w, ψ(x, y)⟩ with a score per class, trained by the multiclass Perceptron (w ← w + ψ(x, y) − ψ(x, ŷ) on each mistake).
- Compare the combined prediction regions and training errors: with three bands side by side, the middle class cannot be separated from the rest, so One-vs-All by binary labels loses it, while All-Pairs and the direct predictor classify every point.
Default run (8 steps): One-vs-All with 3 classes: train 3 binary classifiers, one per class, each separating that class from all the remaining classes. The binary learner is logistic regression trained by 100 gradient-descent iterations (η = 0.5). … Combine: predict the class whose classifier gives the largest score ⟨w_i,x⟩ + b_i (ties go to the smallest class). Result on the training points: no training errors.
Simplified: Two features, at most 16 points and 3 or 4 classes. Every binary learner is the same deterministic logistic-regression gradient descent from w = 0 (fixed η and iteration count, no regularisation); the direct predictor uses ψ(x, y) = (x1, x2, 1) placed in block y of w and a first-mistake-in-list-order multiclass Perceptron with an update cap. Ties are broken towards the smallest class index, where the textbook allows any choice.
Loading the simulation…
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?
- 1Pair 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.
- 2Change the candidate label
The mapping can instead receive (x, b). The two representations may differ because the class label is part of the input.
- 3Use 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 Rd 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.
- 1Assume that C is multiclass-shattered.
- 2Use f0 and f1 to identify the two class choices for each x in C.
- 3Map each x to ρ(x) = Ψ(x, f0(x)) − Ψ(x, f1(x)).
- 4The set ρ(C) is shattered by homogeneous linear separators in Rd.
- 5Such a shattered set has at most d elements, so |C| ≤ d.
- 6Therefore the largest possible shattered set, and hence Ndim(HΨ), is at most 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?
- 1Identify d
The feature vectors live in R5, so the parameter dimension is d = 5.
- 2Apply the theorem
The general result is Ndim(HΨ) ≤ d.
- 3Substitute the dimension
Replacing d with 5 gives Ndim(HΨ) ≤ 5.
- 4Interpret 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?
- 1List the candidates
The predictor has one score for each of the three possible classes.
- 2Compare the scores
The values are 1.2, 0.7, and 1.8.
- 3Select 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 |
The methods differ in how they create binary problems or direct class comparisons.
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.
Common mistake Assuming that multiclass prediction is defined as one binary classifier per class.
What it looks likeTreating One-versus-All as the only possible multiclass construction.
Why it failsMulticlass prediction is the task of selecting one class from several possible classes. One-versus-All is only one reduction method.
Do this insteadDistinguish the prediction task from the method used to organize candidate classes.
Common mistake Assuming that a good multiclass predictor guarantees a good reduction.
What it looks likeExpecting independently trained binary classifiers to reproduce every useful direct multiclass boundary.
Why it failsThe reduced binary problems and the aggregation rule may not preserve the original multiclass decision structure.
Do this insteadEvaluate both the reduced problems and the final combination rule.
Common mistake Treating Ndim(HΨ) ≤ d as proof that the dimension equals d.
What it looks likeConcluding Ndim(HΨ) = 5 solely because the feature mapping outputs vectors in R^5.
Why it failsThe theorem supplies a ceiling. A matching lower bound requires evidence that a set of that size is actually shattered.
Do this insteadReport 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
- 1The Natarajan dimension measures the multiclass shattering capacity of a hypothesis class.
- 2A 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.
- 3The proof transforms two competing class choices into difference vectors ρ(x), then uses homogeneous linear separators to show Ndim(HΨ) ≤ d.
- 4One-versus-All separates each class from the rest, whereas All-Pairs compares classes two at a time.
- 5A 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.
At a glance
- 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 Rd, 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.