Machine Learning/Learning Center/Linear Models/Multi-Class Classification

Multi-Class Classification

Learn strategies to extend binary classifiers to multi-class problems using One-vs-One, One-vs-Rest, and error-correcting output codes with practical examples

The Multi-Class Problem

Problem Decomposition

Many real-world classification problems involve more than two classes. While some algorithms (like LDA, softmax regression, decision trees) naturally handle multiple classes, powerful binary classifiers like SVM and logistic regression require special strategies to tackle multi-class problems.

Three Main Strategies

1. One-vs-One (OvO)

Train a classifier for every pair of classes. For K classes, build K(K-1)/2 classifiers.

2. One-vs-Rest (OvR) or One-vs-All (OvA)

Train one classifier per class, treating that class as positive and all others as negative. Build K classifiers.

3. Many-vs-Many (MvM)

Use error-correcting output codes (ECOC) to create M binary classifiers with redundancy for robustness.

When You Need These Strategies

•Using binary classifiers (SVM, logistic regression) for K > 2 classes
•Product categorization (electronics, apparel, home goods, etc.)
•Image classification with multiple object types
•Medical diagnosis with multiple disease types

Key Insight

These strategies let you leverage the power of well-tuned binary classifiers for multi-class problems. Instead of building a new multi-class algorithm, decompose the problem into multiple binary problems that are easier to solve and understand.

One-vs-One (OvO) Strategy

Pairwise classification with voting

How OvO Works

Train a separate binary classifier for every pair of classes. For K classes, you need K(K-1)/2 classifiers:

Training Phase

• For classes C₀, C₁, train classifier h_0,1 using only samples from C₀ and C₁
• For classes C₀, C₂, train classifier h_0,2 using only samples from C₀ and C₂
• Continue for all pairs: h_0,3, h_1,2, h_1,3, h_2,3, etc.
• Each classifier only sees data from two classes (simplified binary problem)

Prediction Phase (Voting)

1. Submit test sample to all K(K-1)/2 classifiers
2. Each classifier votes for one of its two classes
3. Count votes for each class across all classifiers
4. Assign the class with the most votes as the final prediction

Example: 4-Class Product Categorization

Categories: Electronics, Apparel, Home & Kitchen, Sports

Number of classifiers needed: 4 × 3 / 2 = 6

h₁: Electronics vs Apparel

h₂: Electronics vs Home & Kitchen

h₃: Electronics vs Sports

h₄: Apparel vs Home & Kitchen

h₅: Apparel vs Sports

h₆: Home & Kitchen vs Sports

Sample Prediction:

New product: "Bluetooth Earbuds, $59.99, wireless audio"

h₁ vote:	Electronics
h₂ vote:	Electronics
h₃ vote:	Electronics
h₄ vote:	Apparel
h₅ vote:	Apparel
h₆ vote:	Home & Kitchen

Final: Electronics (3 votes) > Apparel (2 votes) > Home & Kitchen (1 vote)

OvO Pros & Cons

Advantages

• Each classifier only uses relevant training data (2 classes)
• Training is fast because each classifier sees fewer samples
• Works well with moderate number of classes (K < 20)
• Each binary problem is often easier to solve
• Naturally parallelizable - train all classifiers simultaneously

Disadvantages

• Number of classifiers grows quadratically: O(K²)
• Prediction is slow (must query all K(K-1)/2 classifiers)
• Impractical for very large K (e.g., 100 classes = 4,950 classifiers!)
• Voting can produce ties or ambiguous results
• Storage cost increases significantly with more classes

One-vs-Rest (OvR) Strategy

Also known as One-vs-All (OvA)

How OvR Works

Train one classifier per class, where each treats its class as positive and all other classes as negative. For K classes, you need exactly K classifiers:

Training Phase

• Classifier h₀: Treat class 0 as positive (+1), all others (1,2,3,...) as negative (-1)
• Classifier h₁: Treat class 1 as positive (+1), all others (0,2,3,...) as negative (-1)
• Continue for all K classes, each seeing the entire training set
• Each classifier learns "Is this sample from class k or not?"

Prediction Phase (Confidence Selection)

1. Submit test sample to all K classifiers
2. Each classifier outputs a confidence score (probability or decision value)
3. Select the class whose classifier has the highest confidence
4. If using probabilities, choose argmax_k P(y=k|x)

Example: E-Commerce Product Categories

Categories: Electronics, Apparel, Home & Kitchen, Sports, Books

Number of classifiers needed: 5 (one per category)

h₁: Electronics vs {Apparel, Home, Sports, Books}

h₂: Apparel vs {Electronics, Home, Sports, Books}

h₃: Home & Kitchen vs {Electronics, Apparel, Sports, Books}

h₄: Sports vs {Electronics, Apparel, Home, Books}

h₅: Books vs {Electronics, Apparel, Home, Sports}

Sample Prediction:

New product: "Nike Training Sneakers, size 10, mesh upper"

Classifier	Confidence Score
Electronics	0.12
Apparel	0.87
Home & Kitchen	0.08
Sports	0.73
Books	0.05

Final: Apparel (confidence: 0.87)

OvR Pros & Cons

Advantages

• Only K classifiers needed (scales linearly with classes)
• Works well for large number of classes (K > 20)
• Prediction is fast (query only K classifiers)
• Each classifier provides interpretable confidence scores
• Easy to add new classes (just train one more classifier)
• Most popular choice in practice (used by sklearn default)

Disadvantages

