Cost-Saving Effect of Crowdsourcing Learning

1 Introduction

Crowdsourcing [Brabham, 2008] is a popular paradigm to outsource work to individuals and is widely adopted in various domains [Yang et al., 2012; Afuah and Tucci, 2012; Li et al., 2013; LeBras et al., 2013]. In the machine learning community, crowdsourcing is commonly used as a costsaving way to collect labels for training data. Specifically, unlabeled instances are outsourced to a large group of people, also known as a crowd, who will label some of these instances on their own knowledge and get paid accordingly. "True" labels are inferred from these labels given by the crowd. Then, a model would be learned with these crowd-labeled data.

Our focus in this paper is the cost-saving effect of crowdsourcing learning. In many applications, it is expected that crowdsourcing is cost-saving. In other words, crowdsourcing is expected to be of high performance while saving money at the same time. As to the crowdsourcing learning problem, we hope to get high-quality labels from a crowd and learn a model with these crowd-labeled data at a low cost. To achieve this goal, some issues must be considered.

First of all, it is necessary to ensure that a high-quality label can actually be induced from labels given by a crowd. It is not always the truth, and for some professional problems, experts play a non-substitutable role. For example, few patients are willing to rely on a crowd of amateurs to make important diagnoses. In general, compared with labels given by experts, labels from a crowd are cheaper but less accurate.

⇤This work was supported by the NSFC (61333014) and 973 Program (2014CB340501).

For obtaining high-quality labels, a feasible solution is to get every instance labeled multiple times by a crowd in order to gather more information. We call such a single label from the crowd as a crowd label for convenience. With these multiple crowd labels, a direct way to infer the true label is the majority voting strategy. In addition, many other strategies have been proposed based on different assumptions [Dawid and Skene, 1979; Whitehill et al., 2009; Raykar et al., 2010; Karger et al., 2011; Zhou et al., 2012; Oyama et al., 2013; Zhang et al., 2014; Tian and Zhu, 2015].

Second, it is noteworthy that the number of crowd labels required is concerned. A single crowd label may be cheap, but if one hopes to get high-quality labels by increasing the number of crowd labels, the cost budget may still run out. For an extreme example, if high-quality labels can only be attained by using an infinite crowd, then crowdsourcing cannot save any cost unless crowd labels are free.

The third issue lies in the fact that in crowdsourcing learning, the crowdsourcing step is just used to collect labels for training data, whereas the performance of the model learned with these data, instead of the quality of labels themselves, is concerned. There are some studies about learning from weak teachers or crowd labels [Dekel and Shamir, 2009; Yan et al., 2011; Urner et al., 2012; Zhong et al., 2015], and learning from crowd labels is also closely related to the label noise problem [Angluin and Laird, 1987; Kearns, 1998; Fr´enay and Verleysen, 2014]. A distinct point in our setting is for crowdsourcing learning, we can conveniently draw crowd labels for an instance over and over again. This paper focuses on the cost-saving effect of crowdsourcing learning. Given a crowdsourcing learning task, one must collect at least a number of crowd labels for PAC learning; we call this number as the "minimally-sufficient" number, and in this paper we present an upper bound. Note that the number of crowd labels corresponds to the cost, and thus, this is actually an upper bound about the minimal cost for crowdsourcing learning.

Overall, our theoretical study discloses how many crowd labels, to the least, should be acquired and how the labeling tasks should be allocated. Some of our results are validated empirically.

In the following we start with preliminaries and then present our main results, followed by experiments and conclusions.

2 Preliminaries

In the machine learning community, crowdsourcing is often used to collect labels for training data. Then, a model is learned with these crowd-labeled instances. We call such a process as crowdsourcing learning. For convenience, we first give some definitions for crowdsourcing learning.

Definition 1 (The Ground-Truth Label, Crowd Label and Aggregated Label). For a labeling task, an instance has an unknown true label called the ground-truth label. The instance is labeled one or multiple times by a crowd. Every single label given by a crowd is called a crowd label. The label inferred from these crowd labels is the aggregated label. A high-quality aggregated label disagrees with the ground-truth label with low probability. In other words, the error rate of a high-quality aggregated label is small.

