Dynamic Task Allocation Algorithm for Hiring Workers that Learn

1 Introduction

Crowdsourcing has become a prevalent tool for outsourcing tasks with varying complexity. One of the most common type of crowdsourcing tasks is consensus tasks, where workers are asked to provide opinions which are then aggregated to predict the answer to a question. From the requester's perspective, the objective is to hire as few workers as possible to save on the cost while still generating accurate outputs from the aggregated opinions.

There exists a rich body of research that explored mechanisms for hiring the best workers. In most cases, such mechanisms assume that the quality of workers is fixed. In reality, workers can learn from experience and improve over time. Mechanisms that only select the top workers may end up with mediocre workers, by ignoring incoming workers with low initial quality but high learning potential; such a system is not optimal in the long run.

In this paper, we propose to model the learning process of crowd workers using hyperbolic learning curves, to estimate both their current quality as well as projected future improvement. Our work makes two contributions. First, through experimentation, we demonstrate that workers performing a complex consensus task-identifying sleep spindles, a particular kind of EEG pattern-do learn and improve over time.

Second, we introduce a dynamic hiring mechanism which allocates tasks to workers, not based on their current quality, but based on their learning potential. Results, from both simulation and crowdsourcing experiments involving the sleep spindle detection task, show that our algorithm can save cost, while achieving high accuracy.

1.1 RelatedWork

There are several strategies for improving the quality of consensus tasks in the absence of ground truth-one can hire more workers to redundantly perform the same task [Sheng et al., 2008; Lin et al., 2014], intelligently weigh workers based on their inferred expertise [Donmez et al., 2009; Raykar et al., 2010; Welinder et al., 2010], or hire a small group of top quality workers [Zhao et al., 2013; Li et al., 2014; Li and Liu, 2015; Carvalho et al., 2016]. Our approach follows the third strategy, except that our hiring algorithm uses not only current performance, but also learning potentials, as the criteria for choosing the "top" workers.

Prior work on hiring algorithms are centered on exploration-exploitation strategies that use some portion of the task budget to learn the quality of the available workers, then use the remaining budget to hire the best worker. For example, Tran-Thanh et al. introduces a hiring algorithm based on a variation of the multi-armed bandit model [TranThanh et al., 2014]; Donmez et al. presents a sequential Bayesian estimation algorithm that continuously tracks and selects the best labelers over time [Donmez et al., 2010]. Closest to our approach is Kamar et al. [Kamar et al., 2012; 2013; Kamar and Horvitz, 2015], which use machine learning to model agents' behaviour doing consensus tasks, and use this model to predict a candidate worker's behaviour. They model the series of hiring decisions as a Markov Decision Process, where the rewards are the system's belief in the correctness of the aggregate prediction from the hired workers minus the cost to hire those workers. Finally, there are also recent approaches for modeling the time-varying performance of workers [Jung et al., 2014]. In all these approaches, it is assumed that workers have a level of quality that may fluctuate between tasks, but remains relatively constant over time.

2 DoWorkers Learn?

In the first study, our goal is to establish whether workers exhibit learning behavior while performing consensus tasks, and whether we can model and predict their improvement using learning curves. In industrial engineering, prior work has shown that the quality of workers improve as they complete repetitive tasks [Adler and Clark, 1991; Vits and Gelders, 2002]. Such improvements are often modeled using learning curves-a mathematical description of worker's performance for repetitive tasks [Fioretti, 2007]. While numerous forms of learning curves have been proposed, we use the hyperbolic model in this work since it was designed to measure and predict each worker's percentage of correctly completed tasks in production scenarios [Mazur and Hastie, 1978]. This can be translated directly to our setting of crowdsourcing consensus tasks as the percentage of correctly predicted or labeled tasks. Additionally, there is strong evidence that the hyperbolic curve model is a well studied and validated model which outperforms many other models in terms of efficiency, stability, and robustness [Nembhard and Uzumeri, 2000; Anzanello and Fogliatto, 2007]. Our experimental results here provide support for this argument.

Let w be a worker with learning speed rw and prior knowledge pw. Then, the hyperbolic learning curve model states that the percentage of correct predictions worker w has made up till the x'th task (i.e. its cumulative quality) is defined as

Given Qw(x), we can calculate qw(x), the worker's quality (the probability of making a correct prediction) at task x as:

