A Minimax Optimal Algorithm for Crowdsourcing

Abstract

We consider the problem of accurately estimating the reliability of workers based on noisy labels they provide, which is a fundamental question in crowdsourcing. We propose a novel lower bound on the minimax estimation error which applies to any estimation procedure. We further propose Triangular Estimation (TE), an algorithm for estimating the reliability of workers. TE has low complexity, may be implemented in a streaming setting when labels are provided by workers in real time, and does not rely on an iterative procedure. We further prove that TE is minimax optimal and matches our lower bound. We conclude by assessing the performance of TE and other state-of-the-art algorithms on both synthetic and real-world data sets.

19 pages, NIPS 2017

Cited by in corpus (12)

• Variational Inference based on Robust Divergences
• Blind Multiclass Ensemble Classification
• Auxiliary-task Based Deep Reinforcement Learning for Participant Selection Problem in Mobile Crowdsourcing
• Analysis of Minimax Error Rate for Crowdsourcing and Its Application to Worker Clustering Model
• Crowd-Powered Data Mining
• NIPS - Not Even Wrong? A Systematic Review of Empirically Complete Demonstrations of Algorithmic Effectiveness in the Machine Learning and Artificial Intelligence Literature
• A Technical Survey on Statistical Modelling and Design Methods for Crowdsourcing Quality Control
• Online Algorithm for Unsupervised Sequential Selection with Contextual Information
• Streaming Bayesian Inference for Crowdsourced Classification
• Online Algorithm for Unsupervised Sensor Selection
• Modelling Instance-Level Annotator Reliability for Natural Language Labelling Tasks
• Thompson Sampling for Unsupervised Sequential Selection