Department of Statistics Weekly Seminar

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 significantly 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.