Luis von Ahn

Thesis Title: Human Computation
Degree Type: Ph.D. in Computer Science
Advisor(s): Manuel Blum
Graduated: December 2005

Abstract:

Tasks like image recognition are trivial for humans, but continue to challenge even the most sophisticated computer programs. This thesis introduces a paradigm for utilizing human processing power to solve problems that computers cannot yet solve. Traditional approaches to solving such problems focus on improving software. I advocate a novel approach: constructively channel human brainpower using computer games. For example, the ESP Game, introduced in this thesis, is an enjoyable online game -- many people play over 40 hours a week -- and when people play, they help label images on the Web with descriptive keywords. These keywords can be used to significantly improve the accuracy of image search. People play the game not because they want to help, but because they enjoy it.

I introduce three other examples of "games with a purpose": Peekaboom, which helps determine the location of objects in images, Phetch, which collects paragraph descriptions of arbitrary images to help accessibility of the Web, and Verbosity, which collects "common-sense" knowledge.

In addition, I introduce CAPTCHAs, automated tests that humans can pass but computer programs cannot. CAPTCHAs take advantage of human processing power in order to differentiate humans from computers,an ability that has important applications in practice.

The results of this thesis are currently in use by hundreds of Web sites and companies around the world, and some of the games presented here have been played by over 100,000 people. Practical applications of this work include improvements in problems such as: image search, adult-content filtering, spam, commonsense reasoning, computer vision, accessibility, and security in general.

Thesis Committee:
Manuel Blum (Chair)
Takeo Kanade
Michael Reiter
Josh Benaloh (Microsoft Research)
Jitendra Malik (University of California, Berkeley)

Jeannette Wing, Head, Computer Science Department
Randy Bryant, Dean, School of Computer Science

Keywords:
CAPTCHA, the ESP Game, Peekaboom, Verbosity, Phetch, human computation, automated Turing test, games with a purpose