Wikipedia

Human-based computation

This is an old revision of this page, as edited by 67.171.79.240 (talk) at 03:04, 15 August 2006. The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

In computer science, human-based computation or simply human computation is a technique where a computational process employs humans to perform its function, using human abilities to solve a certain problem or a set of problems. This approach explores differences in abilities and alternative costs between humans and computer agents to achieve symbiotic human-computer interaction.

In traditional computation, a human employs computers to solve a problem: a human provides a formalized problem description to a computer, and receives a solution to interpret. In human-based computation, the roles are reversed: a computer asks a person or often a large number of people to solve a problem, then collects, interprets, and integrates their solutions. Precursors of this idea are interactive programs requesting input from a user, e.g. asking a confirmation to delete a file. [Sims 91] used human visual perception and esthetic ability to implement evaluation function in evolutionary programming application and evolve pieces of graphic art this way. A more explicit example of Human-based computation is the ESP Game. ESP is a popular online game: many people play over 40 hours a week. By playing, they provide meaningful, accurate keyword labels for images on the Web; for instance, an image with a dog gets the label "dog." These labels can be used, among other things, to improve the accuracy of image search.

Human computation focuses on harnessing human time and energy for addressing problems that computers cannot yet tackle on their own. Although computers have advanced significantly in many respects over the last 50 years, they still do not possess the basic conceptual intelligence or perceptual capabilities that most humans take for granted. By leveraging human skills and abilities in a novel way, the hope is to solve large-scale computational problems that computers cannot yet solve and begin to teach computers many of these human talents.

Methods of human-based computation

  • Darwin [Vyssotsky, Morris, McIlroy 61] and Core War [Jones, Dewdney 84] These are activities where several programs written by people compete in a tournament (computational simulation) in which fittest programs will survive. Authors of the programs copy, modify, and recombine successful strategies to improve their chances of winning.
  • Interactive genetic algorithm [Sims 91] IGA enables the user to create an abstract drawing only by selecting his/her favorite images displayed on the computer screen, so human performs fitness computation. [Unemi 1998] Simulated breeding style introduces no explicit fitness, just selection, which is easier for human. In a typical IGA system, a computer program generates an image and presents it to a human user for evaluation/classification.
  • Wiki [Cunningham 95] enables editing the web content by multiple users, but more importantly, provides the mechanism for reversing the changes that allows for selection among several versions of the page. Wiki is sometimes interpreted as the backronym for "What I know is", which describes the knowledge contribution, storage and exchange function.
  • Human-based genetic algorithms [Kosorukoff 98] HBGA uses human selection in the same way as IGA, but also enables users to take part in innovation by performing intelligent mutation and crossover. In this method, all operators of a typical genetic algorithm are outsourced to humans (hence the name human-based). The first HBGA is 3form Free Knowledge Exchange that implements collaborative problem-solving mechanism.
  • Captcha (reverse Turing test) [Lillibridge 98, von Ahn 00] Automated tests to distinguish a human user from a computer program using open problems in AI that have no suitable algorithmic solutions.
  • Games with a Purpose [von Ahn 03]: These are programs that extract knowledge from people in an entertaining way. Some exaples include: The ESP Game, in which players contribute accurate keyword labels for images; Peekaboom, in which players locate objects within images; and Verbosity, which collects common-sense facts. The output of each of these games has multiple applications, including training artificial intelligence (AI) systems.

See also

References

  1. [Sims 91] Sims, K.: Artificial Evolution for Computer Graphics, Computer Graphics, 25(4) (SIGGRAPH'91), 319-328 (1991)
  2. [Unemi 98] Unemi, T.: A Design of multi-field user interface for simulated breeding, Proceedings of the Third Asian Fuzzy and Intelligent System Symposium, 489-494 (1998)
  3. [Kosorukoff 98] Alex Kosorukoff, Free Knowledge Exchange, human-based genetic algorithm on the web archive description
  4. [Lillibridge 98] Lillibridge et al. (1998) Method for selectively restricting access to computer systems, US Patent 6,195,698
  5. [Burgener 99] Twenty questions: the neural-net on the Internet archive website
  6. [Kosorukoff 00] Alex Kosorukoff (2000) Human-based genetic algorithm online
  7. [Cunningham 01] Cunningham, Ward and Leuf, Bo (2001): The Wiki Way. Quick Collaboration on the Web. Addison-Wesley, ISBN 0-201-71499-X.
  8. [Takagi 01] Hideyuki Takagi (2001), Interactive Evolutionary Computation: Fusion of the Capabilities of EC Optimization and Human Evaluation, Proceedings of the IEEE, vol.89, no. 9, pp. 1275-1296
  9. [Kosorukoff 01] Alex Kosorukoff, Human-based Genetic Algorithm. IEEE Transactions on Systems, Man, and Cybernetics, SMC-2001, 3464-3469
  10. [Kosorukoff 02] Alex Kosorukoff, David E. Goldberg, Genetic algorithm as a form of organization, Proceedings of Genetic and Evolutionary Computation Conference, GECCO-2002, pp 965-972
  11. [von Ahn 03] Luis von Ahn, Manuel Blum, Nick Hopper and John Langford CAPTCHA: Using Hard AI Problems for Security In Eurocrypt 2003
  12. [von Ahn 03] Luis von Ahn Method for labeling images through a computer game US Patent Application 10/875913
  13. [von Ahn 04] Luis von Ahn and Laura Dabbish Labeling Images with a Computer Game In ACM CHI 2004
  14. [Gentry 05] Craig Gentry, Zulfikar Ramzan, Stuart Stubblebine Secure Distributed Human Computation In Ninth International Conference on Financial Cryptography and Data Security FC'2005 online
  15. [von Ahn 06] Luis von Ahn, Mihir Kedia and Manuel Blum Verbosity: A Game for Collecting Common-Sense Facts To Appear in ACM CHI Notes 2006
  16. [von Ahn 06] Luis von Ahn, Shiry Ginosar, Mihir Kedia, Rouran Liu and Manuel Blum Improving Accessibility of the Web with a Computer Game To Appear in ACM CHI Notes 2006
Retrieved from "https://en.wikipedia.org/w/index.php?title=Human-based_computation&oldid=69723080"