Efficient crowdsourcing for multi-class labeling

David R. Karger, Sewoong Oh, Devavrat Shah

Research output: Chapter in Book/Report/Conference proceedingConference contribution


Crowdsourcing systems like Amazon's Mechanical Turk have emerged as an effective large-scale human-powered platform for performing tasks in domains such as image classification, data entry, recommendation, and proofreading. Since workers are low-paid (a few cents per task) and tasks performed are monotonous, the answers obtained are noisy and hence unreliable. To obtain reliable estimates, it is essential to utilize appropriate inference algorithms (e.g. Majority voting) coupled with structured redundancy through task assignment. Our goal is to obtain the best possible trade-off between reliability and redundancy. In this paper, we consider a general probabilistic model for noisy observations for crowd-sourcing systems and pose the problem of minimizing the total price (i.e. redundancy) that must be paid to achieve a target overall reliability. Concretely, we show that it is possible to obtain an answer to each task correctly with probability 1 - ε as long as the redundancy per task is O((K/q) log(K/ε)), where each task can have any of the K distinct answers equally likely, q is the crowd-quality parameter that is defined through a probabilistic model. Further, effectively this is the best possible redundancy-accuracy trade-off any system design can achieve. Such a single-parameter crisp characterization of the (order-)optimal trade-off between redundancy and reliability has various useful operational consequences. Further, we analyze the robustness of our approach in the presence of adversarial workers and provide a bound on their influence on the redundancy-accuracy trade-off. Unlike recent prior work [13, 17, 19], our result applies to non-binary (i.e. K > 2) tasks. In effect, we utilize algorithms for binary tasks (with inhomogeneous error model unlike that in [13, 17, 19]) as key subroutine to obtain answers for K-ary tasks. Technically, the algorithm is based on low-rank approximation of weighted adjacency matrix for a random regular bipartite graph, weighted according to the answers provided by the workers.

Original languageEnglish (US)
Title of host publicationSIGMETRICS 2013 - Proceedings of the 2013 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems
Number of pages12
Edition1 SPEC. ISS.
StatePublished - 2013
Event2013 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems, SIGMETRICS 2013 - Pittsburgh, PA, United States
Duration: Jun 17 2013Jun 21 2013

Publication series

NamePerformance Evaluation Review
Number1 SPEC. ISS.
ISSN (Print)0163-5999


Other2013 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems, SIGMETRICS 2013
Country/TerritoryUnited States
CityPittsburgh, PA


  • Crowd-sourcing
  • Low-rank Matrices
  • Random Graphs

ASJC Scopus subject areas

  • Software
  • Hardware and Architecture
  • Computer Networks and Communications


Dive into the research topics of 'Efficient crowdsourcing for multi-class labeling'. Together they form a unique fingerprint.

Cite this