Adaptive Task Assignment for Crowdsourced Classification

Chien-Ju Ho, Shahin Jabbari, Jennifer Wortman VaughanICML 2013 · OpenReview

Most crowdsourcing systems assign tasks randomly, relying on redundancy to filter out noise. However, this paper demonstrates that adaptive task assignment—dynamically matching specific workers to specific tasks—significantly reduces costs and errors, particularly when workers have diverse skills or tasks vary in difficulty. By leveraging online primal-dual optimization techniques, the authors develop an algorithm that learns worker skills on the fly, assigning tasks to minimize costs while guaranteeing a target accuracy.

The Crowdsourcing Challenge

Crowdsourcing platforms like Amazon Mechanical Turk are widely used to collect labels for machine learning (e.g., "Is this image a cat?"). However, workers are often noisy, careless, or even "spammers." The standard solution is redundancy: ask five people for the same label and take a majority vote.

The authors identify a major gap in this approach: most existing research assumes the requester has no control over who does which task. They argue that tasks are heterogeneous (some are harder than others) and workers are diverse (some are experts, others are not). Assigning a hard task to a low-skill worker wastes money. The core challenge is deciding in real-time, as workers arrive, which task to give them without knowing their skills in advance.

Optimization and Adaptive Methods

The authors frame task assignment as a constrained optimization problem: minimize the total number of assignments such that every task reaches a specific confidence threshold.

  1. The Optimization Framework: They start with an Integer Program (IP) for the "offline" version, where everyone's skills are known upfront. Because the real world operates "online" (workers arrive sequentially), they utilize a linear programming relaxation and its dual.
  2. Exploration vs. Exploitation: The algorithm operates in two phases:
  3. Exploration: A small portion of workers are given "gold standard" tasks (where the answer is known) to estimate their skill levels. These workers also help estimate "task weights" (dual variables) representing the effort each task requires.
  4. Exploitation: For the remaining workers, the algorithm uses the estimated task weights and worker skills to assign tasks that maximize the value of that worker's contribution.
  5. Online Primal-Dual: Adapting techniques from online ad-auctions, the assignment strategy updates dynamically. This allows the authors to prove a competitive ratio, meaning their online algorithm performs nearly as well as an "all-knowing" offline algorithm.

Key Insights and Empirical Results

The paper relies on synthetic datasets to rigorously test theoretical bounds, simulating populations with "spammers" (random guessers) and "hammers" (highly accurate workers), as well as scenarios with $k$ different types of specialized tasks.

The Power of the Dual: In their model, the dual variables act as a "price" or "weight" for a task. If a task is difficult or lacks sufficient labels, its weight increases, signaling the system to assign it to a high-skill worker.

Adaptivity Requires Diversity: A critical insight is that if all workers are identical and all tasks are equally difficult, adaptive assignment offers no benefit over random assignment. However, when specialized skills or varying difficulties are introduced, the adaptive approach drastically outperforms baselines.

Error rates comparing adaptive assignment vs. message-passing across uniform and diverse worker populations.

As shown above, the adaptive algorithm achieves significantly lower error rates for the same budget (total number of assignments) compared to the state-of-the-art message-passing algorithm when workers are diverse. When workers are uniform, the performance is nearly identical, confirming that diversity is the catalyst for adaptive gains.

Robustness to Task Types: In experiments with multiple task types ($k$), the adaptive algorithm proved highly resilient.

Error rates as the number of task types (k) increases, demonstrating the robustness of the adaptive algorithm compared to standard message-passing.

While the error rate of the non-adaptive message-passing baseline spiked significantly as the number of task types ($k$) increased from 1 to 3, the adaptive algorithm's error rate remained low and stable, efficiently matching specialized workers to their corresponding task types.

Limitations and Future Work

  • Gold Standard Reliance: The algorithm requires a set of "gold standard" tasks for each type to evaluate workers. In niche domains, creating these can be expensive.
  • Task Categorization: The model assumes tasks can be grouped into discrete types. In reality, task difficulty often exists on a continuous spectrum.
  • Worker Persistence: The model assumes workers are "one-and-done." Future work could explore settings where workers stay longer, allowing for sophisticated long-term skill tracking.
  • Pricing: The paper assumes every label costs the same amount. Extending this to cases where different workers charge different prices remains an open area for exploration.

Summary updated

Abstract

Crowdsourcing markets have gained popularity as a tool for inexpensively collecting data from diverse populations of workers. Classification tasks, in which workers provide labels (such as “offensi...
BibTeX
@inproceedings{ho2013adaptive,
  author = {Chien-Ju Ho and Shahin Jabbari and Jennifer Wortman Vaughan},
  title = {{Adaptive Task Assignment for Crowdsourced Classification}},
  booktitle = {International Conference on Machine Learning},
  year = {2013},
  url = {https://openreview.net/forum?id=rJ-eZ3W_-S},
}
Figure