Optimal Inference in Crowdsourced Classification via Belief Propagation

Cited 0 time in webofscience Cited 0 time in scopus
  • Hit : 81
  • Download : 0
Crowdsourcing systems are popular for solving large-scale labeling 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 the belief propagation (BP) exactly matches the 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 the BP is close to optimal for all regimes considered and improves upon competing the state-of-the-art algorithms.
Publisher
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
Issue Date
2018-09
Language
English
Article Type
Article
Citation

IEEE TRANSACTIONS ON INFORMATION THEORY, v.64, no.9, pp.6127 - 6138

ISSN
0018-9448
DOI
10.1109/TIT.2018.2846582
URI
http://hdl.handle.net/10203/245646
Appears in Collection
EE-Journal Papers(저널논문)
Files in This Item
There are no files associated with this item.

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0