Just Sort It! A Simple and Effective Approach to Active Preference Learning

Lucas Maystre, Matthias Grossglauser
Proceedings of the 34th International Conference on Machine Learning, PMLR 70:2344-2353, 2017.

Abstract

We address the problem of learning a ranking by using adaptively chosen pairwise comparisons. Our goal is to recover the ranking accurately but to sample the comparisons sparingly. If all comparison outcomes are consistent with the ranking, the optimal solution is to use an efficient sorting algorithm, such as Quicksort. But how do sorting algorithms behave if some comparison outcomes are inconsistent with the ranking? We give favorable guarantees for Quicksort for the popular Bradley-Terry model, under natural assumptions on the parameters. Furthermore, we empirically demonstrate that sorting algorithms lead to a very simple and effective active learning strategy: repeatedly sort the items. This strategy performs as well as state-of-the-art methods (and much better than random sampling) at a minuscule fraction of the computational cost.

Cite this Paper

BibTeX
@InProceedings{pmlr-v70-maystre17a, title = {Just Sort It! {A} Simple and Effective Approach to Active Preference Learning}, author = {Lucas Maystre and Matthias Grossglauser}, booktitle = {Proceedings of the 34th International Conference on Machine Learning}, pages = {2344--2353}, year = {2017}, editor = {Precup, Doina and Teh, Yee Whye}, volume = {70}, series = {Proceedings of Machine Learning Research}, month = {06--11 Aug}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v70/maystre17a/maystre17a.pdf}, url = {https://proceedings.mlr.press/v70/maystre17a.html}, abstract = {We address the problem of learning a ranking by using adaptively chosen pairwise comparisons. Our goal is to recover the ranking accurately but to sample the comparisons sparingly. If all comparison outcomes are consistent with the ranking, the optimal solution is to use an efficient sorting algorithm, such as Quicksort. But how do sorting algorithms behave if some comparison outcomes are inconsistent with the ranking? We give favorable guarantees for Quicksort for the popular Bradley-Terry model, under natural assumptions on the parameters. Furthermore, we empirically demonstrate that sorting algorithms lead to a very simple and effective active learning strategy: repeatedly sort the items. This strategy performs as well as state-of-the-art methods (and much better than random sampling) at a minuscule fraction of the computational cost.} }
Endnote
%0 Conference Paper %T Just Sort It! A Simple and Effective Approach to Active Preference Learning %A Lucas Maystre %A Matthias Grossglauser %B Proceedings of the 34th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2017 %E Doina Precup %E Yee Whye Teh %F pmlr-v70-maystre17a %I PMLR %P 2344--2353 %U https://proceedings.mlr.press/v70/maystre17a.html %V 70 %X We address the problem of learning a ranking by using adaptively chosen pairwise comparisons. Our goal is to recover the ranking accurately but to sample the comparisons sparingly. If all comparison outcomes are consistent with the ranking, the optimal solution is to use an efficient sorting algorithm, such as Quicksort. But how do sorting algorithms behave if some comparison outcomes are inconsistent with the ranking? We give favorable guarantees for Quicksort for the popular Bradley-Terry model, under natural assumptions on the parameters. Furthermore, we empirically demonstrate that sorting algorithms lead to a very simple and effective active learning strategy: repeatedly sort the items. This strategy performs as well as state-of-the-art methods (and much better than random sampling) at a minuscule fraction of the computational cost.
APA
Maystre, L. & Grossglauser, M.. (2017). Just Sort It! A Simple and Effective Approach to Active Preference Learning. Proceedings of the 34th International Conference on Machine Learning, in Proceedings of Machine Learning Research 70:2344-2353 Available from https://proceedings.mlr.press/v70/maystre17a.html.

Related Material