Home / MLP / Week 7

Week 7 · Multiclass classifiers

Official syllabus line: Classification on scikit-learn - Multiclass classifier

About 80 minQuiz 2 material (see exam radar)BSCS2008 · Ashish Tendulkar

Before you start: MLP weeks 5 and 6 (logistic regression and binary-classification metrics).

Watch first: the animated story of this weekAbout 1-2 minutes of real 3D animation with a friendly voice. Pause any time.

Read the words of the video

Imagine a machine that only says 'yes' or 'no'. But what if a post office needs to read a '3' or a '7'? Or a zoo app must identify a specific animal from many? Sometimes, our computers need to choose one answer from many options, not just two. This is where clever tricks help them do more!
To choose from many, we can use two main tricks. In 'one-versus-rest', we make a 'yes or no' machine for each choice, like 'is it a three?' or 'is it a seven?'. Then, we pick the answer that gets the strongest 'yes'. The other trick, 'one-versus-one', pairs up every choice against each other.
Let's try an example. If we have four types of animals – say, cats, dogs, birds, and fish – the 'one-versus-rest' trick needs four yes-or-no machines, one for each animal. But for 'one-versus-one', we need to compare every pair. That means six separate yes-or-no machines in total! See the difference?
For exams, remember that 'one-versus-one' usually needs more yes-or-no machines than 'one-versus-rest', especially for many choices! We also learned about finding mistakes using a 'confusion matrix' and the differences between picking one answer, several answers, or multiple types of answers. Keep up the great work!

The one-minute story

Think of it like this

So far the answer was yes or no. But a post office needs to read ten digits, a zoo app must pick one animal out of thousands, and a photo app wants to tag a picture with several labels at once ("beach", "dog", "sunset").

Some classifiers can only say yes/no. How do you build a ten-way digit reader from yes/no machines? Two classic tricks:

One-versus-rest (OvR): train one machine per class: "is it a 3 or not?" "is it a 7 or not?" ... Ask all ten and take the one that shouts loudest.
One-versus-one (OvO): train a machine for every pair of classes ("3 vs 7", "3 vs 8", ...). Let them vote.

scikit-learn picks the right trick for you automatically, but exam questions love to ask how many machines that takes. This week also separates three confusingly similar problems: multiclass, multilabel and multioutput.

By the end of this week you can:

say which strategy (OvR or OvO) a classifier uses and count the binary classifiers;
train a multiclass classifier and read a confusion matrix for error analysis;
tell multiclass, multilabel and multioutput problems apart;
preprocess labels correctly in each setting.

Words you need

Multiclass - each example has exactly one label out of $K>2$ classes (a digit 0 to 9).
Multilabel - each example can have several labels at once (a photo tagged beach + dog).
Multioutput - several different prediction targets, each possibly multiclass (predict both the digit and its colour).
OvR / OvA - one-versus-the-rest (one-versus-all).
OvO - one-versus-one.
Error analysis - studying which mistakes the model makes, to improve it.

Idea 1: Binary machines, many classes

For $K$ classes:

Strategy	Number of binary classifiers	Each trained on	Predict by
One-versus-rest (OvR)	$K$	all the data (class $k$ = positive, everything else = negative)	the class whose classifier gives the highest score
One-versus-one (OvO)	$\dfrac{K(K-1)}2$	only the examples of two classes	majority vote of all the pairwise duels

For the 10 digits: OvR = 10 classifiers, OvO = 45. For 4 classes: OvR 4, OvO 6. For 3 classes both give 3. Because $\frac{K(K-1)}2>K$ for $K>3$ , the method that needs more than $K$ classifiers is OvO.

Why OvO at all? Each OvO classifier trains on a small subset, which is much faster for algorithms that scale badly with data size (SVMs). OvR is the default for most others.

scikit-learn picks automatically: SGDClassifier, LogisticRegression, LinearSVC use OvR (or softmax) internally; SVC uses OvO internally (though by default it reports scores in the one-vs-rest shape, decision_function_shape="ovr").
To force one: wrap any binary estimator:

from sklearn.multiclass import OneVsRestClassifier, OneVsOneClassifier
ovr = OneVsRestClassifier(SGDClassifier(random_state=42)).fit(X_train, y_train)
ovo = OneVsOneClassifier(SGDClassifier(random_state=42)).fit(X_train, y_train)
len(ovr.estimators_), len(ovo.estimators_)        # (10, 45) on the digits data

