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
* Auteur correspondant
2 SEQUEL - Sequential Learning
LIFL - Laboratoire d'Informatique Fondamentale de Lille, LAGIS - Laboratoire d'Automatique, Génie Informatique et Signal, Inria Lille - Nord Europe
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.
Type de document :
Communication dans un congrès
28th AAAI Conference on Artificial Intelligence (AAAI-14), Jul 2014, Quebec City, Canada
Liste complète des métadonnées

Littérature citée [20 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01079283
Contributeur : Balazs Szorenyi <>
Soumis le : vendredi 20 novembre 2015 - 20:20:47
Dernière modification le : jeudi 11 janvier 2018 - 01:49:33
Document(s) archivé(s) le : vendredi 14 avril 2017 - 11:32:41

Fichier

aaai_2014_auth_2.pdf
Fichiers produits par l'(les) auteur(s)

Licence


Copyright (Tous droits réservés)

Identifiants

  • 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〉

Partager

Métriques

Consultations de la notice

221

Téléchargements de fichiers

81