A graph-theoretic approach for reducing one-versus-one multi-class classication to ranking
Willem Waegeman, Bernard De Baets, Luc Boullart · 2008
Can a multi-class classication model in some situations be simplied to a ranking model without sacricing performance? We try to answer that question from a theoretical point of view for one-versus-one multi-class ensembles. To this end, sucient conditions are derived for which a one-versus-one ensemble becomes ranking representable, i.e. conditions for which the ensemble can be reduced to a ranking or ordinal regression model such that a similar performance on training data is measured. As performance measure, we use the area under the ROC curve (AUC) and its reformulation in terms of graphs. By means of a graph-theoretic analysis of the problem, we are able to formulate necessary and sucient conditions for ranking representability. For the three class case, this results in a new type of transitivity for pairwise AUCs that can be veried by solving an integer quadratic program.