Budget-optimal Task Allocation for Reliable CrowdsourcingProfessor Sewoong Oh AbstractCrowdsourcing systems, like Amazon Mechanical Turk, provide platforms where large-scale projects are broken into small tasks that are electronically distributed to numerous on-demand contributors. Because these low-paid workers can be unreliable, we need to devise schemes to increase confidence in our answers, typically by assigning each task multiple times and combining the answers in some way. I will present a rigorous treatment of this problem, under a widely used probabilistic model known as the Dawid-Skene model. We provide both an order-optimal task assignment scheme (using a random graph) and an order-optimal inference algorithm (based on low-rank matrix approximation and belief propagation) for that task assignment. We show that out approach achieves performance close to the mini-max lower bound on what the best inference algorithm can achieve together with the best task-assignment scheme. To analyze our message-passing algorithm, we borrow techniques from coding theory known as density evolution, and give a precise description of the density (or distribution) of the messages. Our analysis technique provides a precise description of the empirical distribution of the entries of the top singular vector of sparse random matrices and might be of independent interest. This is joint work with David R. Karger (MIT), Devavrat Shah (MIT), and Prateek Jain (MSR,India). BiographySewoong Oh is an Assistant Professor of Industrial and Enterprise Systems Engineering at UIUC. His research interest is in understanding how to extract meaningful information from societal data, such as aggregating opinions on social computation platforms like Mechanical Turk, and recommendations and rank aggregations from comparisons. He finished his PhD at Stanford under the direction of Andrea Montanari in 2011, working in matrix completion problems. |