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 metadatas

Cited literature [20 references]  Display  Hide  Download

https://hal.inria.fr/hal-01079283
Contributor : Balazs Szorenyi <>
Submitted on : Friday, November 20, 2015 - 8:20:47 PM
Last modification on : Thursday, February 21, 2019 - 10:52:49 AM
Long-term archiving on : Friday, April 14, 2017 - 11:32:41 AM

File

aaai_2014_auth_2.pdf
Files produced by the author(s)

Licence


Copyright

Identifiers

  • HAL Id : hal-01079283, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

384

Files downloads

114