Abstract-Crowdsourcing-system, där många uppgifter distribueras elektroniskt till många "informationsarbetare", har framgått som ett effektivt paradigm för mänsklig lösning av storskaliga problem inom områden som bildklassificering, datainmatning, optisk karaktärsigenkänning, rekommendationer och korrekturläsning. Eftersom dessa lågavlönade arbetstagare kan vara opålitliga, måste nästan alla crowdsources utforma system för att öka förtroendet för sina svar, vanligtvis genom att tilldela varje uppgift flera gånger och kombinera svaren på något sätt såsom majoritetsomröstning. I detta dokument överväger vi en modell av sådana crowdsourcing uppgifter och utgör problemet med att minimera det totala priset (dvs. antal uppdrag) som måste betalas för att uppnå ett mål övergripande tillförlitlighet. Vi ger en ny algoritm för att bestämma vilka uppgifter som ska tilldelas vilka arbetstagare och för att komma fram till korrekta svar från arbetarnas svar. Vi visar att vår algoritm, baserad på låggradig matris approximation, avsevärt överträffar majoritetsomröstning och, i själva verket, är orderoptimal genom jämförelse med ett orakel som vet tillförlitligheten hos varje arbetare.
Karger m.fl. REF utvecklar en algoritm för att generera en graf som representerar en uppgiftstilldelning till arbetstagare och leder till korrekta svar baserat på låggradig matris approximation.
Budget-optimal crowdsourcing using low-rank matrix approximations
{'venue': '2011 49th Annual Allerton Conference on Communication, Control, and Computing (Allerton)', 'journal': '2011 49th Annual Allerton Conference on Communication, Control, and Computing (Allerton)', 'mag_field_of_study': ['Computer Science']}