Fundamental Limits of Budget-Fidelity Trade-off in Label Crowdsourcing
Digital crowdsourcing (CS) is a modern approach to perform certain large projects using small contributions of a large crowd. In CS, a taskmaster typically breaks down the project into small batches of tasks and assigns them to so-called workers with imperfect skill levels. The crowdsourcer then collects and analyzes the results for inference and serving the purpose of the project. In this work, the CS problem, as a human-in-the-loop computation problem, is modeled and analyzed in an information theoretic rate-distortion framework. The purpose is to identify the ultimate fidelity that one can achieve by any form of query from the crowd and any decoding (inference) algorithm with a given budget. The results are established by a joint source channel (de)coding scheme, which represent the query scheme and inference, over parallel noisy channels, which model workers with imperfect skill levels. We also present and analyze a query scheme dubbed k-ary incidence coding and study optimized query pricing in this setting.
The paper considers a crowdsourcing set up where a taskmaster divides a big task (say an inference problem) into small tasks. These small tasks are then presented to crowd or workers. A crowdsourcer then collects the information provided by these workers (after completion of their assigned tasks) and process this information to conclude the inference task. This setup allows for the worker to have varying skill levels as well as to be unreliable in reporting their information to the crowdsourcer. The objective of the whole system is to ensure certain level of fidelity or 'goodness' of the final outcome at the crowdsourcer, even in the presence of some wrong information presented by the participating workers. This requires the taskmaster to carefully design small tasks (or queries) to be allocated to the workers. The paper defines the total number of queries presented to the workers as the budget of the crowdsourcing system.  The paper studies a fundamental trade-off between the budget (number of queries presented to the workers by the taskmaster) and fidelity (quality of the inference task performed at the crowdsourcer). This trade-off is obtained by mapping the crowdsourcing system described above to the problem of joint source channel coding in information theory literature. The taskmaster is treated as an transmitter and the crowdsourcer is mapped to a receiver/decoder. The unreliable links from the workers to the crowdsourcer constitute a communication channel. Given this mapping a lower bound on the budget (no. of queries) for a desirable fidelity level follows from the standard results in information theory literature. This bound is independent of the schemes used by the taskmaster to design the queries and the algorithm used at the crowdsourcer to process the information collected from the workers. The authors then consider a specific scheme at the taskmaster, called k-ary incidence coding and analyze its performance. The authors then compare the performance of this encoding scheme with the obtained information theoretic lower bound for a specific channel model.
The reviewer finds the parallel drawn between the rate-distortion framework and the crowdsourcing system with unreliable workers quite interesting. This work may invite other researcher to study the crowdsourcing framework using information theoretic tools. However, the reviewer is not sure if the results presented in this paper model the real crowdsourcing systems in a very realistic way. One reason behind this could be that the paper wants the crowdsourcing problem to exactly map to the point-to-point communication problem so that the existing results from the information theory literature can be directly applied with the minimal efforts.  It would be great if the authors can comment on the following issues.   1) It seems that the reliability and skill level of the workers is merged together and modeled as a single channel. The paper assumes that the transmitter (taskmaster) allocates same no. of queries to all the workers irrespective of their skill level. This may not be true in the real systems where the workers may carry some rating with them which represents their skill level.  2) How realistic are the channel models to take the unreliability of the workers into account. What about the workers which can have some knowledge of the task at hand and try to degrade the fidelity in an adversarial manner.  The explanation of Numerical results is not very clear. The labeling of various curves in Fig.~2 can be improved. What does $k=1$ case correspond to. The worker directly gives you the correct label of the presented query as you can not present a pair and ask if they share the same label in this case?  In page 6, line 246 the authors mention that they assume the knowledge of $P(B(X))$. The reviewer believe that this should have been stated much earlier in the paper.   In page 4, line 135:  Figure 1.a --> Figure 1.b In page 4, line 135:  Figure 1.b --> Figure 1.c  The authors repeatedly use 'Theorem', 'Lemma' and 'Corollary' even when these terms are not accompanied by a specific theorem or lemma number. The reviewer believes that 'theorem', 'lemma' and 'corollary' would be more appropriate in such cases.