PaperlayerView exact revision on arXiv

Source-linked AI summary

Learning to Hire Teams

Adish Singla, Eric Horvitz, Pushmeet Kohli, Andreas Krause

arXiv:1508.02823v1cs.HCcs.CYcs.LG

TL;DR

Recruiters in contract-based crowdsourcing need to learn workers’ expertise across complex task types while controlling the tests needed to hire a team. The paper frames hiring as best-action selection and extends its algorithms to exploit task and worker graph side-observations. The algorithms have PAC budget bounds, and experiments report faster learning with side-observations.

  • Problem

    Hiring for ongoing, heterogeneous crowdsourcing work requires learning applicants’ skills and expertise while minimizing the budget spent on tests before committing to a team.

    Source: Introduction · pp. 1–2

  • Method

    The paper casts budgeted team hiring as online best-action selection and extends its algorithms with a joint graph model of task and worker commonalities.

    Source: Introduction · p. 2, Exploiting side-observation graphs · p. 4

  • Results

    Both algorithms learn faster with side-observations, especially UEXPSELECT; on synthetic data, AEXPSELECT exceeds 90% precision at budget 20·M·N.

    Source: Results · p. 9

  • Takeaways & Limitations

    The results support continued study of algorithmic team hiring for contract-based crowdsourcing using task and worker commonalities.

    Source: Conclusions and Future Work · p. 9

    Team quality uses a simple optimality notion; richer team relations and more realistic side-observation models remain future work.

    Source: Conclusions and Future Work · p. 9

Abstract

from arXiv · show

Crowdsourcing and human computation has been employed in increasingly sophisticated projects that require the solution of a heterogeneous set of tasks. We explore the challenge of building or hiring an effective team, for performing tasks required for such projects on an ongoing basis, from an available pool of applicants or workers who have bid for the tasks. The recruiter needs to learn workers' skills and expertise by performing online tests and interviews, and would like to minimize the amount of budget or time spent in this process before committing to hiring the team. How can one optimally spend budget to learn the expertise of workers as part of recruiting a team? How can one exploit the similarities among tasks as well as underlying social ties or commonalities among the workers for faster learning? We tackle these decision-theoretic challenges by casting them as an instance of online learning for best action selection. We present algorithms with PAC bounds on the required budget to hire a near-optimal team with high confidence. Furthermore, we consider an embedding of the tasks and workers in an underlying graph that may arise from task similarities or social ties, and that can provide additional side-observations for faster learning. We then quantify the improvement in the bounds that we can achieve depending on the characteristic properties of this graph structure. We evaluate our methodology on simulated problem instances as well as on real-world crowdsourcing data collected from the oDesk platform. Our methodology and results present an interesting direction of research to tackle the challenges faced by a recruiter for contract-based crowdsourcing.

Introduction

Complex, ongoing crowdsourced projects need skilled teams, but recruiters must learn applicants’ expertise while controlling testing costs. This paper frames team hiring as online best-action selection and develops budget-bounded algorithms that can exploit task and worker commonalities.

Crowdsourcing context

  • Contract-based crowdsourcing increasingly requires skilled workers whose expertise and coordination suit complex, ongoing tasks, beyond independent microtasking.Platforms such as oDesk offer self-assessments, interviews, tests, and skill-specific feedback to support recruiting.Source: Introduction · p. 1

Team quality

  • For a heterogeneous project, team quality is measured by the highest expertise among hired workers for each required skill.The passage illustrates this with web development, Spanish translation, and video editing task types.Source: Introduction · p. 1

Recruiting challenge

  • Recruiters need to learn workers’ unknown expertise across task types while minimizing tests and choosing a near-optimal team under an allowed error tolerance.Tests can assess expertise through online evaluations or gold-standard questions.Source: Introduction · p. 2

Exploiting commonalities

  • Task similarities and worker commonalities, including social ties, may provide information that speeds expertise learning.For example, a test for JavaScript may also inform Ajax expertise at no additional cost.Source: Introduction · p. 2

Contributions

  • The paper presents algorithms with PAC budget bounds for hiring a near-optimal team with high confidence, framing team hiring as online learning for best action selection.It also proposes modeling task and worker commonalities jointly and evaluates the methods on synthetic and oDesk data.Source: Introduction · p. 2

Related Work

Prior work addresses worker selection, task assignment, coordination, crowd learning, best-action identification, and graph-based side-observations. This paper positions its contribution at the intersection of budgeted team hiring and side-observation models.

Heterogeneous crowdsourcing markets

  • Earlier heterogeneous-market work studies worker eligibility, skill-compatible assignment, and team coordination, while this paper targets team hiring with optimality and budget guarantees.The cited examples include social-profile selection, bipartite skill compatibility, and coordinated human-machine teams.Source: Related Work · p. 2

Learning in crowdsourcing

  • Crowdsourcing learning research uses multi-armed bandit methods for expertise, task assignment, and label inference, while other work studies price curves and dynamic payments.The cited expertise-learning work seeks lower-cost prediction accuracy, a different goal from this paper’s hiring objective.Source: Related Work · p. 2

