Ranking Performance Measures
Multiclass prediction can be reduced to binary classification, but the reduction must include a rule for combining binary outputs.
From Two Choices to Many
Start by identifying what the learner must produce. In binary classification, the prediction concerns two possible classes. In multiclass categorization, an instance belongs to one of several possible target classes. Formally, a predictor maps an instance space X to a finite set of categories Y. For example, X might contain documents and Y their possible topics, or X might contain images and Y the possible objects appearing in them.
A binary learner cannot by itself express the whole multiclass decision when more than two categories are possible. A reduction method addresses this by creating several binary learning tasks and then adding a rule for combining their outputs. The combination rule is not an optional final detail: it is part of the multiclass method.
One-versus-All Reduction
One-versus-All creates one binary task for each class. Each task contrasts one selected class with all of the remaining classes. The method therefore changes one multiclass problem into several binary contrasts. After the binary learners produce their outputs, a combination rule uses those outputs to choose the final multiclass category.
Three Classes with One-versus-All
Suppose the possible categories are A, B, and C. Show the binary tasks created by One-versus-All and the role of the final decision.
Create the first task: Train a binary learner that contrasts class A with all remaining classes, meaning B and C together.
Create the second task: Train a binary learner that contrasts class B with all remaining classes, meaning A and C together.
Create the third task: Train a binary learner that contrasts class C with all remaining classes, meaning A and B together.
Combine outputs: Apply a rule to the outputs of the three binary learners. The rule selects one final category rather than returning three independent binary answers.
One multiclass task has been represented by three class-versus-rest binary tasks plus a rule for combining their outputs.
All-Pairs Comparisons
All-Pairs takes a different route. Instead of contrasting each class with all remaining classes, it contrasts every pair of classes. Each binary learner addresses one pairwise question. The resulting wins are then used together to make the multiclass decision.
Three Classes with All-Pairs
Suppose the possible categories are A, B, and C. Show the pairwise binary tasks and how their outcomes contribute to the final decision.
Compare A and B: Create a binary learner for the pair A and B.
Compare A and C: Create a binary learner for the pair A and C.
Compare B and C: Create a binary learner for the pair B and C.
Combine wins: Collect the wins from the pairwise comparisons and use them to select the final multiclass category.
All-Pairs represents the multiclass task through every pairwise comparison and a rule based on the resulting wins.
Where Reduction Can Break
A reduction method has two connected parts: the binary learning tasks and the rule that combines their outputs. A binary learner may solve its individual task correctly, yet the complete multiclass predictor can still perform poorly at the combination stage. The reason is that the binary learner is trained without directly knowing how its output will later participate in the multiclass decision.
Treating the binary learners as independent final answers.
The reduction must include a method for combining binary outputs.
Fix:
Trace the combination stage explicitly and ask how the separate outputs determine the final class.Assuming correct binary training guarantees a correct multiclass predictor.
The reduction can fail when the outputs are combined, even when the individual binary learners solve their tasks.
Fix:
Assess the complete multiclass decision, not only the component binary tasks.Confusing multiclass categorization with ranking.
These tasks require different kinds of outputs.
Fix:
First identify whether the learner must select one category, predict structured components, or order candidates by preference.
Three Output Tasks
Before comparing reduction methods, identify the required output. Multiclass categorization assigns an instance to one of several possible target classes. Structured output learning concerns predicting related structured components. A ranking problem concerns ordering candidates by preference. These should not be treated as interchangeable simply because each may involve several possible outcomes.
| Task type | Required output | Central question |
|---|---|---|
| Multiclass categorization | One class from several target classes | Which category does this instance belong to? |
| Structured output learning | Related structured components | What structured output should be predicted? |
| Ranking | An ordering of candidates by preference | Which candidates should come before others? |
Practice Check
A task has four possible target classes. You are considering One-versus-All and All-Pairs. Describe the binary tasks created by each method, then explain why the final combination rule must be evaluated separately from the binary learners.
Hints
- For One-versus-All, begin with one selected class and contrast it with all remaining classes.
- For All-Pairs, list comparisons between each pair of the four classes.
- For the final part, distinguish the quality of individual binary tasks from the quality of the complete multiclass decision.
Key Takeaways
- Multiclass categorization maps an instance to one of several possible target classes.
- One-versus-All contrasts each class with all remaining classes.
- All-Pairs contrasts every pair of classes and uses the resulting wins.
- A reduction method includes both its binary learners and its rule for combining their outputs.
- Multiclass categorization, structured output learning, and ranking differ according to the output the learner must produce.
Key Takeaways
- Multiclass categorization selects one class from several possible target classes.
- One-versus-All creates one class-versus-rest binary task for each class.
- All-Pairs creates a binary comparison for every pair of classes and combines the resulting wins.
- Correct binary learners do not guarantee a correct multiclass prediction because the combination stage can fail.
- Always identify whether the required output is one category, a structured output, or an ordering of candidates.