If rw and pw were known in advance, then computing Qw(x) and qw(x) would be straightforward. Instead, we approximate Qw(x) by estimating the number of correct answers each worker has provided so far (e.g., via comparison against ground truth data). To learn a model for Qw(x), we map a linear model to the data:

where Zw(x) = 1 1-Qw(x) , ↵w = 1 rw and βw = pw rw + 1, and use linear-regression tools to estimate the parameters of Zw(x), and thus estimate Qw(x).

Modeling workers' learning curves has two advantages. First, we can use the estimated rw's to rank workers by learning speed, and select the most promising ones to train. Furthermore, with Qw(x) and qw(x), we can estimate the probability a worker will make a correct prediction in future tasks, and use this information in our hiring decisions.

2.1 Crowdsourcing Study

To assess the goodness of fit of the learning curve model, we hired crowdworkers on Amazon Mechanical Turk to perform sleep spindle identification tasks [Warby et al., 2014]. A sleep spindle is a discrete, intermittent pattern appearing on sleepstudy EEG recordings, which neurologists use to identify particular sleep stages. A sleep spindle is identified based on its waxing/waning shape (i.e., like a diamond or football), frequency (i.e., oscillate at approximately 12-15 cycles per second), and duration (i.e., mostly between 0.5 to 1.0 seconds in length), and amplitude (usually slightly taller than the waves around it). The task of identifying sleep spindles is a fitting case study for our setting-it is straightforward enough that the crowdworkers are able to understand how to proceed just by reading the instructions, but the task is challenging enough that one would expect workers' performance to be low at the onset and improve with training and feedback.

After reviewing a brief instructions page, workers were provided with a sequence of 20 windows of EEG recording. We asked workers to identify all the sleep spindles in the recording by clicking and dragging boxes around them. After the worker submits each window, the system provides feedback, revealing the actual locations of the sleep spindles before showing the next window. All workers are given the exact same sequence of 54 windows and each window contains at least one sleep spindle. We removed workers who did not complete all 54 windows and workers who spent less than 10 minutes completing all tasks, which is less than 25% of the average time required to complete the task. After filtering, we have 10 workers whose data we used for our analysis. All the EEG recordings and ground truth sleep spindle identifications used in our experiment come from Devuyst's DREAMS Sleep Spindle Database [Devuyst et al., 2011].

The primary goal of this study is to assess whether the crowd as a whole is improving with experience, and the feasibility of using learning curves to model their improvement. For each annotation, we considered it to be correct if the bounding box overlapped with a ground truth identification. We measured each worker's quality using common metrics, such as precision, recall, F1 and F2 scores. We then computed a cumulative quality measure by aggregating workers' performance on a per window basis. Cumulative quality at the i-th task is computed by aggregating all reported sleep spindles from all 10 workers up to window i. This cumulative quality metric enables us to apply the learning curve model and avoid the sometimes drastic fluctuation in workers' taskto-task performance, thereby better modeling the general per-

(b) Worker-level learning curves (cumulative F1 Scores) projected from 30 windows

5▷16 ⇥ 10-10

Table 1: Estimated population-level learning speed, prior knowledge, standard error and P-value

formance trend over time.

The estimated learning speed r, prior knowledge p, and associated standard error and p-values from the linear regression test are shown in Table 1. The population-level and worker-level learning curves (in Figure 2(a) and Figure 2(b)) show that cumulative quality (solid curves) has a noticeable upward trend and has a significant relationship (p << 0▷05) with our proposed hyperbolic learning curve (dashed curves). These results give us insight into the difficulty level of the tasks, e.g. how many tasks in general are needed for a worker with no prior knowledge to reach 50% quality, and the overall quality of the worker population, e.g. workers in average have a quality score of around 70% at the beginning.

3 ADynamic Hiring Procedure

In this section, we show how it is possible to incorporate information about workers' learning into the hiring process, allowing the system to balance the quality of task output, the cost of hiring workers, and the future benefit derived from assigning tasks to workers for training purposes.

3.1 AMarkov Decision Process forWorker Hiring