Crowdsourcing could be divided into two steps. The first step (the crowdsourcing step) is distributing instances to a crowd and inferring the aggregated label from crowd labels. The second step (the learning step) is learning a model with crowd-labeled instances. We regard the total payment to the crowd as the cost of crowdsourcing learning.

2.1 The Crowdsourcing Step

In the crowdsourcing step, we have to ensure that high-quality aggregated labels can actually be induced from crowd labels and this process should be cost-saving compared with employing experts to get labels.

Given an instance, n crowd labels Y1↪ Y2↪ · · · ↪ Yn are collected. These crowd labels are independent and identically distributed. These labels have K possible values, where K ≥ 2, that is, the label space Y = ¶0↪ 1↪ · · · ↪K - 1♦. For every i 2 ¶1↪ 2↪ · · · ↪ n♦, Yi is distributed as

that is, Pr[Yi = j] = qj. Without loss of generality, we assume that the ground-truth label j ⇤ 2 ¶0↪ 1↪ · · · ↪K - 1♦. Moreover, to guarantee crowdsourcing to be viable, it is assumed that 8j 6= j ⇤ ↪ j 2 ¶0↪ 1↪ · · · ↪K - 1♦, we have qj ⇤ > qj. The assumption is reasonable since it simply implies that the ability of the crowd is better than a totally random behavior.

For simplicity, we adopt the majority voting strategy to induce the aggregated label. Let nj denote the number of valuej labels in the n crowd labels. Then, for the aggregated label ˆ Y , we have

To illustrate the label quality issue clearly, we consider the binary case first, that is, K = 2. We designate p = qj ⇤ as the crowd qualification. In this case, p is the probability that a sample of crowd labels is correct in the sense of average and p > 12 . Let Zi be an indicator variable:

To avoid ending in a tie, here we assume that n is an odd integer. The aggregated label disagrees with the ground-truth label with probability ⌘ = Pr ⇥ 1n Pni=1 Zi  12 ⇤, where the expectation E[Zi] = p, and the variance D[Zi] = p(1 - p). By the central limit theorem (CLT), the error rate of the aggregated label satisfies

where Φ(·) is the cumulative distribution function of the standard normal distribution:

To show the functional relationship among p, n and ⌘ clearly, Figure 1 is plotted according to (6). It shows that the error rate of the aggregated label is controlled by the number of crowd labels in the crowdsourcing step.

In the following pages, unless with definite declaration, we will only talk about the binary case.

2.2 The Learning Step

In the learning step, crowd-labeled instances will be given as training data of a learning algorithm. In this case, what we actually care about is the model learned with the crowdlabeled training data instead of the label quality of training data themselves. The issue is how the performance of the learned model is influenced by crowdsourcing and then how crowdsourcing should be used for learning.

A classic learning problem is described as below. H is a set of functions, of which the domain is X and the range is Y. H is called the hypothesis class and every member in H is called a hypothesis. D is an unknown distribution over X and f is an unknown function X ! Y. For simplicity, it is assumed that f 2 H, which is called the realizability assumption. A learner is given access to an oracle EX(f↪ D), which outputs instances one at a time randomly and independently according to D and labels them by f. The task is to identify f in H.

S = ((x1↪ y1)↪ · · · ↪ (xm↪ ym)) is a finite sequence in X ⇥ Y. This is the learner's input and is generated by m calls of EX(f↪D). S is also known as the training data or the training set. The learner's output is hS 2 H. To measure the success of the learner, we define the true error of a function h : X !Y, to be

which is the probability that h disagrees with f on distribution D. In the best case, hS agrees with f in the whole domain, that is, L(D↪f)(hS) = 0.

Since D and f are unknown to the learner, the true error is not available. We can not identify f directly by comparing the true error of different hypotheses. Instead, empirical risk minimization (ERM) is a common learning paradigm generating a hypothesis h that minimizes the training error

which is the proportion of cases where h disagrees with f on the training data S. Since the sequence S is drawn from EX(f↪D), intuitively, if a hypothesis h performs pretty well on a large S, the true error of h could be small with high probability.

