Multiclass Linear Predictors

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.

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.

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.

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.

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.

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.

Mistakes in Reduction Design

• Treating several binary learners as a complete multiclass method.

  The reduction must include a rule for combining binary outputs.

  Fix: Define the score comparison or vote aggregation step explicitly.

• Confusing One-versus-All with All-Pairs.

  One-versus-All contrasts each class with all remaining classes, whereas All-Pairs contrasts every pair of classes.

  Fix: Name the contrast used by each binary learner before discussing its outputs.

• Assuming correct binary training guarantees correct multiclass prediction.

  The binary learners are trained without directly knowing how their outputs will later be combined.

  Fix: Evaluate the complete reduction, including the aggregation rule.

• Choosing a reduction before identifying the output problem.

  Multiclass categorization, structured output learning, and ranking describe different output requirements.

  Fix: First state what the learner must produce.

Check Your Understanding