Sewoong Oh (University of Illinois at Urbana-Champaign): Budget-Optimal Task-Allocation for Reliable Crowdsourcing Systems
Speaker Sewoong Oh, University of Illinois at Urbana-Champaign
Date Sep 27, 2012
Time 4:00 pm – 5:00 pm
Location 156 Henry
Sponsor Statistics Department
Event type Seminar
This talk is on my ongoing research on designing reliable and cost-efficient crowdsourcing systems. Crowdsourcing is a novel paradigm for solving large scale problems by breaking them down into small tasks that are electronically distributed to numerous on-demand human contributors. In typical crowdsourcing, these tasks are submitted to an electronic labor market and completed by any worker choosing to pick it up for a small reward. However, since typical crowdsourced tasks are tedious and the reward is small, errors are common even among those who make an effort. Thus, all taskmasters need to devise schemes to increase confidence in their answers. A common approach is to assign each task multiple times and combining the answers in some way such as majority voting. For such systems, there is a fundamental problem of interest: how can we achieve a certain reliability in our answers at minimum cost? Under a general model, we provide an optimal algorithm based on low-rank matrix approximation and belief propagation. We prove that our approach signiﬁcantly outperforms majority voting and, in fact, is asymptotically order-optimal through comparison to an oracle that knows the reliability of every worker. We also provide experimental results on synthetic and real datasets that support the optimality of our approach.