Wikipedia

Human-based computation

This is an old revision of this page, as edited by Alex Kosorukoff (talk | contribs) at 17:59, 3 March 2006. The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

In computer science, a technique when an algorithm or computational process relies on human abilities to perform its function, e.g. to solve a certain computational problem or a set of problems. This approach explores differences in abilities and alternative costs between humans and computer agents to achieve human-computer symbiotic interaction. This approach was originated at the intersection of computer graphics and evolutionary computation by Karl Sims, who used human visual perception and esthetic ability to implement evaluation function in evolutionary programming application.

Methods of human-based computation

  • Interactive genetic algorithm [Sims 91] IGA enables the user to create an abstract drawing only be 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 generate 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 algorithm [Kosorukoff 98] HBGA uses human selection in the same way as IGA, but also enables users to take part in the innovation performing intelligent mutation and crossover, thus all operators of a typical GA are now outsourced to humans (hence the name human-based). The first HBGA (Free Knowledge Exchange) is in the form of a collaborative problem-solving game where a score measure the contribution of each person in solving problems of others.
  • Captcha (reverse Turing test) [Lillibridge 98] Automated tests to distinguish a human user from a computer program using open problems in AI that have no suitable algorithmic solutions. In some sense, they are also a reverse of IGA: a computer program generates an image and presents it to an agent for evaluation/classification, but uses a reply of the agent to classify it into human or non-human category.
  • Interactive online guessing games [Burgener 99, von Ahn 03]: These are programs that extract knowledge from people in an entertaining way. Some of them can be described in terms of HBGA model.

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 for webmasters
  4. [Lillibridge 98] 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. [Cunningham 01] Cunningham, Ward and Leuf, Bo (2001): The Wiki Way. Quick Collaboration on the Web. Addison-Wesley, ISBN 0-201-71499-X.
  7. [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
  8. [Kosorukoff 01] Alex Kosorukoff, Human-based Genetic Algorithm. IEEE Transactions on Systems, Man, and Cybernetics, SMC-2001, 3464-3469
  9. [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
  10. [von Ahn 03] Luis von Ahn, Manuel Blum, Nick Hopper and John Langford CAPTCHA: Using Hard AI Problems for Security In Eurocrypt 2003
  11. [von Ahn 03] Luis von Ahn Method for labeling images through a computer game US Patent Application 10/875913
  12. [von Ahn 04] Luis von Ahn and Laura Dabbish Labeling Images with a Computer Game In ACM CHI 2004
  13. [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
Retrieved from "https://en.wikipedia.org/w/index.php?title=Human-based_computation&oldid=42078829"