Big data acquisition by crowdsourcing: fundamental limits and efficient algorithms

Abstract

Today, it is crucial to collect accurate and large labeled data for artificial intelligence or machine learning algorithms to train their models. Crowdsourcing system has emerged as an effective platform to acquire labeled data with relatively low cost by using non-expert workers, because one can access to this system anytime anywhere. Although the way of crowdsourced data collection has become ubiquitous, this way can have a problem because workers who provide answers through crowdsourcing may not give accurate answers for various reasons. Therefore, it is common to infer the correct label from many answers provided by workers. However, inferring correct labels from multiple noisy answers on data has been a challenging problem, since the quality of answers varies widely across tasks and workers. Many previous works have assumed a simple model where the order of workers in terms of their reliabilities is fixed across tasks, and focused on estimating the worker reliabilities to aggregate answers with different weights. We propose a highly general $d$-type worker-task specialization model in which the reliability of each worker can change depending on the type of a given task, where the number $d$ of types can scale in the number of tasks. In this model, we characterize the optimal sample complexity to correctly infer labels with any given accuracy, and propose an algorithm achieving the optimal result under some assumptions. We also conduct experiments both on synthetic and real datasets, and show that our algorithm outperforms the existing algorithms developed based on strict model assumptions. Finally, we conclude this dissertation by presenting a direction of future work that can be studied later.