Learn AI Create the Future — with Pranay
Main site

Imbalanced, Multi-class and Multi-label

One-vs-rest and one-vs-one

Two classic recipes turn any yes/no classifier into a many-class classifier — one fights each class against everyone, the other runs every pairwise duel.

Read these first

On this page 5
  1. Why it exists
  2. How it works
  3. A real example you have seen
  4. Remember this
  5. What to learn next

One lesson, three depths. Pick the one that fits you today — you can switch any time.

Beginner — No maths. Plain English.

One-vs-rest and one-vs-one are two ways to answer a many-option question using models that can only answer yes or no.

Think of a fruit vendor sorting a mixed basket into mangoes, bananas and guavas. One helper can only answer yes/no questions. Strategy one: ask "is it a mango, or not?", then "banana, or not?", then "guava, or not?", and keep the most confident yes. Strategy two: run duels — mango vs banana, mango vs guava, banana vs guava — and crown the fruit that wins the most duels.

Why it exists

Some models are naturally two-sided. A basic logistic regression draws one line with one class on each side. Support vector machines are the same. But real problems have ten digits, twenty topics, a hundred products.

The two strategies bridge the gap:

  • One-vs-rest (OvR): train one specialist per class. Each learns "my class versus everybody else". The most confident specialist wins.
  • One-vs-one (OvO): train one duellist per pair of classes. Predict by holding all the duels and counting wins.

How it works

one-vs-rest (3 classes → 3 models):     one-vs-one (3 classes → 3 duels):
  mango  vs  everything-else              mango  vs banana
  banana vs  everything-else              mango  vs guava
  guava  vs  everything-else              banana vs guava
  → pick the loudest "yes"                → pick the duel champion

The counts grow differently. Ten classes need ten OvR models, but forty-five OvO duels — every possible pair. Each duel, though, trains on only two classes' worth of data, so each individual duel is fast.

A real example you have seen

Handwritten digit reading on postal codes and bank cheques was an early success of this. Classic digit recognisers were support vector machines running all forty-five pairwise duels between the digits zero to nine. The digit recognition project tackles the same task with modern tools.

Remember this

  • OvR: one model per class, each against everyone. Few models, each sees all data.
  • OvO: one model per pair. Many models, each sees only two classes.
  • Modern libraries hide this machinery, but it still runs underneath — and you can choose it.

What to learn next

Developer — Code and libraries.

Setup

bash
pip install scikit-learn

Outputs verified with scikit-learn 1.7.2, CPU only. Runs in a few seconds.

Ten digits, two strategies

ovr_ovo.py
from sklearn.datasets import load_digits
from sklearn.model_selection import train_test_split
from sklearn.multiclass import OneVsOneClassifier, OneVsRestClassifier
from sklearn.pipeline import make_pipeline
from sklearn.preprocessing import StandardScaler
from sklearn.svm import LinearSVC

X, y = load_digits(return_X_y=True)        # 1797 tiny images, 10 digit classes
X_tr, X_te, y_tr, y_te = train_test_split(X, y, stratify=y, random_state=42)

svm = make_pipeline(StandardScaler(), LinearSVC())

ovr = OneVsRestClassifier(svm).fit(X_tr, y_tr)
ovo = OneVsOneClassifier(svm).fit(X_tr, y_tr)

print("classes:", len(ovr.classes_))
print("OvR trained", len(ovr.estimators_), "models ->",
      f"accuracy {ovr.score(X_te, y_te):.2f}")
print("OvO trained", len(ovo.estimators_), "models ->",
      f"accuracy {ovo.score(X_te, y_te):.2f}")
Output
classes: 10
OvR trained 10 models -> accuracy 0.95
OvO trained 45 models -> accuracy 0.97

The walkthrough

10 versus 45. OvR builds one model per class. OvO builds one per pair: ten classes give 10 × 9 ÷ 2 = 45. For 100 classes that becomes 4950 — the pair count grows with the square of the class count.

Why OvO edged ahead here. Each duel is a clean two-class problem — "3 versus 8" — without the other classes muddying the boundary. Each OvR model instead fights a lopsided battle: one digit versus nine others, which is a built-in 1-to-9 class imbalance. With LinearSVC that slight awkwardness shows up as two accuracy points.

