A transitivity analysis of bipartite rankings in pairwise multi-class classification

Many multi-class classification algorithms in statistics and machine learning typically combine several binary classifiers in order to construct an overall classifier. In the popular pairwise ensemble, one classifier is built for each pair of classes, resulting in pairwise bipartite rankings. In contrast, ordinal regression algorithms consider a single ranking function for several ordered classes. It is known in the literature that pairwise ensembles can be useful for ordinal regression. However, can single ranking models make a contribution to multi-class classification? The answer to this question should be affirmative, as supported by theoretical results presented in this article. We conduct a formal analysis of the consistency of pairwise bipartite rankings by uncovering the conditions under which they can be equivalently expressed in terms of a single ranking. Similar to the utility representability of pairwise preference relations, it turns out that transitivity plays a crucial role in the characterization of the ranking representability of pairwise bipartite rankings. To this end, we introduce the new concepts of strict ranking representability, a restrictive condition that can be verified easily, and AUC ranking representability, a practically more useful condition that is more difficult to verify. However, the link between pairwise bipartite rankings and dice games allows us to formulate necessary transitivity conditions for AUC ranking representability. A sufficient condition on the other hand is obtained by introducing a new type of transitivity that can be verified by solving an integer quadratic program. (C) 2010 Elsevier Inc. All rights reserved.