Nonetheless, in crowdsourcing learning, labels of training data are inferred from crowd labels in the crowdsourcing step. The aggregated labels induced from the crowd labels are not always identical to the ground-truth label. In this case, we have no access to EX(f↪D). Instead, we assume that the training data are generated by a noisy oracle EX⌘(f↪D). EX⌘(f↪ D) generates an instance by first drawing an instance (x↪ y) from EX(f↪D) and then flipping the label y with probability ⌘. EX⌘(f↪D) is weaker than EX(f↪D), since EX⌘(f↪ D) does not know the ground-truth label.

In the learning step, we learn a model with access to EX⌘(f↪ D). The label generated by EX⌘(f↪ D) corresponds to the aggregated label and ⌘ is the error rate of the aggregated label. ⌘ could be controlled in the crowdsourcing step by changing the number of crowd labels per instance. The total number of crowd labels used corresponds to the cost of crowdsourcing learning. Since our focus is the cost-saving effect of crowdsourcing learning, the number of crowd labels required in the whole process lies at the heart of the problem.

3 Main Results

Theorem 1. Let H be a finite hypothesis class. Let δ↪ ✏ 2 (0↪ 1), p 2 ( 12 ↪ 1), γ = 2p - 1 and let m0 be an integer that satisfies

where

Then, for any labeling function f and for any distribution D, for which the realizability assumption holds, given i.i.d. sampled instances which will be labeled repeatedly by a crowd with crowd qualification p, we have that m0 crowd labels are sufficient to learn a hypothesis h which holds that

Remarks: Theorem 1 is the main theoretical result of this paper. Literally speaking, it shows that, for a sufficiently large m, m crowd labels are sufficient to learn a model which is probably (with confidence 1 - δ) approximately (up to an error of ✏) correct (PAC) for the crowdsourcing learning task. In other words, given a crowdsourcing learning task, one must collect at least a number of crowd labels for PAC learning; we call this number as the "minimally-sufficient" number. In addition, Theorem 1 presents an upper bound for the minimallysufficient number. Note that the number of crowd labels corresponds to the cost, and thus, this is actually an upper bound about the minimal cost for crowdsourcing learning.

As will be shown in the proof to Theorem 1, ⌘b denotes the upper bound for the error rate of aggregated labels in the crowdsourcing step. In the crowdsourcing learning setting, ⌘b is adjustable by controlling the number of crowd labels per instance. Different ⌘bs correspond to different allocation schemes for crowd labels. To ensure a small ⌘b, more crowd labels per instance are required in the crowdsourcing step, while less instances will be required in the learning step. It is a trade-off between the number of crowd labels per instance and the number of instances for the crowdsourcing learning task. Note that

and let

where x 2 (0↪ 12 ). The functional relationship is plotted in Figure 2, and ⌘⇤ b is the minimum point of the function, that is,

Theorem 1 indicates ⌘⇤ b could be a good choice for ⌘b to reduce the number of crowd labels required. In this sense, Theorem 1 sheds a light on how to allocate crowd labels in order to save the total cost in crowdsourcing learning. Generally speaking, it inspires us to choose an appropriate ⌘b for the quality of aggregated labels by specifying the number of crowd labels per instance. To be specific, if aggregated labels are of poor quality, we should increase the number of crowd labels per instance rather than labeling more fresh instances; if a single crowd label or the aggregated label performs well enough, it is preferable to label more fresh instances.

Before presenting the proof to Theorem 1, we need to introduce some lemmas.

Lemma 1. Given an instance with n crowd labels independently and identically distributed according to parameters q = [q0↪ q1↪ · · · ↪ qK-1], where the ground-truth label j ⇤ 2 ¶0↪ 1↪ · · · ↪K - 1♦, and γ = minj6=j ⇤ qj ⇤ - qj > 0, for the error rate of the aggregated label to be upper-bounded by ⌘b, it is sufficient that

Proof. Let Z j1↪j2 i be an indicator variable such that

