Poster
Crowdsourcing via Pairwise Co-occurrences: Identifiability and Algorithms
Shahana Ibrahim · Xiao Fu · Nikolaos Kargas · Kejun Huang

Wed Dec 11th 05:00 -- 07:00 PM @ East Exhibition Hall B + C #95

The data deluge comes with high demands for data labeling. Crowdsourcing (or, more generally, ensemble learning) techniques aim to produce accurate labels via integrating noisy, non-expert labeling from annotators. The classic Dawid-Skene estimator and its accompanying expectation maximization (EM) algorithm have been widely used, but the theoretical properties are not fully understood. Tensor methods were proposed to guarantee identification of the Dawid-Skene model, but the sample complexity is a hurdle for applying such approaches---since the tensor methods hinge on the availability of third-order statistics that are hard to reliably estimate given limited data. In this paper, we propose a framework using pairwise co-occurrences of the annotator responses, which naturally admits lower sample complexity. We show that the approach can identify the Dawid-Skene model under realistic conditions. We propose an algebraic algorithm reminiscent of convex geometry-based structured matrix factorization to solve the model identification problem efficiently, and an identifiability-enhanced algorithm for handling more challenging and critical scenarios. Experiments show that the proposed algorithms outperform the state-of-art algorithms under a variety of scenarios.

Author Information

Shahana Ibrahim (Oregon State University)
Xiao Fu (Oregon State University)
Nikolaos Kargas (University of Minnesota)
Kejun Huang (University of Florida)