One-vs-Rest (OvR)

One-vs-Rest turns a \(K\)-class problem into \(K\) binary ones. Classifier \(i\) is trained to answer “is this class \(i\), or anything else?”, and at prediction time the class whose classifier scores highest wins.

For {apple, banana, orange} that is three models. If they score 0.1, 0.2 and 0.9 the answer is orange. The appeal is that any binary classifier becomes a multiclass one, the model count grows linearly in \(K\), and each component is inspectable on its own.

One correction first, because it is widely repeated: scikit-learn’s LogisticRegression does not use OvR. Its documentation states that for three or more classes every solver except liblinear optimizes the multinomial loss, and the multi_class switch that used to select OvR no longer exists. Getting OvR means asking for it with OneVsRestClassifier.

The scores are not a distribution

import numpy as np
from sklearn.datasets import make_classification
from sklearn.linear_model import LogisticRegression
from sklearn.multiclass import OneVsRestClassifier
from sklearn.model_selection import train_test_split

X, y = make_classification(n_samples=6000, n_features=10, n_informative=7,
                           n_classes=5, n_clusters_per_class=1, random_state=0)
xtr, xte, ytr, yte = train_test_split(X, y, test_size=0.3, stratify=y, random_state=0)

softmax = LogisticRegression(max_iter=5000).fit(xtr, ytr)
ovr = OneVsRestClassifier(LogisticRegression(max_iter=5000)).fit(xtr, ytr)
print(f"scikit-learn's LogisticRegression fits one multinomial model: coef_ shape {softmax.coef_.shape}")
print(f"OneVsRestClassifier fits {len(ovr.estimators_)} separate binary models\n")

for k in range(5):
    print(f"  class {k}: positives in its own binary problem {np.mean(ytr == k):.4f}")

raw = np.column_stack([e.predict_proba(xte[:4])[:, 1] for e in ovr.estimators_])
print(f"\nthe four test rows, each binary model's probability that the row is its class")
for i, row in enumerate(raw):
    print(f"  row {i}  " + "  ".join(f"{v:.4f}" for v in row) + f"   sum {row.sum():.4f}")
print(f"\npredict_proba divides those by their sum: row 0 becomes "
      + "  ".join(f"{v:.4f}" for v in ovr.predict_proba(xte[:1])[0]))
print(f"\nthe two strategies disagree on {np.mean(softmax.predict(xte) != ovr.predict(xte)):.4f} of the test set;"
      f" accuracy {softmax.score(xte, yte):.4f} against {ovr.score(xte, yte):.4f}")
# scikit-learn's LogisticRegression fits one multinomial model: coef_ shape (5, 10)
# OneVsRestClassifier fits 5 separate binary models
#
#   class 0: positives in its own binary problem 0.1988
#   class 1: positives in its own binary problem 0.2005
#   class 2: positives in its own binary problem 0.1998
#   class 3: positives in its own binary problem 0.2007
#   class 4: positives in its own binary problem 0.2002
#
# the four test rows, each binary model's probability that the row is its class
#   row 0  0.0408  0.1617  0.0036  0.0061  0.8329   sum 1.0452
#   row 1  0.0428  0.7368  0.0093  0.0014  0.1363   sum 0.9266
#   row 2  0.0585  0.0690  0.8847  0.0006  0.0710   sum 1.0837
#   row 3  0.0056  0.0496  0.0659  0.8791  0.0157   sum 1.0159
#
# predict_proba divides those by their sum: row 0 becomes 0.0391  0.1547  0.0035  0.0059  0.7969
#
# the two strategies disagree on 0.0778 of the test set; accuracy 0.7439 against 0.7172

Each of the five models was fitted separately and knows nothing about the others. So their outputs have no reason to sum to one, and they do not: 1.0452, 0.9266, 1.0837, 1.0159 on four rows.

For single-label multiclass input, predict_proba divides the separate estimates by their row sum. The true class posteriors must sum to one because the classes are mutually exclusive and exhaustive, but separately fitted estimates need not satisfy that constraint. Renormalization supplies a normalized vector; it does not by itself establish that the entries are calibrated class risks.

Compare the \(K\) model outputs on a suitable common scale and check calibration where probabilities drive decisions. Calibration of each binary output alone does not guarantee joint posterior consistency or calibration after normalization. Validate the final probabilities on held-out data; a multinomial fit also needs that check.

The decomposition creates imbalance

The middle block is worth pausing on. This is a balanced five-class problem — each class is about a fifth of the data. Every one of the five binary problems it produces has a positive rate near 0.20.

For K equally common classes, each OvR binary problem has prevalence 1/K. That affects baseline metrics and the amount of positive data available. It does not by itself make a correctly estimated posterior miscalibrated or require a threshold other than 0.5; the suitable decision rule also depends on costs and the joint multiclass task.

And where the original classes are already uneven, the rarest class gets a binary problem with both a tiny positive rate and few positive examples. A softmax fit shares parameters and evidence across classes; OvR does not.

It gives different answers, not just slower ones

The last line of the run: the two strategies disagree on 7.78% of the test set, with accuracy 0.7439 for the multinomial fit against 0.7172 for OvR.

The usual summary — OvR is “less efficient than direct multiclass methods” — undersells this. They are different models. The multinomial fit optimizes one objective over all classes at once; OvR optimizes \(K\) independent objectives and then compares their outputs. Which wins is an empirical question, and on this data it is not close enough to ignore.

When to reach for it

• The base learner has no multiclass form. A binary-only SVM or a bespoke scorer becomes multiclass through OvR, and that is the original reason for the technique.
• Separate binary models are operationally useful. They can be inspected or updated separately, but adding a class also changes the negative rest population for every existing classifier. Train the new classifier, evaluate the existing ones on the expanded task, and retrain them when needed; one new fit is not generally equivalent to refitting the full OvR system.
• The problem is actually multi-label. There OvR is not a workaround but the standard approach — binary relevance — and the scores not summing to one is correct rather than awkward, since several labels can be right at once.

The alternative decomposition, One-vs-One, trains \(K(K-1)/2\) models on pairs and votes. Each model sees only its two classes, but their sample counts can still be imbalanced. The quadratic model count adds fitting and maintenance costs as the label inventory grows. For anything with a native multiclass formulation, the direct fit is usually the better default — and knowing that OvR is a choice rather than the library’s behavior is the point of this article.

Changing the label inventory can also change the imbalanced data problem faced by each binary model.

References

• scikit-learn API reference, OneVsRestClassifier
• scikit-learn API reference, LogisticRegression
• scikit-learn User Guide, Multiclass and multioutput algorithms