--- title: "Obtaining High-Quality Label by Distinguishing between Easy and Hard Items in Crowdsourcing" authors: - "Wei Wang" - "Xiang-Yu Guo" - "Shao-Yuan Li" - "Yuan Jiang" - "Zhi-Hua Zhou" doi: "10.24963/ijcai.2017/413" url: "https://ijcai.org/proceedings/2017/413" pdf: "https://ijcai.org/proceedings/2017/0413.pdf" venue: "Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence" year: 2017 pages: "2964-2970" track: "Main track" keywords: - "Machine Learning: Machine Learning" - "Machine Learning: Multi-instance/Multi-label/Multi-view learning" --- # Obtaining High-Quality Label by Distinguishing between Easy and Hard Items in Crowdsourcing Wei Wang, Xiang-Yu Guo, Shao-Yuan Li, Yuan Jiang, Zhi-Hua Zhou *Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence*, pages 2964-2970. DOI: [10.24963/ijcai.2017/413](https://doi.org/10.24963/ijcai.2017/413) ## Abstract Crowdsourcing systems make it possible to hire voluntary workers to label large-scale data by offering them small monetary payments. Usually, the taskmaster requires to collect high-quality labels, while the quality of labels obtained from the crowd may not satisfy this requirement. In this paper, we study the problem of obtaining high-quality labels from the crowd and present an approach of learning the difficulty of items in crowdsourcing, in which we construct a small training set of items with estimated difficulty and then learn a model to predict the difficulty of future items. With the predicted difficulty, we can distinguish between easy and hard items to obtain high-quality labels. For easy items, the quality of their labels inferred from the crowd could be high enough to satisfy the requirement; while for hard items, the crowd could not provide high-quality labels, it is better to choose a more knowledgable crowd or employ specialized workers to label them. The experimental results demonstrate that the proposed approach by learning to distinguish between easy and hard items can significantly improve the label quality. ## Full text ## 1 Introduction In recent years, unlabeled data can often be obtained abundantly and cheaply, e.g., one can write a crawler in a few lines of code and automatically download hundreds of thousands of images from the internet. Generally, these unlabeled data cannot be directly used in machine learning, since learning algorithms need data with labels to train a model for making predictions, e.g., the complex deep neural network requires large amounts of labeled data in the training process. Providing labels for large amounts of unlabeled data has always been a challenge because labeling the data is expensive and time-consuming. An effective and efficient paradigm for label collection is crowdsourcing [Howe, 2006; 2008], e.g., in the famous crowdsourcing system Amazon Mechanical Turk (AMT), the taskmaster submits the task that can be completed by voluntary workers in exchange for small monetary payments. This task is usually called Human Intelligence Task (HIT), which computers are currently unable to perform while humans can complete easily, e.g., annotating images of trees versus images of non-trees. Crowdsourcing makes it possible for many independent and relatively inexpensive workers to provide labels for largescale unlabeled data together. These workers usually come from a large society and each of them is presented with multiple items of the crowdsourcing task. Each worker has to answer the question about the item presented to her/him and provides a label based on her/his own knowledge. Crowdsourcing can collect large-scale labels with small monetary payments in a short period of time, unfortunately, these labels collected via crowdsourcing are typically highly erroneous [Kazai et al., 2011; Vuurens et al., 2011] due to the fact that most workers in the crowd are non-experts. In machine learning, label quality is crucial to the performance of learning algorithm and higher-quality labels will bring better predictions. How to obtain high-quality labels via crowdsourcing is an important issue to address. For improving the label quality, the common wisdom is to add redundancy into the labels, i.e., each item is presented with multiple workers. In this way, multiple labels are collected for each item and the final solution is determined by aggregating these crowded labels [Sheng et al., 2008; Snow et al., 2008; Sorokin and Forsyth, 2008]. In the past few years, researchers have developed many methods for inferring good labels from the crowd, most of which build probabilistic models for the crowdsourcing process and derive the labels using algorithms based on Expectation Maximization (EM) and other inference tools. Raykar et al. [2009; 2010] used a two-coin model to measure the sensitivity and specificity of each worker and iteratively estimated the two terms by an EM algorithm. Whitehill et al. [2009; 2010] formulated a probabilistic model of worker quality and applied an EM algorithm to infer the most probable label. Raykar and Yu [2012] developed an empirical Bayesian algorithm based on EM to iteratively estimate the ground-truth label and eliminate the spammers. Liu et al. [2012] transformed the crowdsourcing problem into a variational inference problem in graphical models and inferred the labels with variational inference tools including Belief Propagation and Mean Field. Tian and Zhu [2015] inferred the ground-truth label based on the max-margin principle by maximizing the margin between the aggregated score of potential true label and other alternatives. The minimax entropy principle has also been introduced into crowdsourcing. Zhou et al. [2012; 2014] proposed a minimax entropy method to infer the ground-truth label by minimizing the entropy of the probabilistic distribution. Wauthier and Jordan [2011] proposed a Bayesian framework named the Bayesian Bias Mitigation to unify the process of inferring the labels and learning from the inferred labels. Wang and Zhou [2016] presented a PAC bound on the number of labels collected via crowdsourcing for learning a good model. Some other works focused on how to choose which items are assigned to each worker. Yan et al. [2011] employed a probabilistic model to select the worker from which to query the label. Karger et al. [2011; 2014] proposed an item assignment algorithm based on a random regular bipartite graph. Ho and Vaughan [2012] developed an algorithm for assigning heterogeneous items to workers with different qualities based on the online primal-dual technique [Buchbinder and Naor, 2005]. Later, Ho and Vaughan [2013] utilized items with true labels to estimate workers' performance and proposed a provably near-optimal assignment algorithm for heterogeneous items. Liu et al. [2013] also exploited items with known answers to evaluate workers' performance for item assignment. Chen et al. [2013; 2015] formulated a finite horizon Markov Decision Process in a Bayesian setting and characterized the optimality using dynamic programming. Raykar and Agrawal [2014] modeled the item assignment problem as a Markov decision process and defined an Bayesian decision theoretic utility function to jointly consider the cost for acquiring additional labels and the possible accuracy improvement. There are also some interesting works on developing payment mechanisms to encourage workers to provide high-quality labels for items [Shah et al., 2015; Shah and Zhou, 2015; 2016]. In this situation, the task is posted together with the labeling guidelines and payment instructions, and it is demanded that the worker label each item according to her/his own belief of the answer being correct. They also assumed that the threshold of this belief is known to the payment mechanism designer and that the worker's payment is based on her/his performance on the gold standard items (a set of items whose true labels are known). However, it is difficult to get this threshold in real-world applications and the gold standard items will increase the labeling cost. ## 1.1 Our Focus and Contribution In crowdsourcing, thousands of workers have internet access to the posted task. These voluntary workers have different abilities, since they may come from different regions, receive different educations and have different knowledge. Usually, the items of the crowdsourcing task also have different difficulties for different workers. For easy items, most workers could provide correct labels with high probability, aggregating several labels from the crowd could infer the high-quality labels; while for hard items which need specific domain knowledge for correct labeling, only a portion of the crowd could provide correct labels with high probability, aggregating several labels from the crowd without knowing who these knowledgable workers are may not infer the highquality labels. An optimistic idea is to identify these knowledgable workers and let them provide labels to hard items. However, it is difficult to identify the knowledgable workers without prior knowledge about the crowd. Furthermore, in many crowdsourcing systems, the voluntary workers are anonymous and transient, the taskmaster cannot assign particular items to an identified worker, nor could she/he expect some worker to show up again in the future. This motivates us to propose a novel crowdsourcing approach, in which we learn to distinguish between easy and hard items for the crowd. For easy items, it is feasible to derive high-quality labels from the current crowd; while for hard items, it is difficult to derive high-quality labels from the current crowd without prior knowledge. Choosing a more knowledgable crowd or employing specialized workers for these hard items will be a good strategy for obtaining highquality labels. Following this direction, we propose a twostage efficient algorithm: in the first stage, we let the crowd label a small portion of items to estimate their difficulty; then in the second stage we train a model with this training set to predict the difficulty of future items. Similar items should have similar labels and the worker would provide similar labels to similar items. Thus, similar items should have similar labeling difficulty with respect to the same crowd. This could explain why the process of learning the difficulty is reasonable. The experimental results demonstrate that learning to distinguish between easy and hard items with the proposed algorithm can significantly improve the label quality. The rest of this paper is organized as follows. After introducing some preliminaries in Section 2, we present our approach in Section 3 and discuss how to choose the parameter in Section 4. Finally, we conduct experiments in Section 5 and make a conclusion in Section 6. ## 2 Preliminaries In this paper, we consider the task involving binary-choice items. The task has a set of m items {x1, . . . , xm} over X, each item corresponds to a binary-choice example xi with an unobserved true label yi ∈ {0, 1}, 1 ≤ i ≤ m (e.g., annotating whether an image contains trees or not). These items will be labeled by a crowd, where W denotes the set of all workers in the crowd. To improve label quality and reliability, an example xi is generally presented to N workers denoted by {w1, . . . ,wN}, wj ∈ W, 1 ≤ j ≤ N. For any item xi ∈ X, a worker wj provides a label yj i = wj(xi) ∈ {0, 1} on xi and a final label is then inferred for xi based on the multiple labels. The item may have different difficulties for different workers and the difficulty depends on many factors, e.g., the time it takes for labeling, the knowledge required for correct labeling, the worker's honesty, the payment mechanism, and the item itself. In fact, the difficulty of an item can be evaluated from the output of the worker, i.e., if worker wj provides a correct label to item xi with great probability, it is regarded that xi is an easy item for wj ; if wj provides an incorrect label to xi with great probability, it is regarded that xi is a hard item for wj. The posterior probability dxi (wj) = P(yj i ̸= yi|xi) denotes the probability that wj provides an incorrect label for xi and can be thought of as the difficulty of xi for wj . For any item x, we define the following difficulty of x for the crowd Definition 1 (Difficulty) Let DW denote the underlying distribution over the workers in the crowd W, the difficulty of the item (x, y) with respect to the crowd W is defined as For the sake of convenience, we will write dx(W) as dx for the fixed crowd W. In particular, one frequently provides nearly random labels to the items that are too difficult to answer [Shah and Zhou, 2015], and the empirical observations also show that the workers in crowdsourcing systems, as opposed to being adversarial in nature, at worst provide random labels to items [Yuen et al., 2011; Gadiraju et al., 2015]. Although the crowd may contain few adversaries who give wrong answers deliberately, it is reasonable to assume that dx ≤ 1/2, i.e., the crowd is not dominated by the adversaries. When dx is small, x is an easy item; while dx is large, x is an hard item. For hard items, there may exist some knowledgable workers wj with small dx(wj). However, it is not feasible to identify these knowledgable workers for hard items without prior knowledge about the crowd. ## 3 Our Method When no prior knowledge about the crowd is known, randomly selecting N workers from the crowd and using the majority voting to infer the final label ̂ y for x is a good error-pruning strategy, i.e., For the item x, we can give the upper bound on the label quality for majority voting with respect to the difficulty of the item in the following proposition. Proposition 1 For the item (x, y) and the crowd W, let ̂ y denote the inferred label of x with majority voting from N workers, the following inequality holds. Proof. Proposition 1 can be proved with Hoeffding [1963] bound. □ Proposition 1 states that small dx will bring high-quality label while large dx will lead to low-quality label. If the taskmaster requires that a minimum quality of the labels obtained from the crowd should be achieved, the maximum difficulty dx can be derived according to Equation 1. This maximum difficulty dx can be thought of as a threshold η, the easy items whose dx is no larger than η could be labeled by the crowd and the label quality of them could satisfy the requirement; while the hard items whose dx is larger than η should not be labeled by the current crowd since the crowd may provide low-quality labels for themwith great risk. Now an important issue arises: how to estimate the difficulty efficiently? A straight-forward way is that we let the crowd label all items and then estimate dx with these crowded labels. The item x ∈ X is labeled by N workers {w1, . . . ,wN}, we give the definition of empirical difficulty ̂ dx of x: With this empirical difficulty ̂ dx, we give the following proposition: Proposition 2 For the item (x, y) and any ϵ ∈ (0, 1), the following inequality on ̂ dx and dx holds. Proof. For the item (x, y), if ̂ y = y, it is easy to prove that P(|dx - ̂ dx| ≥ ϵ) ≤ 2 exp(-2Nϵ2 ) with Hoeffding [1963] bound; if ̂ y ̸= y, it is easy to prove that P(|(1 - dx) - ̂ dx| ≥ ϵ) ≤ 2 exp(-2Nϵ2 ) with Hoeffding [1963] bound. So we get that P (∣∣|1/2 - dx| - |1/2 - ̂ dx|∣∣ ≥ ϵ) ≤ 2 exp(-2Nϵ2 ). Since the label ̂ y is inferred by majority voting, we get that ̂ dx ≤ 1/2 with Equation 2. Considering that dx ≤ 1/2, we have that P (∣∣̂ dx - dx ∣∣ ≥ ϵ) ≤ 2 exp(-2Nϵ2 ). □ Proposition 2 states that ̂ dx is a good approximation of dx when we can not reach the true label of the item. After the crowd has labeled all items, we get the estimation ̂ dx of the true difficulty dx for each item. If ̂ dx ≤ η, it implies that x is an easy item; if ̂ dx > η, it implies that x is a hard item. For the requirement of high label quality, we should not accept the inferred labels for hard items. In this situation, the crowd has provided labels to these hard items, but we could not accept their labels in order to avoid the risk. This wastes too much labeling cost and motivates us to develop an approach for estimating the difficulty before labeling all items. In order to address this problem we propose a two-stage algorithm. In the first stage, we select a small portion of items T ⊂ X randomly from the whole set X and let the crowd provide labels to them. With these crowded labels we estimate the empirical difficulty ̂ dx of the item x ∈ T and construct a training set L with the estimated difficulty, i.e., L = {(x1, ̂ dx1 ), . . . , (x|T |, ̂ dx|T | )}. Then in the second stage we learn a model with L to predict the difficulty of the item in X - T . With the predicted difficulty, we set a threshold η to distinguish between easy and hard items (please see Section 4 for how to choose η). Let Φ : X → RM denote the kernel mapping from the input space X to RM , considering the linear hypothesis space we assume that the difficulty is determined by the function that with h∗ and b∗ , i.e., for any item x, With the training set L, we try to find the optimal (h∗ , b∗ ) with Kernel Ridge Regression by minimizing the following loss function: For this learning problem, our aim is to predict whether the item x should be labeled by the crowd to achieve high-quality label with small risk, i.e., ̂ dx ≤ η or not. For a good model f(·), the easy items in the training set L should also be predicted as the easy ones by f(·), i.e., if ̂ dxi ≤ η, f(xi) ≤ η; otherwise, f(xi) > η. So we introduce the constraints into the optimization and Equation 5 is transformed into: After introducing the parameter β, the optimization problem with constraints can be formalized as The optimization problem in Equation 7 can not be solved efficiently, since the last term I(t ≤ 0) is not differentiable. We replace it with its surrogate loss function log2(1 + e-t ) and get the optimization problem shown as Thus, by solving the optimization problem in Equation 8 with the training set L, we can find the optimal solution (h∗ , b∗ ) to predict the difficulty of the item in X - T . The process is described in Algorithm 1. With the predicted difficulty dx = 1 1+exp(-(h∗ ·Φ(x)+b∗ )) and the threshold η, we can determine whether an item should be labeled by the crowd, i.e., if dx ≤ η, x should be labeled by the crowd; otherwise, x should not be labeled by the crowd due to high risk. In the following section, we will discuss how to choose the parameter η. ## 4 The Parameter η η is a parameter in the process, smaller η will bring less easy items and higher label quality, while larger η will lead to more easy items but lower label quality. η depends on the required label quality or the ratio of items that need to be labeled by the crowd, we will discuss how to choose it in this section. ## Algorithm 1 Difficulty Learning ## Input: Unlabeled items X, the crowd W, the threshold η, the parameter γ and the kernel Φ. ## Process: 1. Select number of γ|X| items randomly fromX as T ; 2. Each item xi ∈ T is presented to N workers from the crowd W and its label ̂ yi is inferred by majority voting; 3. Calculate the estimated difficulty ̂ dxi for each item xi ∈ T according to Equation 2 and get the training set L = {(x1, ̂ dx1 ), . . . , (x|T |, ̂ dx|T | )}; 4. Solve the optimization problem to get (h∗ , b∗ ) with the training set L according to Equation 8. ## Output: The difficulty dx = 1 1+exp(-(h∗ ·Φ(x)+b∗ )) for each item x ∈ X -T . - Label Quality. Choose η with respect to the required label quality. Proposition 1 indicates that the upper bound on the error rate of labels depends on the difficulty of the item. We can derive the maximum difficulty dxmax according to the required label accuracy and set the threshold η = dx max. - Item Ratio. Choose η with respect to the required item ratio. In some applications, the volume of unlabeled items is huge. The taskmaster must set a minimum ratio R of these unlabeled items that need to be labeled by the crowd to save labeling cost, since employing the crowd costs less than employing specialized workers. Thus, R is the ratio of easy items whose difficulty is no larger than η. With the training set L = {(x1, ̂ dx1 ), . . . , (x|T |, ̂ dx|T | )}, we set η according to the following Equation 9, i.e., we use the ratio of easy items in the training set L as an estimation of R. ## · Label Information. In other applications, the taskmaster may require that both the ratio of items that need to be labeled by the crowd and the label accuracy on these labeled items should be as high as possible. Let A denote the label accuracy on the easy items that need to be labeled by the crowd, A can be denoted as The ratio of easy items can be denoted as We define Label Information I in Equation 10, i.e., the probability that the item in X - T can be labeled correctly by the crowd. If the taskmaster requires that both the ratio of labeled items and the label accuracy on these labeled items are as high as possible, it implies that the threshold η should be the one that maximizes the label information I. In real-world crowdsourcing, most items can be labeled correctly by the crowd, the number of hard items is much less than that of easy ones and the probability distribution of item's difficulty can be estimated from the training set L. In the following part of this section, we give an example for choosing the parameter η. From the training set L constructed in Section 5, we get the cumulative distribution function of item's difficulty, which is depicted as the black dashed line in Figure 1. Considering the truncated Beta distribution whose probability density function is shown in Equation 11 with parameters s and t, Z is the normalization term such that ∫ 12 0 1Z xs-1 (1-x)t-1 B(s,t) = 1, we get its cumulative distribution function with s = 0.231 and t = 0.774, which is depicted as the blue solid line in Figure 1. It can be found that the cumulative distribution function of item's difficulty in the training set L is very close to the cumulative distribution function of the truncated Beta distribution with s = 0.231 and t = 0.774. So we assume that the probability distribution of item's difficulty follows the truncated Beta distribution to facilitate the calculation. For easy items, with Proposition 1 we get that A ≥ 1 - exp ( - 2N(1/2 - η)2 ) since dx ≤ η; with the truncated Beta distribution, we get that the ratio of easy items is So we get that Thus, the optimal η∗ can be denoted as With the parameters s = 0.231, t = 0.774 and N = 9, the optimal η∗ ≈ 0.16. Figure 1: Cumulative distribution function. ![Image](https://ijcai.org/proceedings/2017/fulltext/413/image_000000_ea5bc6205e1134e17c39d930f2b23c7e51cb2d005fa52046d8756d0b094cc301.png) ## 5 Experiments In order to study whether we can obtain high-quality labels by learning to distinguish between easy and hard items we conduct experiments in this section. We perform experiments on the real data. In the task, there are 1499 different images and the workers are required to label whether tree appears in the image or not. The crowd that labels the data consists of 38 graduate students. Each image is labeled by several workers selected randomly from the crowd. Due to various reasons, some workers did not return their labels for some images. Finally, we drop those images labeled by less than 5 workers and get 1495 images. The number of labels provided by workers for each image ranges from 5 to 16. We use fisher vector of each image as its feature, which is a 1248-dimension vector. We randomly select 20% images to generate the training set L and the difficulty of these images are estimated according to Equation 2. The optimization problem in Equation 8 is solved to predict the difficulty of the images in X -L, where the kernel function Φ is set to be the linear kernel, α = 10-4 and β = 3. The parameter η is set between 0.1 and 0.3. Each experiment is repeated for 50 runs and the average performance is depicted in Figure 2. Figure 2(a) presents the ratio of images that are predicted as the easy ones and the accuracy of the labels inferred from the crowd on easy items with respect to different choices of η. The line Ratio of Easy denotes the ratio of images that are predicted as the easy ones; the line MV ACC-Easy denotes the accuracy of labels on easy items; the line MV ACC-Overall denotes the accuracy of labels inferred by majority voting when all items are labeled by the crowd; the line OptKG ACC-Overall denotes the accuracy of labels inferred by the state-of-art crowdsourcing method OptKG [Chen et al., 2013; 2015] when all items are labeled by the crowd. From Figure 2(a) we find that the label accuracy of easy items is much higher than that of MV ACC-Overall and that of OptKG ACCOverall. For example, when η = 0.2 the ratio of easy items is 0.773 and the label accuracy of easy items is 95.5%, while the accuracy of MV ACC-Overall is 92.0% and the accuracy of OptKG ACC-Overall is 92.3%. We also present the results on hard items in Figure 2(b), which shows the ratio of items that are predicted as the hard ones and the accuracy of the labels inferred on these hard items with respect to different choices of η. From Figure (a) Accuracy and ratio w.r.t. easy items. ![Image](https://ijcai.org/proceedings/2017/fulltext/413/image_000001_d2550e36354c78dd5ac1df3c446f7b990cea9305e089d5d2cb31e29a018142f3.png) (b) Accuracy and ratio w.r.t. hard items. ![Image](https://ijcai.org/proceedings/2017/fulltext/413/image_000002_cedd9793edad6511a87c16355c71ae0aa88145e29d48287ef26fd2b42e98ee09.png) Figure 2: Results on the data. 2(b) we find that the label accuracy of hard items is much lower than that of MV ACC-Overall and that of OptKG ACCOverall. For example, when η = 0.2, the ratio of hard items is 0.227 and the label accuracy of these hard items is only 80.1%. The current crowd could not provide high-quality labels to these hard items, we should find a more knowledgable crowd or employ specialized workers to label them. Figure 2 validates that we could obtain high-quality labels by learning to distinguish between easy and hard items. When the taskmaster requires high label quality, we should choose a small η; when the taskmaster requires both high label quality and large ratio of items that need to be labeled by the crowd, we should choose a medium η. In order to show whether the size of training set L influences the label accuracy, we run experiments with different sizes of L, i.e., from 10% to 40% with an interval 5%, and the results for a fixed η = 0.2 are depicted in Figure 3. From Figure 3 we can find that the label accuracy on easy items varies from 95.0% to 95.9% increasingly with the size of L varying from 10% to 40%. It indicates that the label quality is not very sensitive to the size of L. ## 6 Conclusion In this paper, we propose an approach for obtaining highquality labels from the crowd by learning to distinguish between easy and hard items before they are sent out to workers, which is complementary to the line of work that tries to obtain reliable labels via crowdsourcing for machine learning or other applications. It allows for better post-processing of hard items, i.e., we should find a more knowledgable crowd or employ specialized workers to label them, and provides a possibility that the items could be completed by different crowds with respect to their difficulty. We regard this work as preliminary and expect that more researches will follow this direction. Figure 3: Accuracy with different sizes of L for η = 0.2. ![Image](https://ijcai.org/proceedings/2017/fulltext/413/image_000003_125814a63742725065d11365eeafa275ca39d627818c97a73c39079280ca9c1e.png) ## Acknowledgments This work was supported by the NSFC (61673202, 61673201), 973 Program (2014CB340501), and the Collaborative Innovation Center of Novel Software Technology and Industrialization. ## References 1. [Buchbinder and Naor, 2005] Niv Buchbinder and Joseph Naor. Online primal-dual algorithms for covering and packing problems. In ESA, pages 689-701, Palma de Mal- lorca, Spain, 2005. 2. [Chen et al., 2013] Xi Chen, Qihang Lin, and Dengyong Zhou. Optimistic knowledge gradient policy for optimal budget allocation in crowdsourcing. In ICML, pages 64- 72, Atlanta, GA, 2013. 3. [Chen et al., 2015] Xi Chen, Qihang Lin, and Dengyong Zhou. Statistical decision making for optimal budget al- location in crowd labeling. Journal of Machine Learning Research, 16:1-46, 2015. 4. [Gadiraju et al., 2015] Ujwal Gadiraju, Ricardo Kawase, Stefan Dietze, and Gianluca Demartini. Understanding malicious behavior in crowdsourcing platforms: The case of online surveys. In ACM CHI, pages 1631-1640, Seoul, Republic of Korea, 2015. 5. [Ho and Vaughan, 2012] Chien-Ju Ho and Jennifer W. Vaughan. Online task assignment in crowdsourcing mar- kets. In AAAI, Toronto, Canada, 2012. 6. [Ho et al., 2013] Chien-Ju Ho, Shahin Jabbari, and Jen- nifer W. Vaughan. Adaptive task assignment for crowd- sourced classification. In ICML, pages 534-542, Atlanta, GA, 2013. 7. [Hoeffding, 1963] Wassily Hoeffding. Probability inequali- ties for sums of bounded random variables. Journal of the American Statistical Association, 58:13-30, 1963. 8. [Howe, 2006] Jeff Howe. The rise of crowdsourcing. Wired, 2006. 9. [Howe, 2008] Jeff Howe. Why the power of the crowd is driving the future of business. Crown Business, 2008. 10. [Karger et al., 2011] David R. Karger, Sewoong Oh, and De- vavrat Shah. Iterative learning for reliable crowdsourcing systems. In NIPS, pages 1953-1961. MIT Press, Cam- bridge, MA, 2011. 11. [Karger et al., 2014] David R. Karger, Sewoong Oh, and De- vavrat Shah. Budget-optimal task allocation for reliable crowdsourcing systems. Operations Research, 62(1):1- 24, 2014. 12. [Kazai et al., 2011] Gabriella Kazai, Jaap Kamps, Marijn Koolen, and Natasa Milic-Frayling. Crowdsourcing for book search evaluation: impact of hit design on compara- tive system ranking. In ACM SIGIR, pages 205-214, Bei- jing, China, 2011. 13. [Liu et al., 2012] Qiang Liu, Jian Peng, and Alexander T. Ih- ler. Variational inference for crowdsourcing. In NIPS, pages 701-709. MIT Press, Cambridge, MA, 2012. 14. [Liu et al., 2013] Qiang Liu, Alexander T. Ihler, and Mark Steyvers. Scoring workers in crowdsourcing: How many control questions are enough? In NIPS, pages 1914-1922. 15. [Raykar and Agrawal, 2014] Vikas C. Raykar and Priyanka Agrawal. Sequential crowdsourced labeling as an epsilon- greedy exploration in a markov decision process. In AIS- TATS, pages 832-840, Reykjavik, Iceland, 2014. 16. [Raykar and Yu, 2012] Vikas C. Raykar and Shipeng Yu. E- liminating spammers and ranking annotators for crowd- sourced labeling tasks. Journal of Machine Learning Re- search, 13:491-518, 2012. 17. [Raykar et al., 2009] Vikas C. Raykar, Shipeng Yu, Linda H. Zhao, Anna K. Jerebko, Charles Florin, Gerardo Her- mosillo Valadez, Luca Bogoni, and Linda Moy. Super- vised learning from multiple experts: whom to trust when everyone lies a bit. In ICML, Quebec, Canada, 2009. 18. [Raykar et al., 2010] Vikas C. Raykar, Shipeng Yu, Linda H. Zhao, Gerardo Hermosillo Valadez, Charles Florin, Luca Bogoni, and Linda Moy. Learning from crowds. Journal of Machine Learning Research, 11:1297-1322, 2010. 19. [Shah and Zhou, 2015] Nihar B. Shah and Dengyong Zhou. Double or nothing: Multiplicative incentive mechanisms for crowdsourcing. In NIPS, pages 1-9. MIT Press, Cam- bridge, MA, 2015. 20. [Shah and Zhou, 2016] Nihar B. Shah and Dengyong Zhou. No oops, you won't do it again: Mechanisms for self- correction in crowdsourcing. In ICML, pages 1-10, New York, NY, 2016. 21. [Shah et al., 2015] Nihar B. Shah, Dengyong Zhou, and Yu- val Peres. Approval voting and incentives in crowdsourc- ing. In ICML, pages 10-19, Lille, France, 2015. 22. [Sheng et al., 2008] Victor S. Sheng, Foster J. Provost, and Panagiotis G. Ipeirotis. Get another label? improving data quality and data mining using multiple, noisy labelers. In ACM SIGKDD, pages 614-622, Las Vegas, NV, 2008. 23. [Snow et al., 2008] Rion Snow, Brendan O'Connor, Daniel Jurafsky, and Andrew Y. Ng. Cheap and fast -but is it good? evaluating non-expert annotations for natural lan- guage tasks. In EMNLP, pages 254-263, Honolulu, HI, 2008. 24. [Sorokin and Forsyth, 2008] Alexander Sorokin and David A. Forsyth. Utility data annotation with ama- zon mechanical turk. In CVPR Workshop on Internet Vision, pages 1-8, Anchorage, AK, 2008. 25. [Tian and Zhu, 2015] Tian Tian and Jun Zhu. Max-margin majority voting for learning from crowds. In NIPS, pages 1612-1620. MIT Press, Cambridge, MA, 2015. 26. [Vuurens et al., 2011] Jeroen Vuurens, Arjen P. de Vries, and Carsten Eickhoff. How much spam can you take? an anal- ysis of crowdsourcing results to increase accuracy. In ACM SIGIR Workshop on Crowdsourcing for Information Re- trieval, pages 21-26, Beijing, China, 2011. 27. [Wang and Zhou, 2016] Lu Wang and Zhi-Hua Zhou. Cost- saving effect of crowdsourcing learning. In IJCAI, pages 2111-2117, New York, NY, 2016. 28. [Wauthier and Jordan, 2011] Fabian L. Wauthier and Michael I. Jordan. Bayesian bias mitigation for crowd- sourcing. In NIPS, pages 1800-1808. MIT Press, Cambridge, MA, 2011. 29. [Welinder et al., 2010] Peter Welinder, Steve Branson, Serge J. Belongie, and Pietro Perona. The multidimen- sional wisdom of crowds. In NIPS, pages 2424-2432. 30. [Whitehill et al., 2009] Jacob Whitehill, Paul Ruvolo, T- ingfan Wu, Jacob Bergsma, and Javier R. Movellan. Whose vote should count more: Optimal integration of la- bels from labelers of unknown expertise. In NIPS, pages 2035-2043. MIT Press, Cambridge, MA, 2009. 31. [Yan et al., 2011] Yan Yan, Róomer Rosales, Glenn Fung, and Jennifer G. Dy. Active learning from crowds. In ICM- L, pages 1161-1168, Bellevue, WA, 2011. 32. [Yuen et al., 2011] Man-Ching Yuen, Irwin King, and Kwong-Sak Leung. A survey of crowdsourcing system- s. In SocialCom, pages 766-773, Boston, MA, 2011. 33. [Zhou et al., 2012] Dengyong Zhou, John C. Platt, Sumit Basu, and Yi Mao. Learning from the wisdom of crowd- s by minimax entropy. In NIPS, pages 2204-2212. MIT Press, Cambridge, MA, 2012. 34. [Zhou et al., 2014] Dengyong Zhou, Qiang Liu, John C. Platt, and Christopher Meek. Aggregating ordinal labels from crowds by minimax conditional entropy. In ICML, pages 262-270, Beijing, China, 2014.