• Class imbalance: each classifier sees K-1 negatives vs 1 positive
• Training is slower (each classifier uses full dataset)
• Confidence scores across classifiers may not be calibrated
• Can have poorly defined decision regions (multiple classifiers say "yes")
• Less accurate than OvO when classes are similar to each other

Many-vs-Many (MvM) with ECOC

Error-Correcting Output Codes for robust classification

How ECOC Works

ECOC (Error-Correcting Output Codes) assigns each class a unique binary code of length M. Train M binary classifiers, one for each bit position. Prediction involves finding which class's code is closest to the predicted bit string.

Code Matrix Example (4 classes, 7 bits)

Class	C₁	C₂	C₃	C₄	C₅	C₆	C₇
Electronics	1	1	1	0	0	0	1
Apparel	0	1	0	1	0	1	0
Home & Kitchen	1	0	0	1	1	0	1
Sports	0	0	1	0	1	1	1

Each column represents a binary classifier. Classifier C₁ learns to distinguish{Electronics, Home} (coded 1) from {Apparel, Sports} (coded 0).

Prediction with Error Correction

Step 1: Query all M classifiers to get predicted code

Step 2: Calculate Hamming distance from predicted code to each class's code

Step 3: Assign the class with minimum Hamming distance

Example Prediction:

Predicted code from classifiers: 1 1 0 0 0 0 1

Distance to Electronics [1 1 1 0 0 0 1]: 1 (differs in 1 bit)

Distance to Apparel [0 1 0 1 0 1 0]: 4 (differs in 4 bits)

Distance to Home & Kitchen [1 0 0 1 1 0 1]: 3 (differs in 3 bits)

Distance to Sports [0 0 1 0 1 1 1]: 5 (differs in 5 bits)

Prediction: Electronics (minimum distance = 1)

Even with one classifier error, ECOC correctly identified the class through error correction!

Designing Good Codes

Key Properties

Row separation: Each pair of classes should differ in many bits
Column separation: Each classifier should have balanced partitions
Redundancy: Use M > log₂(K) bits for error correction capability
Minimum distance: Larger minimum Hamming distance = more errors tolerated

Code Generation Methods

• Random codes: Generate random binary matrix (simple but effective)
• BCH codes: Use algebraic error-correcting codes from coding theory
• Hadamard codes: Maximize distance between codewords
• Data-driven: Optimize codes based on confusion patterns in data

In practice, random codes with M ≈ 10 log₂(K) work surprisingly well.

ECOC Pros & Cons

Advantages

• Error correction: Robust to individual classifier mistakes
• Improved accuracy through redundancy
• Theoretical guarantees on error tolerance
• Can outperform both OvO and OvR on difficult problems

Disadvantages

• More complex to implement and tune
• Requires careful code design
• Computational overhead (M classifiers, M typically > K)
• Less interpretable than OvR or OvO
• Not widely supported in standard libraries

Strategy Comparison & Recommendations

Choosing the right approach for your problem

Aspect	OvO	OvR	ECOC
Number of Classifiers	K(K-1)/2	K	M (typically 10 log₂K)
Training Time	Fast per classifier	Slower (full dataset)	Medium
Prediction Time	Slow (many queries)	Fast (K queries)	Medium (M queries)
Scalability with K	Poor (quadratic)	Excellent (linear)	Good (log-linear)
Class Imbalance	Balanced (2 classes each)	Imbalanced (1 vs K-1)	Varies by design
Accuracy	Good for small K	Good overall	Best (with good codes)
Implementation	Simple	Very simple	Complex
Best For	K < 10, SVM	K > 10, general use	Critical applications, noisy data

Practical Recommendations

Default choice: Use One-vs-Rest (OvR) - it's simple, scales well, and is the default in most libraries (scikit-learn, TensorFlow). Works for most applications.

For SVM with small K (< 15 classes): Use One-vs-One (OvO) - SVMs train quickly on smaller datasets, and LibSVM uses OvO by default.

For high-stakes applications: Consider ECOC when you need maximum accuracy and can afford extra computation (medical diagnosis, autonomous systems).

For very large K (> 100 classes): Use OvR or consider hierarchical classification, label trees, or natively multi-class methods (softmax regression, decision trees).

Common Questions About Multi-Class Classification

Can I use softmax regression instead of these strategies?

Yes! Softmax (multinomial logistic regression) naturally handles multi-class problems by extending logistic regression with the softmax function. It's often preferable for neural networks. However, these decomposition strategies are still useful when you want to use powerful binary classifiers like SVM or when you need the modularity of independent classifiers.

How do I handle class imbalance with OvR?

OvR inherently creates imbalance (1 positive class vs K-1 negative classes). Solutions: (1) Use class weights in your binary classifier to penalize minority class errors more, (2) Apply SMOTE or other oversampling to the positive class for each binary problem, (3) Use balanced accuracy or F1 score as your metric instead of simple accuracy, or (4) Switch to OvO which has natural balance.

What if classifiers disagree in OvR (multiple classes predicted positive)?

This is common. Always use the confidence scores or probabilities, not just binary decisions. Select the class with highest confidence: argmax_k f_k(x), where f_k is classifier k's confidence. Don't rely on threshold-based binary decisions (positive/negative) alone—the confidence values provide crucial ranking information.

When should I NOT use these decomposition strategies?

Skip decomposition when: (1) Your base algorithm already handles multi-class natively (decision trees, random forests, naive Bayes, k-NN), (2) You're using neural networks with softmax output, (3) You have extreme number of classes (> 1000) where even OvR becomes expensive—consider hierarchical methods instead, or (4) Classes have natural hierarchical structure (use label trees).