Spectral Methods meet EM: A Provably Optimal Algorithm for Crowdsourcing

Abstract

Crowdsourcing is a popular paradigm for effectively collecting labels at low cost. The Dawid-Skene estimator has been widely used for inferring the true labels from the noisy labels provided by non-expert crowdsourcing workers. However, since the estimator maximizes a non-convex log-likelihood function, it is hard to theoretically justify its performance. In this paper, we propose a two-stage efficient algorithm for multi-class crowd labeling problems. The first stage uses the spectral method to obtain an initial estimate of parameters. Then the second stage refines the estimation by optimizing the objective function of the Dawid-Skene estimator via the EM algorithm. We show that our algorithm achieves the optimal convergence rate up to a logarithmic factor. We conduct extensive experiments on synthetic and real datasets. Experimental results demonstrate that the proposed algorithm is comparable to the most accurate empirical approach, while outperforming several other recently proposed methods.

References in corpus (5)

• A Spectral Algorithm for Latent Dirichlet Allocation
• Ranking and combining multiple predictors without labeled data
• Minimax Optimal Convergence Rates for Estimating Ground Truth from Crowdsourced Labels
• Spectral Experts for Estimating Mixtures of Linear Regressions
• Learning Mixtures of Discrete Product Distributions using Spectral Decompositions

Cited by in corpus (16)

• Snorkel: Rapid Training Data Creation with Weak Supervision
• Data Programming: Creating Large Training Sets, Quickly
• Gradient Descent Only Converges to Minimizers: Non-Isolated Critical Points and Invariant Regions
• Blind Multiclass Ensemble Classification
• Transfer Learning for Nonparametric Classification: Minimax Rate and Adaptive Classifier
• Optimal Deterministic Algorithm Generation
• A Tensor-EM Method for Large-Scale Latent Class Analysis with Binary Responses
• Interactive Weak Supervision: Learning Useful Heuristics for Data Labeling
• A Worker-Task Specialization Model for Crowdsourcing: Efficient Inference and Fundamental Limits
• Variational Bayesian Inference for Crowdsourcing Predictions
• Machine Truth Serum
• Crowdsourced Labeling for Worker-Task Specialization Model
• Crowdsourcing Utilizing Subgroup Structure of Latent Factor Modeling
• Truth Inference at Scale: A Bayesian Model for Adjudicating Highly Redundant Crowd Annotations
• Binary Classification with XOR Queries: Fundamental Limits and An Efficient Algorithm
• Optimal Clustering from Noisy Binary Feedback