Human Computation
Published on 22 Aug 2007 at 11:44 am.
1 Comment.
Filed under Computation, Internet, Programming, Research, Software, Technology.
My friend Carlos recently emailed me an interesting talk on leveraging human computation to solve difficult computational problems. The talk was by Luis von Ahn from the Computer Science Department from Carnegie Mellon University, and was presented as a Google Tech Talk last year on July 26, 2006.
As a physicist, I have always marvelled at the amount of time and effort people spend solving puzzles where the answers are known. I was surprised to learn from this talk that people have spent 9 Billion Hours playing computer solitaire in 2003! In the talk, Luis highlights that it took only 7 Million Human Hours to build the Empire State Building, which is only 6.8 days of world-wide Solitaire-playing. In addition, the Panama Canal took 20 Million Hours to build, which amounts to one day of Solitaire-playing. Personally, I prefer to work on unsolved problems. Granted, they are more difficult, but far more satisfying.
Luis von Ahn discussed ways in which computer scientists been taking advantage of this by introducing online games where they can extract important information from the players. One such game is the ESP game, where the two online players are paired up and are each given the same image. The goal is for the two players to look at the image and guess the word that the other player will type to describe the image. When there is a match, the server records the word as a keyword for the image. The goal is for the players to agree on as many keywords as possible in two minutes. Of course the human players get points, and enjoy the game. Once an array of keywords are accumulated, these words are listed as taboo, which means that the players have to come up with other words to win the game.
Another game that they have introduced is Peekaboom. In this game, there is a pair of online players who are assigned an image with keywords. The first player is given the image and the second player is given a blank screen. The first player with the image is also given a keyword and the player’s job is to get the second player to guess the keyword by clicking on a part of the image. A small area that the first player clicks on is sent to the second player’s screen revealing just a small part of the image. This continues until the second player guesses the keyword. At this point the server records the area of the image that has been sent to the second player. After this image has been given to several players, this data can be combined resulting in a statistically reasonable area of the image that refers to the keyword. One can even highlight image areas according to their importance to that keyword.
Verbosity is a game of words that use human players to encode a set of commonsense facts that are associated with words. It is a two-player word-guessing game with one playing a Narrator and the second playing the Guesser. During each round, the Narrator gets a word that he has to get the Guesser to guess. The Narrator uses a sentence template to create statements of fact about the word. When the Guesser guesses, the common-sense fact is more strongly associated with the word.
These are very useful methods to leverage human computation to solve some of the most important unsolved problems in computer science.
Kevin Knuth
Albany NY
joe on 22 Aug 2007 at 12:29 pm: 1
In animals, behavioral norms and rituals demonstrate an individual’s genetic fitness.
In humans, games train us to perform mental and physical skills and are ad hoc ways we measure ourselves against others.
These games are ways to have a pairs label data and derive statistical information based on consensus. Do the games have the same appeal, a human working against an unbiased test?
What if you draw a weak partner? These games seem to test the skills of pairs, not individuals. They may not have the same appeal as memorizing a ritual or working on a common, hard problem.