On the Cost Complexity of Crowdsourcing

1 Introduction

Crowdsourcing provides an effective means for solving many real-world problems, e.g. labeling training data for machine learning. As crowdsourcing workers are normally nonexperts, the individual contributions from one worker can be unreliable. In practice, task redundancy is commonly used to amortize the unreliability in crowdsourcing with extra costs.

Many efforts [Ho et al., 2013; Roy et al., 2015; Yu et al., 2017; Tran-Thanh et al., 2013] have been made to obtain high quality results with as few costs as possible, where the quality is often measured with the result error rate and the costs are evaluated with the times of querying humans. To evaluate the effectiveness of the proposed methods, prior works mainly employ experimental analysis. However, the same methods often exhibit contradicting results in different experiments [Liu et al., 2012; Zhou et al., 2015; Li and Liu, 2015]. For instance, [Zhou et al., 2012] shows that the Dawid & Skene (DS) model [Dawid and Skene, 1979] outperforms majority voting (MV) in terms of result accuracy while [Han et al., 2016] presents exactly reverse results in tasks for acquiring specific knowledge. [Liu et al., 2012] demonstrates that the homogeneous DS (HDS) model [Raykar et al., 2010] is better than MV in bluebird dataset while MV is better than HDS in rte and temp. Therefore, empirical analysis is not a reliable means to evaluate crowdsourcing methods for general cases, which calls for theoretical research to overcome such limitations. In this regard, the NSF computing division [Wing, 2008] considers the development of theoretical tools for systems involving human computation as one of the five major challenges that today's computing faces.

∗Corresponding author

Inspired by the theorectical computer science, some efforts [Shahaf and Amir, 2007; Kulkarni, 2011] concern the theoretical models involving humans in computation. [Shahaf and Amir, 2007] presents a Human-Assisted Turing Machine (HTM) that models the hybrid computation paradigm with machines and humans. Basing on HTM, the authors discuss how to measure human efforts such as the times and size of human input so as to define the algorithm and problem complexity, but they do not consider the unreliability of workers or the trade-off of costs and quality in crowdsourcing. Furthermore, [Kulkarni, 2011] discusses the importance of building a theoretical model of computation involving humans in terms of algorithm evaluation, algorithm comparison and cost quantification. Another line of theoretical research efforts [Li and Liu, 2015; Wang and Zhou, 2016; Gao and Zhou, 2016; Gao et al., 2016] focus on estimating the upper bound on the mean error rate of specific algorithms. [Li and Liu, 2015] gives the upper bound on the mean error rate with weighted majority voting (WMV). [Wang and Zhou, 2016] theoretically analyzes the costs and the result error rate of MV. And [Gao and Zhou, 2016; Gao et al., 2016] theoretically studies the performance of the DS model, but ignores the parameter learning that can greatly affects the result accuracy. [Nushi et al., 2015; Venanzi et al., 2014] addresses the parameter learning issue in the context of data sparsity, which is helpful for better algorithm designing. In summary, although existing efforts recognize the importance of theoretical models in human participant computation systems like crowdsourcing, few provide general theoretical methods for crowdsourcing.

In this work, motivated by the classical computational complexity, the sample complexity and the PAC theory in machine learning [Balcan et al., 2010], we study a general theoretical approach to understanding the complexity of crowdsourcing that is affected by multiple interplaying factors such as number of workers, worker ability and aggregation methods. Specifically, we propose the cost complexity of crowdsourcing to theoretically address the trade-off of costs and quality in crowdsourcing. We argue that like computational complexity, the cost complexity of crowdsourcing is useful for evaluating, comparing and designing of algorithms, measuring the complexity of crowdsourcing problems and etc.

Our major contributions are as follows:

• We define the cost complexity of crowdsourcing, which measures how many costs are needed to meet certain quality requirements. To the best of our knowledge, this is the first effort to give a formal definition of the crowdsourcing complexity that relates costs with quality.
• We give two theorems that can derive the cost complexity of general crowdsourcing. For a specific crowdsourcing algorithm, our method not only can give the theoretical upper bound on the mean error rate, but can estimate how many workers to hire for achieving a certain quality objective. Following the theorems, we also obtain a set of corollaries that have been verified in existing work.
• Through a set of case studies, we have verified our method through theoretical analysis and experimental evaluation on real-world datasets. The outcome explains the contradicting results in previous work. For instance, when each worker completes more than 1 (ηMV-ηHDS )2 ln 2|H| δ ) tasks, HDS will outperform MV; otherwise, MV is better.

