Multiclass Linear Predictors
A multiclass problem is not solved merely by collecting several binary predictions. The system also needs a rule that combines those binary outputs into one multiclass decision.
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…
From Two Labels to Many
Binary classification chooses between two possible labels. Multiclass categorization chooses one class from several possible target classes. Formally, a multiclass predictor maps an instance space X to a finite set of categories Y. For example, the instances might be documents and the categories might be their possible topics, or the instances might be images and the categories might be the possible objects appearing in them.
A multiclass problem is not solved merely by collecting several binary predictions. The system also needs a rule that combines those binary outputs into one multiclass decision.
Class-Specific Scores
A multiclass linear predictor can be understood as comparing class-specific scores for one input. Each possible class contributes a score, and the prediction is the class associated with the largest score. This gives the learner a direct mental model for multiclass prediction: one input is evaluated against several class possibilities, then the scores are compared.
Selecting the Largest Class Score
An input is evaluated for three possible classes. The resulting scores are Class A: 0.42, Class B: 0.81, and Class C: 0.37. Which class is selected?
- 1Compare
Place the three class-specific scores side by side.
- 2Find the largest
The score for Class B is larger than the scores for Class A and Class C.
- 3Select
Use the class associated with the largest score as the prediction.
The predicted class is Class B.
One-versus-All Reduction
One-versus-All, also called One-versus-Rest, contrasts each class with all remaining classes. For every possible class, a binary learner is trained to distinguish that class from the collection of other classes. A multiclass input is then passed through the class-specific binary learners, and their outputs are combined using a decision rule. The class with the strongest resulting score is selected.
One-versus-All for Three Topics
A document must be assigned to one of three topics: sports, science, or travel. Describe the One-versus-All binary tasks and use their scores to choose a topic.
- 1Create binary tasks
Train one learner for sports versus all other topics, one for science versus all other topics, and one for travel versus all other topics.
- 2Evaluate the document
The document is evaluated by all three binary learners.
- 3Combine outputs
Compare the three resulting class scores using the multiclass decision rule.
- 4Choose one class
Assign the document to the topic whose learner produces the strongest resulting score.
One-versus-All turns the three-class task into three binary contrasts and then needs a score-combination rule to produce one topic.
All-Pairs Voting
All-Pairs contrasts every pair of classes. Instead of comparing one class with all remaining classes, it creates a binary learner for each pair, such as Class A versus Class B and Class A versus Class C. For a new input, the pairwise learners produce binary outcomes. The system combines the resulting wins, and the class with the strongest overall vote is selected.
Combining Pairwise Wins
Three classes, A, B, and C, are compared in every pair. An input is assigned the winner A in A versus B, the winner A in A versus C, and the winner C in B versus C. Which class receives the most wins?
- 1List comparisons
The pairwise learners compare A with B, A with C, and B with C.
- 2Count wins
Class A receives two wins. Class B receives no wins. Class C receives one win.
- 3Aggregate
Use the accumulated wins as the multiclass decision signal.
Class A is selected because it receives the most pairwise wins.
When Reduction Breaks
A reduction method can perform poorly at the combination stage even when every binary learner has solved its own training problem correctly. The reason is that each binary learner is trained separately and does not directly know how its output will later participate in the multiclass decision. The binary tasks may therefore produce outputs that are individually reasonable but collectively difficult to combine.
Binary learners are evaluated separately. Each learner solves its own contrast.
Individual binary tasks appear reasonable.
The reduction combines all binary outputs. The final multiclass decision is evaluated as a whole.
The combined multiclass prediction may still be poor.
Three Output Problems
Before comparing reduction methods, identify what the learner must produce. In multiclass categorization, an instance belongs to one of several possible target classes, so the predictor maps an instance to a finite set of categories. Structured output learning and ranking are different problem types rather than alternative names for this same multiclass task. The important diagnostic question is whether the desired result is one category from a finite set, an output with additional structure, or an ordering among possibilities.
State the output requirement before selecting One-versus-All or All-Pairs. A reduction is appropriate only after the task has been identified as multiclass categorization and the desired combination rule is clear.
Mistakes in Reduction Design
Common mistake Treating several binary learners as a complete multiclass method.
What it looks likeTrain one binary learner per class but never specify how their outputs select one final class.
Why it failsThe reduction must include a rule for combining binary outputs.
Do this insteadDefine the score comparison or vote aggregation step explicitly.
Common mistake Confusing One-versus-All with All-Pairs.
What it looks likeDescribe a Class A versus all-other-classes learner as if it were only a Class A versus Class B learner.
Why it failsOne-versus-All contrasts each class with all remaining classes, whereas All-Pairs contrasts every pair of classes.
Do this insteadName the contrast used by each binary learner before discussing its outputs.
Common mistake Assuming correct binary training guarantees correct multiclass prediction.
What it looks likeConclude that the final predictor must be good because every binary learner performs well on its own task.
Why it failsThe binary learners are trained without directly knowing how their outputs will later be combined.
Do this insteadEvaluate the complete reduction, including the aggregation rule.
Common mistake Choosing a reduction before identifying the output problem.
What it looks likeApply a multiclass categorization reduction to a problem whose desired result is an ordering rather than one category.
Why it failsMulticlass categorization, structured output learning, and ranking describe different output requirements.
Do this insteadFirst state what the learner must produce.
Check Your Understanding
A task has four possible target classes. You want to reuse binary learning algorithms. Describe how One-versus-All would create its binary tasks, then describe how All-Pairs would create its binary tasks. Finally, explain one reason the final multiclass predictor could perform poorly even if all binary learners were trained correctly.
Hints
- For One-versus-All, describe one class versus all remaining classes.
- For All-Pairs, describe comparisons between every pair of classes.
- Include the missing combination or aggregation stage in your explanation.
What do you think happens?
A multiclass system has three class-specific scores for one input: Class A is 0.55, Class B is 0.31, and Class C is 0.72. Which class does the score-based decision rule select?
Reveal answer
Class C
Class C has the largest class-specific score.
Key Takeaways
- Multiclass categorization maps an instance to one class from a finite set of possible categories.
- One-versus-All contrasts each class with all remaining classes and combines the resulting class-specific outputs.
- All-Pairs contrasts every pair of classes and uses the resulting wins to select a class.
- A reduction method can fail during output combination even when its individual binary learners solve their own tasks correctly.
- Before choosing a reduction, identify whether the learner must produce one category, a structured output, or an ordering.