BUDGET OPTIMAL CROWDSOURCING

• US 20140172767A1
• Filed: 12/14/2012
• Published: 06/19/2014
• Est. Priority Date: 12/14/2012
• Status: Abandoned Application

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Zhou, Dengyong, Chen, Xi, Lin, Qihang
• Application Number:
  US13/715,907
• Publication Number:
  US 20140172767A1
• Time in Patent Office: Days
• US Class Current: 706/50
• CPC Class Codes: G06N 7/01 Probabilistic graphical models, e.g. probabilistic networks
• CPC Class Codes: G06Q 10/0631 Resource planning, allocation, distributing or scheduling for enterprises or organisations
• CPC Class Codes: G06Q 10/103 Workflow collaboration or project management

Abstract

To optimize the number of correct decisions made by a crowdsourcing system given a fixed budget, tasks for multiple decisions are allocated to workers in a sequence. A task is allocated to a worker based on results already achieved for that task from other workers. Such allocation addresses the different levels of difficulty of decisions. A task also can be allocated to a worker based on results already received for other tasks from that worker. Such allocation addresses the different levels of reliability of workers. The process of allocating tasks to workers can be modeled as a Bayesian Markov decision process. Given the information already received for each item and worker, an estimate of the number of correct labels received can be determined. At each step, the system attempts to maximize the estimated number of correct labels it expects to have given the inputs so far.

Claims

1. A computer-implemented process, comprising:

accessing data describing a plurality of decisions, each decision having an associated task, each task having an associated cost;

accessing data describing a plurality of individuals;

selecting a task for one of the plurality of decisions and one of the plurality of individuals based on results already achieved for the tasks as already performed by other of the plurality of individuals, by maximizing an estimated number of correct decisions given a budget;

delivering a request to perform the task for the selected decision to a computer associated with the selected individual;

receiving a result for the task from the computer associated with the selected individual; and

repeating the steps of selecting, delivering and receiving until the budget is exhausted.

2. The computer-implemented process of claim 1, wherein the decisions have a variety of levels of difficulty.

3. The computer-implemented process of claim 1, wherein the individuals have a variety of levels of reliability.

4. The computer-implemented process of claim 1, wherein the result for a task is selected from a binary set of candidate results.

5. The computer-implemented process of claim 1, result for a task is selected from a finite, multiclass set of candidate results.

6. The computer-implemented process of claim 1, wherein maximizing an estimated number of correct decisions includes computing a Bayesian Markov decision process.

7. The computer-implemented process of claim 6, wherein computing comprises computing an optimistic knowledge gradient.

8. An article of manufacture comprising:

a computer storage medium;

computer program instructions stored on the computer storage medium which, when processed by a processing device, instruct the processing device to perform a process comprising;

accessing data describing a plurality of decisions, each decision having an associated task, each task having an associated cost;

accessing data describing a plurality of individuals;

selecting a task for one of the plurality of decisions and one of the plurality of individuals based on results already achieved for the tasks as already performed by other of the plurality of individuals, by maximizing an estimated number of correct decisions given a budget;

delivering a request to perform the task for the selected decision to a computer associated with the selected individual;

receiving a result for the task from the computer associated with the selected individual; and

repeating the steps of selecting, delivering and receiving until the budget is exhausted.

9. The article of manufacture of claim 8, wherein the decisions have a variety of levels of difficulty.

10. The article of manufacture of claim 8, wherein the individuals have a variety of levels of reliability.

11. The article of manufacture of claim 8, wherein the result for a task is selected from a binary set of candidate results.

12. The article of manufacture of claim 8, wherein the result for a task is selected from a finite, multiclass set of candidate results.

13. The article of manufacture of claim 8, wherein maximizing an estimated number of correct decisions includes computing a Bayesian Markov decision process.

14. The article of manufacture of claim 13, wherein computing comprises computing an optimistic knowledge gradient.

15. A computer system comprising:

a database including storage that stores results for tasks performed by workers;

a task management module configured to connect to a computer network to manage communication of tasks to workers and receipt of results from works, and configured to access the database to store the results of tasks performed by workers;

an optimization engine configured to access the database and manage assignments of tasks to workers by sequentially selecting a task for a worker based on results already achieved for the tasks as already performed by other workers, by maximizing an estimated number of correct decisions given a budget.

16. The computer system of claim 15, wherein the decisions have a variety of levels of difficulty.

17. The computer system of claim 15, wherein the result for a task is selected from a binary set of candidate results.

18. The computer system of claim 15, wherein the result for a task is selected from a finite, multiclass set of candidate results.

19. The computer system of claim 15, wherein maximizing an estimated number of correct decisions includes computing a Bayesian Markov decision process.

20. The computer system of claim 19, wherein computing comprises computing an optimistic knowledge gradient.