# Iterative Learning for K-Approval Votes in Crowdsourcing Systems
## 1 Introduction  
As the need for large-scale labeled data grows in various fields, crowdsourcing has become an attractive paradigm in human-powered problem solving systems. Web-based crowdsourcing platforms such as Amazon Mechanical Turk and Zooniverse are now in widespread use for amassing enormous amounts of responses from many crowds in a short time with a relatively low budget [1, 2, 3]. For example, ImageNet, a large-scale image database, was a successful project that exploited the idea of crowdsourcing to label 3.2 million images hierarchically [4].  
Unfortunately, the responses obtained from workers via crowdsourcing can be highly erroneous [5, 6, 7, 8], since common workers hired by crowdsourcers are low-paid, and lack expertise and responsibility [9]. Thus, extensive research has been conducted to find solutions that can collect higher-quality labels from workers [9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20].  
In eliciting the wisdom of crowds, many crowdsourcing platforms encourage workers to select top-\(K\) alternatives they believe as correct candidates. This voting rule is called \"\(K\)-approval voting\" and its interface provides workers with more flexibility to respond and even takes advantage of their partial expertise [21, 22]. Due to the above merits, many crowdsourcers adopted the \(K\)-approval voting setup to collect a large amount of responses. For real crowdsourcing examples, two tasks described in Figures 1 and 2 are real-world crowdsourcing examples of \(K\)-approval voting. Figure 1 shows a task being distributed on Amazon Mechanical Turk; the task was requested by one of the well-known online shopping platforms, Amazon. The goal of the task was to classify the best category of the item in the picture from given alternatives. Figure 2 shows another real task named \"Wisconsin Wildlife Watch\" on Zooniverse, which is another popular crowdsourcing system. The goal of this task is to correctly figure out what Wisconsin wildlife animals were pictured. Although the demand on \(K\)-approval voting increases, there is not much work involved ininferring the correct answer from the collected data via a \(K\)-approval voting. One natural method to aggregate responses is majority voting. However, it is insufficient to exploit the wisdom of crowds appropriately since it assumes that the reliability levels of the responses of all workers are the same. In fact, it was recently demonstrated that majority voting is sub-optimal for any \(K\)-approval voting systems [22].  
In this paper, we design a novel algorithm for \(K\)-approval-voting systems that evaluates workers' reliability to infer the correct answers to the tasks more precisely. This work can be generally applicable on real crowdsourcing platforms in practice where tasks have \(D\) multiple-choice questions allowing workers to select top-\(K\) alternatives. Moreover, our algorithm can be applied to the case that each problem has a different \((D,K)\) value.  
One of main contributions of this paper is the performance guarantee of our algorithm. We rigorously prove that the error bound of our algorithm decays exponentially. An interesting aspect of the error bound is its dependency on the negative entropy of workers in a perspective on information theory. Additionally, we verify the performance of our algorithm through numerical experiments on various cases including a realistic case containing mixed tasks with various numbers \(D\) of alternatives and \(K\) selections. Moreover, through experiments, we show that our algorithm estimates the relative reliabilities of the workers properly.  
The paper is organized as follows: In Section 3, we make a setup, and in Section 4, we describe our algorithm to infer the correct answers for \(K\)-approval votes. Then, we provide performance guarantees for our algorithm in Section 5. In Section 6, we present comparative results through numerical experiments, and we draw conclusions in Section 7.