Concepts / Structured Output Learning

Structured Output Learning

A multiclass predictor must combine evidence for several possible classes into one output.

  • 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

  1. 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).
  2. 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.
  3. 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.
  4. 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).
  5. 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 Many Classes to One Decision

A multiclass prediction problem asks a learner to assign each instance to one class from a finite collection. A document might receive one topic, or an image might receive one object category. The central challenge is that the predictor must combine evidence about several possible classes and return one output.

Input instancefeaturesMulticlass predictorcombine evidenceClass AClass BClass Cpresent featureschoose onechoose onechoose one
How does an input move from its feature representation to one choice among a fixed set of possible classes?

The source presents two ways to construct this decision from binary classification: One-versus-All and All-Pairs. Both reuse a binary learning algorithm, but they create different binary training sets and combine their predictions differently.

One-versus-All Data Construction

Suppose the original problem has k classes. One-versus-All creates one binary classifier for each class. For the classifier devoted to class i, examples whose original label is i receive the positive label +1. Every example belonging to any other class receives the negative label -1. The classifier therefore learns to separate one chosen class from the entire remainder.

Original labelsA, B, CClass A+1Class B-1Class C-1label A becomes positiveother labels become negativeother labels become negative
How is the original multiclass dataset transformed into one binary dataset for a classifier devoted to a selected class?
Worked example

Building the Class-B Binary Set

A generated three-class dataset has original labels A, B, and C. Construct the binary labels for the One-versus-All classifier devoted to class B.

  1. 1
    Select the target class

    The classifier is devoted to class B.

  2. 2
    Relabel B examples

    Every example originally labeled B receives +1.

  3. 3
    Relabel the remaining examples

    Every example originally labeled A or C receives -1.

Result

The resulting binary task is B versus not-B: B is +1, while A and C are both -1.

Combining One-versus-All Outputs

After training, there is one predictor for each class. Each predictor supplies evidence about whether the input belongs to its own class rather than to the rest. The multiclass rule compares these class-specific outputs and selects the class with the largest output, an argmax decision.

Input instanceClassifier Ascore for AOutput comparisonlargest scoreChosen classone outputClassifier Bscore for BClassifier Cscore for Cevaluateevaluateevaluateoutputoutputoutputargmax
How do the outputs of several binary classifiers get combined to select one class?
Worked example

Selecting the Largest Class-Specific Output

A generated example has three One-versus-All outputs for one input: classifier A returns 0.4, classifier B returns 1.2, and classifier C returns 0.8. Which class does the multiclass rule select?

  1. 1
    Collect the outputs

    The three class-specific outputs are 0.4 for A, 1.2 for B, and 0.8 for C.

  2. 2
    Compare the outputs

    The largest value is 1.2, supplied by the classifier devoted to B.

  3. 3
    Apply the multiclass rule

    The argmax rule selects the class associated with the largest output.

Result

The selected class is B.

Edge case

If the binary predictors provide only binary outputs, more than one classifier may return +1. The system then needs a tie-breaking rule. Real-valued outputs are useful because their values can express confidence and can be compared directly.

All-Pairs Training Sets

All-Pairs uses a different decomposition. For every pair of distinct classes i and j, it keeps only examples whose labels are i or j. It then marks class i as +1 and class j as -1, training a binary predictor for that pair. Unlike One-versus-All, each binary task focuses on a direct comparison between two classes.

Class 1Classifier 1 vs 2examples from 1 and 2Class 2Classifier 1 vs 3examples from 1 and 3Class 3Classifier 2 vs 3examples from 2 and 3training examplestraining examplestraining examplestraining examplestraining examplestraining examples
Which training examples are used when a separate classifier is created for every pair of classes?
Worked example

Three Classes, Three Pairwise Problems

A generated problem has classes 1, 2, and 3. List the All-Pairs binary classifiers and describe the examples retained by each.

  1. 1
    Create the first pair

    The classifier for 1 versus 2 keeps only examples labeled 1 or 2.

  2. 2
    Create the second pair

    The classifier for 1 versus 3 keeps only examples labeled 1 or 3.

  3. 3
    Create the third pair

    The classifier for 2 versus 3 keeps only examples labeled 2 or 3.

  4. 4
    Assign binary labels

    Within each pair, one class receives +1 and the other receives -1.

Result

The construction produces the three comparisons 1 versus 2, 1 versus 3, and 2 versus 3.

Counting Pairwise Wins

At prediction time, each pairwise classifier chooses a winner between its two classes. The final All-Pairs rule counts the wins associated with each class and selects the class with the highest number of wins. For three classes, the three pairwise outcomes are combined into one winner count for each class.

Worked example

Combining Pairwise Outcomes

