PAC Rank Elicitation Through Adaptive Sampling of Stochastic Pairwise Preferences
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 ranking procedure, such as Copeland's method, that determines 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 different distance measures and ranking procedures. For these instantiations, we devise efficient strategies for sampling pairwise preferences and analyze the corresponding sample complexity. We also present first experiments to illustrate the practical performance of our methods.
Cite
Text
Busa-Fekete et al. "PAC Rank Elicitation Through Adaptive Sampling of Stochastic Pairwise Preferences." AAAI Conference on Artificial Intelligence, 2014. doi:10.1609/AAAI.V28I1.8978Markdown
[Busa-Fekete et al. "PAC Rank Elicitation Through Adaptive Sampling of Stochastic Pairwise Preferences." AAAI Conference on Artificial Intelligence, 2014.](https://mlanthology.org/aaai/2014/busafekete2014aaai-pac/) doi:10.1609/AAAI.V28I1.8978BibTeX
@inproceedings{busafekete2014aaai-pac,
title = {{PAC Rank Elicitation Through Adaptive Sampling of Stochastic Pairwise Preferences}},
author = {Busa-Fekete, Róbert and Szörényi, Balázs and Hüllermeier, Eyke},
booktitle = {AAAI Conference on Artificial Intelligence},
year = {2014},
pages = {1701-1707},
doi = {10.1609/AAAI.V28I1.8978},
url = {https://mlanthology.org/aaai/2014/busafekete2014aaai-pac/}
}