All-Pairs Reduction

The defining organizational idea is not a single binary classifier. It is a collection of pair-specific classifiers whose outputs must later be combined.

Programming

Interactive lab

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.

Educational simulation

Loading the simulation…

From Binary Outputs to One Label

A multiclass prediction problem has more than two possible labels, but a reduction can solve it by assembling several binary classifiers. Each binary classifier examines a new instance and produces a binary prediction. A separate prediction rule then receives the collection of binary outputs and selects one multiclass label.

How are multiclass labels connected to the collection of binary classifiers, with one classifier assigned to each pair of labels?

Pairwise Classifier Organization

In All-Pairs, the binary classifiers are organized around pairs of multiclass labels. For every pair under consideration, one binary classifier is assigned to that pair. The classifier produces a binary result for a new instance, and the complete collection of pairwise results is passed to the prediction rule.

For a set of labels, how does each label pair map to a binary classifier?

Key point

The defining organizational idea is not a single binary classifier. It is a collection of pair-specific classifiers whose outputs must later be combined.

Combining the Binary Predictions

The binary outputs do not automatically constitute the final answer. The reduction also specifies a prediction rule. That rule takes the collection of binary predictions and converts it into one multiclass label. Consequently, changing the binary classifiers can change the output pattern, while changing the prediction rule can change how the same pattern is interpreted.

How do the outputs of all pairwise binary classifiers become one final multiclass label?

Worked example

Tracing an Abstract Prediction

Suppose three labels are available and the three pairwise classifiers produce a collection of binary outputs for one new instance. How does the reduction use those outputs?

1
Collect
Each pairwise classifier produces its binary prediction for the same new instance.
2
Combine
The prediction rule receives the full collection rather than examining only one binary prediction.
3
Select
The prediction rule interprets that collection and chooses one multiclass label.

Result

The final prediction is produced by the pairwise classifiers together with the prediction rule. The binary-output pattern alone is not the complete reduction specification.

What do you think happens?

If one pairwise classifier changes its prediction while all other classifiers and the prediction rule stay fixed, what can change?

Reveal answer

Answer:

The collection of binary outputs can change, and therefore the final multiclass prediction can change.

The multiclass label is selected from the combined binary-output pattern. Changing one binary output changes that pattern.

Complexity of the Induced Class

A reduction produces a multiclass hypothesis class. Its complexity is measured using the Natarajan dimension. The important point is that this induced multiclass class is determined jointly by the binary hypothesis class and the prediction rule. Studying only one binary classifier in isolation does not describe the whole multiclass construction.

How does Lemma 29.6 relate the complexity of the binary class to the complexity of the induced multiclass class?

Framework and Named Methods

Multiclass-to-binary reduction is the general framework: assemble several binary classifiers and use a prediction rule to produce one multiclass label. One-versus-All and All-Pairs are specific reductions within that framework. They differ in how the binary classifiers are organized and how their predictions are combined, while sharing the broader pattern of binary training followed by multiclass prediction.

What is shared by multiclass-to-binary reductions, and what differs between One-versus-All and All-Pairs?

Item	What it specifies
General reduction framework	Several binary classifiers plus a prediction rule that produces one multiclass label
One-versus-All	A specific organization of binary classifiers and their final prediction rule
All-Pairs	A specific organization using classifiers assigned to pairs of multiclass labels
Lemma 29.6	A relationship that uses binary VC dimension to upper bound the Natarajan dimension of the induced multiclass class

The general framework contains specific methods; the complexity lemma analyzes the resulting multiclass class.

Common Reasoning Errors

Common mistake
Treating one binary classifier as the entire multiclass predictor.
What it looks like
Looking at only the classifier assigned to one label pair and calling its output the final multiclass answer.
Why it fails
The reduction assembles several binary classifiers, and a separate prediction rule combines their outputs.
Do this instead
Track the complete collection of binary predictions before identifying the final label.
Common mistake
Ignoring the prediction rule.
What it looks like
Describing the binary classifiers but never specifying how their outputs become one multiclass label.
Why it fails
The resulting multiclass hypothesis class depends on the binary class and the prediction rule together.
Do this instead
Treat the prediction rule as a required part of the reduction.
Common mistake
Confusing the VC dimension with the Natarajan dimension.
What it looks like
Calling the VC dimension the complexity measure of the final multiclass class.
Why it fails
The binary hypothesis class has VC dimension, while the induced multiclass class is measured using the Natarajan dimension.
Do this instead
Use the VC dimension as the binary-side quantity and the Natarajan dimension for the resulting multiclass class.
Common mistake
Treating All-Pairs as the general framework.
What it looks like
Using the name All-Pairs for every multiclass-to-binary reduction.
Why it fails
All-Pairs is one specific method inside the broader multiclass-to-binary reduction framework.
Do this instead
Separate the shared framework from the organization specific to All-Pairs.

Check Your Understanding

MEDIUM

A reduction uses several binary classifiers and a prediction rule. Explain what information is produced by the binary classifiers, what the prediction rule does with that information, and which dimension measures the complexity of the resulting multiclass hypothesis class.

Hints

Mention the collection of binary predictions for a new instance.
Explain why the final label cannot be identified from one binary classifier alone.
Distinguish the VC dimension of the binary class from the Natarajan dimension of the induced multiclass class.

Your attempt (not saved)

MEDIUM

Compare the general multiclass-to-binary reduction framework with All-Pairs and One-versus-All. State what all three share and what the named methods specify more narrowly.