Cost-Saving Effect of Crowdsourcing Learning

Lu Wang, Zhi-Hua Zhou

Abstract

Crowdsourcing offers a cost-effective alternative to expert labeling for machine learning, yet the inherent noise of non-expert workers poses a significant challenge. This paper establishes a theoretical foundation for determining the "minimally-sufficient" number of crowd labels required for effective model training. By analyzing the trade-off between label quantity (number of instances) and label quality (repeated labeling per instance), the authors identify an optimal error rate "sweet spot" and provide an upper bound for total labeling costs within the Probably Approximately Correct (PAC) learning framework. Empirical results on real-world datasets validate these theoretical findings, demonstrating how the optimal allocation of a labeling budget depends critically on worker qualification.

Introduction

In machine learning, crowdsourcing platforms like Amazon Mechanical Turk are frequently used to label large datasets due to their low cost relative to domain experts. However, crowd workers are often less accurate. To mitigate this, researchers typically collect multiple labels for the same instance and aggregate them (e.g., via majority voting) to approximate a ground-truth label. This creates a fundamental resource allocation dilemma: given a fixed budget, should one prioritize quantity (many unique instances labeled once) or quality (fewer instances labeled many times)? This paper addresses the lack of a theoretical framework to determine the minimum cost required to achieve a specific level of model performance.

Methodology

The authors integrate classical learning theory with crowd-noise modeling to optimize resource allocation:

  • Aggregation Strategy: A simple Majority Voting strategy is assumed to induce an aggregated label from multiple crowd labels.
  • Noise Modeling: Worker ability is modeled by a qualification parameter $p$ (probability of a correct label). Using the Central Limit Theorem and Hoeffding’s inequality, the authors bound the error rate ($\eta$) of the aggregated label based on the number of labels per instance ($n$).
  • PAC Learning Framework: The study builds upon the work of Angluin and Laird regarding learning from noisy oracles to define the total number of crowd labels ($m'$) required for successful learning.
  • Optimization: Theorem 1 defines the total cost function. By treating the error rate of the aggregated label as a variable, the authors identify the value that minimizes the total labeling expenditure.

Theoretical Insights

The Minimally-Sufficient Number

The paper defines the minimum number of total crowd labels needed to guarantee a model is "probably approximately correct." This provides a theoretical floor for the cost of crowdsourcing. As shown in the scaling analysis, the required number of labels per instance ($n_{cr}$) to reach a target error rate increases dramatically as worker qualification ($p$) nears random guessing (0.5).

The critical number of labels ($n_{cr}$) required to reach a target error rate ($\eta^*$) for different worker qualifications ($p$).

The Noise Sweet Spot

A key discovery is the identification of a theoretical "sweet spot": total cost is minimized when the error rate of the aggregated labels ($\eta$) is approximately 0.084. If aggregated labels are noisier than this, the budget should be shifted toward increasing labels per instance. If they are cleaner, the budget is better spent on labeling more unique instances to improve the model's generalization.

Empirical Validation

The authors validated their theory using the Mushrooms (8,124 instances) and Splice (3,175 instances) datasets from the LIBSVM repository. Crowd labels were simulated by flipping ground-truth labels based on the qualification parameter $p$.

Testing accuracy vs. number of labels per instance for different worker qualifications ($p$) on Mushrooms and Splice datasets.

Key Results

  • High Qualification ($p=0.9$): When workers are highly skilled, labeling an instance multiple times is redundant. The highest accuracy is achieved by labeling as many unique instances as possible.
  • Low Qualification ($p=0.6$ or $0.65$): When workers are less skilled, models fail to learn effectively with only one label per instance. In these scenarios, repeated labeling is essential to improve data quality enough for the learning algorithm to succeed.
  • Budget Efficiency: With a fixed budget, the optimal allocation strategy (labels per instance) shifts significantly based on worker accuracy, confirming that "cost-saving" is highly sensitive to the crowd's skill level.

Limitations and Future Work

While providing a robust foundation, the study focuses on Majority Voting and binary classification. Future research could extend these bounds to more complex aggregation methods (e.g., worker reliability estimation), multi-class problems, and agnostic learning scenarios where the "true" function may not exist within the hypothesis class. Additionally, modeling heterogeneous worker qualifications would bring the theory closer to real-world crowd dynamics.

Summary updated

Abstract

Crowdsourcing is widely adopted in many domains as a popular paradigm to outsource work to individuals. In the machine learning community, crowdsourcing is commonly used as a cost-saving way to collect labels for training data. While a lot of effort has been spent on developing methods for inferring labels from a crowd, few work concentrates on the theoretical foundation of crowdsourcing learning. In this paper, we theoretically study the cost-saving effect of crowdsourcing learning, and present an upper bound for the minimally-sufficient number of crowd labels for effective crowdsourcing learning. Our results provide an understanding about how to allocate crowd labels efficiently, and are verified empirically.
BibTeX
@inproceedings{wang2016cost,
  author = {Lu Wang and Zhi-Hua Zhou},
  title = {{Cost-Saving Effect of Crowdsourcing Learning}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2016},
}
Figure