# Multi-class classification via all pairwise classifications with LDA

I have trained linear discriminant analysis (LDA) classifiers for three classes of the IRIS data and struggling with how to make the classification. Here is the procedure:

For the Iris data, I have 3 combinations i.e. (0,1), (0,2) and (1,2). So, I trained a simple binary LDA classifier for each combination, and ended up with three classifiers:

Classifier(0,1)
Classifier(0,2)
Classifier(1,2)


Now, say I need to classify an input, say k = [1.2, 2.3, 5.0]. What I am doing is passing this input through all the classifiers individually, which are giving me their respective scores, like:

Classifier(0,1)[k] = {0: some score, 1: some score}
Classifier(0,2)[k] = {0: some score, 2: some score}
Classifier(1,2)[k] = {1: some score, 2: some score}


In a simple binary case of two classes, what we are taught to do is to take the class with maximum score as the result. My question is, what to do in such a scenario, where I have three results from three different classifiers, and I want to classify the output. Please note that I am not using a multiclass LDA. I am just using a binary LDA for all the possible combinations, a technique which is stated here:

quoting the last paragraph of this section: "Another common method is pairwise classification, where a new classifier is created for each pair of classes (giving C(C − 1)/2 classifiers in total), with the individual classifiers combined to produce a final classification."

Can somebody please enlighten me about what needs to be done in such a case for classification? Thank you.

• Interesting. I never used this approach. Thanks for raising the question. Jul 16, 2014 at 19:21
• I suppose that the most obvious way is like this. A 2-class classifier gives, for each case, a probability p of belonging to this class and the probability 1-p of belonging to the other class. With, say, 4 classes you have 6 classifiers and hence 12 propabilities. Each class has 3 probability values (3 "attempts" were made to classify to each class). You might average the 3 probabilities in one(arithmetic or possibly geometric mean?). If it >.5, assign the case to this class. Jul 16, 2014 at 19:32
• You meant to say that in the case of 4 classes, we have 6 classifiers and each classifier has 2 probabilities (since each classifier is a binary classifier). Once we have the results of these classifiers, we must take the average in each classifier result i.e. average of both probabilities in each classifier?
– khan
Jul 16, 2014 at 19:54
• I mean, average 3 values: p(classA not classB), p(classA not classC), p(classA not classD). That would be the "final" p(classA not other class). Do such for each class. Assign the case to class with the highest averaged prob. (Well, I guess it shoud be above 0.5.) Jul 16, 2014 at 20:05
• interesting approach. :-)
– khan
Jul 16, 2014 at 20:47

This question is not restricted to LDA, but can be asked about any binary classifier that is used in a multi-class setting by making all pairwise comparisons. The question is how to combine all pairwise classifications into one final classification.

The simplest approach is as follows. Each of the $\frac{K(K-1)}{2}$ pairwise classifiers results in a "winning" class (among the two considered). Count the number of wins for each of the classes (with the upper bound $K-1$), and assign the observation to the class with most wins. Note that this simple "voting" approach works even if your classifier does not return a probability of belonging to each of the two classes, but simply reports pairwise decisions.

When each of the pairwise classifiers reports not only pairwise decisions, but also probability of belonging to each of the two classes, more sophisticated algorithms become possible. I cannot give an overview or an advice, but there is a massively popular 2004 paper (over 1k citations according to Google Scholar) that reviews exactly this question and offers some novel methods:

I would guess, however, that in many real situations the simple voting method would already give reasonable results.

Update: In the NIPS version of the same paper the authors report performance of several methods, including the "voting" one, on several real datasets with number of classes ranging from 6 to 26, see Table 1. The voting method seems to be very competitive in each case. On some datasets it even seems to outperform all other, much more sophisticated, methods.

• This is a really very good and intuitive approach. I agree, there are multiple of such cases in which this approach is validated. Many thanks.
– khan
Jul 16, 2014 at 21:36
• this simple "voting" approach is very crude. It implies k-1 times of rounding a probability to an integer (0 or 1). Jul 16, 2014 at 22:06
• @ttnphns: Well, it does look crude, however I would not be so sure that in practice it is so very crude as you remark. In the NIPS version of the paper I cited the authors report performance of several methods on several real datasets (with number of classes from 6 to 26), see Table 1. The voting method is very competitive in each case. On some datasets it even seems to outperform all other, much more sophisticated, methods! Jul 16, 2014 at 22:43
• I guess it all boils down to the number of classes involved in the dataset for validating this approach, in particular to the case of LDA. Higher the number of classes, I guess, less performing will be the voting model. But still, seems to work relatively well in lower k's.
– khan
Jul 16, 2014 at 23:03