RI: Small: Modern Machine Learning Algorithms for Ranking from Pairwise and Higher-Order Comparisons

University Of Pennsylvania, Philadelphia PA

Investigators

Abstract

The problem of ranking a large number of items from comparisons among a few items at a time plays a crucial role in many areas, including recommender systems, crowdsourcing, marketing, and econometrics. In modern settings, as the numbers of items to be ranked increase and corresponding datasets grow in size and complexity, it is critical to re-visit the classical algorithms currently used for these problems and to design new algorithms that can better scale to modern needs under fewer assumptions. This project will design modern machine learning algorithms for such problems, while training PhD students and postdoctoral scientists in the interdisciplinary skills needed to design novel machine learning algorithms for problems involving modern datasets. Other broader impacts of the project will also include organization of workshops and/or tutorials to disseminate the results of the research conducted here, survey articles aimed at conveying the ideas to a broad scientific audience, and activities designed to increase participation of under-represented groups in STEM education opportunities and careers. The problem of ranking from pairwise comparisons has been studied in several fields, including statistics, operations research, social choice, and computer science, and several algorithms have been developed; however, very little has been understood in terms of how these different algorithms relate to each other, under what conditions they succeed (or fail), and how insights from one can be used to improve another. Algorithms for ranking from higher-order comparisons are even less well understood. The project will develop a strong understanding of the conditions under which various pairwise ranking algorithms succeed (or fail), and use insights from this understanding to develop modern machine learning algorithms with strong performance guarantees for ranking from pairwise as well as higher-order comparisons. Specifically, the project will investigate the following three directions: (1) Understanding conditions on pairwise models under which current algorithms succeed or fail. (2) Design of new machine learning algorithms for ranking from pairwise comparisons. (3) Ranking from higher-order comparisons. The project will bring a unified perspective to the study of ranking from pairwise comparisons, which hitherto has been scattered across different disciplines; develop new machine learning algorithms that improve the state of the art for a variety of ranking objectives; and initiate a systematic study of ranking from higher-order comparisons, a nascent area at the intersection of machine learning, statistics and econometrics.