Exact Exponent in Optimal Rates for Crowdsourcing

Abstract

In many machine learning applications, crowdsourcing has become the primary means for label collection. In this paper, we study the optimal error rate for aggregating labels provided by a set of non-expert workers. Under the classic Dawid-Skene model, we establish matching upper and lower bounds with an exact exponent $mI(\pi )$ in which $m$ is the number of workers and $I(\pi )$ the average Chernoff information that characterizes the workers' collective ability. Such an exact characterization of the error exponent allows us to state a precise sample size requirement $m>\frac{1}{I(\pi )}\log \frac{1}{\epsilon }$ in order to achieve an $\epsilon$ misclassification error. In addition, our results imply the optimality of various EM algorithms for crowdsourcing initialized by consistent estimators.

arXiv commentTo appear in the Proceedings of the 33rd International Conference on Machine Learning, New York, NY, USA, 2016

References in corpus (2)

• Ranking and combining multiple predictors without labeled data
• Minimax Optimal Convergence Rates for Estimating Ground Truth from Crowdsourced Labels

Cited by in corpus (8)

• Statistical and Computational Guarantees of Lloyd's Algorithm and its Variants
• A Permutation-based Model for Crowd Labeling: Optimal Estimation and Robustness
• Analysis of Minimax Error Rate for Crowdsourcing and Its Application to Worker Clustering Model
• Minimax Rates in Network Analysis: Graphon Estimation, Community Detection and Hypothesis Testing
• A Technical Survey on Statistical Modelling and Design Methods for Crowdsourcing Quality Control
• Breaking the $1/\sqrt{n}$ Barrier: Faster Rates for Permutation-based Models in Polynomial Time
• Towards Optimal Estimation of Bivariate Isotonic Matrices with Unknown Permutations
• A Symmetric Loss Perspective of Reliable Machine Learning