A generated three-class example produces these pairwise outcomes: class 1 defeats class 2, class 1 defeats class 3, and class 2 defeats class 3. Determine the final All-Pairs prediction.

  1. 1
    Count class 1 wins

    Class 1 wins against class 2 and class 3, giving it two wins.

  2. 2
    Count class 2 wins

    Class 2 loses to class 1 but wins against class 3, giving it one win.

  3. 3
    Count class 3 wins

    Class 3 loses to both class 1 and class 2, giving it zero wins.

  4. 4
    Select the largest count

    Class 1 has the greatest number of pairwise wins.

Result

The final All-Pairs prediction is class 1.

Where Reduction Can Fail

A reduction method should be evaluated as a complete multiclass construction, not only by inspecting its binary components. The source gives a three-class case in which One-versus-All can fail even though a direct argmax of suitable linear scores can classify the classes perfectly. The individual one-versus-all optimization may produce outputs that are not useful when combined across all classes.

Multiclass labelsA, B, C remain distinctOne-versus-All taskA versus not-AAll-Pairs tasksA-B, A-C, B-CCombination riskoutputs may not form a goodwholemerge non-target classeskeep one pair at a timecombined outputscombined wins
What class distinctions or relationships can be discarded when a multiclass problem is reduced to binary problems?
Binary trainingseparate objectivesBinary outputsclass-specific evidenceCombination ruleargmax or win countFinal classpossibly poor choiceproducesupply evidenceselect
How can individually trained binary classifiers produce conflicting or incorrect evidence when their predictions are combined?
  • Common mistake

    Assuming that strong binary components guarantee a strong multiclass predictor.

    What it looks like

    Each One-versus-All classifier appears reasonable when viewed separately.

    Why it fails

    The final predictor depends on how all binary outputs interact through the argmax or tie-breaking rule.

    Do this instead

    Check the complete multiclass construction, including the output-combination step.

  • Common mistake

    Treating a One-versus-All negative label as one original class.

    What it looks like

    For the classifier devoted to A, both B and C receive -1.

    Why it fails

    The negative label represents every class other than A.

    Do this instead

    Track the relabeling explicitly: the target class becomes +1 and all remaining classes become -1.

  • Common mistake

    Debugging the wrong stage when the final class is unexpected.

    What it looks like

    Changing the binary training process when the binary outputs were already correct.

    Why it fails

    An error may occur in the argmax or tie-breaking step rather than in binary learning.

    Do this instead

    Inspect binary outputs first, then inspect the combination rule.

Debugging the Decision Pipeline

  1. 1
    Start with the final class selected by the multiclass rule.
  2. 2
    Inspect the outputs supplied by the binary predictors.
  3. 3
    If the outputs are correct but the selected class is wrong, inspect the argmax or tie-breaking step.
  4. 4
    If the outputs themselves are poor, inspect the binary training sets and the binary learner.
  5. 5
    Evaluate the reduction method as a whole rather than judging only its separate binary components.

This debugging boundary separates three stages: preparing binary data, producing binary outputs, and combining those outputs into one class. The separation is useful because an unexpected final prediction does not by itself identify which stage failed.

Practice Check

MEDIUM

A problem has four classes: A, B, C, and D. Describe the One-versus-All binary labels for the classifier devoted to C. Then list every All-Pairs classifier that would be created. Finally, explain what you would inspect first if the final prediction were wrong but all binary outputs appeared reasonable.

Hints
  • For One-versus-All, identify the target class before relabeling the examples.
  • For All-Pairs, list every distinct pair of classes.
  • Separate binary outputs from the rule that combines them.

Finite Classes and Structured Outputs

The reduction methods described here assume a finite set of ordinary classes. The source distinguishes this setting from structured output learning, where the output space can be extremely large but has internal structure. Recognizing handwritten words is one example: the possible outputs are strings of bounded length, and the number of possible strings can be exponential in the maximum word length. In such a setting, treating every possible output as an unrelated class is not the same strategy as exploiting the structure of the output space.

Key Takeaways

  1. 1
    Multiclass categorization assigns an input to one class from a finite set.
  2. 2
    One-versus-All creates one binary dataset per class by labeling the target class +1 and every other class -1.
  3. 3
    One-versus-All combines class-specific outputs with an argmax; binary-only outputs may require tie-breaking.
  4. 4
    All-Pairs creates a binary classifier for every pair of classes and combines the resulting pairwise outcomes by counting wins.
  5. 5
    A reduction method must be evaluated as a complete multiclass predictor because separately trained binary components can combine poorly.
  6. 6
    For very large structured output spaces, exploiting output structure differs from treating every possible output as an unrelated class.

At a glance

  • Multiclass prediction combines evidence for several possible classes into one selected output.
  • One-versus-All separates each target class from all remaining classes and chooses the largest class-specific output.
  • All-Pairs trains one classifier for each pair of classes and selects the class with the most pairwise wins.
  • Errors can arise in binary training, binary outputs, or the final combination rule, so the full construction must be checked.
  • Reduction methods suit manageable finite class sets, while huge structured output spaces require methods that exploit output structure.

Related Topics

Related concepts

More concepts starting with S