Crowdsourced Labeling for Worker-Task Specialization Block Model.

Doyeon Kim, Hye Won ChungarXiv 2020 · OpenReview

TL;DR

This paper tackles the challenge of accurately labeling data using crowdsourcing, specifically when workers have varying expertise (types) and tasks also belong to specific types. They introduce novel algorithms that efficiently infer true labels by intelligently clustering workers and weighting their responses, even without knowing worker/task types or their exact skill levels.

What Problem Does This Paper Address?

Crowdsourcing platforms are invaluable for generating large labeled datasets for tasks like image annotation. However, a key challenge is that not all workers are equally skilled, and their performance can vary depending on the task's nature. Traditional models often assume a uniform worker reliability or a simple error model (like the Dawid-Skene model), which doesn't capture the realistic scenario where workers specialize in certain types of tasks. This paper addresses this by focusing on a "d-type specialization model," where both workers and tasks have one of 'd' types, and workers are more accurate on tasks matching their type. The goal is to infer the true labels of tasks with high accuracy while minimizing the number of queries (i.e., how many times a task needs to be labeled by a worker).

Methods

The authors propose two main algorithms, both building upon a two-stage approach:

  1. Worker Clustering: The first stage involves grouping workers based on the similarity of their answers. This is crucial for identifying potential specialization groups.
  2. Label Inference: The second stage uses the clustered worker information to infer task labels.
  3. Algorithm 1 (Known Parameters): This algorithm assumes knowledge of the worker and task types, as well as the reliability parameters ($p$ for matched tasks, $q$ for unmatched tasks). It refines a previous approach by not discarding answers from "unmatched" clusters but instead weighting them appropriately. This leads to improved performance, especially when $q > 1/2$.
  4. Algorithm 2 (Unknown Parameters): This is the more significant contribution. It tackles the problem without prior knowledge of worker/task types or reliability parameters ($p, q$). It uses a sophisticated technique called Semidefinite Programming (SDP) for worker clustering. After clustering, it estimates the reliability parameters ($p, q$) from the data and then uses these estimates for weighted majority voting to infer task labels.

Datasets

Not discussed in the paper. The evaluation is performed through simulations with synthetic data generated according to the described d-type specialization model.

Key Insights and Ideas

  • Specialization Matters: The core idea is that worker reliability isn't uniform; it's task-dependent. Exploiting this specialization is key to efficient and accurate crowdsourcing.
  • Beyond Discarding: Unlike prior work that might discard answers from "mismatched" worker-task type clusters, the proposed algorithms intelligently weight these answers, extracting more value from the available data.
  • The Power of SDP for Clustering: Using Semidefinite Programming for worker clustering in Algorithm 2 is a novel approach that allows for robust grouping even without knowing the underlying reliability parameters.
  • Estimating Skills from Data: Algorithm 2 demonstrates that it's possible to learn worker reliability parameters ($p, q$) directly from the collected answers, making the system more practical.
  • Performance Gains: The proposed algorithms show significant improvements over simpler methods like majority voting and even a prior specialized algorithm, especially in scenarios where workers have some level of skill even on non-specialized tasks ($q > 1/2$).

Key Results

  • Algorithm 1: Achieves the best known performance for the d-type specialization model when reliability parameters ($p, q$) are known. It requires a number of queries per task that scales logarithmically with the inverse of the desired accuracy, with specific scaling depending on $q$.
  • Algorithm 2: Empirically demonstrates performance comparable to Algorithm 1, despite not requiring prior knowledge of reliability parameters or task/worker types. This makes it highly practical.
  • Outperformance: Both proposed algorithms significantly outperform traditional methods like majority voting and state-of-the-art algorithms designed for the simpler Dawid-Skene model, particularly when the worker-task specialization model is a good fit for the data.
  • Query Efficiency: The algorithms aim to minimize the total number of queries needed to achieve a target accuracy, offering a more cost-effective crowdsourcing solution.

Limitations and Future Work

  • Assumptions: The model assumes a fixed number of types ($d$) and that workers and tasks can be cleanly assigned to these types. Real-world scenarios might involve more nuanced or overlapping expertise.
  • Computational Complexity: While Algorithm 2 avoids prior knowledge, SDP can be computationally intensive. The paper mentions using approximate k-medoids clustering to mitigate this.
  • Future Work: The authors suggest exploring more complex worker models, dynamic task allocation, and investigating the impact of worker collusion or adversarial behavior. They also hint at extending the framework to non-binary labels.

Summary updated

Abstract

We consider crowdsourced labeling under a $d$-type worker-task specialization model, where each worker and task is associated with one particular type among a finite set of types and a worker provides a more reliable answer to tasks of the matched type than to tasks of unmatched types. We design an inference algorithm that recovers binary task labels (up to any given recovery accuracy) by using worker clustering, worker skill estimation and weighted majority voting. The designed inference algorithm does not require any information about worker/task types, and achieves any targeted recovery accuracy with the best known performance (minimum number of queries per task).
BibTeX
@misc{kim2020crowdsourced,
  author = {Doyeon Kim and Hye Won Chung},
  title = {{Crowdsourced Labeling for Worker-Task Specialization Block Model.}},
  year = {2020},
  eprint = {2004.00101},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2004.00101},
}
Figure