Human-based computation

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 is a logical extension of this approach where human also can contribute their innovative solutions into the process and thus have more control over the functions they are performing.

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 Computational Human Computational Parallel GA Interactive GA Human Computer-Aided Design Human-based GA

Methods of human-based computation

• 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 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

1. [Kosorukoff 00] Alex Kosorukoff (2000) Human-based genetic algorithm online
2. [Cunningham 01] Cunningham, Ward and Leuf, Bo (2001): The Wiki Way. Quick Collaboration on the Web. Addison-Wesley, ISBN 0-201-71499-X.
3. [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
4. [Kosorukoff 01] Alex Kosorukoff, Human-based Genetic Algorithm. IEEE Transactions on Systems, Man, and Cybernetics, SMC-2001, 3464-3469
5. [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
6. [von Ahn 03] Luis von Ahn, Manuel Blum, Nick Hopper and John Langford CAPTCHA: Using Hard AI Problems for Security In Eurocrypt 2003
7. [von Ahn 03] Luis von Ahn Method for labeling images through a computer game US Patent Application 10/875913
8. [von Ahn 04] Luis von Ahn and Laura Dabbish Labeling Images with a Computer Game In ACM CHI 2004
9. [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