Centralized Multi-Class Labeling With BCH Codes For Crowdsourcing

Crowdsourcing is an effective paradigm to perform tasks in many scenarios by utilizing crowd’s intelligence and resources. However, due to the low rewards for crowd and diverse expertise and ability of crowd, the responses provided by crowd are usually unreliable. To improve the accuracy of these crowd users’ responses, a model named multi-class labeling was proposed recently. For situation where the reliability of crowd is unknown, in this paper we propose a centralized multi-class labeling design based on BCH codes for crowdsourcing: We design a centralized system framework for multi-class labeling in crowdsourcing and design a BCH codeword for each label with maximum fault tolerance capability, then to map the responses from the crowd into an estimated codeword based on this designed BCH code matrix so as to determine the ?nal approximate label. The multi-class labeling design based on BCH codes for crowdsourcing avoid the assumption that the crowd users and crowdsourcing platform have an uniform standard of cognition. The centralized multi-class labeling process in crowdsourcing platform is not limited by human’s real ?nite imagination, when allocating the tasks to crowd users. The BCH codes based code matrix generation does not depend on the reliability distribution of speci?c crowd. The design of BCH codes further makes the distances among labels larger to improve the fault tolerance capability for responses from crowd users. In addition, the systematic generation of BCH codes can provide lower computational complexity of code matrix generation.To demonstrate the background and related issues of crowdsourcing, in this paper we ?rst introduce the crowdsourcing system and typical applications. We further present the crowdsourcing system related models, including multi-class labeling model, crowd user model and the well-known optimal inference algorithm. In addition,based on these backgrounds, we present multi-class labeling scheme based on coding theory for crowdsourcing, introduce its system framework and analyze its motivation as well as why it is reasonable, by detailed examples.However, multi-class labeling scheme based on coding theory for crowdsourcing has ?ve limits. Firstly, the crowd users and crowdsourcing platform must have an uniform standard of cognition. Secondly, the code matrix generation requires large computational complexity. Thirdly, the o?ine code matrix generation requires the reliability distribution of a speci?c crowd, therefore the generated code matrix is not optimal for the crowd performing the sub-tasks, whose reliability is unknown. Fourthly,the feature instantiations are limited by human’s ?nite imagination seriously in reality.Fifthly, the online dynamic task allocation cannot guarantee that the diverse expertise and intelligence of crowd users can match the sub-tasks well. To solve these limits,we propose a centralized multi-class labeling design based on BCH codes for crowdsourcing(BCH-CMCL), to turn the process of dealing with the responses of the crowd users from distributed way into a centralized way, and to replace the code matrix generation in multi-class labeling scheme based on coding theory for crowdsourcing, with BCH codes generation. The centralized framework and process in multi-class labeling crowdsourcing system does not assume that the crowd users and crowdsourcing platform have an uniform standard of cognition, and avoid the situation where the task allocation is limited by human’s ?nite imagination in reality.Since BCH codes has larger hamming distance and systematic generation, BCH-CMCL does not depend on the reliability distribution of speci?c crowd and can achieve larger fault tolerance capability and lower computational complexity of code matrix generation. In detail, we show the system framework diagram of BCH-CMCL, analyze its advantages from the viewpoint of Set with detailed examples, present the construction and properties of BCH codes, propose the design and algorithm of BCH-CMCL for code matrix generation,and summarize the matrix design’s advantages in brief.We further give the theoretical analysis of BCH-CMCL, including comparisons between BCH-CMCL and multi-class labeling scheme based on coding theory for crowdsourcing in terms of fault tolerance capability, hamming distance and computational complexity of code matrix generation, and an upper bound, with a su?cient condition and a necessary condition, of average mis-label probability of BCH-CMCL.The theoretical analysis proves that compared with multi-class labeling scheme based on coding theory for crowdsourcing, BCH-CMCL has larger hamming distance and fault tolerance capability for crowd with unknown reliability, and lower computational complexity of o?ine code matrix generation. Furthermore, when the reliability of crowd is not too low, BCH-CMCL can achieve relative high accuracy.To validate the performance of BCH-CMCL, we set up the simulation modules and show several simulated results, including comparisons between BCH-CMCL and multi-class labeling scheme based on coding theory for crowdsourcing in terms of fault tolerance capability and hamming distance, the theoretical upper bounds and actual performance of average mis-label probability of BCH-CMCL, and accuracy performance comparisons of Majority Voting, multi-class labeling scheme based on coding theory for crowdsourcing and BCH-CMCL. These simulations results match the theoretical analysis well, which means that BCH-CMCL can provide solutions with higher accuracy from the responses of crowd users.