Efficient Techniques for Crowdsourced Top-k Lists

Luca de Alfaro, Vassilis Polychronopoulos, Neoklis PolyzotisIJCAI 2017 · DOI

TL;DR

This paper introduces Crowd-Top-k, a novel recursive algorithm for efficiently obtaining top-k lists from large itemsets using crowdsourcing. It addresses the challenges of worker inaccuracy and adversarial behavior by proposing a budgeting strategy and a randomized variant that significantly reduces costs with minimal risk to result quality.

What Problem Does This Paper Address?

Imagine you have a massive collection of items – say, thousands of college applications – and you need to select the top k best ones. Doing this manually is infeasible, and traditional automated methods struggle with the scale and the inherent unreliability of human judgment when crowdsourcing. This paper tackles the problem of efficiently and accurately retrieving these top-k lists from large itemsets by leveraging human workers for comparisons, while mitigating issues like worker errors, random spamming, and even malicious adversarial behavior. Existing approaches often have high latency, are inefficient with resources, or make unrealistic assumptions about worker accuracy.

Methods

The core of the paper is the Crowd-Top-k algorithm, a recursive approach that decouples the size of the top-k list from the size of the ranking tasks given to humans. Here's how it works:

  • Recursive Reduction: The algorithm partitions the large itemset into smaller subsets. Human workers rank items within these subsets. The algorithm then takes the "best" item from each subset (the maximum) to form a new, smaller itemset. This process repeats recursively.
  • Endgame Phase: When the itemset becomes small enough (less than ks items), the algorithm enters an "endgame" phase. Here, it uses specialized algorithms (like human-powered sorts or unbalanced rank estimation) to determine the final top-k list for this small set.
  • Handling Inaccuracy: To combat honest mistakes and random spamming, the paper uses median rank aggregation and an adaptive task allocation method.
  • Budgeting Strategy: A key innovation is a budgeting strategy designed to combat adversarial spammers. This strategy optimizes the allocation of ranking tasks across the recursive calls to minimize the impact of malicious workers.
  • Randomized Variant: The authors propose a randomized variant of Crowd-Top-k. This variant introduces a controlled risk of losing items from the top-k list due to randomization, but in return, it can drastically reduce the budget required, especially for very large itemsets and top-k lists.

Datasets

The paper does not introduce new datasets. Instead, it uses simulations and experiments on Amazon Mechanical Turk. For the Mechanical Turk experiments, they used sets of polygons with varying levels of difficulty (easy, medium, hard) to test the ranking of items based on their size.

Key Insights and Ideas

  • Recursive Decoupling is Key: The recursive nature of Crowd-Top-k is crucial for handling arbitrarily large itemsets and top-k lists, a significant improvement over methods that are tied to the size of individual ranking tasks.
  • Budgeting for Adversaries: The budgeting strategy is a clever way to proactively defend against adversarial workers, transforming a potential weakness into a manageable challenge.
  • The Power of Controlled Risk: The randomized variant demonstrates that accepting a small, controlled risk can lead to substantial cost savings without significantly compromising the quality of the final top-k list. This is a powerful trade-off for practical crowdsourcing applications.
  • Logarithmic Latency: The algorithm achieves logarithmic latency in terms of recursive calls, making it highly scalable for large datasets.

Key Results

  • Efficiency Gains: The randomized Crowd-Top-k algorithm achieved budget savings of up to 57% for a very low risk threshold (3 x 10^-4) with no noticeable change in quality.
  • Superiority over Prior Art: Simulations showed Crowd-Top-k outperforming traditional tournament approaches and methods like Feige et al. (1994) and Davidson et al. (2013) in terms of latency and quality, especially for large top-k lists.
  • Robustness: Experiments demonstrated the techniques' tolerance to errors and vandalism.
  • Mechanical Turk Performance: On Amazon Mechanical Turk, Crowd-Top-k showed comparable quality to other methods but with significantly lower latency (72 minutes vs. 508 minutes for Davidson et al.).

Limitations and Future Work

  • Adversarial Model: While the budgeting strategy addresses adversarial behavior, the paper acknowledges that the effectiveness might depend on the specific assumptions made about the nature and prevalence of these adversaries.
  • Endgame Algorithm Choice: The Crowd-Top-k algorithm is generic with respect to the endgame method. The paper explored several options, but further research could investigate optimal endgame strategies for different scenarios.
  • Risk Threshold Tuning: The randomized variant requires users to set a risk threshold. Determining the optimal threshold for different applications and risk appetites could be a direction for future work.

Summary updated

BibTeX
@inproceedings{alfaro2017efficient,
  author = {Luca de Alfaro and Vassilis Polychronopoulos and Neoklis Polyzotis},
  title = {{Efficient Techniques for Crowdsourced Top-k Lists}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2017},
  doi = {10.24963/ijcai.2017/670},
}
Figure