A Maximum Likelihood Approach For Selecting Sets of Alternatives

Ariel D. Procaccia, Sashank J. Reddi, Nisarg Shah
Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence, PMLR R10:694-703, 2012.

Abstract

We consider the problem of selecting a subset of alternatives given noisy evaluations of the relative strength of different alternatives. We wish to select a k-subset (for a given k) that provides a maximum likelihood estimate for one of several objectives, e.g., containing the strongest alternative. Although this problem is NP-hard, we show that when the noise level is sufficiently high, intuitive methods provide the optimal solution. We thus generalize classical results about singling out one alternative and identifying the hidden ranking of alternatives by strength. Extensive experiments show that our methods perform well in practical settings.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR10-procaccia12a, title = {A Maximum Likelihood Approach For Selecting Sets of Alternatives}, author = {Procaccia, Ariel D. and Reddi, Sashank J. and Shah, Nisarg}, booktitle = {Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence}, pages = {694--703}, year = {2012}, editor = {de Freitas, Nando and Murphy, Kevin}, volume = {R10}, series = {Proceedings of Machine Learning Research}, month = {14--18 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r10/main/assets/procaccia12a/procaccia12a.pdf}, url = {https://proceedings.mlr.press/r10/procaccia12a.html}, abstract = {We consider the problem of selecting a subset of alternatives given noisy evaluations of the relative strength of different alternatives. We wish to select a k-subset (for a given k) that provides a maximum likelihood estimate for one of several objectives, e.g., containing the strongest alternative. Although this problem is NP-hard, we show that when the noise level is sufficiently high, intuitive methods provide the optimal solution. We thus generalize classical results about singling out one alternative and identifying the hidden ranking of alternatives by strength. Extensive experiments show that our methods perform well in practical settings.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T A Maximum Likelihood Approach For Selecting Sets of Alternatives %A Ariel D. Procaccia %A Sashank J. Reddi %A Nisarg Shah %B Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2012 %E Nando de Freitas %E Kevin Murphy %F pmlr-vR10-procaccia12a %I PMLR %P 694--703 %U https://proceedings.mlr.press/r10/procaccia12a.html %V R10 %X We consider the problem of selecting a subset of alternatives given noisy evaluations of the relative strength of different alternatives. We wish to select a k-subset (for a given k) that provides a maximum likelihood estimate for one of several objectives, e.g., containing the strongest alternative. Although this problem is NP-hard, we show that when the noise level is sufficiently high, intuitive methods provide the optimal solution. We thus generalize classical results about singling out one alternative and identifying the hidden ranking of alternatives by strength. Extensive experiments show that our methods perform well in practical settings. %Z Reissued by PMLR on 04 October 2026.
APA
Procaccia, A.D., Reddi, S.J. & Shah, N.. (2012). A Maximum Likelihood Approach For Selecting Sets of Alternatives. Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R10:694-703 Available from https://proceedings.mlr.press/r10/procaccia12a.html. Reissued by PMLR on 04 October 2026.

Related Material