Binary Classification

The binary results from the relevant class comparisons are considered together to form a multiclass prediction.

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 Object to Prediction

A classification problem begins with two separate questions: What objects are we studying, and what labels could describe those objects? The collection of studied objects is the domain set, written as X. The collection of possible labels is the label set, written as Y. Binary classification uses a label set with two possible outcomes, while multiclass prediction has more than two possible target classes.

Domain Points and Feature Vectors

The domain set X contains the objects under study. An individual object in X is called a domain point. A domain point is usually represented by a vector of features. Each feature describes an aspect of that object for the learning problem. In the source example, a papaya is represented using features such as color and softness. These features describe the papaya; they are not labels.

How does a domain object become a vector of feature values, and what does each vector position represent?

Worked example

Separating object, features, and label

Consider the papaya example. Identify which items belong to X, which items belong to Y, and which items describe a domain point.

1
Domain set
X is the set of all papayas, so every papaya, including one particular papaya, belongs on the domain side.
2
Feature representation
Color and softness are features used to represent a papaya as a domain point.
3
Label set
Y is {0, 1}, so 0 and 1 are the possible labels in this binary example.

Result

The papaya is the object, color and softness are features, and 0 and 1 are possible labels.

Domain and Label Roles

Definition

The domain set X names the collection of objects being studied. The label set Y names the collection of possible labels. A domain object and a possible label play different roles: the object is what the problem examines, while the label is one of the allowed outcomes that can describe it.

What is contained in the domain set X versus the label set Y, and why are domain objects different from the labels that can be assigned to them?

When a domain point is considered together with a possible label, the object comes from X and the candidate outcome comes from Y. In the papaya example, a particular papaya remains a domain object even when it is considered together with 0 or with 1. The label does not become a feature, and the feature vector does not become a label.

How is a domain object considered together with a possible label, such as an object x paired with a label y?

Multiclass Prediction

Definition

A multiclass prediction problem has more than two possible target classes. Its goal is to learn a function that maps an input to one of k classes. Because a multiclass problem has several possible classes, it can be reduced to several binary classification problems, each asking a simpler yes-or-no question.

The reduction does not change the central distinction between domain objects and labels. The input is still a domain point represented by features, while the final prediction is selected from the problem's possible classes. What changes is the organization of the binary tasks used to reach that multiclass prediction.

One-Versus-All Training

The One-Versus-All Approach trains one binary classifier for each class. For a problem with k classes, it creates k binary training sets and k binary predictors. The classifier associated with class i learns to distinguish class i from every other class. Thus, each binary task gives one class its own contest against all remaining classes.

How is one multiclass training set transformed into several binary training sets, each separating one class from all remaining classes?

For a new instance, the trained predictors are considered together to construct a multiclass predictor. Each predictor represents one candidate class and distinguishes that class from all the remaining classes. The important point is the structure: there is one binary task per class, not one task for every pair of classes.

All-Pairs Training

The All-Pairs Approach trains a binary classifier for every pair of classes. The training set for a pair of classes i and j contains only examples whose original labels are i or j. Instead of asking one class to compete against all remaining classes, this approach gives every pair of classes a direct binary comparison.

How are binary training sets created for every pair of classes, and how do their comparisons contribute to a multiclass prediction?

The prediction process follows the same pairwise organization. The binary results from the relevant class comparisons are considered together to form a multiclass prediction. The source establishes that these results are combined differently from One-Versus-All; the essential distinction is that each result comes from a direct comparison between two classes.

Two Reduction Structures

Aspect	One-Versus-All	All-Pairs
Binary training sets	One for each class	One for every pair of classes
Examples used by one task	The selected class versus all remaining classes	Only examples whose labels are the selected pair
Binary predictors for k classes	k predictors	A predictor for every class pair
Meaning of each binary task	One class competes against the rest	Two classes compete directly
Multiclass prediction	The class-specific predictors are considered together	The pairwise comparisons are considered together

The approaches use the same general reduction idea but organize binary tasks differently.

What differs between the number and structure of binary models trained and the sequence of decisions made during prediction in the two approaches?

Common Classification Mistakes

Common mistake
Treating a domain object as a label
What it looks like
Putting a papaya on the label side of the problem.
Why it fails
The papaya is an object in the domain set X, while the labels belong to Y.
Do this instead
Place the papaya in X and reserve 0 and 1 for the possible labels in the source example.
Common mistake
Treating features as labels
What it looks like
Calling color and softness the two labels.
Why it fails
Color and softness are features used to represent a domain point.
Do this instead
Use color and softness as feature components, and use 0 and 1 as the possible labels.
Common mistake
Describing One-Versus-All as a pairwise method
What it looks like
Saying that each One-Versus-All classifier compares two selected classes.
Why it fails
One-Versus-All compares one class with every other class in its binary task.
Do this instead
Remember that All-Pairs creates a separate task for each pair, while One-Versus-All creates one task for each class.
Common mistake
Assuming both approaches use the same training examples in each binary task
What it looks like
Using every original example in an All-Pairs task.
Why it fails
An All-Pairs training set for classes i and j contains only examples whose original labels are i or j.
Do this instead
Select only the examples belonging to the chosen pair for an All-Pairs task.

Check Your Understanding

MEDIUM

A problem has three possible classes. Explain how One-Versus-All and All-Pairs would organize its binary training tasks. Then explain what kind of results would be considered together when making a multiclass prediction.

Hints

For One-Versus-All, identify how many class-versus-rest tasks are created.
For All-Pairs, list the kinds of class pairs that can be selected.
Keep the training structure separate from the prediction process.

Your attempt (not saved)

What do you think happens?

For a three-class problem, which approach creates a binary task whose training examples contain only classes 1 and 3?

One-Versus-All
All-Pairs
Both approaches in the same form

Reveal answer

Answer:

All-Pairs

The All-Pairs Approach creates a binary training set for every pair of classes, and the task for classes 1 and 3 contains only examples whose original labels are 1 or 3.

Key Takeaways

1
X is the domain set of objects being studied; Y is the label set of possible labels.
2
A domain point is usually represented by a feature vector, and features are not labels.
3
In the source papaya example, X is the set of all papayas and Y is {0, 1}.
4
A multiclass problem has more than two target classes and can be reduced to several binary problems.
5
One-Versus-All trains one class-versus-rest classifier per class, while All-Pairs trains one classifier for every pair of classes.
6
The two approaches differ both in which examples each binary task uses and in how the binary results are considered together for multiclass prediction.

At a glance

The domain set X contains the objects under study, while the label set Y contains possible labels.
Feature vectors represent domain points; their features should not be confused with labels.
Multiclass prediction can be reduced to several binary classification tasks.
One-Versus-All creates one class-versus-rest task for each class.
All-Pairs creates one task for every pair of classes and uses those pairwise results together for prediction.

More concepts starting with B