Paper Reading #6

TurKit: human computation algorithms on mechanical turk

Authors:
Greg Little Massachusettes Institute of Technology, Cambridge, MA, USA
Lydia B. Chilton University of Washington, Seattle, WA, USA
Max Goldman Massachusettes Institute of Technology, Cambridge, MA, USA
Robert C. Miller Massachusettes Institute of Technology, Cambridge, MA, USA

Released:
UIST '10 Proceedings of the 23nd annual ACM symposium on User interface software and technology




Summary:
A set of tools is described for using humans to perform computational tasks. Humans tend to take anywhere from a few seconds to a few minutes to accomplish a tash, so repeating tasks should be minimized or eliminated. Mechanical Turk is a system in which programmers can create tasks to be directly assignable to humans in a simple programming standpoint. Also, since machine computation is so much faster than human computational tasks, it is simple to just crash the program to wait and rerunning the program up to the current state instead of blocking the program.

Contributions: (in lieu of hypothesis)

• TurKit Script: An API for algorithmic MTurk tasks.
• Crash-and-Rerun Programming: A programming model suited to algorithmic use of human Computation, addressing issues related to high-cost and high-latency steps involving humans.
• TurKit Online: A public web GUI for running and managing TurKit scripts.

Methods:
Since saving every state of a program in a database is exponential, TurKit only stores the responses from humans. This allows for a new way of thinking about the programming flow since a deterministic program could be run again nearly instantly if the human responses are stored. This is done by using the once identifier to store the human answer and question in a database. Also instead of waiting for humans in a blocking programming standpoint, TurKit offers two alternatives:

• Forking to implement parallelism.
• Crashing the program and recomputing up to the last state.

Three examples are shown using the TurKit framework. The first example is a simplified quicksort. By recursively asking a person to objectively rate a subset, objective sorting is possible in parallel. 

The next example is an iterative captioning algorithm. An image is shown and a question is asked to describe the image. After each iteration, people are allowed to vote an improve on the caption. The voting system allows for bad improvements to be sorted out.

The last example is iterative OCR. Humans know how to read mostly, so human computation is a decent way to perform the task. For the example, people are asked to write the words in an excerpt and put a '*' character on words that are not known. This way, each enhancing/voting iteration gets the state closer to the goal. 

Results:

The most visible results came from the OCR test. There was only one error after 12 iterations. However other tests were shown to determine the efficiency of the TurKit system. The time used for completing singular tasks was nearly proportional to the amount of money sent per task, up to 10 cents. Over the whole study, just $364 was spent to generate about 30,000 tasks.'

Discussion:

I find the idea of using humans to do tasks fascinating. Since AI technology sometimes can not cope with problems today, or general programmers do not know AI concepts, this offers a simple solution. In the future, it would be interesting to see actual incorporation of AI to accomplish some tasks where humans accomplish others using the same framework.