Reliable Crowdsourcing under the Generalized Dawid-Skene Model

Ashish Khetan, Sewoong Oh

Abstract

Crowdsourcing platforms provide marketplaces where task requesters can pay to get labels on their data. Such markets have emerged recently as popular venues for collecting annotations that are crucial in training machine learning models in various applications. However, as jobs are tedious and payments are low, errors are common in such crowdsourced labels. A common strategy to overcome such noise in the answers is to add redundancy by getting multiple answers for each task and aggregating them using some methods such as majority voting. For such a system, there is a fundamental question of interest: how can we maximize the accuracy given a fixed budget on how many responses we can collect on the crowdsourcing system. We characterize this fundamental trade-off between the budget (how many answers the requester can collect in total) and the accuracy in the estimated labels. In particular, we ask whether adaptive task assignment schemes lead to a more efficient trade-off between the accuracy and the budget. Adaptive schemes, where tasks are assigned adaptively based on the data collected thus far, are widely used in practical crowdsourcing systems to efficiently use a given fixed budget. However, existing theoretical analyses of crowdsourcing systems suggest that the gain of adaptive task assignments is minimal. To bridge this gap, we investigate this question under a strictly more general probabilistic model, which has been recently introduced to model practical crowdsourced annotations. Under this generalized Dawid-Skene model, we characterize the fundamental trade-off between budget and accuracy. We introduce a novel adaptive scheme that matches this fundamental limit. We further quantify the fundamental gap between adaptive and non-adaptive schemes, by comparing the trade-off with the one for non-adaptive schemes. Our analyses confirm that the gap is significant.

Introduction

In crowdsourcing platforms like Amazon Mechanical Turk, requesters pay workers to label data. Because workers can be unreliable, requesters assign multiple workers to the same task and aggregate the answers to ensure quality. A major open question in this space is whether adaptive task assignment—assigning tasks to arriving workers based on the answers collected so far—is superior to non-adaptive assignment.

In practice, adaptive schemes work well. However, existing theoretical analyses based on the classic Dawid-Skene (DS) model suggested that adaptivity offers almost no benefit. This paper identifies the flaw in the old theory: the standard DS model assumes all tasks are equally difficult. If all tasks are equally hard, dynamically hunting for "hard" tasks is unnecessary. To bridge this gap, this paper analyzes a generalized Dawid-Skene model that explicitly allows tasks to have varying levels of difficulty, proving exactly how and why adaptivity saves money.

Notation and Framework

To analyze the fundamental limits of crowdsourcing, we establish a rigorous mathematical framework. The generalized model introduces parameters for task-specific difficulty and worker-specific reliability. The table below summarizes the key notation used throughout our analysis, including the critical difficulty parameters $\lambda$ (collective difficulty) and $\lambda_{min}$ (worst-case difficulty).

Summary of notation and data types used in the generalized Dawid-Skene model.

Methodology

We establish fundamental mathematical lower bounds (minimax rates) for both adaptive and non-adaptive schemes. To achieve the optimal adaptive bound, we propose a novel Adaptive Task Assignment and Inference Algorithm that operates in rounds:

  1. Initial Sampling: Assign a small number of workers to all tasks.
  2. Filtering: Use a spectral message-passing algorithm (based on the non-backtracking operator) to estimate true labels and calculate confidence scores.
  3. Iterative Refinement: Tasks crossing a confidence threshold are permanently classified. The remaining, more ambiguous tasks are carried over to the next round with a higher worker budget.

For scenarios where the budget is critically small (below the "spectral barrier"), we also propose an alternative inference algorithm based on alternating minimization to reliably extract labels.

Key Results and Insights

Our analysis reveals that the bottleneck of non-adaptive schemes is that the overall error rate is dominated by the hardest tasks. Requesters are forced to over-spend on easy tasks just to ensure hard tasks get enough coverage.

The Mathematical Gain of Adaptivity

The budget required for a non-adaptive scheme scales with the worst-case task difficulty ($\lambda_{min}$). In contrast, the budget for an adaptive scheme scales with the collective average task difficulty ($\lambda$). The theoretical gain of using an adaptive scheme over a non-adaptive one is exactly the factor of $\lambda / \lambda_{min}$.

  • Fundamental Limits: To achieve an error rate of $\varepsilon$, the optimal adaptive scheme requires a budget scaling as $\Theta((m/\lambda\sigma^2) \log(1/\varepsilon))$, while non-adaptive schemes require $\Theta((m/\lambda_{min}\sigma^2) \log(1/\varepsilon))$.
  • Empirical Validation: In synthetic experiments, the adaptive scheme required significantly fewer queries. For example, to hit a 0.002 error rate, the adaptive scheme required ~157 queries per task, while the non-adaptive version required 360 queries—matching the theoretical prediction.

Conclusion and Future Work

This work proves that adaptivity provides significant budget savings when accounting for varying task difficulty. While the current analysis relies on asymptotic assumptions (large $m$), future work will focus on proving sharp bounds for finite regimes and analyzing how estimation errors might accumulate across rounds. Extending these trade-off analyses to other complex crowdsourcing models, such as permutation-based models, remains an open challenge.

Summary updated

Abstract

Crowdsourcing platforms provide marketplaces where task requesters can pay to get labels on their data. Such markets have emerged recently as popular venues for collecting annotations that are crucial in training machine learning models in various applications. However, as jobs are tedious and payments are low, errors are common in such crowdsourced labels. A common strategy to overcome such noise in the answers is to add redundancy by getting multiple answers for each task and aggregating them using some methods such as majority voting. For such a system, there is a fundamental question of interest: how can we maximize the accuracy given a fixed budget on how many responses we can collect on the crowdsourcing system. We characterize this fundamental trade-off between the budget (how many answers the requester can collect in total) and the accuracy in the estimated labels. In particular, we ask whether adaptive task assignment schemes lead to a more efficient trade-off between the accuracy and the budget. Adaptive schemes, where tasks are assigned adaptively based on the data collected thus far, are widely used in practical crowdsourcing systems to efficiently use a given fixed budget. However, existing theoretical analyses of crowdsourcing systems suggest that the gain of adaptive task assignments is minimal. To bridge this gap, we investigate this question under a strictly more general probabilistic model, which has been recently introduced to model practical crowdsourced annotations. Under this generalized Dawid-Skene model, we characterize the fundamental trade-off between budget and accuracy. We introduce a novel adaptive scheme that matches this fundamental limit. We further quantify the fundamental gap between adaptive and non-adaptive schemes, by comparing the trade-off with the one for non-adaptive schemes. Our analyses confirm that the gap is significant.
BibTeX
@inproceedings{khetan2016reliable,
  author = {Ashish Khetan and Sewoong Oh},
  title = {{Reliable Crowdsourcing under the Generalized Dawid-Skene Model}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2016},
  url = {https://openreview.net/forum?id=ByW5Dw-_-H},
}
Figure