Ranking and Embedding From Pairwise Comparisons

Ranking, clustering, or metrically-embedding a set of items (e.g., images, documents, products) based on human judgments can shed light on preferences and human reasoning. Two common approaches to collecting data from people are rating and comparison-based systems. Ratings can be difficult to calibrate across people. Also, in certain applications, it may be far easier to compare items than to rate them (e.g., rating funniness of jokes is more difficult than deciding which of two jokes is more funny). For these reasons, pairwise comparisons are often used in practice. This talk focuses on ranking and metric embedding from pairwise comparisons, and theory and methods for adaptive data collection in particular. Adaptive data collection can reduce the number of comparisons required to learn an accurate ranking or embedding, but is challenging to mathematically analyze. The gap between theory and practice is relatively small in the case of ranking, but many difficult mathematical questions remain for embedding from pairwise comparisons. The talk will also illustrate progress and challenges through several ranking and embedding experiments carried out with a new open-source software system called NEXT.