of which the support is [-1↪ 1] and the expectation E hZ j1↪j2 i i = qj1 - qj2 . When adopting the majority voting strategy, the error rate of the aggregated label ⌘ satisfies:

To upper-bound ⌘ with ⌘b, by (23), we have

Corollary 1. In the binary case, given an instance with n crowd labels independently and identically distributed according to the crowd qualification p, where p > 12 and γ = 2p - 1, for the error rate of the aggregated label to be upper-bounded by ⌘b, it is sufficient that

Proof. It is a corollary of Lemma 1. By setting K = 2, p = qj ⇤ and γ = 2p - 1, we have this corollary in the binary case.

Lemma 1 and Corollary 1 show that high-quality aggregated labels can actually be inferred from crowd labels. Specifically, the error rate of the aggregated label converges linearly to 0 with the number of crowd labels n, and the parameter γ (related to the crowd qualification p in the binary case) determines the rate of convergence. Similar results have been achieved [Wang and Zhou, 2015] under different assumptions [Dawid and Skene, 1979]. It is interesting to see that it is very similar to some theoretical results in ensemble learning which generates predictions by combining multiple weak learners [Zhou, 2012], suggesting that crowdsourcing learning might get inspirations from ensemble learning.

In general, labels given by experts cost much more than crowd labels. If the crowdsourcing step is indeed cost-saving, it is preferable to collect crowd labels to induce high-quality aggregated labels rather than employing experts for labeling.

It is significant to investigate to what extent the crowdsourcing step is cost-saving. For convenience, we assume that the number of crowd labels n is an odd integer. In this case, the error rate of the aggregated label is exactly

Let ccr and cem denote the cost per crowd label and the cost per label given by experts respectively. Let ⌘⇤ denote the error rate that experts can achieve. In the crowdsourcing step, ⌘⇤ is the required error rate of the aggregated label and it is expected to ensure that ⌘  ⌘⇤ . Let ncr denote the minimum number of crowd labels to satisfy ⌘  ⌘⇤ . Specifically,

In this case the crowdsourcing step is cost-saving if and only if

The values of p, ⌘⇤ , ccr and cem jointly determine whether (28) is satisfied.

The functional relationship between ncr and ⌘⇤ for different p is shown in Figure 3 according to (27).

As Figure 3 shows, given an instance, as long as the labeling of the crowd is better than totally random behavior, which means p > 12 , the error rate of the aggregated label converges to 0 with the number of crowd label n. In addition, the rate of convergence determined by the crowd qualification p is also very important for the number of required crowd labels and thus important for the cost of the crowdsourcing step. For example, given ⌘⇤ = 0▷05, if p = 0▷65, we have ncr = 29; while if p = 0▷55, we have ncr = 269. In the first case, if the crowd label price ccr is relatively small, the crowdsourcing step is cost-saving. In the second case, it is hard to make similar conclusions. Generally speaking, only if crowd labels are cheap and perform well enough, the crowdsourcing step is cost-saving.

In the learning step, if ground-truth labels are available, some number of training instances are enough for PAC learning as follows.

Lemma 2 ([Blumer et al., 1986]). Let H be a finite hypothesis class. Let δ↪ ✏ 2 (0↪ 1) and let m be an integer that satisfies

Then, for any f and D, for which the realizability assumption holds, given a sequence S of size m generated by EX(f↪ D), if a hypothesis h 2 H satisfies that LS(h) = 0, we have

However, in crowdsourcing learning, only the aggregated labels are available. The learner has access to EX⌘(f↪D) rather then EX(f↪D). For a function h : X ! Y, let the true error L(D↪f)(h) be abbreviated as `(h) and let `0 (h) denote the probability that a labeled instance from EX⌘(f↪D) disagrees with h. Then, we have

If ⌘ < 12 , `0 (h) is monotonically increasing with `(h). The relationship between ` and `0 suggests that some number of training instances could still be enough for PAC learning with access to EX⌘(D↪ f) as below.

Lemma 3 ([Angluin and Laird, 1987]). Let H be a finite hypothesis class. Let δ↪ ✏ 2 (0↪ 1), ⌘b 2 (0↪ 12 ) and let m be an integer that satisfies

