Home // IMMM 2017, The Seventh International Conference on Advances in Information Mining and Management // View article

Efficient Selection of Pairwise Comparisons for Computing Top-heavy Rankings

Authors:
Shenshen Liang
Luca de Alfaro

Keywords: Top-heavy Ranking; Pairwise Comparison; Active Learning; Crowdsourcing.

Abstract:
Crowdsourcing provides an efficient way to gather information from humans for solving large scale problems. Learning to rank via pairwise comparison is one of the most essential tasks in crowdsourcing, and it is widely used in applications, such as recommendation systems, online contests, player matching, and more. While much research has been done on how to aggregate the comparison data into an overall ranking, comparatively less research has been done on how to optimally select items for pairwise comparison. In this research, we consider ranking problems where the benefit for each item to be ranked in position n is a geometrically decreasing function of n. This geometric dependence between ranking and benefit is common online and on the web. We define the quality of a ranking as the total misallocated benefit, so that in learning a ranking, we are more sensitive to errors in the ordering of top items than errors in items ordered in the long tail. We propose and compare several active learning methods for selecting pairs for comparison. The methods actively search for the pairs to compare, present them to the crowd, and update the ranking according to the comparison outcomes. We show experimentally that the best-performing method selects pairs on the basis of the expected benefit mis-allocation between the items in the pair. As the size of the ranking problem grows, the computational cost of selecting the optimal pair for each comparison becomes prohibitive. We propose and show an efficient algorithm that selects items in batches while retains nearly optimal performance, at a cost per comparison that grows only logarithmically with the total number of items.

Pages: 52 to 59

Copyright: Copyright (c) IARIA, 2017

Publication date: June 25, 2017

Published in: conference

ISSN: 2326-9332

ISBN: 978-1-61208-566-1

Location: Venice, Italy

Dates: from June 25, 2017 to June 29, 2017