Transcript StevePresentation575

Human Computation
Steven Emory
CS 575
Human Issues in Computing
Overview
What is Human Computation?
History of Human Computation
Examples of Human Computation
Challenges in Human Computation
Definition of Computation
Normally we rely on computers to do all the
work
On input:
Step #1 (computer)
Step #2 (computer)
... (computer)
Step #n (computer)
Ouput
Definition of Human Computation
Some or all steps solved by human(s)
Roles reversed: Computer asks us to solve a
problem
On input:
Step #1
Step #2 (ask a human)
...
Step #n
Output
History of Human Computation
1980's: Interactive Genetic Algorithms
2000's: Human-Based Genetic Algorithms
2000's: Outsourced Human Spam
2000's: Interactive Guessing Games
Notes on Human Computation
While Interactive and Human-Based GAs can
employ the use of a single person, the term
Human Computation is typically only used when
many humans are involved
Difficult to get a lot of data out of just one person
Results are statistically better when many people
agree (if it's just one person are you sure he's telling
the truth?)
Humans are typically networked (not communicating,
collaborating, or cheating)
Quicksort Example
Bad Example: Quicksort
Input: Unsorted array
Select a pivot (human selection)
Swap last element with pivot element
Partition array using pivot element
Insert pivot element into correct position
Repeat above steps for left/right side partitions
Output: Sorted array
Quicksort Problems
Solved faster by computer alone
Not rewarding
Boring/painful
Wouldn't do this even if I was paid to do it
Using first row of students, would everyone pick
the same pivots?
Photomosaic Demo
To demonstrate that humans are better at some
things than computers, consider a photomosaic:
Can be solved by computer alone.
On input “image gallery,” “source image”
1.) Tile source image.
2.) From left-to-right, top-to-bottom, compare each
image in the image gallery to each tile in the source
image, inserting the gallery image with the lowest
error.
3.) Output photomosaic.
Photomosaic Problems
Noticeable visual artifacts (no image reuse)
Could use a randomized algorithm instead
Could optimize important features first
However, no general “select important features”
algorithm exists
Must ask a human (the user) to select important
features
Photomosaic Solutions
Revised algorithm:
On input “image gallery,” “source image”
1.) Tile source image.
2.) Select important features (ask human).
3.) Optimize (randomly) important features.
4.) Optimize (randomly) unimportant features.
5.) Output photomosaic.
Unlike the Quicksort example:
this is rewarding and fun
When to Use
When the problem:
is hard for a computer, but easy for a human
is not boring to humans (music, art, games)
is rewarding (financially or emotionally)
Human Computation Challenges
User interface design
Coordinating many human participants
Analogous to distributed computing
Honesty
Prolonged computation
Maintaining human interest and motivation
reCAPTCHA Example
Used to digitize old books (make e-books)
OCR normally works 99% of the time
OCR accuracy drops for older books
Old paper
Old printing techniques
Solution: Ask humans to determine words OCR
fails to classify
When enough humans agree, consider it solved
reCAPTCHA Example
Metadata Example
Algorithm: Assign metadata to images
Useful for content/multimedia management
systems (i.e. Istockphoto)
No algorithm exists for image labeling
Luis Von Ahn's solution: The ESP Game
http://www.espgame.org
ESP Game Demo
Metadata Example
Problem:
Getting humans to agree correctly
Electric Sheep Example
Brief fractal explanation:
Iterative process based on chaos, dynamical systems
Newton's Method Fractal
Solve az3 + bz2 + cz + d = 0 for complex numbers
a, b, c, d are fractal parameters
Cubic equation has 3 roots
Red = converges to root #1
Green = converges to root #2
Blue = converges to root #3
Black = fails to converge
Electric Sheep Example
Electric Sheep Example
Animated fractal screensaver application
Also an interactive genetic algorithm
Humans (users of screensaver) evaluate fitness
Animated fractal parameters are mutated
Algorithm has been running for years
http://www.electricsheep.org/
Electric Sheep Example
Outsourced Human Spam
On input “http://acm.calstatela.edu/forum”:
Find Register link (spam bot)
Download registration form (spam bot)
Fill out registration form (spam bot)
Find CAPTCHA (spam bot)
Solve CAPTCHA (human)
Send registration form (spam bot)
Output: SPAM!!!
Conclusions
There many hard/impossible to solve problems
Nothing shameful about using Human
Computation
Applications in art, music, computer vision,
security, content management
References
Luis Von Ahn
Google Talk lecture on Human Computation
http://www.cs.cmu.edu/~biglou/
http://www.espgame.org
The Art of Artificial Evolution (2008)
http://www.springerlink.com/content/r68831/?p=d04c
460aa17749eb8153fec3d0507f68&pi=9