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)

1 MTA-SZTE Research Group on Artificial Intelligence
2 SEQUEL - Sequential Learning
3 University of Paderborn

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.

Domaines: Machine Learning [stat.ML]

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⟩