Multi-class classification via all pairwise classifications with LDA

Question

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:

http://en.wikipedia.org/wiki/Linear_discriminant_analysis#Multiclass_LDA

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.

Answer 1

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:

• Wu, T. F., Lin, C. J., & Weng, R. C. (2004). Probability estimates for multi-class classification by pairwise coupling. The Journal of Machine Learning Research, 5, 975-1005.

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.