Best action selection

  • Best-action selection provides PAC methods for identifying one or multiple high-performing actions, and uniform exploration and LUCB-1 underpin this paper’s algorithms.The paper also draws on joint learning across multiple problem instances and extends LUCB-1 to that setting.Source: Related Work · pp. 2–3

Side-observations

  • Graph-based side-observation research spans adversarial and stochastic bandits, correlated actions, and contextual bandits; this paper combines task and worker graphs for best-action selection.The combined model is a cross product of two side-observation graphs.Source: Related Work · p. 3

Problem Statement

The problem is to choose a small team from workers with unknown, task-specific performance. The recruiter pays for tests, seeks an ϵ-optimal team, and may use graph-derived side-observations to reduce learning effort.

Performance model

  • Worker performance for each task is modeled as an unknown mean of bounded stochastic feedback, with observations i.i.d. for each fixed worker-task pair and independent across pairs and time.The support is assumed to lie within [0, 1].Source: Problem Statement · p. 3

Side-observation model

  • Known worker and task graphs represent side-observations available at no additional cost when a worker is assigned a task.The model assumes undirected graphs and notes that it could be extended to directed graphs.Source: Problem Statement · p. 3

Side-observation scope

  • The algorithms aim to interpolate between bandit feedback with no graph edges and full information with fully connected worker and task graphs.An assignment can reveal observations for neighboring tasks or workers.Source: Problem Statement · p. 3

Objective

  • The objective is to hire at most M workers so that each task has a team member with performance near the best available worker for that task.The team must be learned from an initially unknown performance matrix.Source: Problem Statement · p. 3

PAC criterion

  • Each worker-task assignment yields a unit-cost test, and a PAC algorithm must return an ϵ-optimal team with probability at least 1 − δ.Efficiency is measured by the total number of tests, equivalently the budget spent.Source: Problem Statement · p. 3

Algorithms for Budgeted Hiring

The algorithms build on best-action selection, jointly allocate learning across tasks, and use graph structure to exploit side-observations. They output a team satisfying the paper’s ϵ-optimality criterion with a PAC guarantee.

Overview of basic approach

  • For one task, UEXPSELECT builds on NAIVE’s uniform exploration, while AEXPSELECT builds on LUCB-1’s adaptive confidence-bound strategy.LUCB-1 adapts to instance difficulty, whereas uniform exploration does not distinguish easier from harder actions.Source: Overview of basic approach · p. 4
  • For multiple tasks, the algorithms jointly identify strong workers across tasks and allocate budget adaptively rather than treating each task as a separate instance.AEXPSELECT extends LUCB-1 to this joint setting.Source: Overview of basic approach · p. 4

Exploiting side-observation graphs

  • The method combines worker and task side-observation graphs as a Cartesian-product graph, then uses an approximate dominating set to select actions whose observations cover neighboring actions.The graph has M · N vertices; exact minimum dominating-set computation is NP-hard, so the paper uses an approximate solution.Source: Exploiting side-observation graphs · p. 4

Model parameters and execution variables

  • The output is a team of at most M workers that is ϵ-optimal with probability at least 1 − δ, where worker gaps are measured against the best task-specific performance.The algorithms construct the product graph and its approximate dominating set before selecting actions and collecting observations.Source: Model parameters and execution variables · pp. 4–5

11 Output: S

The output is a team containing an ϵ-optimal worker for every task. UEXPSELECT explores worker-task assignments and uses side-observations when selecting actions and updating estimates.

11 Output: S

  • An ϵ-optimal team contains at least one ϵ-optimal worker for each task; setting ϵ = 0 gives the optimal team.The algorithm's output is a team of at most M workers that is ϵ-optimal with probability at least 1 − δ.Source: §11 · p. 5, Algorithm UEXPSELECT · p. 5

Algorithm UEXPSELECT

  • UEXPSELECT uniformly explores actions, choosing an assignment with the fewest observations so far.Its input includes the tasks, workers, side-observation graphs, and PAC parameters (ϵ, δ).Source: Algorithm UEXPSELECT · p. 5
  • After an assignment, the algorithm obtains observations for actions dominated by the selected action and updates estimates and task gaps.It computes the product graph and its domination relation for side-observation feedback.Source: Algorithm UEXPSELECT · p. 5

17 Output: St

The algorithm selects workers using observed performance and confidence bounds, then stops considering a task once its stopping condition is met. A shared clock lets it allocate assignments across tasks and exploit side-observation graphs.

17 Output: St

  • The output procedure selects the best worker set using observed performances after actions have accumulated the required observations.Ignoring side-observations reduces each observation set to a singleton.Source: §17 · p. 5