Some classifiers are natively multiclass and need no trick: Naive Bayes, random forests, decision trees, k-NN, multinomial logistic regression.

Idea 2: A real multiclass run

The scikit-learn digits data: 1797 images of $8\times8$ pixels (64 features), digits 0 to 9, about 180 of each. We split 75/25 with stratify=y:

sgd = make_pipeline(StandardScaler(), SGDClassifier(random_state=42)).fit(X_train, y_train)
sgd.score(X_test, y_test)                       # 0.947
sgd[-1].coef_.shape                             # (10, 64): one row of weights per class (OvR)
sgd.decision_function(X_test[:2]).shape         # (2, 10): one score per class

For each example the model computes 10 scores and predicts argmax. predict_proba is available only if the loss supports it (loss="log_loss").

Metrics for many classes. accuracy_score still works. precision_score(y, pred, average="macro") computes one precision per class and averages them; "weighted" weights by class size; "micro" pools all decisions. For multiclass you must say which average= you want (the default "binary" fails).

Idea 3: Error analysis with the confusion matrix

For $K$ classes the confusion matrix is $K\times K$ : row = true class, column = predicted class. The diagonal is correct; off-diagonal cells are the mistakes.

cm = confusion_matrix(y_test, sgd.predict(X_test))
np.trace(cm), cm.sum() - np.trace(cm)           # 426 correct, 24 wrong (of 450)

The biggest single confusion in our run: true digit 1 predicted as 8 (5 times). That tells us where to look: maybe more training data of 1s, cleaner pixel features, or a better model. To see rates rather than counts, divide each row by its sum (normalize="true"). Zeroing the diagonal before plotting makes the mistakes stand out.

Idea 4: Multiclass, multilabel, multioutput

Problem	Targets $y$ look like	Example	Tool
Multiclass	one number per example, from $K$ classes	digit	any classifier above
Multilabel	several yes/no columns: $(m,L)$ matrix of 0/1	beach? dog?	`KNeighborsClassifier`, `RandomForest`, `MultiOutputClassifier`, `ClassifierChain`
Multioutput	several columns, each multiclass	(digit, colour)	`MultiOutputClassifier`, native in trees/k-NN

"A model predicts multiple labels (more than two) for each instance" is multilabel classification.

y_multilabel = np.c_[(y >= 7), (y % 2 == 1)].astype(int)     # "is large?" and "is odd?"
knn = KNeighborsClassifier().fit(X_train, y_multilabel_train)
knn.predict(X_test[:3])      # [[0,1],[0,0],[1,1]]: two yes/no answers per example

KNeighborsClassifier supports multilabel directly. Evaluate with f1_score(y, pred, average="macro") per label.

Idea 5: Preparing the labels

Task	Right label preprocessing
Multiclass, strings like "cat","dog"	`LabelEncoder` (to 0,1,2...) or leave strings (most classifiers accept them); `LabelBinarizer` for one-hot targets
Multilabel sets like `{"a","b"}`	`MultiLabelBinarizer` $\to$ 0/1 matrix
Features that are categories	`OneHotEncoder` / `OrdinalEncoder` (not `LabelEncoder`)

LabelBinarizer().fit_transform([2, 0, 1, 2])       # [[0,0,1],[1,0,0],[0,1,0],[0,0,1]]
MultiLabelBinarizer().fit_transform([{"a","b"}, {"b"}, {"a","c"}])
#                                     [[1,1,0],[0,1,0],[1,0,1]]

Solved examples

Solved example: 1. Count the classifiers

Question. A 6-class problem. How many binary classifiers does OvR train? OvO?

Solution. OvR: $\mathbf6$ . OvO: $\frac{6\cdot5}2=\mathbf{15}$ .

Solved example: 2. Reading a shape

Question. A 5-class SGDClassifier is trained on 8 features. What is coef_.shape? What is decision_function(X_new).shape for 20 new rows?

Solution. coef_: $(5,8)$ (OvR: one weight vector per class). decision_function: $(20,5)$ .

Solved example: 3. Name the problem

Question. (a) Tag each news article with all topics that apply (politics, sport, health ...). (b) Classify each fruit as apple, banana or orange. (c) For each photo predict the animal and its age group.

Solution. (a) Multilabel. (b) Multiclass. (c) Multioutput (two multiclass targets).

Your turn

Your turn: 1. OvR versus OvO

10 classes. If each OvO classifier needs 2 seconds and each OvR classifier 30 seconds, which total is cheaper?

