One-vs-Rest and One-vs-One Multiclass Strategies

Some classifiers handle many classes natively. Others, most notably the standard SVM, are defined only for two classes. Classifying a trade into one of six venue-routing categories with an inherently binary classifier needs a strategy for combining several two-class decisions into one many-class answer. One-vs-rest and one-vs-one are the two standard recipes.

The analogy: elimination bracket versus round-robin

Picking a winner among six contestants using a judge who only compares two at a time: one-vs-rest has each contestant face "everyone else combined" — six matches. One-vs-one is a full round-robin, every pair facing off directly, $\binom{6}{2}=15$ matches, with the winner decided by tallying head-to-head wins. Round-robin uses more matches but each is a cleaner, more focused comparison.

The mechanics: rest-versus-all, or every pair

One-vs-rest (OvR) trains $K$ classifiers, each distinguishing "class $k$" from everything else pooled together: $\hat y = \arg\max_k f_k(x)$. Each classifier learns a boundary between one class and a merged blob of the rest — a harder, more imbalanced problem than distinguishing two specific classes.

One-vs-one (OvO) trains $\binom{K}{2}$ classifiers, one per pair, each seeing only those two classes' rows, with the final answer decided by majority vote across pairwise contests. More classifiers, but each solves an easier, balanced two-class problem on a smaller, more homogeneous subset.

Worked example: six venue-routing classes

Routing to one of six venues, OvR trains 6 classifiers, each "venue A vs. everything else" — a 5-to-1 imbalance built into every one of the 6 problems. OvO trains $\binom{6}{2}=15$ classifiers on pairs — "A vs. B," "A vs. C," and so on — with no imbalance and smaller, cleaner training sets per classifier. For a new order, if venue A wins 4 of its 5 pairwise contests while venue F wins only 3, the order routes to A by majority vote across all 15 contests.

Each pairwise OvO boundary above only ever separates two classes cleanly; stitching many such simple boundaries together (rather than one classifier fighting a merged "rest") is the core trade-off between the two strategies.

What this means in practice

OvR trains fewer classifiers on the full dataset and scales well as $K$ grows, but each faces a harder, artificially imbalanced problem. OvO trains $O(K^2)$ classifiers but each is cheaper and cleaner per pair — a good default for kernel SVMs, whose training cost grows superlinearly with sample size, since many small subproblems can be cheaper overall than few large ones.