Crowdsourcing via Tensor Augmentation and Completion

Yao Zhou, Jingrui He

Introduction

Crowdsourcing platforms like Amazon Mechanical Turk have revolutionized data collection by allowing researchers to gather large volumes of labeled data at a low cost. However, the reliance on non-expert workers introduces a significant challenge: noise. Labels are often inconsistent, and determining the "ground truth" from conflicting reports is a non-trivial task. Traditional approaches, such as Majority Voting, assume uniform worker reliability, which is rarely the case in practice. More sophisticated probabilistic models, like the Dawid-Skene Expectation-Maximization (EM) algorithm, estimate worker quality but often fail to capture the complex, multi-dimensional interactions between specific workers, items, and classes.

This paper proposes a shift from purely statistical inference to a structured data recovery perspective. By representing crowdsourced data as a 3D tensor and leveraging low-rank completion techniques, the authors introduce a framework that exploits the inherent structural patterns in labeling behavior.

The TAC Framework

The core of the proposed approach is Tensor Augmentation and Completion (TAC). The input data is structured into a 3D tensor $\mathcal{T}$ with dimensions representing Workers, Items, and Classes. A specific cell $(i, j, k)$ is marked if Worker $i$ assigns Item $j$ to Class $k$.

The innovation lies in tensor augmentation: adding a "Ground Truth Layer" to the worker dimension. This layer acts as a proxy for a hypothetical perfect worker. By assuming that the augmented tensor is low-rank—reflecting the fact that worker errors and item difficulties follow predictable patterns—the problem of finding the true labels is transformed into a tensor completion task.

Two primary formulations are introduced:

  • PG-TAC (Prior Guided): Incorporates statistical priors (e.g., initial estimates from simpler models) to guide the recovery process.
  • RS-TAC (Relaxed Simplex): Imposes a simplex constraint on the ground truth layer, ensuring class probabilities for each item sum to approximately one, which provides robustness against overfitting in complex scenarios.

These optimization problems are solved using Block Coordinate Descent (BCD), an iterative algorithm that ensures convergence to a stable solution.

Experimental Evaluation

The authors evaluated TAC against state-of-the-art methods using both synthetic data and six real-world datasets, ranging from binary classification (e.g., RTE, Spam) to multi-class tasks (e.g., Web, Dog, Age).

Performance trends of TAC variants across different synthetic configurations, showing error rates relative to the number of workers, classes, items, and label sparsity.

Key Results

The experimental results demonstrate that PG-TAC consistently outperforms traditional methods like DS-EM and MMCE. For instance, on the Web dataset, PG-TAC reduced the error rate to 10.82%, compared to 16.92% for DS-EM and 26.93% for Majority Voting. On more challenging tasks like the Age dataset, which features seven classes and unbalanced distributions, RS-TAC proved most effective with an error rate of 31.14%.

Synthetic experiments (shown in the figure above) highlight several critical trends:

  • Scalability: As the number of workers ($N_w$) increases, the performance gap between TAC and baseline methods widens, indicating superior scalability.
  • Complexity Handling: While error rates naturally rise with the number of classes ($N_c$), TAC maintains a competitive edge.
  • Robustness to Sparsity: The model remains accurate even when a large portion of labels are missing (high probability $q$ of no labels), thanks to the low-rank completion mechanism.

Discussion and Future Work

The tensor-based approach effectively captures the "geometry" of crowdsourced data, treating worker errors as structured information rather than random noise. By using the "perfect worker" proxy, the authors successfully adapt powerful matrix and tensor completion techniques to the crowdsourcing domain.

Despite its strengths, the method has limitations. It is sensitive to initialization, often requiring a starting point from algorithms like DS-EM. Additionally, the computational cost of Singular Value Decomposition (SVD) in tensor completion is higher than simpler voting methods. Future research could focus on integrating item features (e.g., image or text data) directly into the tensor or exploring more efficient decomposition techniques to handle massive-scale datasets.

Summary updated

Abstract

Nowadays, the rapid proliferation of data makes it possible to build complex models for many real applications. Such models, however, usually require large amount of labeled data, and the labeling process can be both expensive and tedious for domain experts. To address this problem, researchers have resorted to crowdsourcing to collect labels from non-experts with much less cost. The key challenge here is how to infer the true labels from the large number of noisy labels provided by non-experts. Different from most existing work on crowdsourcing, which ignore the structure information in the labeling data provided by non-experts, in this paper, we propose a novel structured approach based on tensor augmentation and completion. It uses tensor representation for the labeled data, augments it with a ground truth layer, and explores two methods to estimate the ground truth layer via low rank tensor completion. Experimental results on 6 real data sets demonstrate the superior performance of the proposed approach over state-of-the-art techniques.
BibTeX
@inproceedings{zhou2016crowdsourcing,
  author = {Yao Zhou and Jingrui He},
  title = {{Crowdsourcing via Tensor Augmentation and Completion}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2016},
}
Figure