Learning accurate rankings from noisy human comparison feedback
Learning a Ranking from Human Feedback in Log-Concave Random Utility Models
Machine Learning
Summary
This paper looks at how to figure out the order of a set of items based on how humans compare them, even when those comparisons have some randomness or noise. Sometimes, the human gives a full ranking of all items; other times, they just pick the top item. The researchers show how many examples are needed to get a ranking that’s close enough to the true order, and they create methods that work well even without knowing the exact noise details. They also find that learning from only the winner is harder than learning from full rankings.
What this means in practice
- •For product recommendation teams: Develop accurate item rankings from noisy customer preference data with minimal feedback requirements.
- •For market research analysts: Improve survey designs by understanding the trade-offs between detailed rankings and simple winner-only feedback when evaluating product preferences.
Authors
Diego Alovisetti, Marco Mussi, Alberto Maria Metelli
Abstract
We study the problem of recovering the ranking of a fixed set of items according to their unknown numerical utilities. At each interaction with the environment, a learner presents the item set to a human and receives comparative feedback of two types. Under full-ranking feedback, each interaction reveals a noisy ranking of all items, whereas under winner-only feedback, it reveals only the item ranked first. In both settings, we model human feedback using a random utility model with log-concave noise and study the number of observations needed to recover an $ε$-accurate ranking with high probability. This novel criterion tolerates ordering errors only between items whose utilities differ by less than $ε$. For both feedback types, we establish worst-case sample-complexity lower bounds and develop algorithms that match these bounds up to logarithmic factors. Neither algorithm requires knowledge of the noise distribution, while only requiring an upper bound on its variance. Our results show that the ranking problem under winner-only feedback is intrinsically harder by exposing the sample complexity dependence on the minimum winning probability across the item set.