Let W be the set of workers, where the quality qw of each worker w 2 W is defined by his learning speed rw, prior knowledge level pw and number of completed tasks xw. Similar to other researchers (see, for example [Lin et al., 2012; Dai et al., 2010]), we use a decision-theoretic framework to model the hiring problem for a single task. We define a finitehorizon Markov Decision Process (MDP) as hl↪ S↪A↪ T↪Ri where l is the task horizon (the maximum number of workers the system will hire for a single task), S is the state space, A is the action set, T is the transition probability function, and R is the reward function.

States: A state, st 2 S is defined as a set of workers hired until time t, along with an opinion aw from each worker w. That is st = ¶(w1↪ a1)↪ ▷ ▷ ▷ ↪ (wt↪ at)♦ = ¶(wi↪ ai)ti=1 ♦. For ease of explanation we assume that the tasks are structured so that there are only two opinions (for example, yes or no); however our model easily generalizes to situations where the set of possible opinions is larger.

Actions: At each state st, the system can take one of two actions-terminate hiring and return the workers' aggregated opinions to the task owner (≻H), or select a new worker, wi, to hire from the worker pool (Hwi ). That is, A = ¶≻H♦ [ ¶Hw♣w 2 W♦.

If action ≻H is taken in state st = ¶(wi↪ ai)ti=1 ♦, the workers' opinions are aggregated as follows: Assuming that workers' opinions are conditionally independent given the correct classification ˆa, the system's belief, b, that classification a is correct is

where λa is a normalizing factor and Pr(a) is the prior probability. Since, for each worker, we know their current quality, qw, we have

The system returns the classification

and updates its knowledge about the workers. In particular, for eachworker w hired, xw xw+1which induces changes in qw. When asked to hire workers for a new task, the system uses this updated worker-population information.

