Obtaining High-Quality Label by Distinguishing between Easy and Hard Items in Crowdsourcing

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;
2. 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 | )};
3. 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.

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

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.

Acknowledgments

This work was supported by the NSFC (61673202, 61673201), 973 Program (2014CB340501), and the Collaborative Innovation Center of Novel Software Technology and Industrialization.