Skip to Main content Skip to Navigation
Conference papers

PAC Rank Elicitation through Adaptive Sampling of Stochastic Pairwise Preferences

Róbert Busa-Fekete 1 Balázs Szörényi 1, 2, * Eyke Hüllermeier 3
* Corresponding author
2 SEQUEL - Sequential Learning
LIFL - Laboratoire d'Informatique Fondamentale de Lille, Inria Lille - Nord Europe, LAGIS - Laboratoire d'Automatique, Génie Informatique et Signal
Abstract : We introduce the problem of PAC rank elicitation, which consists of sorting a given set of options based on adaptive sampling of stochastic pairwise preferences. More specifically, we assume the existence of a rank-ing procedure, such as Copeland's method, that deter-mines an underlying target order of the options. The goal is to predict a ranking that is sufficiently close to this target order with high probability, where closeness is measured in terms of a suitable distance measure. We instantiate this setting with combinations of two dif-ferent distance measures and ranking procedures. For these instantiations, we devise efficient strategies for sampling pairwise preferences and analyze the corre-sponding sample complexity. We also present first ex-periments to illustrate the practical performance of our methods.
Document type :
Conference papers
Complete list of metadata

Cited literature [20 references]  Display  Hide  Download
Contributor : Balazs Szorenyi Connect in order to contact the contributor
Submitted on : Friday, November 20, 2015 - 8:20:47 PM
Last modification on : Saturday, December 18, 2021 - 3:05:29 AM
Long-term archiving on: : Friday, April 14, 2017 - 11:32:41 AM


Files produced by the author(s)




  • HAL Id : hal-01079283, version 1



Róbert Busa-Fekete, Balázs Szörényi, Eyke Hüllermeier. PAC Rank Elicitation through Adaptive Sampling of Stochastic Pairwise Preferences. 28th AAAI Conference on Artificial Intelligence (AAAI-14), Jul 2014, Quebec City, Canada. ⟨hal-01079283⟩



Les métriques sont temporairement indisponibles