Spectral Methods Meet EM: A Provably Optimal Algorithm for Crowdsourcing

By Yuchen Zhang, Xi Chen, Dengyong Zhou, Michael I. Jordan. 2014

406 citations recorded by the source corpus.

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.

Subfields: Civil and Structural Engineering, Computer Science Applications, Electrical and Electronic Engineering, Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Civil and Structural Engineering

In Computer Science Applications

In Electrical and Electronic Engineering

In Optimization & Training

Citations in the corpus

Snorkel: Rapid Training Data Creation with Weak Supervision (2017, background): “Much of this work has focused on crowdsourcing, in which workers have unknown accuracy [11, 23, 53].”
Concrete Problems in AI Safety (2016, background): “As in [145], one can approach unsupervised risk estimation by positing certain conditional independencies in the distribution of errors, and using this to estimate the error distribution from unlabeled data [38, 165, 119, 72].”
Data Programming: Creating Large Training Sets, Quickly (2016, background): “More recent results provide formal guarantees even in the absence of labeled data using various approaches [3,8,14,15,22,31].”
The Role of Massively Multi-Task and Weak Supervision in Software 2.0 (2019, background): “…to weak supervision, we build on the paradigm introduced in the Snorkel system [27, 29], and extended thereafter [3, 12, 32, 40, 41]; for a more comprehensive review of prior and related weak super-vision work, such as distant supervision [1, 15, 23] and crowdsourcing [4, 8, 9, 18, 45], see [27].”
Estimating the accuracies of multiple classifiers without labeled data (2014, methodology): “This motivates the development of tensor or higher order methods to solve the multi-class case, as for example in Zhang et al. [2014]. In Sec.”
Learning From Noisy Singly-labeled Data (2017, methodology): “EM converges to the true confusion matrices and the true labels given an appropriate spectral initialization of worker confusion matrices (Zhang et al., 2014).”
Gradient Descent Only Converges to Minimizers: Non-Isolated Critical Points and Invariant Regions (2016, background): “dictionary learning [1], latent-variable models [28], matrix completion [9], and phase retrieval [2]).”
Interactive Weak Supervision: Learning Useful Heuristics for Data Labeling (2020, background): “…(Ratner et al., 2016) combines multiple weak supervision sources by using an unsupervised label model to estimate the latent true class label, an idea that has close connections to modeling workers in crowd-sourcing (Dawid & Skene, 1979; Karger et al., 2011; Dalvi et al., 2013; Zhang et al., 2014).”
Snuba: Automating Weak Supervision to Label Training Data (2018, background): “Combining labels from multiple sources like heuristics is well-studied problem [11], especially in the context of crowdsourcing [9, 23, 61].”
Gradient Descent Converges to Minimizers (2016, background): “More broadly, many recent works have shown that gradient des cent plus smart initializations provably converges to the global minimum for a variety of non-convex p roblems: such settings include matrix factorization [16, 30], phase retrieval [9, 8], dictionary lea rning [3], and latent-variable mode”
Efficient Learning for Crowdsourced Regression (2017, background): “…a variety of real-world tasks ranging from classification Sheng et al. (2008) and regression Marcus et al. (2012) to more complex tasks such as protein folding Peng et al. (2013), searching videos Bernstein et al. (2011), ranking Lee et al. (2012) and natural language processing Wu et al. (2012).”
Facial Expression Recognition with Inconsistently Annotated Datasets (2018, methodology): “65 inconsistent annotations EM+CNN(spectral init.[32]) 78.”
Learning the Structure of Generative Models without Labeled Data (2017, methodology): “ch to estimating the accuracy of members of classiﬁer ensembles. Many methods for crowdsourcing estimate the accuracy of workers without hand-labeled data (e.g.,Dalvi et al.,2013;Joglekar et al.,2015;Zhang et al., 2016). In data programming, the scaling of data to label sources is different from cro”
Training Complex Models with Multi-Task Weak Supervision (2018, methodology): “, (Dalvi et al. 2013b; Zhang et al. 2014; Dawid and Skene 1979), it suffices to make the assumption that the sources are on average non-adversarial; i.”
Tensor Factorization via Matrix Factorization (2015, unknown): “We incorporate our tensor factorization algorithms within the estimator and evaluate the approach on the same datasets as [17] except one, which we could not obtain.”
Snorkel: rapid training data creation with weak supervision (2019, background): “Much of this work has focused on crowdsourcing, in which workers have unknown accuracy [11, 23, 53].”
Socratic Learning: Augmenting Generative Models to Incorporate Latent Subsets in Training Data (2016, background): “Estimating the accuracies of these sources without access to ground truth labels is a classic problem [9], especially in the ﬁeld of crowdsourcing [10, 7, 14, 33].”
SLiMFast: Guaranteed Results for Data Fusion and Source Reliability (2015, background): “(6)While we do not obtain a bound for object values, previous work [16, 42] has shown that under strong generative assumptions such a bound can be obtained.”
Unsupervised Risk Estimation with only Structural Assumptions (2016, methodology): “…et al. (2011) assume Gaussianity of model scores, while a line of work starting with Dawid & Skene (1979) assume multiple classifiers with known dependency structure, which specifies a complete generative distribution for the 0/1-loss (Zhang et al., 2014; Platanios, 2015; Jaffe et al., 2015).”
On Bayes Risk Lower Bounds (2014, background): “Unfortunately, it is diﬃcult, in most problems, to determine the minimax risk exactly.”