Then, for any f and D, for which the realizability assumption holds, given a sequence S of size m generated by EX⌘(f↪ D), where ⌘  ⌘b, if a hypothesis h 2 H minimizes LS(h), we have

Lemma 3 shows that although the aggregated labels are not ground-truth, the ERM rule over a finite hypothesis class will still be probably (with confidence 1 - δ) approximately (up to an error of ✏) correct (PAC). In other words, a wellperformed model can actually be learned with crowd-labeled training data.

It is noteworthy that Lemma 3 is originally a theoretical result for the label noise setting. However, in the crowdsourcing learning setting, unlike in the label noise setting, ⌘b is adjustable by changing the number of crowd labels per instance. Estimating the noise rate is a challenging task in the label noise setting [Menon et al., 2015; Liu and Tao, 2016], but beyond the scope of this paper. For the moment, we just explore the effect of ⌘b on the cost for crowdsourcing learning while ignoring the estimation of ⌘b.

Corollary 1 shows how many crowd labels per instance are enough to make the error rate of the aggregated label to be upper-bounded by ⌘b and Lemma 3 shows that with the upper bound ⌘b Now we can give the proof to Theorem 1.

Proof to Theorem 1. Given ⌘b, Corollary 1 gives the upper bound of the minimally-sufficient number of crowd labels per instance, that is,

Lemma 3 gives the upper bound of the minimally-sufficient number of crowd-labeled instances, that is,

By (35) and (36), the sufficient number of crowd labels is

where ⌘b 2 (0↪ 1-p]. See ⌘b as a variable and minimize (38), then we have (11).

4 Experiments

To verify our theoretical results of Theorem 1, we design some experiments following an empirical study on repeated labeling [Sheng et al., 2008].

Two real-world datasets 1 are adopted, of which the dataset Mushrooms has 112 features and 8124 instances, while the dataset Splice has 60 features and 3175 instances. For each dataset, 30% of instances are used as testing data and the others as a pool from which instances are sampled for training. A training instance is labeled one or multiple times. These labels are independent and identically distributed. Each label is identical to the ground-truth label with probability p. We adopt the majority voting strategy to induce aggregated labels of training data.

We devise four ways to allocate crowd labels, of which the numbers of crowd labels per instance are [1↪ 5↪ 9↪ 15] respectively and the total number of crowd labels is fixed to be 1800. The issue in the experiments is whether it is worthwhile to label an instance multiple times rather than labeling more fresh instances.

J48 decision trees in Weka [Witten and Frank, 1999] are used in our experiments, and results on Mushrooms and Splice are shown in Figure 4. Testing accuracy values are calculated on testing data with ground-truth labels. Average results from 20 random partitions for testing data are reported.

1 http://www.csie.ntu.edu.tw/⇠cjlin/libsvmtools/datasets/

We discuss in detail about the results on the dataset Mushrooms as an example to demonstrate the experimental results clearly.

• ÷ p = 0▷9. A single crowd label performs pretty well. Labeling an instance multiple times is a waste compared with labeling more fresh instances.
• ÷ p = 0▷7. A single crowd label performs well. Labeling an instance several times is appropriate. However, as the number of crowd labels per instance increases, the gain of performance brought by repeated labeling is reduced. When the quality of the aggregated labels is good enough, labeling more fresh instances is preferable.
• ÷ p = 0▷6 and p = 0▷65. A single crowd label is of poor quality. We have to label an instance multiple times to improve the quality of aggregated labels.

As to the dataset Splice, similar results are presented as well, as observed in Figure 4. Moreover, some related empirical results can be found in some previous work [Sheng et al., 2008; Ipeirotis et al., 2014].

5 Conclusion

In this paper, we theoretically investigate some basic issues about crowdsourcing learning. In particular, we present an upper bound for the minimally-sufficient number of crowd labels, i.e., the minimal cost required for effective crowdsourcing learning. Our theoretical results also shed a light on how to allocate crowd labels for cost-saving.

This is a very preliminary attempt for the theoretical foundation of crowdsourcing learning. Further studies about more complex assumptions and labeling strategies are desired for future work.