Learning to rank: a ROC-based graph-theoretic approach

This note summarizes the main results presented in the author's Ph.D. thesis, supervised by Luc Boullart and Bernard De Baets. The thesis was defended on 14th October 2008 at Universiteit Gent. It is written in English and available for download at http://users.ugent.be/~wwaegemn/thesis.pdf The work deals with preference learning, with emphasis on the ranking and ordinal regression machine learning settings and their connections to decision theory. Based on receiver operator characteristics analysis and graph theory, new performance measures are proposed to evaluate this type of models, and new algorithms are presented to compute and optimize these performance measures efficiently. Furthermore, the relationship with other settings like pairwise preference learning and multi-class classification is discussed.