2 Overview of CrowdsourcingWorkflows

Fig.1 shows the general framework of crowdsourcing workflows consisting of task allocation and result inference.

2.1 Task Allocation

Task allocation involves worker pool construction and task assignment. First, a high-quality worker pool can be built by filtering out low-ability workers with qualification tests [AMT, 2017; Ipeirotis and Gabrilovich, 2014; Marcus et al., 2015] or by analyzing historical logs [Jung, 2014; Ambati et al., 2011]. Then the distribution of the workers in worker pool over ability can be obtained through qualification tests or log analysis by statistical methods. For instance, Quizz [Ipeirotis and Gabrilovich, 2014] obtains the Beta distribution of worker ability with qualification tests. Next, in task assignment, a task is assigned to a certain number of workers selected from the work pool with a specific strategy. Then with the constructed worker pool and the adopted task assignment strategy, we can obtain the distribution of participating workers over ability (denoted by W) in task processing. And for result inference, W can be considered the prior knowledge.

Assume that there are m workers and n tasks. We denote the ground truth set by Y = {yj|0 < j < n}, and the truth answer to task j by yj that takes on a value in a candidate answer set A = {0, · · · , K - 1}. Let X = {xij |i ≤ m, j ≤ n} be the answer set of n tasks from m workers, xij be the answer given by worker i to task j, and Xj denote the answer set of task j. We use the confusion matrix in (1) to characterize workers' abilities.

which satisfies ∑Ll=1 πij kl = 1. Given yj = k, xij is generated by a multinomial distribution with πij k∗ = (πij k1 , · · · , πij kL). Thus the three-dimensional matrix π(i) = [πij kl ] denotes the abilities of worker i in all tasks. After task allocation, we may not know π, but we can know its distribution W.

2.2 Result Inference

Result inference is to infer the truth result of a task by aggregating the answers. There are mainly two lines of work. 1) Voting. Majority voting, as the simplest voting method, infers the final result by simply counting the votes for each alternative answer [Snow et al., 2008; Ipeirotis and Gabrilovich, 2014]. Though simple, it suffers from being error-prone due to the ignorance of the difference of workers' abilities and other parameters. In light of this, weighted majority voting [Li and Liu, 2015] incorporates workers' abilities into majority voting. Specifically, it assigns different weights to votes according to workers' abilities that are unknown parameters. 2) Probabilistic approach. Probabilistic generative models containing unknown parameters (e.g. worker ability) are employed to specify workers' performance on tasks, and then the parameters are estimated (parameter learning), finally the answers are aggregated through model inference, e.g. inferring the final result by using EM algorithm for parameter estimation of probabilistic generative models [Dawid and Skene, 1979; Raykar et al., 2010; Salek et al., 2013].

Without loss of generality, we define a unified aggregation function f : A|Xj| →A as follows:

where Asj(i, k, xij) is the aggregation score when worker i gives answer xij ∈ A to task j the ground truth of which is k ∈ A. (2) is a universal representation of result inference. For majority voting, we have Asj(i, k, xij) = I(xij = k), where I(·) is an indicator function; and for weighted majority voting, Asj(i, k, xij) = viI(xij = k), where vi is the weight of worker i which can be obtained with machine learning. In probabilistic methods (e.g. DS model), Asj (i, k, l) = log πij kl (we use l to mark xij), where πij kl ∈ π(i) denotes the worker ability that needs to be estimated with machine learning.

Let D denote the distribution of the ground truth among the candidate answers. We define the loss function to measure the mean error rate of f as follows:

However, to evaluate the effectiveness of f, we first need to learn the unknown parameters in f. Straightforwardly, the more workers' answers we have, the better we can learn the parameters of f , which is exactly what sample complexity addresses. In computational learning theory, probably approximately correct (PAC) learning is a framework for mathematical analysis of the sample complexity of machine learning algorithms. H is a set of answer aggregation functions with different parameters, the input and output of which are X and Y respectively. H is called the hypothesis class and every member in H is called a hypothesis. f is an unknown answer aggregation function f : A|Xj| →A. For simplicity, it is assumed that f ∈ H, which is called the realizability assumption. A learner is given access to an oracle EX(D,W, f), which outputs aggregated answers one at a time randomly and independently according to D, W and f. The goal is to learn f from H so that the corresponding parameters can be correctly learned.

S = (X1,X2, · · ·Xn) is a finite sequence of answers set for all tasks. This is the learner's input and is generated by n calls to EX(D,W, f). The learner's output is h ∈ H, h is the answer aggregation function with the estimated value of parameters. To measure the effectiveness of the learner, we define the error of a function h as follows:

