Top-k Selection based on Adaptive Sampling of Noisy Preferences

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v28-busa-fekete13, title = {Top-k Selection based on Adaptive Sampling of Noisy Preferences}, author = {Busa-Fekete, Robert and Szorenyi, Balazs and Cheng, Weiwei and Weng, Paul and Huellermeier, Eyke}, booktitle = {Proceedings of the 30th International Conference on Machine Learning}, pages = {1094--1102}, year = {2013}, editor = {Dasgupta, Sanjoy and McAllester, David}, 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 = {https://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.} }
Endnote
%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 %P 1094--1102 %U https://proceedings.mlr.press/v28/busa-fekete13.html %V 28 %N 3 %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.
RIS
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 DA - 2013/05/26 ED - Sanjoy Dasgupta ED - David McAllester ID - pmlr-v28-busa-fekete13 PB - PMLR DP - Proceedings of Machine Learning Research VL - 28 IS - 3 SP - 1094 EP - 1102 L1 - http://proceedings.mlr.press/v28/busa-fekete13.pdf UR - https://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 -
APA
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 Proceedings of Machine Learning Research 28(3):1094-1102 Available from https://proceedings.mlr.press/v28/busa-fekete13.html.

Related Material