Need a hint?

Count the classifiers first.

Show the full solution

OvO: $45\times2=90$ s. OvR: $10\times30=300$ s. OvO wins here because each OvO machine sees only a small slice of the data.

Your turn: 2. Which needs more than

n

"Which classification method needs more than $n$ classifiers, where $n$ is the number of classes?" (OvR, OvO, softmax regression)

Need a hint?

Compare $K$ with $K(K-1)/2$ .

Show the full solution

OvO (for $K>3$ , $\frac{K(K-1)}2>K$ ). OvR needs exactly $K$ and softmax regression is a single model.

Your turn: 3. Confusion matrix reading

In a 3-class confusion matrix [[30,2,1],[3,25,2],[0,4,28]], how many examples are there, and what is the accuracy? Which class is most often confused with which?

Need a hint?

Trace over total.

Show the full solution

Total $=30+2+1+3+25+2+0+4+28=95$ . Correct $=30+25+28=83$ . Accuracy $=\frac{83}{95}=0.874$ . The largest off-diagonal entry is $4$ : true class 3 predicted as class 2.

Your turn: 4. Which label tool?

Targets are [{"rock","pop"}, {"jazz"}, {"pop","jazz"}]. Which preprocessing?

Need a hint?

Several labels per example.

Show the full solution

MultiLabelBinarizer (this is a multilabel problem).

Your turn: 5. Averages

For multiclass precision you call precision_score(y, pred) and get an error. Why, and what is the fix?

Need a hint?

The default is for two classes.

Show the full solution

The default is average="binary", which assumes two classes. Pass average="macro" (or "weighted" or "micro").

Exam radar

In MLP Quiz 2: "Which of the options below represent the correct method to preprocess class labels in a multiclass setup?", "Which type of classification problem predicts multiple labels (more than 2) for each instance?" (multilabel), and "Which method of classification needs more than $n$ classifiers?" (OvO). The End Term adds OneVsRestClassifier/OneVsOneClassifier counts, decision_function shapes, and confusion-matrix error analysis.

Memorise: OvR $=K$ , OvO $=K(K-1)/2$ ; SVMs prefer OvO; multilabel = several yes/no columns.

Watch out - real exam trap

OvO needs $\frac{K(K-1)}2$ classifiers (not $K^2$ , not $K!$ ).
Multilabel $\neq$ multiclass: multilabel examples can have several labels at once.
LabelEncoder is for targets; use OneHotEncoder for categorical features.
In a multiclass confusion matrix, rows are the truth.
Multiclass precision_score needs average=.

Quick quiz

How many binary classifiers does one-versus-one train for 8 classes?

8 x 7 / 2 = 28.

A model predicts several labels for each photo (beach, dog, sunset). This is...

multiclass
multilabel
regression
clustering

Several yes/no labels per example is a multilabel problem.

Which of these is a natively multiclass classifier?

a single linear SVM
a random forest
a perceptron
the sigmoid

Trees and forests handle several classes directly; binary linear machines need OvR or OvO.

Select all TRUE statements. (select all that apply)

OvR trains one classifier per class on all the data.
SVC uses one-versus-one internally.
OvO trains K classifiers for K classes.
LabelEncoder should be used for categorical input features.

OvO trains K(K-1)/2 classifiers, and LabelEncoder is meant for targets.

Recap

Remember this

OvR: $K$ classifiers, take the highest score. OvO: $\frac{K(K-1)}2$ , vote; good for SVMs. Wrap with OneVsRestClassifier / OneVsOneClassifier.
Multiclass coef_ shape $(K,d)$ , decision_function $(m,K)$ . Use average="macro"|"weighted" for metrics.
Error analysis: $K\times K$ confusion matrix, rows = truth; find the biggest off-diagonal cells.
Multiclass (one label of $K$ ), multilabel (several yes/no), multioutput (several multiclass). LabelEncoder/LabelBinarizer for labels, MultiLabelBinarizer for label sets.

Formulas to keep

OvR classifiers $=K$ ; OvO classifiers $=\frac{K(K-1)}2$ (10 classes: 10 vs 45)
precision_score(y, pred, average="macro"|"weighted"|"micro")
confusion_matrix(y_true, y_pred): rows = true, columns = predicted

Connected weeks (learn them together)

MLT week 12 - Neural networks: Multiclass classification.

Practise with real exam questions

These come straight from past papers (with the real figures and the official answer key). Open 9 real questions on this week All Quiz 2 papers