View source for Human-based computation

In [[computer science]], '''human-based computation''' is a technique when a computational process performs its function via [[outsourcing]] certain steps to humans (Kosorukoff, 2001). This approach leverages differences in abilities and alternative costs between humans and computer agents to achieve symbiotic human-computer interaction.

In traditional computation, a human employs a 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 often reversed: the computer asks a person or a large number of people to solve a problem, then collects, interprets, and integrates their solutions.

==Early work==

Early work implementing this concept was made by Victor Johnston and Karl Sims. They used human evaluation in an [[evolutionary computation]] (EC), by asking many humans to, in essence, be the fitness function for an evolutionary algorithm using their visual perception and aesthetic judgments  (Caldwell and Johnston, 1991; Sims, 1991). As a result, their programs could evolve beautiful faces and pieces of art. These programs effectively reversed the common interaction between computers and humans. In these programs, the computer is no longer an agent of its user, but instead, a coordinator aggregating efforts of many human evaluators. These and other similar research efforts were generalized as [[interactive evolutionary computation]] or aestetic selection, however the full potential of the technique was not fully explored as the role of humans was limited to evaluating solutions.

[[Human-based genetic algorithm]] (HBGA) is the EC method that allowed human participation in multiple different roles. In HBGA, humans are not limited to the role of evaluator, but can perform a diverse set of functions. In particular, they can contribute their innovative solutions into the evolutionary process, make incremental changes to existing  solutions, and perform intelligent recombination. In short, HBGA outsources to humans all operations of a typical [[genetic algorithm]] and can be viewed as a form of social organization coordinated by a computer program (Kosorukoff and Goldberg, 2002). As a result of outsourcing, HBGA can process the representations for which there is no computational innovation operators available, for example, natural languages. Thus, HBGA obviated the need for a fixed representational scheme that was a limiting factor of both standard and interactive EC.

==Classes of human-based computation==

Human-based computation methods combine computers and humans in different roles. Kosorukoff (2000) proposed a way to describe division of labor in computation, that groups human-based methods into three classes. The following table uses the evolutionary computation model to describe four classes of computation, three of which rely on humans in some role. For each class, a representative example is shown. The classification is in terms of the roles (innovation or selection) performed in each case by humans and computational processes. This table is a slice of three-dimensional table. The third dimension defines if the organizational function is performed by humans or a computer. Here it is assumed to be performed by a computer.

<center>
<table border=1 cellpadding=0 cellspacing=0 bgcolor=white><tr><td>

<table width=640 border=0 cellpadding=5 cellspacing=1 bgcolor=lightblue>
<tr><th colspan=4>Division of labor in computation</th></tr>
<tr bgcolor="#E0E0FF"><th bgcolor=white><font color="#A0A0FF">Selection agent</font><br><hr><font color="#FFA0A0">Innovation agent</font></th><th>Computer</th><th>Human</th></tr>
<tr><th bgcolor="#FFE0E0">Computer</th><th>[[Genetic Algorithm]]</th><th>[[Interactive genetic algorithm]]</th></tr>

<tr><th bgcolor="#FFE0E0">Human</th><th>[[Computer-adaptive test|Computerized Tests]]</th><th>[[Human-based genetic algorithm]]</th></tr>
</table>
</table>
</center>

Classes of human-based computation from this table can be referred by two-letter abbreviations: HC, CH, HH. Here the first letter identifies the type of agents performing innovation, the second letter specifies the type of selection agents. In some implementations (wiki is the most common example), human-based selection functionality might be limited, it can be shown with small h.

==Methods of human-based computation==
* (HC) [[Darwin (programming game)|Darwin]] (Vyssotsky, Morris, McIlroy, 1961) and [[Core War]] (Jones, Dewdney 1984) 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.

* (CH) [[Interactive genetic algorithm|Interactive EC]] (Caldwell and Johnston, 1991; Sims, 1991) IEC enables the user to create an abstract drawing only by selecting his/her favorite images, so human only performs fitness computation and software performs innovative role. [Unemi 1998] Simulated breeding style introduces no explicit fitness, just selection, which is easier for humans.

* (HH<sub>2</sub>) [[Wiki]] (Cunningham, 1995) enabled editing the web content by multiple users, i.e. supported two types of human-based innovation (contributing new page and its incremental edits). However, the selection mechanism was absent until 2002, when wiki has been augmented with a revision history allowing for reversing of unhelpful changes. This provided means for selection among several versions of the same page and turned wiki into a tool supporting collaborative content evolution (would be classified as human-based evolution strategy in EC terms).

