Error Rate Bounds in Crowdsourcing Models

• Activity Number: 301
• Type: Contributed
• Date/Time: Tuesday, August 5, 2014 : 8:30 AM to 10:20 AM
• Sponsor: Section on Statistical Learning and Data Mining
• Author(s): Hongwei Li*+ and Bin Yu and Dengyong Zhou
• Companies: University of California, Berkeley and University of California, Berkeley and Microsoft
• Keywords: crowdsourcing ; Noisy labels ; error rate bounds ; Maximum a posterior ; human computation ; weighted majority voting

Abstract

Crowdsourcing has become an effective and popular tool for human-powered computation on labeling large datasets. Since the workers can be unreliable, it is common in crowdsourcing to assign multiple workers to each task, and to aggregate the inputs of workers to yield results of higher quality. In this paper, we provide finite-sample exponential bounds on the error rate (in probability and in expectation) of general aggregation rules under the Dawid-Skene crowdsourcing model. Based on the bound results in this paper, we propose an iterative weighted majority voting method that optimizes the error rate bound and approximates the oracle Maximum A Posterior rule, and it has a provable theoretical guarantee on the error rate of its one step version. The iterative weighted majority voting method is intuitive and can be implemented with a few lines of Matlab code. Experimental results on simulated and real data show that the iterative weighted majority voting method performs at least on par with the state-of-the-art methods, and it has low computational cost (around one hundred times faster than the state-of-the-art methods).