Ranking Performance Measures
A ranking problem concerns ordering candidates by preference.
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.
- 1Create the first task
Train a binary learner that contrasts class A with all remaining classes, meaning B and C together.
- 2Create the second task
Train a binary learner that contrasts class B with all remaining classes, meaning A and C together.
- 3Create the third task
Train a binary learner that contrasts class C with all remaining classes, meaning A and B together.
- 4Combine 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.
- 1Compare A and B
Create a binary learner for the pair A and B.
- 2Compare A and C
Create a binary learner for the pair A and C.
- 3Compare B and C
Create a binary learner for the pair B and C.
- 4Combine 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.
Common mistake Treating the binary learners as independent final answers.
What it looks likeReading the outputs of several class-versus-rest tasks without applying a rule that selects one multiclass category.
Why it failsThe reduction must include a method for combining binary outputs.
Do this insteadTrace the combination stage explicitly and ask how the separate outputs determine the final class.
Common mistake Assuming correct binary training guarantees a correct multiclass predictor.
What it looks likeConcluding that the overall reduction must work because each individual binary task was solved correctly.
Why it failsThe reduction can fail when the outputs are combined, even when the individual binary learners solve their tasks.
Do this insteadAssess the complete multiclass decision, not only the component binary tasks.
Common mistake Confusing multiclass categorization with ranking.
What it looks likeDescribing a task that selects one category as though it were a task that orders candidates by preference.
Why it failsThese tasks require different kinds of outputs.
Do this insteadFirst 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? |
Identify the output before selecting or comparing a learning method.
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
- 1Multiclass categorization maps an instance to one of several possible target classes.
- 2One-versus-All contrasts each class with all remaining classes.
- 3All-Pairs contrasts every pair of classes and uses the resulting wins.
- 4A reduction method includes both its binary learners and its rule for combining their outputs.
- 5Multiclass categorization, structured output learning, and ranking differ according to the output the learner must produce.
At a glance
- 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.