Learning to Top-K Search using Pairwise Comparisons

Brian Eriksson
Proceedings of the Sixteenth International Conference on Artificial Intelligence and Statistics, PMLR 31:265-273, 2013.

Abstract

Given a collection of N items with some unknown underlying ranking, we examine how to use pairwise comparisons to determine the top ranked items in the set. Resolving the top items from pairwise comparisons has application in diverse fields ranging from recommender systems to image-based search to protein structure analysis. In this paper we introduce techniques to resolve the top ranked items using significantly fewer than all the possible pairwise comparisons using both random and adaptive sampling methodologies. Using randomly-chosen comparisons, a graph-based technique is shown to efficiently resolve the top O(\logN) items when there are no comparison errors. In terms of adaptively-chosen comparisons, we show how the top O(\logN) items can be found, even in the presence of corrupted observations, using a voting methodology that only requires O(N\log^2N) pairwise comparisons.

Cite this Paper

BibTeX
@InProceedings{pmlr-v31-eriksson13a, title = {Learning to Top-K Search using Pairwise Comparisons}, author = {Eriksson, Brian}, booktitle = {Proceedings of the Sixteenth International Conference on Artificial Intelligence and Statistics}, pages = {265--273}, year = {2013}, editor = {Carvalho, Carlos M. and Ravikumar, Pradeep}, volume = {31}, series = {Proceedings of Machine Learning Research}, address = {Scottsdale, Arizona, USA}, month = {29 Apr--01 May}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v31/eriksson13a.pdf}, url = {https://proceedings.mlr.press/v31/eriksson13a.html}, abstract = {Given a collection of N items with some unknown underlying ranking, we examine how to use pairwise comparisons to determine the top ranked items in the set. Resolving the top items from pairwise comparisons has application in diverse fields ranging from recommender systems to image-based search to protein structure analysis. In this paper we introduce techniques to resolve the top ranked items using significantly fewer than all the possible pairwise comparisons using both random and adaptive sampling methodologies. Using randomly-chosen comparisons, a graph-based technique is shown to efficiently resolve the top O(\logN) items when there are no comparison errors. In terms of adaptively-chosen comparisons, we show how the top O(\logN) items can be found, even in the presence of corrupted observations, using a voting methodology that only requires O(N\log^2N) pairwise comparisons.} }
Endnote
%0 Conference Paper %T Learning to Top-K Search using Pairwise Comparisons %A Brian Eriksson %B Proceedings of the Sixteenth International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2013 %E Carlos M. Carvalho %E Pradeep Ravikumar %F pmlr-v31-eriksson13a %I PMLR %P 265--273 %U https://proceedings.mlr.press/v31/eriksson13a.html %V 31 %X Given a collection of N items with some unknown underlying ranking, we examine how to use pairwise comparisons to determine the top ranked items in the set. Resolving the top items from pairwise comparisons has application in diverse fields ranging from recommender systems to image-based search to protein structure analysis. In this paper we introduce techniques to resolve the top ranked items using significantly fewer than all the possible pairwise comparisons using both random and adaptive sampling methodologies. Using randomly-chosen comparisons, a graph-based technique is shown to efficiently resolve the top O(\logN) items when there are no comparison errors. In terms of adaptively-chosen comparisons, we show how the top O(\logN) items can be found, even in the presence of corrupted observations, using a voting methodology that only requires O(N\log^2N) pairwise comparisons.
RIS
TY - CPAPER TI - Learning to Top-K Search using Pairwise Comparisons AU - Brian Eriksson BT - Proceedings of the Sixteenth International Conference on Artificial Intelligence and Statistics DA - 2013/04/29 ED - Carlos M. Carvalho ED - Pradeep Ravikumar ID - pmlr-v31-eriksson13a PB - PMLR DP - Proceedings of Machine Learning Research VL - 31 SP - 265 EP - 273 L1 - http://proceedings.mlr.press/v31/eriksson13a.pdf UR - https://proceedings.mlr.press/v31/eriksson13a.html AB - Given a collection of N items with some unknown underlying ranking, we examine how to use pairwise comparisons to determine the top ranked items in the set. Resolving the top items from pairwise comparisons has application in diverse fields ranging from recommender systems to image-based search to protein structure analysis. In this paper we introduce techniques to resolve the top ranked items using significantly fewer than all the possible pairwise comparisons using both random and adaptive sampling methodologies. Using randomly-chosen comparisons, a graph-based technique is shown to efficiently resolve the top O(\logN) items when there are no comparison errors. In terms of adaptively-chosen comparisons, we show how the top O(\logN) items can be found, even in the presence of corrupted observations, using a voting methodology that only requires O(N\log^2N) pairwise comparisons. ER -
APA
Eriksson, B.. (2013). Learning to Top-K Search using Pairwise Comparisons. Proceedings of the Sixteenth International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 31:265-273 Available from https://proceedings.mlr.press/v31/eriksson13a.html.

Related Material