* (HH<sub>3</sub>) [[Human-based genetic algorithm]] (Kosorukoff, 1998) uses both human-based selection and three types of human-based innovation (contributing new content, mutation, and recombination). Thus, all operators of a typical [[genetic algorithm]] are outsourced to humans (hence the origin of '''human-based'''). Examples include the [[3form|3form Free Knowledge Exchange]] ([http://3form.com website]), [[Knowledge iN]], and [[Yahoo! Answers]], all of which implement some form of collaborative problem-solving.

* (HH<sub>1</sub>) [[Social search]] applications accept contributions from users and attempt to use human evaluation to select the fittest contributions that get to the top of the list. These use one type of human-based innovation. Early work was done in the context of HBGA. [[Digg]] and [[Reddit]] are recently popular examples.

* (HC) Computerized tests. A computer generates a problem and presents it to evaluate a user. For example [[CAPTCHA]], a [[reverse Turing test]], tells human users from computer programs by presenting a problem that is supposedly easy for a human and difficult for a computer (Suggested by [[Moni Naor]], 1996). Unfortunately, the results obtained from humans are usually discarded. This makes it an example of wasting human computation.

* (HC) Interactive online [[guessing game]]s: These are programs that extract knowledge from people in an entertaining way (Burgener, 1999; von Ahn 2003).

==Incentives to participation==

In different human-based computation projects people are motivated by one or more of the following.

* Receiving a fair share of the result
* Direct monetary compensation (e.g. in Amazon's Mechanical turk)
* Desire to diversify their activity (e.g. "people aren't asked in their daily lives to be creative" <ref>[http://www.wired.com/techbiz/media/news/2007/07/crowd_captain (Q&A) Your Assignment: Art]</ref>)
* Esthetic satisfaction
* Curiosity, desire to test if it works
* Volunteerism, desire to support a cause of the project
* Reciprocity, exchange, mutual help
* Competitive spirit of a game
* Desire to communicate and share knowledge
* Desire to share a user innovation to see if someone else can improve on it
* Desire to game the system and influence the final result

Many projects had explored various combinations of these incentives. See more information about motivation of participants in these projects in Kosorukoff (2000) and 
von Hippel (2005).

==Human-based computation as a form of social organization==

Viewed as a form of social organization, human-based computation often surprisingly turns out to be more robust and productive than traditional organizations (Kosorukoff and Goldberg, 2002). The latter depend on obligations to maintain their more or less fixed structure, be functional and stable. Each of them is similar to a carefully designed mechanism with humans as its parts. However, this limits the freedom of their human employees and subjects them to various kinds of stresses. Most people, unlike mechanical parts, find it difficult to adapt to some fixed roles that best fit the organization. Evolutionary human-computation projects offer a natural solution to this problem. They adapt organizational structure to human spontaneity, accommodate human mistakes and creativity, and utilize both in a constructive way. This leaves their participants free from obligations without endangering the functionality of the whole, making people happier. There are still some challenging research problems that need to be solved before we can realize the full potential of this idea.

==See also==

* [[Simulated reality]]
* [[Social software]]
* [[Social computing]]
* [[Social organization]]
* [[Symbiotic intelligence]]
* [[Collaborative intelligence]]
* [[Collaborative human interpreter]]
* [[Human computer]]
* [[Crowdsourcing]]

==References==
# Caldwell, C. and Johnston V. S. (1991), Tracking a Criminal Suspect through "Face-Space" with a Genetic Algorithm, in Proceedings of the Fourth International Conference on Genetic Algorithm, Morgan Kaufmann Publisher, pp.416-421, July 1991. (US Patent 5,375,195 filed 1992.06.29)
# Sims, K. (1991) Artificial Evolution for Computer Graphics, Computer Graphics, 25(4) (SIGGRAPH'91), 319-328 (US Patent 6,088,510 filed 1992.07.02)
# Herdy, M. (1996) Evolution strategies with subjective selection. In Parallel Problem Solving from Nature, PPSN IV, Volume 1141 of LNCS (pp. 22-31)
# Moni Naor (1996) Verification of a human in the loop, or Identification via the Turing Test, [http://www.wisdom.weizmann.ac.il/~naor/PAPERS/human_abs.html online].
# Unemi, T. (1998) A Design of multi-field user interface for simulated breeding, Proceedings of the Third Asian Fuzzy and Intelligent System Symposium, 489-494
# Kosorukoff (1998) Alex Kosorukoff, Free Knowledge Exchange, human-based genetic algorithm on the web [http://web.archive.org/web/19991122225801/http://formula.virtualave.net/ archive] [http://3form.com/formula/about-us.html description]
# Lillibridge et al (1998) Method for selectively restricting access to computer systems, US Patent {{US patent|6195698}}
# Burgener (1999) Twenty questions: the neural-net on the Internet [http://web.archive.org/web/20000229091147/http://www.20q.net/index.html archive] [http://20q.net website]
# Kosorukoff, A. (2000) Social classification structures. Optimal decision making in an organization, Genetic and Evolutionary Computation Conference, GECCO-2000, Late breaking papers, 175--178 [http://www.ews.uiuc.edu/~kosoruko/pub/classtre.pdf online]
# Kosorukoff, A. (2000) Human-based genetic algorithm [http://www.geocities.com/alex+kosorukoff/hbga/hbga.html online]
# [[Ward Cunningham|Cunningham, Ward]] and Leuf, Bo (2001): The Wiki Way. Quick Collaboration on the Web. Addison-Wesley, ISBN 0-201-71499-X.
# 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
# Kosorukoff, A (2001), Human-based Genetic Algorithm. IEEE Transactions on Systems, Man, and Cybernetics, SMC-2001, 3464-3469
# Kosorukoff, A. & Goldberg, D. E. (2001) Genetic algorithms for social innovation and creativity (Illigal report No 2001005). Urbana, IL: University of Illinois at Urbana-Champaign [http://www.ews.uiuc.edu/~kosoruko/pub/2001005.pdf online]
# Kosorukoff, A, Goldberg D. E. (2002), Genetic algorithm as a form of organization, Proceedings of Genetic and Evolutionary Computation Conference, GECCO-2002, pp 965-972
# Fogarty, T.C., (2003), Automatic concept evolution, Proceedings of The Second IEEE International Conference on Cognitive Informatics. 
# von Ahn, L et al (2003) CAPTCHA: Using Hard AI Problems for Security In Eurocrypt 2003
# von Ahn, L (2003) Method for labeling images through a computer game [http://appft1.uspto.gov/netacgi/nph-Parser?Sect1=PTO2&Sect2=HITOFF&u=%2Fnetahtml%2FPTO%2Fsearch-adv.html&r=1&p=1&f=G&l=50&d=PG01&S1=%28%22von+Ahn%22.IN.%29&OS=IN/%22von+Ahn%22&RS=IN/%22von+Ahn%22 US Patent Application 10/875913]
# von Ahn, L, Dabbish, L (2004) Labeling Images with a Computer Game In ACM CHI 2004 [http://www.cs.cmu.edu/~biglou/ESP.pdf online]
# Fogarty, T.C. and Hammond, M.O. (2005) Co-operative OuLiPian Generative Literature using Human Based Evolutionary Computing, GECCO 2005, Washington DC.
# von Hippel, E. (2005)  Democratizing Innovation, MIT Press [http://web.mit.edu/evhippel/www/democ1.htm online]
# Gentry, C et al (2005) Secure Distributed Human Computation In Ninth International Conference on Financial Cryptography and Data Security FC'2005 [http://fc05.ifca.ai/p26.pdf online]
# von Ahn, L et al (2006) Verbosity: A Game for Collecting Common-Sense Facts, ACM CHI Notes 2006 [http://www.cs.cmu.edu/~biglou/Verbosity.pdf online]
# von Ahn, L at al (2006) Improving Accessibility of the Web with a Computer Game, ACM CHI Notes 2006 [http://www.cs.cmu.edu/~biglou/Phetch.pdf online]
# Sunstein, C. (2006) Infotopia: How Many Minds Produce Knowledge, Oxford University Press, [http://www.oup.com/us/catalog/general/subject/Law/TechnologyandTelecomsLaw/?view=usa&ci=9780195189285 website]
# Tapscott, D., Williams, A. D. (2007) Wikinomics, Portfolio Hardcover [http://www.wikinomics.com website]

==Footnotes==
{{reflist|2}}

==External links==

# [http://video.google.com/videoplay?docid=-8246463980976635143 Human computation], a talk by Luis von Ahn
# [http://utyp.net/ Utyp], Open Source Human Computation based Search Engine for images and pictures utilizing a [http://www.nthinking.net/miss/www.html Flash game]
[[Category:Human-based computation]]

[[pt:Computação humana]]
{{WikiDoc Sources}}