Poster
Just Sort It! A Simple and Effective Approach to Active Preference Learning
Lucas Maystre · Matthias Grossglauser

Tue Aug 8th 06:30 -- 10:00 PM @ Gallery #88

We address the problem of learning a ranking by using adaptively chosen pairwise comparisons. Our goal is to recover the ranking accurately but to sample the comparisons sparingly. If all comparison outcomes are consistent with the ranking, the optimal solution is to use an efficient sorting algorithm, such as Quicksort. But how do sorting algorithms behave if some comparison outcomes are inconsistent with the ranking? We give favorable guarantees for Quicksort for the popular Bradley-Terry model, under natural assumptions on the parameters. Furthermore, we empirically demonstrate that sorting algorithms lead to a very simple and effective active learning strategy: repeatedly sort the items. This strategy performs as well as state-of-the-art methods (and much better than random sampling) at a minuscule fraction of the computational cost.

Author Information

lum Maystre (EPFL)
Matt Grossglauser (EPFL)

Matthias Grossglauser is Associate Professor in the School of Computer and Communication Sciences at EPFL. His current research interests are in machine learning for large social systems, stochastic models and algorithms for graph and mobility mining, and recommender systems. He is also the current director of the Doctoral School in Computer and Communication Sciences. From 2007-2010, he was with the Nokia Research Center (NRC) in Helsinki, Finland, serving as head of the Internet Laboratory, and later as head of a tech-transfer program focused on data mining, analytics, and machine learning. In addition, he served on Nokia's CEO Technology Council, a technology advisory group reporting to the CEO. Prior to this, he was Assistant Professor at EPFL, and a Research Scientist in the Networking and Distributed Systems Laboratory at AT&T Research in New Jersey. He received the 1998 Cor Baayen Award from the European Research Consortium for Informatics and Mathematics (ERCIM), the 2006 CoNEXT/SIGCOMM Rising Star Award, and two best paper awards. He served on the editorial board of IEEE/ACM Transactions on Networking, and on numerous Technical Program Committees.

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors