Hybrid machine/human computing arrangement

• US 7,197,459 B1
• Filed: 10/12/2001
• Issued: 03/27/2007
• Est. Priority Date: 03/19/2001
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Ranganathan, Anand, Rajaraman, Anand, Harinarayan, Venky
• Primary Examiner(s): Hudspeth; David
• Assistant Examiner(s): ALBERTALLI, BRIAN LOUIS
• Application Number:
  US09/976,717
• Time in Patent Office: 1,992 Days
• Field of Search: 707 3- 6, 707/104.1, 382/311, 345/358
• US Class Current: 704/270.1
• CPC Class Codes: G06Q 10/063112 Skill-based matching of a person or a group to a task
• CPC Class Codes: G06Q 10/10 Office automation; Time management
• CPC Class Codes: G10L 15/22 Procedures used during a speech recognition process, e.g. man-machine dialogue

Abstract

A hybrid machine/human computing arrangement which advantageously involves humans to assist a computer to solve particular tasks, allowing the computer to solve the tasks more efficiently. In one embodiment, a computer system decomposes a task, such as, for example, image or speech comparison, into subtasks for human performance, and requests the performances. The computer system programmatically conveys the request to a central coordinating server of the hybrid machine/human computing arrangement, which in turn dispatches the subtasks to personal computers operated by the humans. The humans perform the subtasks and provide the results back to the server, which receives the responses, and generates a result for the task based at least in part on the results of the human performances.

Claims

1. A method for a computer system to use human assistance in performing tasks, the method comprising:

automatically and under control of a first computer system, causing a task to be performed by,

identifying a first and a second subtask of the task, wherein the first subtask involves speech recognition;

retrieving information about past quality of results of one or more humans when previously performing subtasks other than the first subtask;

using the retrieved past quality information to facilitate performance of the first subtask by one or more humans, the facilitating of the performance of the first subtask including,

identifying one or more required capabilities for performance of the first subtask;

dispatching the first subtask to a remote second computer system of a first human for performance by the first human, the first human identified as being one of one or more humans who have capabilities that satisfy the required capabilities for the first subtask, the retrieved past quality information including past quality information for the first human when previously performing multiple subtasks other than the first subtask, the past quality information for the first human being at least part of the capabilities of the first human that satisfy the required capabilities for the first subtask; and

receiving a first result from the first human via the second computer system, the first result generated by performance of the first subtask by the first human;

providing payment to the first human for the performance of the first subtask; and

generating a result for the task based at least in part on the first result.

2. The method of claim 1 wherein the identifying by the first computer system of the first and second subtasks of the task includes decomposing the task into at least the first and second subtasks.

3. The method of claim 1, wherein

the method further comprises the first computer system dispatching said second subtask to a third computer system of a second human for performance by the second human, and the first computer system receiving a second result from the second human via the third computer system for said second subtask;

and

the first computer system further bases its generation of the result for said task on said second result.

4. The method of claim 3, wherein

said task further comprising a third subtask, and the method further comprises the first computer system receiving and performing said third subtask producing a third result;

and

the first computer system further bases its generation of the result for said task on said third result.

5. The method of claim 1, wherein

the method further comprises the first computer system performing said second subtask producing a second result;

and

the first computer system further bases its generation of the result for said task on said second result.

6. The method of claim 1, wherein said first human is one of college educated, at most high school educated, at most elementary school educated, and not formally educated.

7. The method of claim 1, wherein said subtask is one of text, speech, sound, and images related operations.

8. The method of claim 1, wherein said result is one of text, numbers, tuples, and sound.

9. The method of claim 1, wherein said task is one of text classification, image comparison, image processing, speech comparison, speech recognition, conversion of speech into text, and comparison of music samples.

10. The method of claim 1, wherein said task is associated with multiple attributes related to performance of said task, the attributes including an accuracy attribute, a security attribute, a timeout attribute, a maximum time spent attribute, a maximum cost per task attribute, and a maximum total cost attribute, and wherein the identifying of the one or more humans, the dispatching of the first subtask, and the generating of the result for said task are performed in a manner to reflect the multiple associated attributes.

11. The method of claim 1, wherein said task is associated with one or more attributes, and said attributes include an accuracy attribute.

12. The method of claim 1, wherein said task is associated with one or more attributes including a security attribute, and said security attribute comprises a selection of one of a “

strict”

security level, a “

lax”

security level, and “

no”

security level.

13. The method of claim 1, wherein said task is associated with one or more attributes that include a “

maximum time”

attribute specifying a maximum amount of time to be spent by an assigned human to perform said first subtask.

14. The method of claim 1, wherein said task is associated with one or more attributes, and said attributes include a maximum cost per task attribute.

15. The method of claim 1, wherein said task is associated with one or more attributes, and said attributes include a maximum total task cost attribute.

16. The method of claim 1 wherein the first computer system is a task server system that is part of a distributed hybrid computer/human computation arrangement, and wherein the first human is one of numerous humans remote from the task server system who each use distinct client computing devices to act as nodes of the distributed hybrid computer/human computation system.

17. The method of claim 16 wherein the distributed hybrid computer/human computation arrangement further includes one or more distinct coordinating server computing systems remote from the task server system such that the dispatching of the first subtask by the task server system includes sending information to at least one of the coordinating server computing systems that includes an indication of the first subtask and of the identified required capabilities, and wherein one of the coordinating server computing systems coordinates performance of the first subtask by identifying the first human as having capabilities that satisfy the identified required capabilities and by sending to the second computer system of the first human an indication of the first subtask to be performed.

18. The method of claim 1 wherein the first computer system is a coordinating server computing system that identifies the first and second subtasks of the task by receiving information about the first and second subtasks from a remote task server system, wherein the coordinating server computing system causes the result to be generated for the task based at least in part on the first result by sending the received first result to the remote task server system, and wherein the first human is one of numerous humans who each use distinct client computing devices to act as nodes available to the coordinating server computing system.

19. The method of claim 1 wherein the dispatching by the first computer system of the first subtask to the remote second computer system is performed using a defined application programming interface (“

API”

).

20. The method of claim 1 wherein the dispatching by the first computer system of the first subtask to the remote second computer system is performed by programmatically sending one or more messages from the first computer system to the remote second computer system.

21. The method of claim 1 wherein the dispatching by the first computer system of the first subtask to the remote second computer system of the first human includes providing an indication to the first human of the payment to be provided for performance of the first subtask if the first human chooses to perform the first subtask.

22. The method of claim 1 wherein the providing of the payment to the first human is performed in response to the receiving from the first human of the first result from the performance of the first subtask.

23. The method of claim 1 wherein the required capabilities of the human for performance of the first subtask include an ability to speak a specified language.

24. The method of claim 1 wherein the required capabilities of the human for performance of the first subtask include an ability to hear.

25. The method of claim 1 wherein the required capabilities of the human for performance of the first subtask include a specified degree of historical accuracy by the human when performing subtasks.

26. The method of claim 1 wherein the payment provided to the first human for the performance of the first subtask is further based in part on quality of the performance of the first subtask.

27. The method of claim 1 wherein the payment provided to the first human for the performance of the first subtask is further based in part on cumulative contributions of the first human.

28. The method of claim 1 wherein the payment provided to the first human for the performance of the first subtask is further based in part on a prior agreement with the first human.

29. The method of claim 1 wherein the first compensation level is a first monetary amount, and wherein an amount of the payment provided to the first human for the performance of the first subtask is the first monetary amount.

30. The method of claim 29 wherein the second subtask has a distinct second monetary amount of compensation associated with performance of the second subtask, and wherein the method further comprises providing payment of the second monetary amount of compensation to a second human for performance of the second subtask.

31. The method of claim 1 wherein the past quality information for the first human when previously performing subtasks other than the first subtask reflects a past accuracy of the first human in performing those other subtasks.

32. The method of claim 31 further comprising, after the receiving of the first result from the first human, determining an accuracy of the first result and updating the past accuracy information for the first human to reflect the determined accuracy.

33. The method of claim 32 wherein the determining of the accuracy of the first result includes obtaining one or more results that are each generated by performance of the first subtask by a human other than the first human, and using the obtained one or more results as part of the determining of the accuracy of the first result.

34. The method of claim 33 wherein the using of the obtained one or more results as part of the determining of the accuracy of the first result includes weighting each of the obtained one or more results based at least in part on retrieved past accuracy information for the human whose performance generated the result.

35. The method of claim 1 wherein the generating of the result for the task is based at least in part on the past quality information for the first human.

36. The method of claim 1 wherein the payment provided to the first human is based at least in part on the past quality information for the first human.

37. The method of claim 1 wherein the dispatching of the first subtask to the remote second computer system of the first human includes providing an indication to the first human of compensation associated with performance of the first subtask.

38. The method of claim 1 wherein the payment provided to the first human is based at least in part on quality of the first result.

39. The method of claim 1 wherein the first human has at most an average level of skill with respect to performing the first subtask.

40. The method of claim 1 wherein the first human is not an expert with respect to performing the first subtask.

41. The method of claim 1 wherein the first subtask involves an activity that is straightforward for a typical human but is difficult for a computer system.

42. A method for a computing system to use human assistance in performing tasks, the method comprising:

receiving an indication of a first subtask to be performed, the first subtask having one or more associated criteria related to performance, wherein the first subtask involves conversion of speech into text;

sending an indication of the first subtask to multiple humans to each perform the first subtask, each of the humans being identified as being capable of satisfying at least some of the associated criteria for the first subtask;

from each of at least some of the multiple humans, receiving a result of performance of the first subtask by the human; and

automatically facilitating generation of a final result for the first subtask by,

determining that the received results include a common result that was received from each of a selected number of humans, the selected number of humans being greater than 1 and based on at least one of a majority of the at least some humans and of at least a specified number N of two or more humans; and

selecting the common received result as the final result for the first subtask.

43. The method of claim 42 further comprising tracking accuracy of the at least some humans based at least in part on whether a result received from a human is the common result.

44. The method of claim 42 wherein the first subtask is part of a task, and wherein the method further comprises automatically generating a result for the task based at least in part on the selected result for the first subtask and on the accuracy of the at least some humans who provided the selected result.

45. The method of claim 44 wherein the receiving of the indication of the first subtask includes automatically decomposing the task into at least the first subtask and a second subtask.

46. The method of claim 42 wherein the first subtask further has associated compensation for performance of the first subtask, and wherein the method further comprises facilitating providing of the associated compensation to one or more of the humans who provided the common result.

47. The method of claim 42 wherein the multiple humans to whom the indication of the first subtask is sent include a number N1 of the multiple humans, such that N and N1 are integers and N1 is greater than N.

48. The method of claim 42 wherein the at least some humans from whom the results of performance of the first subtask are received include a number N1 of multiple humans, such that N and N1 are integers and N1 is greater than N.

49. The method of claim 42 wherein the facilitating of the generation of the final result for the first subtask includes generating the final result so as to have a desired accuracy by automatically determining the selected number of humans for that desired accuracy.

50. The method of claim 42 wherein the receiving of the indication of the first subtask includes receiving an indication of a desired accuracy for the final result, and wherein the facilitating of the generation of the final result is performed such that the final result has the indicated desired accuracy.

51. The method of claim 42 wherein the facilitating of the generation of the final result for the first subtask includes receiving an indication to use a majority governs policy and automatically determining the selected number of humans to be a number corresponding to the majority of the at least some humans.

52. The method of claim 42 wherein the facilitating of the generation of the final result for the first subtask includes receiving an indication to use the specified number N for the selected number of humans, and automatically determining the selected number of humans to be N.

53. The method of claim 42 wherein the facilitating of the generation of the final result for the first subtask includes, before the determining that the received results include the common result from each of the selected number of humans, determining that a first group of multiple results received from multiple of the humans for the first subtask do not include a common result that was received from each of the selected number of humans, and sending indications of the first subtask to additional humans in order to obtain the common result from each of the selected number of humans.

54. The method of claim 42 wherein the common result received from the selected number of humans includes multiple results that are in agreement.

55. The method of claim 42 wherein the common result received from the selected number of humans includes multiple copies of a single result.

56. The method of claim 42 wherein the first subtask involves image processing.

57. The method of claim 42 wherein the first subtask involves text classification.

58. An apparatus comprising:

a storage medium having stored therein a plurality of programming instructions that are machine executable, wherein when executed, said instructions operate to;

receive indications of a first and a second subtask of a task, the first subtask associated with one or more capabilities to be used in performance of the first subtask and having associated compensation for performance of the first subtask, wherein said task is one of speech comparison, speech recognition, conversion of speech into text, and comparison of music samples;

dispatch information about the first subtask to a remote computer system of a first human for performance by said first human of the first subtask, the first human identified as having one or more capabilities that satisfy the associated capabilities for the first subtask, the dispatched information including an indication of the associated compensation for performance of the first subtask;

receive a first result from the remote computer system based on performance of the first subtask by said first human;

retrieve information about past accuracy of said first human in previously performing subtasks; and

generate a result for said task based at least in part on said first result and at least in part on the past accuracy information for said first human; and

a processor coupled to said storage medium to execute said instructions.

59. The apparatus of claim 58, wherein the receiving of the indications of the first and second subtasks of the task includes decomposing the task into at least the first and second subtasks.

60. The apparatus of claim 58, wherein said instructions, when executed, further operate to dispatch information about said second subtask to a distinct remote computer system of a second human for performance by the second human, receive a second result from the second human via the distinct remote computer system for said second subtask, and generate the result for said task further based on said second result.

61. The apparatus of claim 60, wherein said instructions, when executed, further operate to decompose said task into at least said first, said second, and a third subtask;

perform said third subtask producing a third result; and

generate the result for said task further based on said third result.

62. The apparatus of claim 58, wherein said instructions, when executed, further operate to perform said second subtask producing a second result, and generating the result for said task further based on said second result.

63. The apparatus of claim 58, wherein said first human is one of college educated, at most high school educated, at most elementary school educated, and not formally educated.

64. The apparatus of claim 58, wherein the dispatched information about said first subtask includes speech to be reviewed by the first human.

65. The apparatus of claim 58, wherein said result is one of numbers and tuples.

66. The apparatus of claim 58, wherein said task is associated with attributes that include multiple of an accuracy attribute, a security attribute, a timeout attribute, a maximum time for a task attribute, a cost per task attribute, and a maximum task cost attribute.

67. The apparatus of claim 66, wherein said instructions, when executed, further operate to dispatch information about the first subtask to multiple additional humans to perform said first subtask, and said accuracy is based at least in part on receiving results in agreement from multiple of the humans to whom the information about the first subtask is dispatched.

68. The apparatus of claim 67, where said instructions, when executed, further track the accuracy of the humans.

69. The apparatus of claim 67, where said instructions, when executed, further take into consideration the accuracy of the humans when generating the result.

70. The apparatus of claim 66, wherein said security includes one of a strict security level, a lax security level, and no security.

71. The apparatus of claim 58 wherein said instructions, when executed, further operate to provide the associated compensation to the first human for the performance of the first subtask based in part on the receiving of the first result.

72. A method for a computing system to use human assistance in performing tasks, the method comprising:

receiving an indication of a first subtask to be performed, the first subtask having one or more associated criteria related to performance, wherein the first subtask involves speech comparison;

sending an indication of the first subtask to multiple humans to each perform the first subtask, each of the humans being identified as being capable of satisfying at least some of the associated criteria for the first subtask;

from each of at least some of the multiple humans, receiving a result of performance of the first subtask by the human; and

automatically facilitating generation of a final result for the first subtask by,

determining that the received results include a common result that was received from each of a selected number of humans, the selected number of humans being greater than 1 and based on at least one of a majority of the at least some humans and of at least a specified number N of two or more humans; and

selecting the common received result as the final result for the first subtask.

73. A method for a computing system to use human assistance in performing tasks, the method comprising:

receiving an indication of a first subtask to be performed, the first subtask having one or more associated criteria related to performance, wherein the first subtask involves comparison of music samples;

sending an indication of the first subtask to multiple humans to each perform the first subtask, each of the humans being identified as being capable of satisfying at least some of the associated criteria for the first subtask;

from each of at least some of the multiple humans, receiving a result of performance of the first subtask by the human; and

automatically facilitating generation of a final result for the first subtask by,

determining that the received results include a common result that was received from each of a selected number of humans, the selected number of humans being greater than 1 and based on at least one of a majority of the at least some humans and of at least a specified number N of two or more humans; and

selecting the common received result as the final result for the first subtask.

74. A storage medium having stored therein a plurality of programming instructions that are executable to cause a first computing system to perform a method comprising:

receiving indications of a first and a second subtask of a task, the first subtask associated with one or more capabilities to be used in performance of the first subtask and having associated compensation for performance of the first subtask, wherein said task is one of speech comparison, speech recognition, conversion of speech into text, and comparison of music samples;

dispatching information about the first subtask to a remote computer system of a first human for performance by said first human of the first subtask, the first human identified as having one or more capabilities that satisfy the associated capabilities for the first subtask;

receiving a first result from the remote computer system based on performance of the first subtask by said first human;

retrieving information about past accuracy of said first human in previously performing subtasks; and

generating a result for said task based at least in part on said first result and at least in part on the past accuracy information for said first human.

75. The storage medium of claim 74, wherein said instructions, when executed, further operate to decompose the task to be performed into at least the first and second subtasks.

76. The storage medium of claim 74, wherein said instructions, when executed, further operate to dispatch an indication of said second subtask to a computing system for performance by a second human, receive a second result from the second human for said second subtask, and generate the result for said task further based on said second result.

77. The storage medium of claim 76, wherein said instructions, when executed, further operate to decompose said task into at least said first, said second, and a third subtask;

perform said third subtask producing a third result; and

generate the result for said task further based on said third result.

78. The storage medium of claim 74, wherein said instructions, when executed, further operate to automatically perform said second subtask producing a second result, and generate the result for said task further based on said second result.

79. The storage medium of claim 74, wherein said first human is one of college educated, at most high school educated, at most elementary school educated, and not formally educated.

80. The storage medium of claim 74, wherein said first subtask is one of text and speech.

81. The storage medium of claim 74, wherein said result is one of text, numbers, and tuples.

82. The storage medium of claim 74, wherein said task is associated with attributes that include an accuracy attribute, a security attribute, and a timeout attribute.

83. The storage medium of claim 82, wherein said instructions, when executed, further operate to dispatch said first subtask to N1−

1 additional humans to perform said first subtask, and wherein said accuracy attribute includes an indication of one of majority governs and at least N2 agreed results, with N2 and N1 being integers with N1 greater than N2.

84. The storage medium of claim 82, wherein said security attribute includes an indication of one of a strict security level, a lax security level, and no security level.

85. The storage medium of claim 74, wherein said task is associated with one or more attributes, wherein the attributes indicate a maximum time to be spent on a task, a maximum cost to incur per task, and a maximum total cost for the task.