Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Optimal Inference in Crowdsourced Classification via Belief Propagation
KTH, School of Electrical Engineering and Computer Science (EECS).
Univ Illinois, Dept Ind & Enterprise Syst Engn, Urbana, IL 61801 USA..
Korea Adv Inst Sci & Technol, Dept Elect Engn, Daejeon 34141, South Korea..
Korea Adv Inst Sci & Technol, Dept Elect Engn, Daejeon 34141, South Korea..
2018 (English)In: IEEE Transactions on Information Theory, ISSN 0018-9448, E-ISSN 1557-9654, Vol. 64, no 9, p. 6127-6138Article in journal (Refereed) Published
Abstract [en]

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.

Place, publisher, year, edition, pages
Institute of Electrical and Electronics Engineers (IEEE), 2018. Vol. 64, no 9, p. 6127-6138
Keywords [en]
Crowdsourcing, belief propagation, optimal inference
National Category
Control Engineering
Identifiers
URN: urn:nbn:se:kth:diva-234582DOI: 10.1109/TIT.2018.2846582ISI: 000442350500009Scopus ID: 2-s2.0-85048593754OAI: oai:DiVA.org:kth-234582DiVA, id: diva2:1248426
Note

QC 20180914

Available from: 2018-09-14 Created: 2018-09-14 Last updated: 2018-09-14Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textScopus

Authority records BETA

Ok, Jungseul

Search in DiVA

By author/editor
Ok, Jungseul
By organisation
School of Electrical Engineering and Computer Science (EECS)
In the same journal
IEEE Transactions on Information Theory
Control Engineering

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 10 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf