Robert Busa-Fekete,
Balazs Szorenyi,
Weiwei Cheng,
Paul Weng,
Eyke Huellermeier
;
Proceedings of the 30th International Conference on Machine Learning, PMLR 28(3):1094-1102, 2013.
Abstract
We consider the problem of reliably selecting an optimal subset of fixed size from a given set of choice alternatives, based on noisy information about the quality of these alternatives. Problems of similar kind have been tackled by means of adaptive sampling schemes called racing algorithms. However, in contrast to existing approaches, we do not assume that each alternative is characterized by a real-valued random variable, and that samples are taken from the corresponding distributions. Instead, we only assume that alternatives can be compared in terms of pairwise preferences. We propose and formally analyze a general preference-based racing algorithm that we instantiate with three specific ranking procedures and corresponding sampling schemes. Experiments with real and synthetic data are presented to show the efficiency of our approach.
@InProceedings{pmlr-v28-busa-fekete13,
title = {Top-k Selection based on Adaptive Sampling of Noisy Preferences},
author = {Robert Busa-Fekete and Balazs Szorenyi and Weiwei Cheng and Paul Weng and Eyke Huellermeier},
booktitle = {Proceedings of the 30th International Conference on Machine Learning},
pages = {1094--1102},
year = {2013},
editor = {Sanjoy Dasgupta and David McAllester},
volume = {28},
number = {3},
series = {Proceedings of Machine Learning Research},
address = {Atlanta, Georgia, USA},
month = {17--19 Jun},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v28/busa-fekete13.pdf},
url = {http://proceedings.mlr.press/v28/busa-fekete13.html},
abstract = {We consider the problem of reliably selecting an optimal subset of fixed size from a given set of choice alternatives, based on noisy information about the quality of these alternatives. Problems of similar kind have been tackled by means of adaptive sampling schemes called racing algorithms. However, in contrast to existing approaches, we do not assume that each alternative is characterized by a real-valued random variable, and that samples are taken from the corresponding distributions. Instead, we only assume that alternatives can be compared in terms of pairwise preferences. We propose and formally analyze a general preference-based racing algorithm that we instantiate with three specific ranking procedures and corresponding sampling schemes. Experiments with real and synthetic data are presented to show the efficiency of our approach.}
}
%0 Conference Paper
%T Top-k Selection based on Adaptive Sampling of Noisy Preferences
%A Robert Busa-Fekete
%A Balazs Szorenyi
%A Weiwei Cheng
%A Paul Weng
%A Eyke Huellermeier
%B Proceedings of the 30th International Conference on Machine Learning
%C Proceedings of Machine Learning Research
%D 2013
%E Sanjoy Dasgupta
%E David McAllester
%F pmlr-v28-busa-fekete13
%I PMLR
%J Proceedings of Machine Learning Research
%P 1094--1102
%U http://proceedings.mlr.press
%V 28
%N 3
%W PMLR
%X We consider the problem of reliably selecting an optimal subset of fixed size from a given set of choice alternatives, based on noisy information about the quality of these alternatives. Problems of similar kind have been tackled by means of adaptive sampling schemes called racing algorithms. However, in contrast to existing approaches, we do not assume that each alternative is characterized by a real-valued random variable, and that samples are taken from the corresponding distributions. Instead, we only assume that alternatives can be compared in terms of pairwise preferences. We propose and formally analyze a general preference-based racing algorithm that we instantiate with three specific ranking procedures and corresponding sampling schemes. Experiments with real and synthetic data are presented to show the efficiency of our approach.
TY - CPAPER
TI - Top-k Selection based on Adaptive Sampling of Noisy Preferences
AU - Robert Busa-Fekete
AU - Balazs Szorenyi
AU - Weiwei Cheng
AU - Paul Weng
AU - Eyke Huellermeier
BT - Proceedings of the 30th International Conference on Machine Learning
PY - 2013/02/13
DA - 2013/02/13
ED - Sanjoy Dasgupta
ED - David McAllester
ID - pmlr-v28-busa-fekete13
PB - PMLR
SP - 1094
DP - PMLR
EP - 1102
L1 - http://proceedings.mlr.press/v28/busa-fekete13.pdf
UR - http://proceedings.mlr.press/v28/busa-fekete13.html
AB - We consider the problem of reliably selecting an optimal subset of fixed size from a given set of choice alternatives, based on noisy information about the quality of these alternatives. Problems of similar kind have been tackled by means of adaptive sampling schemes called racing algorithms. However, in contrast to existing approaches, we do not assume that each alternative is characterized by a real-valued random variable, and that samples are taken from the corresponding distributions. Instead, we only assume that alternatives can be compared in terms of pairwise preferences. We propose and formally analyze a general preference-based racing algorithm that we instantiate with three specific ranking procedures and corresponding sampling schemes. Experiments with real and synthetic data are presented to show the efficiency of our approach.
ER -
Busa-Fekete, R., Szorenyi, B., Cheng, W., Weng, P. & Huellermeier, E.. (2013). Top-k Selection based on Adaptive Sampling of Noisy Preferences. Proceedings of the 30th International Conference on Machine Learning, in PMLR 28(3):1094-1102
This site last compiled Mon, 29 May 2017 07:19:20 +0000
