Understanding Machine Learning: From Theory to Algorithms

17.1 One-versus-All and All-Pairs 229

All-Pairs

input:

training setS= (x 1 ,y 1 ),...,(xm,ym)

algorithm for binary classificationA

foreachi,j∈Ys.t.i < j

initializeSi,jto be the empty sequence

fort= 1,...,m

Ifyt=iadd (xt,1) toSi,j

Ifyt=jadd (xt,−1) toSi,j

lethi,j=A(Si,j)

output:

the multiclass hypothesis defined by

h(x)∈argmaxi∈Y

(∑

j∈Ysign(j−i)hi,j(x)

)

Although reduction methods such as the One-versus-All and All-Pairs are
simple and easy to construct from existing algorithms, their simplicity has a
price. The binary learner is not aware of the fact that we are going to use its
output hypotheses for constructing a multiclass predictor, and this might lead
to suboptimal results, as illustrated in the following example.

Example 17.1 Consider a multiclass categorization problem in which the in-
stance space isX=R^2 and the label set isY={ 1 , 2 , 3 }. Suppose that instances
of the different classes are located in nonintersecting balls as depicted in the fol-
lowing.

1 2 3

Suppose that the probability masses of classes 1, 2 ,3 are 40%,20%,and 40%,
respectively. Consider the application of One-versus-All to this problem, and as-
sume that the binary classification algorithm used by One-versus-All is ERM
with respect to the hypothesis class of halfspaces. Observe that for the prob-
lem of discriminating between class 2 and the rest of the classes, the optimal
halfspace would be the all negative classifier. Therefore, the multiclass predic-
tor constructed by One-versus-All might err on all the examples from class 2
(this will be the case if the tie in the definition ofh(x) is broken by the nu-
merical value of the class label). In contrast, if we choosehi(x) = 〈wi,x〉,

wherew 1 =

(

−√^12 ,√^12

)

,w 2 = (0,1), andw 3 =

(

√^1

2 ,

√^1

2

)

, then the classi-

fier defined byh(x) = argmaxihi(x) perfectly predicts all the examples. We see