Multiclass Classification: One-versus-One and One-versus-Rest
Multiclass classification assigns an instance to one of more than two classes; binary classifiers can be combined with the one-versus-rest (OvR/OvA) or one-versus-one (OvO) strategies.
Some algorithms (Random Forest, naive Bayes) handle multiple classes directly. Others, such as SGD and SVM classifiers, are strictly binary. To classify digits 0 to 9 with a binary classifier you can use one of two strategies.
One-versus-the-rest (OvR, also called OvA): train 10 binary classifiers, one per digit (this digit versus the others), run all on a new image, and pick the class whose classifier gives the highest decision score. One-versus-one (OvO): train a binary classifier for every pair of classes. For N classes you need N x (N - 1) / 2 classifiers, so 45 for 10 digits. Its advantage is that each classifier only needs the part of the training set for its two classes, which helps algorithms that scale poorly with training size, like SVMs.
Scikit-Learn picks automatically: OvO for SVMs and OvR for most others.
Key points
- OvR: N classifiers, pick the highest score.
- OvO: N(N-1)/2 classifiers, one per pair of classes; 45 for 10 classes.
- SVMs prefer OvO because they scale poorly with training set size.
- SGD and SVM are binary-only; Random Forest handles multiclass natively.
Worked example
For 3 classes (cat, dog, bird) OvO trains cat-vs-dog, cat-vs-bird and dog-vs-bird: 3 x 2 / 2 = 3 classifiers, and the class that wins the most duels is the prediction.
Common questions
How many classifiers does OvO need for 10 classes?
45, since 10 x 9 / 2 = 45.
Which algorithms are strictly binary?
SGD classifiers and Support Vector Machine classifiers.
Practice questions on this topic
Try these, then open the app to check your answers with explanations.
- There are various strategies that you can use to perform multiclass classification with multiple binary classifiers.
- A. true
- B. false
- What is the difference between a binary classification algorithm and a multiclass classification algorithm
- A. A binary classification algorithm can only predict two classes, while a multiclass classification algorithm can predict three or more classes.
- B. A binary classification algorithm is more accurate than a multiclass classification algorithm.
- C. A binary classification algorithm is more computationally expensive than a multiclass classification algorithm.
- D. A binary classification algorithm is not as flexible as a multiclass classification algorithm.
- In The One-versus-one (OvO) Strategy, you need .............classifiers for MNIST dataset
- A. 45
- B. Nx (N-1)/2
- C. both of them
- D. none of them
- A single binary classifier is more computationally expensive than a multiclass strategy built from several binary classifiers (OvR or OvO).
- A. false
- B. true
- In The One-versus-one (OvO) Strategy, you need........... classifiers for classifiers for MNIST dataset.
- A. 45
- B. N × (N–1)/2
- C. both of them
- D. none of them
Related topics
- Confusion Matrix, Precision, Recall and F1 Score
- ROC Curve and AUC Explained
- K-Fold and Stratified K-Fold Cross-Validation
- MNIST Dataset and SGDClassifier Explained
- What is Machine Learning?
- Supervised vs Unsupervised vs Semi-supervised vs Reinforcement Learning
- All topics: Machine Learning
BASMAGLY is an independent student project, not an official Delta University site. Check lectures and your instructor for the final word.