On the ERA ranking representability of pairwise bipartite ranking functions

作者:

Highlights:

摘要

In domains like decision theory and social choice theory it is known for a long time that stochastic transitivity properties yield necessary and sufficient conditions for the ranking or utility representability of reciprocal preference relations. In this article we extend these results for reciprocal preference relations originating from the pairwise comparison of random vectors in a machine learning context. More specifically, the expected ranking accuracy (ERA) is such a reciprocal relation that occurs in multi-class classification problems, when ranking or utility functions are fitted to the data in a pairwise manner. We establish necessary and sufficient conditions for which these pairwise bipartite ranking functions can be simplified to a single ranking function such that the pairwise expected ranking accuracies of both models coincide. Similarly as for more common reciprocal preference relations, cycle transitivity plays a crucial role in this new setting. We first consider the finite sample case, for which expected ranking accuracy can be estimated by means of the area under the ROC curve (AUC), and subsequently, we further generalize these results to the underlying distributions. It turns out that the ranking representability of pairwisely compared random vectors can be expressed elegantly in a distribution-independent way by means of a specific type of cycle transitivity, defined by a conjunctor that is closely related to the algebraic product.

论文关键词:Pairwise bipartite ranking,Reciprocal preference relation,Cycle transitivity,Receiver operating characteristics (ROC) analysis,Graph theory,Multi-class classification,Decision theory,Machine learning

论文评审过程:Received 31 January 2009, Revised 19 June 2010, Accepted 19 June 2010, Available online 2 December 2010.

论文官网地址:https://doi.org/10.1016/j.artint.2010.11.006