Multi-class Strategies
One-vs-rest, one-vs-one, and error-correcting output codes.
On this page
Beginner: the Perceptron (section 2.4.3) and plenty of other classifiers only know how to answer a yes/no question — "is this a cat, or not?" But most real problems have more than two categories: ten digits, a thousand product SKUs, dozens of diagnoses. Multi-class strategies are the recipes for building a K-category classifier entirely out of yes/no classifiers, without inventing a new model. Softmax regression (section 2.4.2) handles K classes natively, in one model — these strategies are for every classifier that doesn't.
Intermediate: there are three classic recipes. One-vs-Rest (OvR) trains K classifiers, each answering "is it class k, or anything else?", and picks the most confident "yes." One-vs-One (OvO) trains a separate classifier for every pair of classes and lets them vote. Error-Correcting Output Codes (ECOC) generalizes both: assign each class a binary codeword, train one classifier per codeword bit, and decode a new point by finding whose codeword its classifiers' outputs are closest to.
Advanced: all three are instances of the same idea — a coding matrix M ∈ {−1,+1}^(K×L) whose rows are class codewords and whose columns define the L binary sub-problems to train. OvR is the coding matrix M = 2I − 1 (L=K); OvO is a ternary coding matrix with a "don't care" symbol per column (L=K(K−1)/2); ECOC is the general case, and its L can be chosen large enough that the code has real error-correcting power — a genuinely different design space, borrowed directly from information theory, that OvR and OvO don't exploit at all.
One-vs-Rest — argmax over K real-valued confidences:
One-vs-One — majority vote among the K(K−1)/2 pairwise classifiers:
ECOC — nearest codeword by Hamming distance, where o(x) is the vector of all L classifiers' outputs and M_k is class k's codeword (row k of the coding matrix):
For K classes, train K binary classifiers. Classifier k is trained on the relabeled problem "class k" (positive) vs. "every other class pooled together" (negative) — so its training set has n_k positives against n − n_k negatives. As K grows this ratio worsens: with K=10 roughly-balanced classes, every one of the 10 sub-problems is fought at about a 1-to-9 imbalance, even though the original K-class problem was perfectly balanced. That imbalance is a real side effect of the OvR construction itself, not a property of the data.
At prediction time, feed x into all K classifiers. If each one only returned a {−1,+1} vote, two failure modes are common: more than one classifier says "yes" (which class wins?), or every classifier says "no" (there's no "yes" to pick at all). Both are resolved the same way — by using a real-valued score s_k(x) (the Perceptron's raw margin θ_k^⊤x + b_k, or a probability from logistic regression, section 2.4.1) instead of just its sign, and taking argmax_k s_k(x). Multiple "yes" votes are broken by whichever score is most confidently positive; zero "yes" votes are broken by whichever score is least confidently negative. The sign alone throws away exactly the information argmax needs.
Train one binary classifier per unordered pair of classes. Each of the K classes pairs with the other K−1 classes, giving K(K−1) ordered pairs — but the pair (i, j) and (j, i) are the same classifier, so every unordered pair is counted exactly twice. Dividing out that double-count:
For K=3 that's 3 classifiers; for K=10 it's 45; for K=100 it's 4,950 — quadratic in K, against OvR's linear K. Each classifier h_{ij} is trained (and queried) using only the data from classes i and j — it has never seen any other class and has nothing to say about them. At prediction time every one of the K(K−1)/2 classifiers casts a vote for whichever of its own two classes it prefers, and argmax is taken over the resulting vote tally. Because each sub-problem is smaller (only 2 classes' worth of data, typically also more easily separable than "k vs. everything"), each individual OvO classifier is often much cheaper to train than an OvR classifier — a real tradeoff: OvR trains fewer, larger classifiers; OvO trains more, smaller ones. For classifiers whose training cost scales worse than linearly in sample size (kernel SVMs are the classic case), OvO's many small sub-problems can add up to less total training time than OvR's few large ones, which is exactly why libsvm-style toolchains have historically defaulted to OvO.
Plain vote-counting can tie — the diagram below shows a genuine 3-way tie region for K=3. Production implementations break these ties either by comparing each pairwise classifier's real-valued margin (not just its vote) and summing those, or with a dedicated calibration step such as Platt scaling followed by pairwise coupling (fitting a single set of class probabilities that's most consistent with all K(K−1)/2 pairwise probability estimates at once) — the same "use the score, not just the sign" idea as OvR, just applied after the vote instead of instead of it.
Generalize both recipes: choose a coding matrix M ∈ {−1,+1}^(K×L) whose row M_k is class k's length-L binary codeword. Column l of M splits the K classes into two groups (whichever get +1 vs. −1 in that column) and defines one binary classifier h_l, trained on that split. OvR is the special case M = 2I − 1 (an L=K identity-flavored matrix: class k's own column is +1, every other column is −1) — every "rest" group is pooled. OvO is the special case with a ternary alphabet {−1, 0, +1} and L=K(K−1)/2 columns, one per pair (i, j): column (i,j) has +1 in row i, −1 in row j, and 0 ("don't care" — not trained or queried on that class) everywhere else.
To classify a new x, run all L classifiers to get an output vector o(x) = (h_1(x), …, h_L(x)), then decode by picking the class whose codeword is nearest in Hamming distance: ŷ = argmin_k d_H(o(x), M_k). This is literally the same nearest-codeword decoding rule used for error-correcting codes in communications — treat each of the L weak binary classifiers as a noisy "channel" that might flip a bit, and decode by finding the valid codeword closest to what was received.
The correction guarantee. Let d_min be the smallest Hamming distance between any two distinct rows of M. Suppose the true class is k* and, at most, e of the L individual classifiers are wrong (flip a bit) — so d_H(o(x), M_{k*}) ≤ e. For decoding to still pick k* correctly, every other row M_j must be farther from o(x) than M_{k*} is. By the triangle inequality for Hamming distance:
Decoding is guaranteed correct as long as this lower bound still beats e itself — i.e. d_min − e > e, or e < d_min / 2. The largest integer e satisfying that is:
Worked example. Take K=4 classes and L=7 classifiers, with the coding matrix built from an order-8 Hadamard matrix (dropping one constant column) — the largest minimum distance achievable for 4 codewords of length 7:
| class | f1 | f2 | f3 | f4 | f5 | f6 | f7 |
|---|---|---|---|---|---|---|---|
| Class 0 | +1 | +1 | +1 | +1 | +1 | +1 | +1 |
| Class 1 | −1 | +1 | −1 | +1 | −1 | +1 | −1 |
| Class 2 | +1 | −1 | −1 | +1 | +1 | −1 | −1 |
| Class 3 | −1 | −1 | +1 | +1 | −1 | −1 | +1 |
Every pair of rows differs in exactly 4 positions, so d_min = 4 and the guarantee is ⌊(4−1)/2⌋ = 1 — one wrong classifier out of 7 is always survivable. Take the true class as Class 2, codeword (+1,−1,−1,+1,+1,−1,−1). Flip classifier f2's output (1 error): the received vector is now at distance 1 from Class 2, but distance 3 from both Class 0 and Class 1 and distance 5 from Class 3 — Class 2 wins cleanly, exactly as the guarantee promises. Flip f2 and f4 (2 errors, past the guarantee): the received vector happens to land at distance 2 from Class 2 and distance 4 from every other class — still a clean, correct decode, better than the guarantee strictly promises. But flip f2 and f6 instead (also 2 errors): the received vector lands at distance 2 from Class 0, Class 1, and Class 2 all at once — a three-way tie, with no unique decode. That's exactly why the guarantee stops at e_max = 1 and not 2: at 2 errors, d_min − e = 2 is no longer strictly greater than e = 2, so the triangle-inequality argument above no longer forces a unique winner. The interactive diagram below runs all three scenarios live.
Toggle between strategies. OvR's argmax always produces a clean 3-way partition (dots mark cells where a naive yes/no vote alone would have been ambiguous, even though the score resolves it). OvO's 3 independently-trained pairwise classifiers open a genuine gray tie region with no majority winner at all.
A 4-class, 7-bit coding matrix (d_min = 4). Pick a scenario to simulate 0, 1, or 2 flipped classifier outputs on Class 2's true codeword, and watch which row's Hamming distance bar comes out shortest — including the case where 2 flips (past the guarantee) produces a genuine tie.
#include <iostream>
#include <vector>
struct Perceptron {
std::vector<double> w;
double b = 0.0;
double lr = 1.0;
explicit Perceptron(int nFeatures) : w(nFeatures, 0.0) {}
void fit(const std::vector<std::vector<double>>& X, const std::vector<int>& y, int epochs = 20) {
for (int e = 0; e < epochs; ++e) {
for (size_t i = 0; i < X.size(); ++i) {
double margin = y[i] * score(X[i]);
if (margin <= 0) {
for (size_t j = 0; j < w.size(); ++j) w[j] += lr * y[i] * X[i][j];
b += lr * y[i];
}
}
}
}
// Real-valued confidence -- OvR's argmax over K of these needs more than sign(.).
double score(const std::vector<double>& x) const {
double s = b;
for (size_t j = 0; j < w.size(); ++j) s += w[j] * x[j];
return s;
}
};
// One binary Perceptron per class ("class k vs. the other K-1"), predicted by argmax score.
int predictOneVsRest(const std::vector<Perceptron>& classifiers, const std::vector<double>& x) {
int best = 0;
double bestScore = classifiers[0].score(x);
for (size_t k = 1; k < classifiers.size(); ++k) {
double s = classifiers[k].score(x);
if (s > bestScore) { bestScore = s; best = static_cast<int>(k); }
}
return best;
}
int main() {
std::vector<std::vector<double>> X = {
{-1.8, 0.9}, {-1.4, 1.2}, {-1.9, 1.1},
{1.6, 1.0}, {1.9, 1.3}, {1.5, 0.8},
{0.1, -1.7}, {-0.2, -1.9}, {0.2, -1.6},
};
std::vector<int> y = {0, 0, 0, 1, 1, 1, 2, 2, 2};
int K = 3, n = static_cast<int>(X.size());
std::vector<Perceptron> classifiers(K, Perceptron(2));
for (int k = 0; k < K; ++k) {
std::vector<int> yBin(n);
for (int i = 0; i < n; ++i) yBin[i] = (y[i] == k) ? 1 : -1;
classifiers[k].fit(X, yBin);
}
for (const auto& x : X) std::cout << predictOneVsRest(classifiers, x) << " ";
std::cout << "\n";
return 0;
}- Support Vector Machines — SVMs are natively binary (their max-margin formulation doesn't generalize to K classes the way softmax does), so essentially every multi-class SVM in practice is an SVM plus one of these three composition strategies wrapped around it.
- libsvm-style toolchains — historically default to One-vs-One specifically because each pairwise sub-problem is small and fast to train, even though it means training O(K²) classifiers.
- Bioinformatics — ECOC is popular for gene-expression and microarray-based classification, where individual binary classifiers trained on noisy biological data are genuinely unreliable, and ECOC's error-correcting decode gives robustness that a plain vote can't.
- Large-catalog product/text classification — One-vs-Rest is the default first choice when K is large (thousands of categories) precisely because it's the only one of the three that stays linear in K rather than quadratic.
- Historical digit/character recognition pipelines — early multi-class digit classifiers built on linear or kernel binary classifiers relied on OvR or OvO long before softmax-output neural networks made K-way classification a first-class citizen.
- Treating OvR's K binary sub-problems as if they were as balanced as the original K-class problem — each one is really a k-vs-(K−1)-others problem, and that imbalance gets worse as K grows.
- Using OvO without noticing its O(K²) blowup: K=1000 classes means roughly 500,000 pairwise classifiers to train and query, which can dwarf OvR's 1,000 in both training time and prediction latency.
- Assuming any ECOC coding matrix has real error-correcting power. The guarantee is
⌊(d_min−1)/2⌋— a poorly designed matrix (e.g. two nearly identical codeword rows, givingd_min = 1) corrects zero errors and offers no benefit over plain OvR at extra training cost. - Comparing raw
{−1,+1}votes instead of real-valued scores in OvR, and being surprised when "multiple classifiers say yes" or "no classifier says yes" cases seem to have no defined answer — they do, once you use the score instead of the sign.
Going deeper
ECOC's nearest-codeword decoding rule is not just analogous to error-correcting codes in communications theory — it is the same mathematical object. Treating each of the L binary classifiers as an unreliable "channel" that occasionally flips a bit, and decoding by minimum Hamming distance to a valid codeword, is exactly the decoding rule from Hamming's original 1950 work on error-correcting codes, repurposed for machine learning by Dietterich and Bakiri in the mid-1990s. It's also worth being honest about why this whole lesson exists: softmax regression (section 2.4.2) makes almost none of this necessary for models that support K-way output natively — there's no "rest" to pool and no pairwise vote to break, because the model computes all K scores jointly and normalizes them into one probability distribution. These composition strategies earn their keep specifically for models that are fundamentally binary — the Perceptron (2.4.3), and, later in this course, Support Vector Machines — which is a large enough share of classical ML tooling that the machinery is still essential, not merely historical.
A 4-class ECOC coding matrix has minimum pairwise Hamming distance d_min = 4 between codewords. Why does the standard guarantee only promise correcting 1 classifier error, and not 2?
The guarantee is e_max = floor((d_min - 1) / 2), which for d_min = 4 gives floor(3/2) = 1. The triangle-inequality argument behind it needs d_min - e strictly greater than e (so the true codeword stays strictly closer than any rival). With e = 1: d_min - e = 3 > 1, so the true class always wins. With e = 2: d_min - e = 2, which is only equal to e = 2, not greater than it -- so a rival codeword can tie the true one exactly, producing an ambiguous decode instead of a guaranteed-correct one. This is a worst-case guarantee, though: depending on exactly which bits flip, 2 errors can still decode correctly in a specific instance -- it's just no longer promised for every possible pair of flips, only for at most 1.
One-vs-Rest, One-vs-One, and ECOC all solve the same problem — a K-way decision from only binary classifiers — but assume every example belongs to exactly one of the K classes. The next lesson, section 2.4.5 (Multi-label Classification), breaks that assumption: an example can carry several labels at once (a news article can be both "politics" and "economy"), which is a genuinely different problem that none of this lesson's argmax- or majority-vote-based decoding rules are built to solve.