(4) denotes the probability that h disagrees with f on distribution D and W. Ideally, h agrees with f in the whole domain, namely, L(D,W,f)(h) = 0. That is to say the unknown parameters are accurately learned, and the final error rate only depends on answer aggregation function. For instance, majority voting can be viewed as such a special case, where all parameters are known in f.

3 The Cost Complexity of Crowdsourcing

We use the terminology, cost complexity, to denote the costs of solving a crowdsourcing task. Specifically, it measures the number of task requests for human workers. Different from the traditional computational complexity, the cost complexity of crowdsourcing is closely related to the quality requirement and workers' abilities. This section introduces two formal definitions of the cost complexity of crowdsourcing given a certain quality constraint on the mean error rate and the distribution over workers' abilities.

Let U denote the set of workers selected by task allocation. Definition 1. If there is a learning algorithm A(m′ , n′ , δ) that outputs an aggregation function h and three values ηU ∈ R, ϵn′ ∈ R, ηm′ ∈ R after making at most c (c = m′ × n′ ) task requests, such that for any answer aggregation function f ∈ H, ϵ ∈ (0, 1/2), η ∈ (0, 1/2), δ ∈ (0, 1/4), for any m′ ≥ 0, any worker set U, we have P{L(D,W,f)(h) ≤ ϵn′} ≥ 1 - δ and L(D,W,Y)(f) ≤ ηU; and for any ηm′ = exp(EW(ln(ηU )) and c ≥ OW (ϵ, δ, f, η),

Then we call OW (ϵ, η, δ, f) the cost complexity of crowdsourcing with worker distribution W over abilities.

Essentially OW measures how many answers should be solicited from workers for learning an aggregation function and infering the final crowdsourcing results accurately. ϵn′ and ηm′ respectively specify the error rate bounds of the parameter learning of the aggregation function f and the aggregated results. ηU is the error rate bound of the aggregated results determined by the worker set U and is related to ηm′ . Actually OW borrows the concept of sample complexity from machine learning. OW depends on m′ , the total number of workers, and n′ , the number of tasks a worker completes.

A special case of Definition 1 is when all workers exhibit the same ability w, which is not unusual because many microtasks do not require much expertise and all workers can fulfill the tasks. For this case, we define Ow as follows:

Definition 2. If there is a learning algorithm A(m′ , n′ , δ) that outputs an aggregation function h and two values ηm′ ∈ R, ϵn′ ∈ R after making at most c (c = m′ × n′ ) task requests, such that for any answer aggregation function f ∈ H, ϵ ∈ (0, 1/2), η ∈ (0, 1/2), δ ∈ (0, 1/4), for any m′ ≥ 0, n′ ≥ 0, we have P{L(D,w,f)(h) ≤ ϵn′} ≥ 1 - δ, and L(D,w,Y)(f) ≤ ηm′ ; and for any c ≥ Ow (ϵ, δ, f, η), we have

Then we call Ow (ϵ, η, δ, f) the cost complexity of crowdsourcing with identical workers' ability w.

From Definition 2, we know that ηm′ and ϵn′ only depends on m′ and n′ respectively. A simple scenario is when f has no unknown parameters (e.g., MV), which means L(D,w,f)(h) = 0 always hold. In that case, c only depends on m′ , and OW only depends on ηm′ .

Note that our cost complexity specifies the max number of workers needed to achieve an error rate bound. In other word, c is at least OW , but we do not require workers complete the same number of tasks. n′ can be regarded as the min number of tasks a worker must complete. In reality, if a worker completes over n′ tasks, the practical cost is less than that given by the cost complexity for a quality constraint.

4 Main Results

The cost complexity is closely related to the quality requirements measured by error rate ηm′ and ϵn′ . This section first presents Theorem 1 and Theorem 2 to compute OW and the upper bound on the error rate respectively, which are the main contributions of this work.

Theorem 1. Given a task j (1 ≤ j ≤ n) processed by m workers, we can obtain an answer set Xj = {xij|i ≤ m}. For simplicity, we use l to mark xij. Worker i has ability πij = [πij kl ] when processing task j, πij kl is the performance when worker i processes task j the truth answer of which is k ∈ A. Let f(Xj) denote the aggregation method. Then the complexity OW can be computed as follows:

where µi = ∑l πij kl (Asj(i, g, l) -Asj(i, k, l)) is a value specific to worker i, Asj(i, g, l) ∈ [a, b], and g represents any alternative answer other than the truth (i.e. g ̸= k), and DW(µi) and EW(µi) are the variance and expectation of µi respectively.

Remarks. This theorem provides a theoretical means to estimate how many queries of human workers should be made for meeting certain quality requirements. Its benefits are three-fold. First, given a set of workers with distribution W of workers over ability, Theorem 1 can be used to compare the performance of two result aggregation functions. Second, given a result aggregation function, Theorem 1 helps evaluate the performance of different task allocation methods. Third, when both task allocation and result aggregation methods are given, Theorem 1 can estimate how many workers should be hired. In all, Theorem 1 provides a fundamental tool for designing and evaluating general crowdsourcing solutions.

OW depends on the error rate bounds ( ηU and ϵn′ ) of result inference and the parameter learning of the aggregation function. To prove Theorem 1, we first give Theorem 2 that analyzes the error rate bound of result inference.

Theorem 2. For the crowdsourcing tasks described in Theorem 1, the error rate of the aggregated results can be upperbounded as follows:

where K is the size of the answer set A.

Proof. First, we give a general function to denote an aggregation process.

Let Asj(i, k, l) ∈ [a, b], Z gk i = Asj(i, g, l) -Asj(i, k, l), then Z gk i ∈ [a - b, b - a] and the expectation is µi = ∑l πij kl (Asj(i, g, l) -Asj(i, k, l)). First we apply the union bound to get (9) and obtain (10) with Hoeffding's inequality. We get the error rate bound as follows:

Theorem 2 provides a general method to compute the upper bounds of error rates ηU in an aggregation function with the worker set U. Except for result inference, task allocation determines worker distribution W and can greatly affect the crowdsourcing results, and this is what Theorem 1 addresses on the basis of Theorem 2.

For identical worker abilities, we can generalize Theorem 2 to obtain Corollary 1 given in [Wang and Zhou, 2016].

Corollary 1. Given m′ workers whose abilities are i.i.d. according to parameters q = [q0, q1, · · · , qK-1], the groundtruth label i∗ ∈ {0, 1, · · · ,K - 1} and γ = mini̸=i∗(qi∗ - qi) > 0. For the error rate of the aggregated results to be upper-bounded by η, it is sufficient that

We can further generalize Theorem 2 by using the weighted majority voting (WMV) with weight K ˆwi - 1 as the aggregation function. Then we can obtain Corollary 2 that is given in [Li and Liu, 2015].

Corollary 2. For a set of m workers U, using the weighted majority voting with weights K ˆwi - 1, aggregation result ˆ yj of task j. And an unbiased estimator of the workers' ability E( ˆwi) = wi that satisfies {wi}i≤K-1. If the workers' labels are generated independently according to the following probability:

Then we have

With Corollary 2, we can learn that weighted majority voting can achieve the same error rate as majority voting if the weight (worker ability) is a constant value.

However, if workers' abilities are unknown, analyzing the weighted majority voting entails considering the parameter learning process. In practice, the parameter learning is indispensable for many aggregation methods. And it is difficult to learn the unknown parameters 100% accurately due to the limitation of dataset and machine learning algorithms.

Regarding Definition 1, OW involves parameter learning which also affects the error rates of aggregation method with estimated value of unknown parameters. Thus, we use PAC learnability to analyze the mean error rate of aggregation methods. First, we formulate the error rate of inferred results by considering parameter learning.

where L(f,Y) and L(h,f) are the abbreviations of L(D,W,Y)(f) and L(D,W,f)(h) respectively. In some special cases, some aggregation methods, such as majority voting, do not entail parameter learning due to the absence of parameters in their aggregation rules. In this case, err(h) is identical to L(f,Y).

To prove Theorem 1, we still need to introduce the Valiant's PAC (Lemma 1) to compute n′ for achieving the error rate ϵn′ of parameter learning.

Lemma 1. [Angluin and Laird, 1988] Let H be a finite hypothesic class, let δ, ϵ ∈ (0, 1), η ∈ (0, 12 ) and let n′ be an integer that satisfies

Then, for any f and D, for which the realizability assumption holds, given a sequence S of size n′ , if a hypothesis h ∈ H minimizes err(h), we have

Although the parameter space can be infinite, the hypothesis space H is finite. For instance, given n tasks, m workers and answer set A(|A| = K), a hypothesis h ∈ H is actually a mapping from workers' answer set to a set of truth answers. Thus the size of the hypothesis space is |K|n at most. Then we can use VC theory [McAllester, 1998] to obtain |H|.

When each worker has the identical ability (i.e., w1 = w2, · · · ,wm), for task j, more than (b-a)2 2µ2i ln |L|-1 η workers can generate the error rate less than η with the respect to the aggregation rule, where µi = ∑Ll=1 πij kl (Asj (i, g, l) - Asj (i, k, l)). Next we employ PAC learnability to prove Theorem 1.

As for crowdsourcing tasks, the result aggregation method can be viewed as a process of machine Learning. The error rate is η, if the parameters are accurately learned. In particular, err(h) is affected by the error rate of aggregation rule η (i.e. err(h) = L(f,Y)) when the parameter learning process generates no error, i.e. err (Lh,f) = 0). Most existing literatures analyze the result aggregation rule with the impractical assumption that L(D,W,f)(h) = 0.

