Wikipedia

Human-based computation

This is an old revision of this page, as edited by JVittes (talk | contribs) at 06:24, 21 June 2006 (→References). 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 is a technique when 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 computer 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: 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. However, this concept in its explicit form appeared at the intersection of computer graphics and evolutionary computation. [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. The crucial difference here is agency: Sim's program was no longer an agent of its user, but rather a coordinator of many human evaluators who became agents of the program. Human-based genetic algorithm (HBGA) is a logical extension and a quite general model of this approach based on the idea of outsourcing. Thus, in HBGA humans also can contribute their innovative solutions into the process and have more control over the functions they are performing. Most implementations of HBGA also have some kind of motivation system that encourages humans to participate.

The following table from [Kosorukoff 00] uses the evolutionary computation model to describe four classes of computation, three of which rely on humans in some role. The classification is in terms of the roles (innovation or selection) performed in each case by humans and computational processes. This table also has a third dimension, determining how agents are organized. Here we assume that organization and coordination are performed by a program.

General class of organizational evolutionary methods
Selection agent
Innovation agent		ComputationalHuman
ComputationalParallel GAInteractive GA
HumanComputer-Aided DesignHuman-based GA

Methods of human-based computation

  • Darwin [Vyssotsky, Morris, McIlroy 61] and Core War [Jones, Dewdney 84] These are games 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 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 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] 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
  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=59765941"