Crowdsourcing with Sparsely Interacting Workers
This work addresses the challenge of improving crowdsourcing accuracy for tasks like data labeling, though it is incremental as it builds on existing single-coin models.
The paper tackles the problem of estimating worker skills from sparse interaction data in crowdsourcing, showing that skills are identifiable if the interaction graph is irreducible and contains odd cycles, and proposing a gradient descent method that achieves state-of-the-art performance on real-world datasets.
We consider estimation of worker skills from worker-task interaction data (with unknown labels) for the single-coin crowd-sourcing binary classification model in symmetric noise. We define the (worker) interaction graph whose nodes are workers and an edge between two nodes indicates whether or not the two workers participated in a common task. We show that skills are asymptotically identifiable if and only if an appropriate limiting version of the interaction graph is irreducible and has odd-cycles. We then formulate a weighted rank-one optimization problem to estimate skills based on observations on an irreducible, aperiodic interaction graph. We propose a gradient descent scheme and show that for such interaction graphs estimates converge asymptotically to the global minimum. We characterize noise robustness of the gradient scheme in terms of spectral properties of signless Laplacians of the interaction graph. We then demonstrate that a plug-in estimator based on the estimated skills achieves state-of-art performance on a number of real-world datasets. Our results have implications for rank-one matrix completion problem in that gradient descent can provably recover $W \times W$ rank-one matrices based on $W+1$ off-diagonal observations of a connected graph with a single odd-cycle.