Algorithm AEXPSELECT

  • AEXPSELECT adapts to variation in the difficulty of identifying suboptimal workers across tasks and within each task.It is based on ideas from LUCB-1.Source: Algorithm AEXPSELECT · p. 6
  • For each task, the algorithm tracks the gap between the upper confidence bound of a remaining worker and the lower confidence bound of the empirically best worker; increasing observations should shrink the gap below zero.The approach uses high-probability confidence bounds on performance estimates.Source: Algorithm AEXPSELECT · p. 6
  • AEXPSELECT chooses the task with the largest gap and assigns a worker with the larger confidence width; once the condition is met, that task leaves the active set.A common clock across tasks directs more assignments to tasks with greatest uncertainty and allows joint use of side-observation graphs.Source: Algorithm AEXPSELECT · p. 6

Performance Analysis

The analysis establishes sample-complexity bounds for UEXPSELECT and AEXPSELECT, extending best-action-selection results. It examines how graph side-observations affect uniform and adaptive learning, including limits of a static graph strategy.

Performance Bounds for UEXPSELECT

  • Without side-observations, UEXPSELECT has performance bounds equivalent to running M separate NAIVE instances, with confidence controlled by a union bound.Using error probability δ/M for each instance bounds the total error probability by δ.Source: Performance Bounds for UEXPSELECT · p. 6
  • UEXPSELECT uses an approximate dominating set whose actions cover the worker-task action set, offering a potential reduction in tests.The algorithm scans the set uniformly; the supplied passages do not provide an intact numerical saving factor.Source: Performance Bounds for UEXPSELECT · p. 6

Performance Bounds for AEXPSELECT

  • AEXPSELECT jointly learns across tasks by pooling their action gaps and using a common clock to adaptively allocate assignments.Its stated sample-complexity bound is for an (ϵ, δ)-PAC algorithm with expected sample complexity.Source: Performance Bounds for AEXPSELECT · p. 7
  • When tasks have equal hardness, AEXPSELECT’s sample-complexity bound matches that of running separate LUCB-1 instances with separate clocks.The comparison is against the separate-clock bound described in the supplied passages.Source: Performance Bounds for AEXPSELECT · p. 7
  • The AEXPSELECT bound does not explicitly capture side-observation gains, and a fixed dominating set may fail to help in the worst case.The analysis suggests dynamic dominating sets that account for remaining action uncertainty as a more effective approach for adaptive algorithms.Source: Performance Bounds for AEXPSELECT · p. 7

Experimental Evaluation

Experiments compare adaptive and uniform team-selection algorithms on synthetic and oDesk data, measuring team quality against budget and examining problem hardness and side-observation graphs. AEXPSELECT learns faster, and side observations boost both methods.

Experimental Setup and Datasets

Metrics and parameters.

  • Team quality is measured by average precision—the fraction of tasks with an ϵ-optimal selected worker—and average performance gap from the best worker.The gap is averaged over tasks; budget is reported as average tests per worker/task pair.Source: Metrics and parameters · p. 7

Results

  • >90% precision at budget 20·M·N: AEXPSELECT reached this on synthetic data, while UEXPSELECT needed substantially more budget; AEXPSELECT also converged faster on oDesk data.The reported average ∆min_j was 0.25 for both datasets.Source: Figure 2 · p. 8, Figure 3 · p. 8, Results · p. 9

Synthetic data.

  • Synthetic data used 200 workers and 10 tasks, independently sampled task performance vectors, and no side-observation graphs.For hardness comparisons, average ∆min_j ranged from 0.25 to 0.05.Source: Synthetic data · p. 8

oDesk data.

  • The oDesk evaluation used 10 tasks across three top-level categories, linking same-category tasks and workers whose skill-tag Jaccard coefficient exceeded 0.3.The 200-worker sample and performance matrix were derived from marketplace profiles and feedback scores, with random values used when feedback was unavailable.Source: oDesk data · pp. 8–9

Results

  • As average ∆min_j decreased from 0.25 to 0.05 at a fixed budget of 20 tests per worker/task pair, both algorithms degraded, but AEXPSELECT's gain remained consistent..Source: Figure 2 · p. 8, Results · p. 9
  • Side-observations significantly accelerated learning for both algorithms, with a larger boost for UEXPSELECT than for AEXPSELECT.The graph-complexity measure eγGwo was 600 with task graphs only and 386 with both task and worker graphs.Source: Figure 3 · p. 8, Results · p. 9

Conclusions and Future Work

The paper frames efficient team hiring for contract crowdsourcing as online best-action selection, with algorithms that have PAC bounds and can exploit task and worker commonalities. Future work would extend the team model and develop more realistic side-observation models and real-world experiments.

Conclusions and Future Work

  • The paper presents team hiring as online best-action selection, with PAC-bounded algorithms extended to exploit commonalities among tasks and workers.Source: Conclusions and Future Work · p. 9
  • Future work could model richer team relations, including workload balancing, diminishing returns, communication and coordination costs, and combinatorial constraints.Source: Conclusions and Future Work · p. 9
  • The authors also identify more realistic side-observation models and real-world experiments using those models as future directions.Source: Conclusions and Future Work · p. 9
Loading 1508.02823v1…