DS303: Introduction to Machine Learning
Multiclass Classification
Manjesh K. Hanawal
12th March 2025
Introduction
▶ Multiclass Learning: Classify an instance x into one of k
possible classes.
▶ Examples:
▶ Classifying documents by topic (each topic = a distinct class).
▶ Determining which object appears in an image (each category
of objects = a class).
▶ Straightforward Approaches:
▶ Reductions to binary classification (One-Versus-All, All-Pairs).
▶ Direct methods (e.g., linear multiclass predictors, multiclass
SVM).
DS303 Manjesh K. Hanawal 2
One Versus All
▶ Train k binary classifiers, each distinguishing “class i” vs.
“not class i.”
▶ Training:
1. For each class i:
▶ Label examples of class i as +1, all others as -1.
▶ Train a binary classifier hi .
2. Final prediction: arg max hi (x) (or use confidence scores).
i
▶ Pros:
▶ Simple to implement; reuse any binary classifier.
▶ Cons:
▶ Each binary classifier is unaware it will be combined; can lead
to suboptimal multiclass performance.
DS303 Manjesh K. Hanawal 3
One Versus All Algorithm
One-versus-All
input:
training set S = (x1 , y1 ), . . . , (xm , ym )
algorithm for binary classification A
foreach i ∈ Y:
▶ let Si = x1 , (−1) 1[y1 ̸=i] , . . . , xm , (−1) 1[ym ̸=i]
▶ let hi = A(Si )
output:
the multiclass hypothesis defined by
h(x) ∈ arg max hi (x).
i∈Y
DS303 Manjesh K. Hanawal 4
All-Pairs
▶ Train k2 binary classifiers, each discriminating between
classes i and j.
▶ Training:
1. For each pair (i, j):
▶ Label examples of class i as +1 and class j as -1.
▶ Train a binary classifier hi,j .
2. Final prediction: class with the most “wins” among all
pairwise classifiers.
▶ Pros:
▶ Often more accurate than One-versus-All on some tasks.
▶ Cons:
▶ k2 classifiers can be expensive if k is large.
▶ Combining outputs can still be suboptimal.
DS303 Manjesh K. Hanawal 5
All Pairs Algorithm
All-Pairs
input:
training set S = (x1 , y1 ), . . . , (xm , ym )
algorithm for binary classification A
foreach i, j ∈ Y such that i < j:
▶ initialize Si,j to be the empty sequence
▶ for t = 1, . . . , m:
▶ If yt = i add (xt , +1) to Si,j
▶ If yt = j add (xt , −1) to Si,j
▶ let hi,j = A(Si,j )
output:
the multiclass hypothesis defined by
X
h(x) ∈ arg max hi,j (x) .
i∈Y
j∈Y,j̸=i
DS303 Manjesh K. Hanawal 6
Problem with Reduction Approaches
Example (Multiclass categorization in R2 )
Consider a multiclass categorization problem in which the instance
space is X = R2 and the label set is Y = {1, 2, 3}. Suppose that
instances of the different classes are located in nonintersecting
balls, as depicted in Figure 1 below.
Figure: Three classes in R2 , each in a separate nonintersecting ball.
Suppose that the probability masses of classes 1, 2, and 3 are 40%,
20%, and 40%, respectively.
DS303 Manjesh K. Hanawal 7
Problem with One-Versus-All and All-pairs
Consider the application of One-versus-All to this problem and
assume that the binary classification algorithm for distinguishing
between class 2 and the rest chooses the all-negative solution
(never predicting class 2). Then the final predictor might
misclassify every example of class 2,
▶ One-Versus-All might produce trivial solutions for a
low-probability class.
▶ A joint linear multiclass approach can perfectly separate all
classes.
1 1 1 1
W1 = − √ , √ , W2 = (0, 1), W3 = √ , √
2 2 2 2
Conclusion: Even if a perfect linear separator exists, the reduction
methods might fail to find it.
DS303 Manjesh K. Hanawal 8
Linear Multiclass Predictors (1/3)
▶ Instead of separate binary classifiers, learn a single-parameter
vector (or set of vectors) for all classes.
▶ Form:
h(x) = arg max ⟨w , Ψ(x, y )⟩.
y ∈{1,...,k}
▶ Ψ is a class-sensitive feature mapping.
▶ Example: Multi vector Construction:
▶ Ψ(x, y ) can be the concatenation of k copies of x, where only
the y -th block is nonzero.
▶ Then ⟨w , Ψ(x, y )⟩ = ⟨wy , x⟩, scoring each class with a
dedicated sub-vector wy .
DS303 Manjesh K. Hanawal 9
Linear Multiclass Predictors (2/3)
A geometric illustration of the multiclass prediction over X = R2 is
given in the following figure:
Figure: Multiclass prediction in R2 . Each region (colored) is classified by
choosing the vector wi that produces the largest inner product ⟨wi , x⟩.
DS303 Manjesh K. Hanawal 10
Linear Multiclass Predictors (3/3)
▶ Advantages:
▶ Single model capturing relationships across classes.
▶ Avoid mismatches from separately learned binary classifiers.
▶ Cost-Sensitive:
▶ A general loss ∆(y ′ , y ) penalizes mistakes differently based on
which pair of classes is confused.
▶ ERM or Surrogate Approaches:
▶ If realizable, it can be solved with linear programs or
generalized Perceptron.
▶ Non-realizable: use multiclass hinge loss + convex
optimization.
DS303 Manjesh K. Hanawal 11
Multiclass SVM and SGD (1/2)
▶ Multiclass SVM:
m
1 X
min λ ∥w ∥2 + max ∆(y ′ , yi )+⟨w , Ψ(xi , y ′ )−Ψ(xi , yi )⟩ .
w m ′
y ∈{1,...,k}
i=1
▶ ∆ is a cost function (e.g., 0–1 or cost-sensitive).
▶ Solved via standard convex optimization or specialized
methods.
DS303 Manjesh K. Hanawal 12
Multiclass SVM and SGD (2/2)
▶ SGD approach:
▶ Uses subgradients of the hinge loss.
▶ Iterative update rule:
wt+1 = wt − ηt Ψ(x, y ∗ ) − Ψ(x, y ) ,
where y ∗ maximizes the hinge expression.
▶ ηt is the learning rate.
▶ Benefits:
▶ Scales to large datasets.
▶ Theoretically grounded with generalization bounds.
DS303 Manjesh K. Hanawal 13
Introduction to Ranking (1/2)
▶ Instead of a single label, we want an ordering of items by
“relevance.”
▶ Examples:
▶ Search-engine results (rank documents by relevance).
▶ Fraud detection (rank transactions by suspiciousness).
▶ Loss Functions:
▶ Kendall-Tau (counts pairwise disagreements).
▶ NDCG (high focus on top-ranked elements).
DS303 Manjesh K. Hanawal 14
Introduction to Ranking (2/2)
▶ Linear Ranking:
hw (x1 , . . . , xr ) = (⟨w , x1 ⟩, . . . , ⟨w , xr ⟩),
then sort by these scores.
▶ Learning:
▶ Use surrogates for ranking losses (e.g., hinge-based) + SGD.
▶ Efficient algorithms rely on structure (e.g., dynamic
programming, Hungarian method) to handle permutations.
DS303 Manjesh K. Hanawal 15