Active Learning for Top-$K$ Rank Aggregation from Noisy Comparisons

Soheil Mohajer, Changho Suh, Adel Elmahdy
Proceedings of the 34th International Conference on Machine Learning, PMLR 70:2488-2497, 2017.

Abstract

We explore an active top-$K$ ranking problem based on pairwise comparisons that are collected possibly in a sequential manner as per our design choice. We consider two settings: (1) top-$K$ sorting in which the goal is to recover the top-$K$ items in order out of $n$ items; (2) top-$K$ partitioning where only the set of top-$K$ items is desired. Under a fairly general model which subsumes as special cases various models (e.g., Strong Stochastic Transitivity model, BTL model and uniform noise model), we characterize upper bounds on the sample size required for top-$K$ sorting as well as for top-$K$ partitioning. As a consequence, we demonstrate that active ranking can offer significant multiplicative gains in sample complexity over passive ranking. Depending on the underlying stochastic noise model, such gain varies from around $\frac{\log n}{\log \log n}$ to $\frac{ n^2 \log n }{\log \log n}$. We also present an algorithm that is applicable to both settings.

Cite this Paper

BibTeX
@InProceedings{pmlr-v70-mohajer17a, title = {Active Learning for Top-$K$ Rank Aggregation from Noisy Comparisons}, author = {Soheil Mohajer and Changho Suh and Adel Elmahdy}, booktitle = {Proceedings of the 34th International Conference on Machine Learning}, pages = {2488--2497}, 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/mohajer17a/mohajer17a.pdf}, url = {https://proceedings.mlr.press/v70/mohajer17a.html}, abstract = {We explore an active top-$K$ ranking problem based on pairwise comparisons that are collected possibly in a sequential manner as per our design choice. We consider two settings: (1) top-$K$ sorting in which the goal is to recover the top-$K$ items in order out of $n$ items; (2) top-$K$ partitioning where only the set of top-$K$ items is desired. Under a fairly general model which subsumes as special cases various models (e.g., Strong Stochastic Transitivity model, BTL model and uniform noise model), we characterize upper bounds on the sample size required for top-$K$ sorting as well as for top-$K$ partitioning. As a consequence, we demonstrate that active ranking can offer significant multiplicative gains in sample complexity over passive ranking. Depending on the underlying stochastic noise model, such gain varies from around $\frac{\log n}{\log \log n}$ to $\frac{ n^2 \log n }{\log \log n}$. We also present an algorithm that is applicable to both settings.} }
Endnote
%0 Conference Paper %T Active Learning for Top-$K$ Rank Aggregation from Noisy Comparisons %A Soheil Mohajer %A Changho Suh %A Adel Elmahdy %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-mohajer17a %I PMLR %P 2488--2497 %U https://proceedings.mlr.press/v70/mohajer17a.html %V 70 %X We explore an active top-$K$ ranking problem based on pairwise comparisons that are collected possibly in a sequential manner as per our design choice. We consider two settings: (1) top-$K$ sorting in which the goal is to recover the top-$K$ items in order out of $n$ items; (2) top-$K$ partitioning where only the set of top-$K$ items is desired. Under a fairly general model which subsumes as special cases various models (e.g., Strong Stochastic Transitivity model, BTL model and uniform noise model), we characterize upper bounds on the sample size required for top-$K$ sorting as well as for top-$K$ partitioning. As a consequence, we demonstrate that active ranking can offer significant multiplicative gains in sample complexity over passive ranking. Depending on the underlying stochastic noise model, such gain varies from around $\frac{\log n}{\log \log n}$ to $\frac{ n^2 \log n }{\log \log n}$. We also present an algorithm that is applicable to both settings.
APA
Mohajer, S., Suh, C. & Elmahdy, A.. (2017). Active Learning for Top-$K$ Rank Aggregation from Noisy Comparisons. Proceedings of the 34th International Conference on Machine Learning, in Proceedings of Machine Learning Research 70:2488-2497 Available from https://proceedings.mlr.press/v70/mohajer17a.html.

Related Material