Aggregating crowdsourced binary ratings

By Nilesh N. Dalvi, Anirban Dasgupta, Ravi Kumar, Vibhor Rastogi. 2013

207 citations recorded by the source corpus.

In this paper we analyze a crowdsourcing system consisting of a set of users and a set of binary choice questions. Each user has an unknown, fixed, reliability that determines the user's error rate in answering questions. The problem is to determine the truth values of the questions solely based on the user answers. Although this problem has been studied extensively, theoretical error bounds have been shown only for restricted settings: when the graph between users and questions is either random or complete. In this paper we consider a general setting of the problem where the user--question graph can be arbitrary. We obtain bounds on the error rate of our algorithm and show it is governed by the expansion of the graph. We demonstrate, using several synthetic and real datasets, that our algorithm outperforms the state of the art.

Subfields: Artificial Intelligence, Computer Science Applications, Electrical and Electronic Engineering, Evaluation & Benchmarks

How researchers see this paper

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

In Artificial Intelligence

In Computer Science Applications

In Electrical and Electronic Engineering

In Evaluation & Benchmarks

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].”
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].”
A Survey on Programmatic Weak Supervision (2022, methodology): “Crowdsourcing models [Dawid and Skene, 1979; Dalvi et al. , 2013; Raykar et al. , 2010; Khetan et al. , 2018] usually leverage the expectation maximization (EM) algo-rithm to estimate the accuracy of each worker as well as infer the latent ground truth labels, which can also be applied here when we…”
Efficient Learning for Crowdsourced Regression (2017, methodology): “We propose a simple assignment scheme, referred to as (`, r)-regular task assignment, popularly adopted in crowdsourcing Dalvi et al. (2013); Liu et al. (2012); Karger et al. (2011, 2013, 2014); Ok et al. (2016).”
Slice-based Learning: A Programming Model for Residual Learning in Critical Data Slices (2019, background): “Weak supervision has been viewed as a new way to incorporate data of varying accuracy sources, including domain experts, crowd sourcing, data augmentations, and external knowledge bases [2, 5, 6, 11, 14, 21, 25, 29, 31].”
The Role of Massively Multi-Task and Weak Supervision in Software 2.0 (2019, methodology): “The idea of using programmatic sources of supervision builds on a long history of work in distant supervision [1, 16, 24] and crowdsourcing [5, 9, 10, 19, 46].”
Inferring Generative Model Structure with Static Analysis (2017, background): “Methods such as crowdsourcing [12, 17, 40], boosting[3, 33], co-training [6], and learning from noisy labels are some of the popular approaches that can combine various sources of weak supervision to assign noisy labels to data.”
Spectral Methods Meet EM: A Provably Optimal Algorithm for Crowdsourcing (2014, methodology): “[7] propose another SVD-based algorithm which explicitly considers the sparsity of the labeling matrix in both algorithm design and theoretical analysis.”
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).”
Comprehensive and reliable crowd assessment algorithms (2014, background): “B) We present experimental results on synthetic data (Section IV-B) and 3 real datasets (Section IV-C) to study the performance of our confidence intervals on k-ary tasks.”
SLiMFast: Guaranteed Results for Data Fusion and Source Reliability (2015, background): “The only work prior to ours that comes with theoretical guarantees on the error rate of accuracy estimates is from the crowdsourcing community [8, 17, 20, 18] where data sources correspond to human workers.”
Snorkel DryBell: A Case Study in Deploying Weak Supervision at Industrial Scale (2018, background): “Many prior weak supervision approaches have relied on either a single source of labels, or a small number of carefully chosen, manually combined sources [16, 30], or on sources that make uncorrelated errors such as independent crowd workers [9, 8].”
Learning the Structure of Generative Models without Labeled Data (2017, methodology): “ al. (2014) proposed a spectral approach 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 ”
A Corpus with Multi-Level Annotations of Patients, Interventions and Outcomes to Support Language Processing for Medical Literature (2018, background): “Such annotations are typically imperfect, but methods that aggregate redundant annotations can mitigate this problem (Dalvi et al., 2013; Hovy et al., 2014; Nguyen et al., 2017).”
Training Complex Models with Multi-Task Weak Supervision (2018, methodology): “In the case where the sources are assumed to be independent, e.g., (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.e., select the sign of the zi that leads to higher average accuracies of the…”
Crowdsourced Data Management: Industry and Academic Perspectives (2015, unknown): “The papers draw from various techniques, including spectral methods [59, 83], message passing [112], a combination of spectral methods and message passing [113], or a combination of spectral methods and EM [201].”
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].”
Learning From Noisy Singly-labeled Data (2017, methodology): “More sophisticated agreementbased algorithms jointly model worker skills and ground truth labels, estimating both using EM or similar techniques (Dawid & Skene, 1979; Jin & Ghahramani, 2003; Whitehill et al., 2009; Welinder et al., 2010; Zhou et al., 2012; Liu et al., 2012; Dalvi et al., 2013; Liu e”