Computer Science – Learning
Scientific paper
2011-10-17
Computer Science
Learning
27 pages, 2 figure, Added new results (section 2.4) on extensions of the optimality of our approach
Scientific paper
Crowdsourcing systems, in which numerous tasks are electronically distributed to numerous "information piece-workers", have emerged as an effective paradigm for human-powered solving of large scale problems in domains such as image classification, data entry, optical character recognition, recommendation, and proofreading. Because these low-paid workers can be unreliable, nearly all crowdsourcers must devise schemes to increase confidence in their answers, typically by assigning each task multiple times and combining the answers in some way such as majority voting. In this paper, we consider a general model of such crowdsourcing tasks and pose the problem of minimizing the total price (i.e., number of task assignments) that must be paid to achieve a target overall reliability. We give a new algorithm for deciding which tasks to assign to which workers and for inferring correct answers from the workers' answers. We show that our algorithm, inspired by belief propagation and low-rank matrix approximation, significantly outperforms majority voting and, in fact, is asymptotically optimal through comparison to an oracle that knows the reliability of every worker. We consider both a one-shot scenario in which all questions are asked and answered simultaneously and an iterative scenario in which one may choose to gather additional responses to certain questions adaptively based on the responses collected thus far. Perhaps surprisingly, we show that the minimum price that must be paid in order to achieve a certain reliability under both scenarios scale in the same manner, which implies that there is no significant gain in asking questions adaptively.
Karger David R.
Oh Sewoong
Shah Devavrat
No associations
LandOfFree
Budget-Optimal Task Allocation for Reliable Crowdsourcing Systems does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Budget-Optimal Task Allocation for Reliable Crowdsourcing Systems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Budget-Optimal Task Allocation for Reliable Crowdsourcing Systems will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-317202