Proof of Theorem 1. Basing on Theorem 2, we set µi = ∑l πij kl (Asj(i, g, l) -Asj(i, k, l)). Workers' abilities vary with different workers in Definition 1. We can obtain

Since ηm′ = exp(EW(ln(ηU)) and ηm′ ≤ η in Definition 2, we can obtain

Based on the property of variance EW(∑mi=1 µi)2 - E2W (∑mi=1 µi) = DW(∑mi=1 µi), we get Since all workers come from the same worker pool following a certain distribution W over ability. Meanwhile, all EW(µi)s are equal, all DW(µi)s are fixed, and workers are independent of each other. Then we can get

It can be simplified as

Since the aggregation function contains parameters, we need parameter learning. Then based on Lemma 1, we get

Corollary 3. Let f(Xj) be the aggregation function of crowdsourcing for each task j (Asj(i, g, l) ∈ [a, b]), suppose all workers have identical ability π, then the cost complexity of crowdsourcing Ow can be computed as follows:

where w = ∑l πij kl (Asj(i, g, l) -Asj(i, k, l)) is the same for all workers.

This section mainly gives a general method to compute the cost complexity of crowdsourcing, which is determined by the distribution of worker over ability, the parameter learning and answer aggregation in result inference. Theorem 1 and 2, the major contributions of this work, provide a method to compute the cost complexity and the upper bound on the mean error rate respectively for general crowdsourcing workflows. Corollary 1-3 give some interesting results that are obtained by generalizing the two theorems to special cases.

Due to space limitation, the proofs of Corollary 1-3 are shared on the web 1 .

5 Case Studies

In this section, we aim at verifying the effectiveness of Theorem 1 through applying it to three representative result aggregation algorithms, including MV, WMV and HDS. Specifically, we conducted case studies both theoretically and empirically.

5.1 Theoretical Analysis

First, for MV, all parameters with f are known. In other words, h is equal to f. Then, we have Corollary 4.

1 Link to the proofs of Corollary 1-3: https://goo.gl/ZhKddo

·104

·104

Figure 3: The error rate analysis on dog dataset. Figure 3: The error rate analysis on dog dataset. Figure 3: The error rate analysis on dog dataset. Figure 3: The error rate analysis on dog dataset.

5.1 Theoretical analysis With HDS model, the workers' abilities are represented as Equation (12). Then, as for MV, there is no unknown parameters with f. In other words, h is equal to f, and there is no parameter learning process in the result inference. Moreover, c in Definition 1 depends on m′ (c = m′ ), and OW only depends on η. Then, we have Corollary 4. 5.1 Theoretical analysis With HDS model, the workers' abilities are represented as Equation (12). Then, as for MV, there is no unknown parameters with f. In other words, h is equal to f, and there is no parameter learning process in the result inference. Moreover, c in Definition 1 depends on m′ (c = m′ ), and OW only depends on η. Then, we have Corollary 4. 5.1 Theoretical analysis With HDS model, the workers' abilities are represented as Equation (12). Then, as for MV, there is no unknown parameters with f. In other words, h is equal to f, and there is no parameter learning process in the result inference. Moreover, c in Definition 1 depends on m′ (c = m′ ), and OW only depends on η. Then, we have Corollary 4. Corollary 4. Let µi = 1 - 2wi, then OW for MV f = argmaxk ∑mi=1 I(xij = k) is computed as follows: OW (ϵ,η, δ, f) = - (2 ln η K-1 ) - DW(µi) E2W (µi) . (17) Similarly, we can obtain Corollary 5 for WMV:

Corollary 4. Let µi = 1-2wi, then the cost complexity OW with MV f = argmaxk ∑mi=1 I(xij = k) can be computed as follows: Corollary 4. Let µi = 1-2wi, then the cost complexity OW with MV f = argmaxk ∑mi=1 I(xij = k) can be computed as follows: Corollary 4. Let µi = 1-2wi, then the cost complexity OW with MV f = argmaxk ∑mi=1 I(xij = k) can be computed as follows: Corollary 5. Let µi = wi(1-2wi), then OW for WMV (f = argmaxk ∑mi=1 wiI(xij = k)) is as follows:

Similarly, based on aggregation method argmaxk ∑i wiI(Zij = k) of WMV, we can obtain Corollary 5: Similarly, based on aggregation method argmaxk ∑i wiI(Zij = k) of WMV, we can obtain Corollary 5: Similarly, based on aggregation method argmaxk ∑i wiI(Zij = k) of WMV, we can obtain Corollary 5: E2W (µi) Furthermore, for HDS, we have Corollary 6:

Corollary 5. Let µi = wi(1 - 2wi), then the cost complexity OW with WMV (f = argmaxk ∑mi=1 wiI(xij = k)) can be computed as follows: Corollary 5. Let µi = wi(1 - 2wi), then the cost complexity OW with WMV (f = argmaxk ∑mi=1 wiI(xij = k)) can be computed as follows: Corollary 5. Let µi = wi(1 - 2wi), then the cost complexity OW with WMV (f = argmaxk ∑mi=1 wiI(xij = k)) can be computed as follows: Corollary 6. Let µi mark ln wi 1-wi (1-2wi), f(Xj) be the aggregation function of HDS, then OW is as below:

E2W (µi)

E2W (µi)

Furthermore, for HDS, we have Corollary 6: Corollary 6. Let µi mark ln wi 1-wi (1-2wi), f(Xj) be the aggregation function of HDS, then the cost complexity of crowdsourcing (OW ) can be computed as follows. OW (ϵ, η, δ, f) =- 2 ϵ2 (1-2η)2 ln( 2|H| δ ) × 2(ln η K-1 ) - DW(µi) E2W (µi) . (19) In Equation (13), there involve the two types of error rate including parameter learning and answer aggregation. Suppose we fix the number of workers processing one task, then we can obtain the the upper bound of error rate in answer aggregation function. As shown in Fig.2, we plot the upper bound on the mean error rate obtained theoretically from the three algorithms including MV, WMV and HDS. We can observe that the upper bound on the mean error rate in MV is stable (i.e. the error rate upper bound is ηMV ) varying Furthermore, for HDS, we have Corollary 6: Corollary 6. Let µi mark ln wi 1-wi (1-2wi), f(Xj) be the aggregation function of HDS, then the cost complexity of crowdsourcing (OW ) can be computed as follows. OW (ϵ, η, δ, f) =- 2 ϵ2 (1-2η)2 ln( 2|H| δ ) × 2(ln η K-1 ) - DW(µi) E2W (µi) . (19) In Equation (13), there involve the two types of error rate including parameter learning and answer aggregation. Suppose we fix the number of workers processing one task, then we can obtain the the upper bound of error rate in answer aggregation function. As shown in Fig.2, we plot the upper bound on the mean error rate obtained theoretically from the three algorithms including MV, WMV and HDS. We can observe that the upper bound on the mean error rate in MV is stable (i.e. the error rate upper bound is ηMV ) varying Furthermore, for HDS, we have Corollary 6: Corollary 6. Let µi mark ln wi 1-wi (1-2wi), f(Xj) be the aggregation function of HDS, then the cost complexity of crowdsourcing (OW ) can be computed as follows. OW (ϵ, η, δ, f) =- 2 ϵ2 (1-2η)2 ln( 2|H| δ ) × 2(ln η K-1 ) - DW(µi) E2W (µi) . (19) In Equation (13), there involve the two types of error rate including parameter learning and answer aggregation. Suppose we fix the number of workers processing one task, then we can obtain the the upper bound of error rate in answer aggregation function. As shown in Fig.2, we plot the upper bound on the mean error rate obtained theoretically from the three algorithms including MV, WMV and HDS. We can observe that the upper bound on the mean error rate in MV is stable (i.e. the error rate upper bound is ηMV ) varying In Equation (13), there involve two types of error rate including parameter learning and answer aggregation. Suppose we fix the number of workers processing one task, then we can obtain the upper bound of error rate in answer aggregation function. As shown in Fig.2, we plot the upper bound on the mean error rate obtained theoretically from the three algorithms including MV, WMV and HDS. We can observe that the upper bound on the mean error rate in MV is stable (i.e. the error rate upper bound is ηMV ) varying with the number of tasks processed by each worker. While the the error rate upper bound with WMV/HDS decreases as number of tasks grows, and WMV outperforms HDS. When the number of tasks processed by each worker is less than 1 (ηMV-ηWMV )2 ln 2|H| δ ( 1 (ηMV-ηHDS )2 ln 2|H| δ ), MV outperforms WMV/HDS, which well explains the contradicting results in existing work [Zhou et al., 2012] and [Han et al., 2016]. Note: as Corollary 4-6 can be proved by simply substituting the expectation and variance of the worker distribution over ability (i.e., (12)) into Theorem 1, we omit the proofs.

with the number of tasks processed by each worker. While the the error rate upper bound with WMV/HDS decreases as number of tasks grows, and WMV outperforms HDS. When the number of tasks processed by each worker is less than 1 (ηMV-ηWMV )2 ln 2|H| δ ( 1 (ηMV-ηHDS )2 ln 2|H| δ ), MV outperforms WMV/HDS, which well explains the contradicting results in existing experimental results [Zhou et al., 2012] and [Han et al., 2016]. Note: as Corollary 4-6 can be proved by simply substituting the expectation and variance of the worker distribution over ability (i.e., (12) into Theorem 1, we omit the proofs. 5.2 Experimental Analysis Here we present the experimental analysis of error rates with two real-world crowdsourcing datasets: dog [Zhou et al., 2012] and temp [Snow et al., 2008]. The maximum numbers of tasks processed by a worker are 345 and 462 respectively for the two datasets. For each dataset, we first divided the answers into subsets according to worker IDs, then varied the number of tasks that a worker processes. Next we inferred the results with three algorithms including MV, WMV and HDS, and we computed the corresponding error rate. The results are plotted in Fig.3 and Fig.4, which demonstrate similar trends to our theoretical analysis shown in Fig.2. with the number of tasks processed by each worker. While the the error rate upper bound with WMV/HDS decreases as number of tasks grows, and WMV outperforms HDS. When the number of tasks processed by each worker is less than 1 (ηMV-ηWMV )2 ln 2|H| δ ( 1 (ηMV-ηHDS )2 ln 2|H| δ ), MV outperforms WMV/HDS, which well explains the contradicting results in existing experimental results [Zhou et al., 2012] and [Han et al., 2016]. Note: as Corollary 4-6 can be proved by simply substituting the expectation and variance of the worker distribution over ability (i.e., (12) into Theorem 1, we omit the proofs. 5.2 Experimental Analysis Here we present the experimental analysis of error rates with two real-world crowdsourcing datasets: dog [Zhou et al., 2012] and temp [Snow et al., 2008]. The maximum numbers of tasks processed by a worker are 345 and 462 respectively for the two datasets. For each dataset, we first divided the answers into subsets according to worker IDs, then varied the number of tasks that a worker processes. Next we inferred the results with three algorithms including MV, WMV and HDS, and we computed the corresponding error rate. The results are plotted in Fig.3 and Fig.4, which demonstrate similar trends to our theoretical analysis shown in Fig.2. with the number of tasks processed by each worker. While the the error rate upper bound with WMV/HDS decreases as number of tasks grows, and WMV outperforms HDS. When the number of tasks processed by each worker is less than 1 (ηMV-ηWMV )2 ln 2|H| δ ( 1 (ηMV-ηHDS )2 ln 2|H| δ ), MV outperforms WMV/HDS, which well explains the contradicting results in existing experimental results [Zhou et al., 2012] and [Han et al., 2016]. Note: as Corollary 4-6 can be proved by simply substituting the expectation and variance of the worker distribution over ability (i.e., (12) into Theorem 1, we omit the proofs. 5.2 Experimental Analysis Here we present the experimental analysis of error rates with two real-world crowdsourcing datasets: dog [Zhou et al., 2012] and temp [Snow et al., 2008]. The maximum numbers of tasks processed by a worker are 345 and 462 respectively for the two datasets. For each dataset, we first divided the answers into subsets according to worker IDs, then varied the number of tasks that a worker processes. Next we inferred the results with three algorithms including MV, WMV and HDS, and we computed the corresponding error rate. The results are plotted in Fig.3 and Fig.4, which demonstrate similar trends to our theoretical analysis shown in Fig.2. 5.2 Emprical Analysis Here we present the experimental analysis of error rates with two real-world crowdsourcing datasets: dog [Zhou et al., 2012] and temp [Snow et al., 2008]. The maximum number of tasks processed by a worker are 345 and 462 respectively for the two datasets. For each dataset, we first grouped the answers into subsets according to worker IDs, then varied the number of tasks that a worker processes. Next we inferred the results with three algorithms including MV, WMV and HDS, and we computed the corresponding error rate. The results are plotted in Fig.3 and Fig.4. As the results presented here are about error rate instead of the upper bound on the error rate shown in Fig.2, the plots fluctuate with the increase of task amount, but they demonstrate similar trends to our theoretical analysis shown in Fig.2. Note in our experiments, for a specific number of tasks x, if a worker finishes over x′ (x′ > x) tasks, we will replace that worker with a group of simulated workers. Each simulated worker finishes x or (x′ mod x) tasks and the total number of tasks they finish is exactly x′ . For instance, for x = 10, if a worker finishes 23 tasks in reality, three workers who finishe 10, 10 and 3 tasks respectively will be generated. 6 Conclusion

6 Conclusion In this work, we study the computational complexity of general crowdsourcing workflows in terms of costs that are measured by the times of querying human workers. We first present an overview of general crowdsourcing workflows that mainly involve two steps including task allocation and result inference. Then borrowing the sample complexity from machine learning, we give two definitions of the cost complexity of crowdsourcing, i.e. OW and Ow , for different worker distribution over workers' abilities. Third, we present two theorems to provide a theoretical method to compute the cost complexity and the upper bound on the mean error rate respectively for general crowdsourcing workflows. We further generalize our theoretical results to special cases and obtain a set of corollaries that have been given in existing work. Finally, to verify the effectiveness of our methods, we present a set of case studies for three representative answer aggregation methods both theoretically and empirically, and the outcome explains the existing contradicting experimental results. In summary, our work benefits crowdsourcing in terms of designing and evaluating crowdsourcing solutions. 6 Conclusion In this work, we study the computational complexity of general crowdsourcing workflows in terms of costs that are measured by the times of querying human workers. We first present an overview of general crowdsourcing workflows that mainly involve two steps including task allocation and result inference. Then borrowing the sample complexity from machine learning, we give two definitions of the cost complexity of crowdsourcing, i.e. OW and Ow , for different worker distribution over workers' abilities. Third, we present two theorems to provide a theoretical method to compute the cost complexity and the upper bound on the mean error rate respectively for general crowdsourcing workflows. We further generalize our theoretical results to special cases and obtain a set of corollaries that have been given in existing work. Finally, to verify the effectiveness of our methods, we present a set of case studies for three representative answer aggregation methods both theoretically and empirically, and the outcome explains the existing contradicting experimental results. In summary, our work benefits crowdsourcing in terms of designing and evaluating crowdsourcing solutions. 6 Conclusion In this work, we study the computational complexity of general crowdsourcing workflows in terms of costs that are measured by the times of querying human workers. We first present an overview of general crowdsourcing workflows that mainly involve two steps including task allocation and result inference. Then borrowing the sample complexity from machine learning, we give two definitions of the cost complexity of crowdsourcing, i.e. OW and Ow , for different worker distribution over workers' abilities. Third, we present two theorems to provide a theoretical method to compute the cost complexity and the upper bound on the mean error rate respectively for general crowdsourcing workflows. We further generalize our theoretical results to special cases and obtain a set of corollaries that have been given in existing work. Finally, to verify the effectiveness of our methods, we present a set of case studies for three representative answer aggregation methods both theoretically and empirically, and the outcome explains the existing contradicting experimental results. In summary, our work benefits crowdsourcing in terms of designing and evaluating crowdsourcing solutions. This work studies the computational complexity of general crowdsourcing workflows. We first give two definitions of the cost complexity of crowdsourcing, i.e. OW and Ow , for different distribution over workers' abilities. Then we present two theorems to compute the cost complexity and the upper bound on the mean error rate respectively for general crowdsourcing workflows. We further generalize our theoretical results to special cases and obtain a set of corollaries that have been verified in existing work. Finally, to verify the effectiveness of our methods, we present a set of case studies for three representative answer aggregation methods both theoretically and empirically, which explains the existing contradicting experimental results. In all, our work benefits crowdsourcing in designing and evaluating crowdsourcing algorithms. Acknowledgements This work was supported partly by National Basic Research Program of China (973 Program) under Grant Nos. 2015CB358700 and 2014CB340304, partly by National Key Research and Development Program of China under Grant No.2016YFB1000804, and partly by National Natural Science Foundation under Grant No. 61421003.