ERA Ranking Representability: The Missing Link Between Ordinal Regression and Multi-class Classi?cation

摘要

Can a multi-class classi?cation model in some situations be simpli?ed to an ordinal regression model without sacri?cing performance? We try to answer this question from a theoretical point of view for one-versus-one multi-class ensembles. To that end, suf?cient 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. For the three-class case, this results in a new type of cycle transitivity for pairwise AUCs that can be veri?ed by solving an integer quadratic program. Moreover, solving this integer quadratic program can be avoided, since its solution converges for an in?nite data sample to a simple form, resulting in a deviation bound that becomes tighter with increasing sample size.