Optimal Inference in Crowdsourced Classification via Belief Propagation
From MaRDI portal
Publication:4682902
DOI10.1109/TIT.2018.2846582zbMATH Open1401.68070arXiv1602.03619OpenAlexW2963027083WikidataQ114373366 ScholiaQ114373366MaRDI QIDQ4682902FDOQ4682902
Authors: Jungseul Ok, Sewoong Oh, Jinwoo Shin, Yung Yi 
Publication date: 19 September 2018
Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)
Abstract: Crowdsourcing systems are popular for solving large-scale labelling tasks with low-paid workers. We study the problem of recovering the true labels from the possibly erroneous crowdsourced labels under the popular Dawid-Skene model. To address this inference problem, several algorithms have recently been proposed, but the best known guarantee is still significantly larger than the fundamental limit. We close this gap by introducing a tighter lower bound on the fundamental limit and proving that Belief Propagation (BP) exactly matches this lower bound. The guaranteed optimality of BP is the strongest in the sense that it is information-theoretically impossible for any other algorithm to correctly label a larger fraction of the tasks. Experimental results suggest that BP is close to optimal for all regimes considered and improves upon competing state-of-the-art algorithms.
Full work available at URL: https://arxiv.org/abs/1602.03619
Cited In (5)
- Learning Complex Concepts Using Crowdsourcing: A Bayesian Approach
- Optimal permutation estimation in crowdsourcing problems
- Statistical Decision Making for Optimal Budget Allocation in Crowd Labeling
- Identifying unreliable and adversarial workers in crowdsourced labeling tasks
- Dense limit of the Dawid–Skene model for crowdsourcing and regions of sub-optimality of message passing algorithms
This page was built for publication: Optimal Inference in Crowdsourced Classification via Belief Propagation
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4682902)
