Crowdsourcing via Pairwise Co-occurrences: Identifiability and Algorithms
arXiv:1909.12325
Abstract
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.
28 pages, 5 figures, to appear in 33rd NeurIPS conference, Vancouver, Canada
Cited by in corpus (9)
- Recovering Joint Probability of Discrete Random Variables from Pairwise Marginals
- Stochastic Mirror Descent for Low-Rank Tensor Decomposition Under Non-Euclidean Losses
- Probabilistic Simplex Component Analysis
- Adversarial Crowdsourcing Through Robust Rank-One Matrix Completion
- Memory-Efficient Convex Optimization for Self-Dictionary Separable Nonnegative Matrix Factorization: A Frank-Wolfe Approach
- Identifiability-Guaranteed Simplex-Structured Post-Nonlinear Mixture Learning via Autoencoder
- Mixed Membership Graph Clustering via Systematic Edge Query
- Crowdsourcing Utilizing Subgroup Structure of Latent Factor Modeling
- Crowdsourcing via Annotator Co-occurrence Imputation and Provable Symmetric Nonnegative Matrix Factorization