| Title | : | Ranking from Pairwise Comparisons |
| Speaker | : | Arun Rajkumar (Conduent Labs) |
| Details | : | Fri, 4 May, 2018 11:00 AM @ A M Turing Hall |
| Abstract: | : | Ranking a set of candidates or items from pairwise comparisons is a fundamental problem that arises in many settings such as elections, recommendation systems, sports team rankings, document rankings and so on. While the problem of ranking from pairwise comparisons has been studied in multiple communities such as machine learning, operations research, linear algebra, statistics etc., and several algorithms (both classic and recent) have been proposed, it is not well understood under what conditions these different algorithms perform well. In this talk, we aim to fill this fundamental gap, by elucidating precise conditions under which different existing algorithms perform well, as well as giving new algorithms that provably perform well under broader conditions. We will define an interesting class of conditions on the pairwise probabilities of items being preferred to one another and develop algorithms that provably produce optimal rankings with a tight sample complexity. We will show that several existing models such as the Bradley-Terry-Luce (BTL) model, Thurstone model etc., are special cases of this condition. We will also look at our latest work on interesting cases where items have associated features and see how one can break the O(nlog(n)) sample complexity barrier for ranking in such cases. Finally, we will briefly discuss notions of tournament solutions and some recent work on identifying winners from a set of items by active pairwise comparisons.
Speaker bio: Arun Rajkumar is currently a research scientist in the Machine learning and Analytics division of Conduent Labs (formerly Xerox Research). Prior to this, he completed his Ph.D from the department of Computer science and automation, Indian institute of Science in the area of Ranking. His research interests include algorithmic machine learning and statistical learning theory with specific focus on ranking algorithms. He is also interested in practical applications of machine learning to the areas of transportation, healthcare etc. |