When you need neither. LogisticRegression handles many classes natively (a softmax over all classes at once), as do trees, forests and neural networks. The wrappers matter when your chosen model is inherently binary, or when you want per-class specialists you can inspect and tune separately.

Prediction cost differs too. OvR runs 10 models per prediction; OvO runs 45 (though each is smaller). For SVMs with expensive kernels, OvO's smaller training sets historically made training cheaper, which is why LIBSVM chose OvO internally.

Common mistakes

Wrapping a model that is already multiclass. OneVsRestClassifier(RandomForestClassifier()) trains ten forests to do what one forest does natively — ten times the cost for no gain, and sometimes worse calibration.

Comparing raw scores across OvR specialists. Each specialist trained on a different imbalanced problem, so their confidence scales differ. Scikit-learn handles the normalisation internally; if you hand-roll OvR, calibrate each model before comparing their outputs.

Forgetting the imbalance inside OvR. Each "one versus rest" split is skewed by construction. If a class is rare and you use OvR, you have stacked two imbalance problems — combine with class_weight="balanced" from class weights.

Assuming ties cannot happen in OvO. With 45 duels, two classes can finish with equal wins. Scikit-learn breaks ties using the underlying decision values, but hand-rolled vote counting needs a tie rule.

Try it yourself

Time both fit calls with time.perf_counter(). Then swap LinearSVC for LogisticRegression(max_iter=2000) and compare against plain LogisticRegression used directly — same accuracy question, three different machineries.

What to learn next

Researcher — Mathematics and papers.

Formal setup

For K classes, OvR trains f_k: X → ℝ for k = 1…K on labels 1[y = k], predicting argmax_k f_k(x). OvO trains f_{ij} for each of the K(K−1)/2 pairs on the subset {y ∈ {i, j}}, predicting by vote count, with decision-value sums as the tie-break.

Training cost: OvR is K fits on n samples each; OvO is K(K−1)/2 fits on ~2n/K samples each. For a learner with cost C(n) = O(n^α), OvO's total is O(K² · (n/K)^α) = O(K^{2−α} n^α) — cheaper than OvR's O(K n^α) when α > 1, which held for kernel SVMs (α ≈ 2–3) and motivated LIBSVM's OvO default (Chang and Lin, 2011). Rifkin and Klautau (2004), In defense of one-vs-all classification, JMLR, argue that with properly tuned binary learners, OvR matches OvO on accuracy — the differences in most published comparisons trace to tuning, not topology.

Beyond voting: pairwise coupling and ECOC

Turning OvO votes into probabilities is the pairwise-coupling problem: given pairwise estimates r_{ij} ≈ P(y = i | y ∈ {i, j}, x), find a consistent p ∈ Δ^{K−1}. Hastie and Tibshirani (1998), Classification by pairwise coupling, minimise a Kullback–Leibler criterion; Wu, Lin and Weng (2004) give the quadratic-program refinement used in LIBSVM's probability outputs.

Both schemes are instances of error-correcting output codes (Dietterich and Bakiri, 1995, JAIR): assign each class a codeword over binary problems; OvR is the identity code, OvO a sparse pairwise code. Random dense codes with L binary learners tolerate ⌊(d_min − 1)/2⌋ binary errors, where d_min is the minimum Hamming distance between codewords — a robustness OvR lacks. In practice ECOC's gains are modest with strong base learners.

Native multinomial vs decomposition

The softmax/multinomial objective optimises the joint log-likelihood; decompositions optimise surrogate objectives per binary task. For linear models the fitted boundaries differ: multinomial boundaries are consistent for the posterior argmax under the model, while OvR can produce regions claimed by no specialist or several. Since scikit-learn 1.5–1.7, LogisticRegression is multinomial for multiclass targets and the old multi_class="ovr" option is deprecated — wrap in OneVsRestClassifier explicitly if you want OvR semantics. Deep networks settled the question by construction: a K-way softmax head is the native multinomial approach, and decompositions survive mainly in extreme-classification systems (millions of labels) where per-label binary models shard cleanly — Babbar and Schölkopf (2017), DiSMEC.

What to learn next