Transitions: If, in state st = ¶(wi↪ ai)ti=1 ♦, action Hw is selected, then the system transitions to state st+1 = ¶(wi↪ ai)ti=1 [ (w↪ aw)♦ with probability T (st↪ Hw↪ st+1) = Pr(aw♣¶ai♦ti=1 ). Letting a represent the true classification of the task, and assuming that workers' responses are conditionally independent given the true classification,

where λ is the normalizing factor, and Pr(ai♣a) is defined by Equation 4.

Rewards: There are two types of rewards in the system: the aggregation reward and the training reward. These rewards, together, allow the system to strike a balance between the goal of hiring workers so as to improve the quality of their aggregated opinions and hiring workers so as to provide them with training to improve their quality for future tasks.

The aggregation reward, R(s↪ ≻H), assuming that the system is in state s and takes action ≻H, is defined by

where bt is a threshold parameter so that only aggregated opinions with high enough belief are rewarded and β is a weighting term which allows the system to tune the reward of an accurate prediction to the actual cost of hiring a worker. In particular, the aggregation reward is an increasing function of the belief the system has in the correctness of the aggregated response from the workers.

The training reward, R(s↪Hw), is awarded when the system is in state s and takes action Hw (i.e., hires a worker w). In its most basic form, we have R(s↪ Hw) = -c where c is the cost of hiring a single worker. However, we also find it useful to use reward shaping (see, for example [Ng et al., 1999]) and allow part of the system reward to directly incorporate information about the change in worker experience and quality. In particular, by hiring worker w, the worker gains more experience and thus its quality changes, as described by its learning curve. If the worker had previously completed xw tasks, then by being hired for an additional task we define the change in quality as

The associated training reward is

where, again, c is the cost of hiring a single worker, and γ is a weighting parameter that allows the system to tune the training reward to the actual cost of hiring a worker.

While we define specific rewards for the system, they are not necessarily unique as the appropriate reward structure may depend on the specific domain. However, we argue that our proposed reward functions are desirable as they are convex functions and so provide higher rewards for more challenging aggregation and quality improvement.

Solving the MDP

Given MDP = hl↪ S↪A↪ T↪Ri, the optimal policy ⇡⇤ specifies an action for each state so that the system utility is maximized. In particular, an optimal policy ⇡⇤ with value function V ⇡⇤ satisfies the Bellman equation

Alternatively, since each action Hw is an informationgathering action, we can reformulate the hiring problem as a value of information (VOI) problem where the VOI at state st = ¶(wi↪ ai)ti=1 ♦, given worker w is hired, is the expected utility of hiring w rather than stopping and aggregating the opinions ¶ai♦ti=1 . In particular,

and

If, at state st, V OI(st) > 0 then the system is best off hiring worker w⇤ = argmaxw2W VOI(st↪w). Otherwise, the system is best off terminating the hiring process and aggregating the workers' opinions and returning the task classification.

Since computing the expected value of information for sequences of observations under uncertainty is intractable [Heckerman et al., 1993], researchers have proposed using sampling-based methods (for example, [Kearns et al., 2002]). In particular, Kamar and Horvitz proposed the MCVOI algorithm, a Monte-Carlo planning algorithm that explores the search space by sampling possible hiring paths, and then evaluates the rewards of either hiring a worker versus stopping and aggregating the collected responses for all states along the sampled path [Kamar and Horvitz, 2013].

We use the MC-VOI algorithm, modifying it to handle our larger search space and richer worker population. In the rest of this section we describe our modifications to MC-VOI, and direct the reader to the original paper introducing MC-VOI for full details of that algorithm [Kamar and Horvitz, 2013]. There are two main components to the MC-VOI algorithm, sampling and evaluation.

Sampling Phase: The sampling phase starts with the initial state where no workers have been hired and proceeds to hire workers until the maximum number is reached (l). If state st was sampled at step t and then action Hw was taken, the probability state st+1 is sampled is defined by Equation 5. Each time a new state is encountered, a new node is added to the search tree. Once l workers have been hired, the aggregated response of the system is determined by Equation 3.

While MC-VOI assumes all workers are interchangeable, in our setting this is not the case. Ideally one should sample all available workers at any hiring state, but as the number of workers increases, the sampling tree grows exponentially and this becomes infeasible. Instead, we propose a priority score for workers that balances their immediate quality with future expected quality, and sample workers in proportion to their score. Recall that each worker w has completed xw tasks before the task of interest, and thus has quality qw(xw). If the worker was allowed to complete an additional n tasks, then its projected quality is qw(xw + n). We define the score of worker w as

where δnow and δfuture are weights that allow us to balance current and future quality. We sample worker w according to probability

and the worker's response, aw is sampled based on qw(xw).

Evaluation Phase: The evaluation phase updates the utility of each sampled state from bottom to top once sampling is done. For any state, sl, in which there are l hired workers, V (sl) = R(sl↪ ≻H). For any state st with t < l, we compute the estimated value of information of hiring worker w. Define g(st↪ aw) to be the state st+1 that arises if worker w is hired in state st and provides opinion aw. Then,

where

is the probability of transitioning from state st to g(st↪ aw) based on the observations from the sampling procedure. If VOI ⇤ (st↪w) < 0 for all w then the optimal action is ≻H, and V (st) = R(st↪ ≻H). Otherwise,

and the action to be taken in state st is set to Hw.

4 Results

We compare our dynamic hiring procedure to two baselinesRandomK, which randomly picks k available workers, and TopK, which ranks all available crowd workers by their observed quality and picks the top k workers to work on the next task. For both baselines, we use majority voting to aggregate opinions to derive a single prediction. We compared the performance of the algorithms based on three metrics: nc (number of correct answers), ch (cost of hiring) and ct (cost of training). ct is a relative monetary measurement where we fix the hiring cost of one worker to perform one task to be 1. Finally, for all experiments, when scoring workers we set δnow = δfuture = 0▷5 and n to be the number of tasks remaining.

Simulation Results

We simulated 100 workers whose performance follows a parameterized hyperbolic learning curve model, with learning speed and prior knowledge drawn from truncated normal distribution R(x) = f(x; 50↪ 5↪ 0↪1) and P(x) = f(x; 80↪ 5↪ 0↪1). These parameters are based on the average values observed from sleep spindle detection workers during the crowdsourcing study. We then created 1000 binary tasks where both outcomes are equally likely to happen, ran each hiring algorithm 30 times (keeping all settings constant), and averaged the results (shown in Table 2 and Figure 3).

First, we simulated a population of workers with relatively uniform learning rates. Results (in Figure 3(a)) show that the performance of RandomK is improving over time in general, because each worker is given an opportunity to learn by performing some tasks. In contrast, TopK performs well since in our setting all workers share a similar learning speed which is relatively fast. No matter which workers were picked, their performance improved to produce very accurate predictions for the system. Our proposed DynamicHiring saves cost (ch=1522, ct=800) on hiring while maintaining high overall accuracy compared to TopK (ch=3000, ct=2000) - which is a 49.3% reduction of hiring cost, and 53.6% reduction taking hiring and training costs into account.

Next, we created a heterogeneous worker population, where the majority of workers are very slow learners with a better starting quality, while a small group of workers starts poorly but are faster learners and can outperform others quickly. In particular, we draw 80 slow learners from R(x) = f(x; 600↪ 5↪ 0↪1) and P(x) = f(x; 800↪ 10↪ 0↪1), with an average starting quality of 57%, and 20 fast learners from R(x) = f (x; 60↪ 5↪ 0↪ 1) and P (x) = f (x; 40↪ 5↪ 0↪ 1) with an average starting quality of 40%. This is a challenging situation for TopK, which may be easily misled to hire slow learners with better starting quality than to take advantage of faster learners and their better performance in the future. Our goal is to demonstrate that DynamicHiring, which takes into account learning rates of individual workers, is adaptive and robust enough to handle this challenging scenario.

Results (in Table 2 and Figure 3(b)) show that due to the small number of high potential workers, it takes DynamicHiring quite a while (i.e., 200 tasks) to locate and hire these workers. The fluctuation towards the end is due to the algorithm constantly exploring unknown workers, who have a lower initial quality but are recognized by the system as potential fast learners. By taking advantage of fast learners, DynamicHiring (nc=931) outperformed TopK (nc=807) by a huge margin, with a 15.4% improvement in quality. More im-

(a) uniform learning rates

(b) heterogeneous learning rates

Figure 3: Simulation results: cumulative quality and number of hired workers

portantly, the hiring-cost savings remain significant (36.6% reduction, or 43% taking into account the cost of training tasks).

Overall, our simulations show that, for both worker populations with uniform and heterogeneous learning rates, our proposed dynamic hiring mechanism is able to yield similar performance to TopK, while providing significant savings on hiring and training costs.

Sleep Spindle Detection

Finally, we tested our dynamic hiring algorithm on the sleep spindle detection task. We assigned the first 20 tasks/spindles as training tasks; that is, TopK sampled all workers for 20 tasks first before hiring for remaining tasks, and DynamicHiring estimated the learning curve model based on worker's tutorial session during these 20 tasks. We retained only workers who annotated all 54 windows, which leaves 15 workers in total. We set k = 3 for both RandomK and TopK so they are not hiring excessive workers and there is no need for any tie breaking. We set the horizon of DynamicHiring, l, equal to 5 so it can explore a bit more at the beginning. For the reward functions we set β = 7▷0, bt = 0▷85, and γ = 100▷0. We ran the experiments 30 times and reported the average performance. After removing the first 20 sleep spindles, there are a total of 81 tasks left for testing.

Results (in Table 3 and Figure 4) show that DynamicHiring, TopK and RandomK achieved similar quality. However, DynamicHiring (ch=208) provides a 62% reduction in terms of hiring cost compared to TopK (ch=543); in fact, it costs even less than RandomK which has no training tasks. In other words, for this non-trivial classification task, our dynamic hiring procedure provided significant cost saving without losing much on performance, demonstrating the feasibility of our approach in real-world crowdsourcing settings.

5 Conclusion

In this work, we demonstrated that, for certain types of tasks, crowd workers learn from experience and their quality of work may improve over time. We demonstrated, through 15 independent case studies, that it is possible to model each worker's learning curve and presented a decision-theoretic hiring model that accounts for the learning processes of the workers. Both simulation-based and experimental results illustrate that our model and approach are feasible-our hiring algorithm reduces hiring costs and provides competitive performance in terms of accuracy with other commonly used hiring mechanisms.

There are a number of future directions for this line of research. First, our dataset for the experimental validation was small; in future work, we aim to test our model on larger realworld crowdsourcing problems. Our model makes the unrealistic assumption that workers are always available; thus, a promising next step is to extend our model and algorithms to settings where workers may enter and leave the platform, leading to interesting dynamics as the system tries to find the right balance between greedily aggregating answers from currently available workers and training promising workers whose future availability is uncertain. Finally, we are interested in expanding our model beyond consensus tasks to handle more complicated (e.g., hierarchical) tasks.