Human-based computation
Encyclopedia
Human-based computation is a computer science
technique in which a computational process performs its function by outsourcing
certain steps to humans. This approach uses 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. Human-based computation frequently reverses the roles; the computer asks a person or a large group of people to solve a problem, then collects, interprets, and integrates their solutions.
. The idea behind interactive evolutionary algorithms is due to Richard Dawkins
. In the Biomorphs software accompanying his book The Blind Watchmaker
(Dawkins, 1986) the preference of a human experimenter is used to guide the evolution of two-dimensional sets of line segments. In essence, this program asks a human to be the fitness function of an evolutionary algorithm, so that the algorithm can use human visual perception and aesthetic judgment to do something that a normal evolutionary algorithm cannot do. However, it is difficult to get enough evaluations from a single human if we want to evolve more complex shapes. Victor Johnston
and Karl Sims
extended this concept by harnessing power of many people for fitness evaluation (Caldwell and Johnston, 1991; Sims, 1991). As a result, their programs could evolve beautiful faces and pieces of art appealing to public. 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 became the topic of research in interactive evolutionary computation
or aesthetic selection, however the scope of this research was limited to outsourcing evaluation and, as a result, it was not fully exploring the full potential of the outsourcing.
Human-based genetic algorithm
(HBGA) encourages human participation in multiple different roles. Humans are not limited to the role of evaluator, but can choose to perform a more 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
. As a result of this 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. These algorithms can be also be viewed as novel forms of social organization coordinated by a computer program (Kosorukoff and Goldberg, 2002).
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.
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).
The algorithmic outsourcing techniques used in human-based computation are much more scalable than the manual or automated techniques used to manage outsourcing traditionally. It is this scalability that allows to easily distribute the effort among thousands of participants. It was suggested recently that this mass outsourcing is sufficiently different from traditional small-scale outsourcing to merit a new name crowdsourcing
(Howe, 2006).
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
technique in which a computational process performs its function by outsourcing
Outsourcing
Outsourcing is the process of contracting a business function to someone else.-Overview:The term outsourcing is used inconsistently but usually involves the contracting out of a business function - commonly one previously performed in-house - to an external provider...
certain steps to humans. This approach uses 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. Human-based computation frequently reverses the roles; the computer asks a person or a large group of people to solve a problem, then collects, interprets, and integrates their solutions.
Early work
Human-based computation research has its origins in the early work on interactive evolutionary computationInteractive evolutionary computation
Interactive evolutionary computation or aesthetic selection is a general term for methods of evolutionary computation that use human evaluation...
. The idea behind interactive evolutionary algorithms is due to Richard Dawkins
Richard Dawkins
Clinton Richard Dawkins, FRS, FRSL , known as Richard Dawkins, is a British ethologist, evolutionary biologist and author...
. In the Biomorphs software accompanying his book The Blind Watchmaker
The Blind Watchmaker
The Blind Watchmaker: Why the Evidence of Evolution Reveals a Universe without Design is a 1986 book by Richard Dawkins in which he presents an explanation of, and argument for, the theory of evolution by means of natural selection. He also presents arguments to refute certain criticisms made on...
(Dawkins, 1986) the preference of a human experimenter is used to guide the evolution of two-dimensional sets of line segments. In essence, this program asks a human to be the fitness function of an evolutionary algorithm, so that the algorithm can use human visual perception and aesthetic judgment to do something that a normal evolutionary algorithm cannot do. However, it is difficult to get enough evaluations from a single human if we want to evolve more complex shapes. Victor Johnston
Victor Johnston
Victor S. Johnston is a prominent Irish-born psychologist whose work emphasis is emotion, and event related potentials. His areas of study include cognitive engineering, biopsychology, and cognitive psychology. His major research interests are evolutionary psychology, electrophysiology and...
and Karl Sims
Karl Sims
Karl Sims is a computer graphics artist and researcher, who is best known for using particle systems and artificial life in computer animation....
extended this concept by harnessing power of many people for fitness evaluation (Caldwell and Johnston, 1991; Sims, 1991). As a result, their programs could evolve beautiful faces and pieces of art appealing to public. 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 became the topic of research in interactive evolutionary computation
Interactive evolutionary computation
Interactive evolutionary computation or aesthetic selection is a general term for methods of evolutionary computation that use human evaluation...
or aesthetic selection, however the scope of this research was limited to outsourcing evaluation and, as a result, it was not fully exploring the full potential of the outsourcing.
Human-based genetic algorithm
Human-based genetic algorithm
In evolutionary computation, a human-based genetic algorithm is a genetic algorithm that allows humans to contribute solution suggestions to the evolutionary process. For this purpose, a HBGA has human interfaces for initialization, mutation, and recombinant crossover. As well, it may have...
(HBGA) encourages human participation in multiple different roles. Humans are not limited to the role of evaluator, but can choose to perform a more 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
Genetic algorithm
A genetic algorithm is a search heuristic that mimics the process of natural evolution. This heuristic is routinely used to generate useful solutions to optimization and search problems...
. As a result of this 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. These algorithms can be also be viewed as novel forms of social organization coordinated by a computer program (Kosorukoff and Goldberg, 2002).
Classes of human-based computation
Human-based computation methods combine computers and humans in different roles. Malone (2009) 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.
| |||||||||||||
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) DarwinDarwin (programming game)Darwin was a programming game invented in August 1961 by Victor A. Vyssotsky, Robert Morris Sr., and M. Douglas McIlroy. The game was developed at Bell Labs, and played on an IBM 7090 mainframe there...
(Vyssotsky, Morris, McIlroy, 1961) and Core WarCore WarCore War is a programming game in which two or more battle programs compete for the control of the "Memory Array Redcode Simulator" virtual computer . These battle programs are written in an abstract assembly language called Redcode...
(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 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.
- (HH2) WikiWikiA wiki is a website that allows the creation and editing of any number of interlinked web pages via a web browser using a simplified markup language or a WYSIWYG text editor. Wikis are typically powered by wiki software and are often used collaboratively by multiple users. Examples include...
(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).
- (HH3) Human-based genetic algorithmHuman-based genetic algorithmIn evolutionary computation, a human-based genetic algorithm is a genetic algorithm that allows humans to contribute solution suggestions to the evolutionary process. For this purpose, a HBGA has human interfaces for initialization, mutation, and recombinant crossover. As well, it may have...
(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 algorithmGenetic algorithmA genetic algorithm is a search heuristic that mimics the process of natural evolution. This heuristic is routinely used to generate useful solutions to optimization and search problems...
are outsourced to humans (hence the origin of human-based). This idea is extended to integrating crowds with genetic algorithm to study creativity in 2011 (Yu and Nickerson, 2011).
- (HH1) Social searchSocial searchSocial search or a social search engine is a type of web search that takes into account the Social Graph of the person initiating the search query...
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. DiggDiggDigg is a social news website. Prior to Digg v4, its cornerstone function consisted of letting people vote stories up or down, called digging and burying, respectively. Digg's popularity prompted the creation of copycat social networking sites with story submission and voting systems...
and RedditRedditreddit is a social news website where the registered users submit content, in the form of either a link or a text "self" post. Other users then vote the submission "up" or "down," which is used to rank the post and determine its position on the site's pages and front page.Reddit was originally...
are recently popular examples.
- (HC) Computerized tests. A computer generates a problem and presents it to evaluate a user. For example CAPTCHACAPTCHAA CAPTCHA is a type of challenge-response test used in computing as an attempt to ensure that the response is generated by a person. The process usually involves one computer asking a user to complete a simple test which the computer is able to generate and grade...
tells human users from computer programs by presenting a problem that is supposedly easy for a human and difficult for a computer. While CAPTCHAs are effective security measures for preventing automated abuse of online services, the human effort spent solving them is otherwise wasted. The reCAPTCHAReCAPTCHAreCAPTCHA is a system originally developed at Carnegie Mellon University's main Pittsburgh campus. It uses CAPTCHA to help digitize the text of books while protecting websites from bots attempting to access restricted areas. On September 16, 2009, Google acquired reCAPTCHA. reCAPTCHA is currently...
system makes use of these human cycles to help digitize books by presenting words from scanned old books that optical character recognition cannot decipher. (von Ahn et al., 2008).
- (HC) Interactive online games: 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 Mechanical TurkAmazon Mechanical TurkThe Amazon Mechanical Turk is a crowdsourcing Internet marketplace that enables computer programmers to co-ordinate the use of human intelligence to perform tasks that computers are unable to do yet. It is one of the suites of Amazon Web Services...
, Answerly Operator, ChaCha Search guide, Mahalo.comMahalo.comMahalo.com is a web directory and Internet-based knowledge exchange launched in alpha test in May 2007 by Jason Calacanis...
Answers members), HumanGrid - Desire to diversify their activity (e.g. "people aren't asked in their daily lives to be creative" )
- Esthetic satisfaction
- Curiosity, desire to test if it works
- Volunteerism, desire to support a cause of the project
- Reciprocity, exchange, mutual help
- Desire to be entertained with the competitive or cooperative 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
- Fun
- Increasing online reputation/recognition
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.The algorithmic outsourcing techniques used in human-based computation are much more scalable than the manual or automated techniques used to manage outsourcing traditionally. It is this scalability that allows to easily distribute the effort among thousands of participants. It was suggested recently that this mass outsourcing is sufficiently different from traditional small-scale outsourcing to merit a new name crowdsourcing
Crowdsourcing
Crowdsourcing is the act of sourcing tasks traditionally performed by specific individuals to a group of people or community through an open call....
(Howe, 2006).
Human-assisted search ranking
An approach to improving internet search involves combining automated ranking with human editorial input.See also
- Citizen scienceCitizen scienceCitizen science is a term used for the systematic collection and analysis of data; development of technology; testing of natural phenomena; and the dissemination of these activities by researchers on a primarily avocational basis...
- Collaborative intelligenceCollaborative intelligenceCollaborative intelligence is a term used in several disciplines, and has several different meanings. In a business setting, it can describe the result of accessing a network of people...
- Collaborative Innovation NetworksCollaborative Innovation NetworksA Collaborative Innovation Network, or CoIN, is a social construct used to describe innovative teams. It has been defined by the originator of the term, Peter Gloor as "a cyberteam of self-motivated people with a collective vision, enabled by the Web to collaborate in achieving a common goal by...
- Collaborative human interpreterCollaborative human interpreterThe Collaborative Human Interpreter is a proposed software interface for human-based computation specially designed for collectingand making use of human intelligence in a computer program.One typical usage is implementing...
- CrowdsourcingCrowdsourcingCrowdsourcing is the act of sourcing tasks traditionally performed by specific individuals to a group of people or community through an open call....
- Game with a purpose (or GWAP)
- Galaxy ZooGalaxy ZooGalaxy Zoo is an online astronomy project which invites members of the public to assist in the morphological classification of large numbers of galaxies. It is an example of citizen science as it enlists the help of members of the public to help in scientific research. An improved version—Galaxy...
- Human computerHuman computerThe term "computer", in use from the mid 17th century, meant "one who computes": a person performing mathematical calculations, before electronic computers became commercially available....
- Human Computer Information RetrievalHuman Computer Information RetrievalHuman–computer information retrieval is the study of information retrieval techniques that bring human intelligence into the search process...
- Simulated realitySimulated realitySimulated reality is the proposition that reality could be simulated—perhaps by computer simulation—to a degree indistinguishable from "true" reality. It could contain conscious minds which may or may not be fully aware that they are living inside a simulation....
- Social softwareSocial softwareSocial software applications include communication tools and interactive tools. Communication tools typically handle the capturing, storing and presentation of communication, usually written but increasingly including audio and video as well. Interactive tools handle mediated interactions between a...
- Social computingSocial computingSocial computing is a general term for an area of computer science that is concerned with the intersection of social behavior and computational systems. It has become an important concept for use in business. It is used in two ways as detailed below....
- Social organization
- Symbiotic intelligence
- Zooniverse (citizen science project)Zooniverse (citizen science project)Zooniverse is a citizen science web portal that grew from the original Galaxy Zoo project. It hosts numerous projects which allow users to participate in scientific research from classifying galaxies to collating climate data...
External links
- Human Computation, a Google Tech Talk by Luis von AhnLuis von AhnLuis von Ahn is an entrepreneur and an associate professor in the Computer Science Department at Carnegie Mellon University. He is known as one of the pioneers of the idea of crowdsourcing. He is the founder of the company reCAPTCHA, which was sold to Google in 2009...
- Utyp, Open Source Human Computation based Search Engine for images and pictures utilizing a Flash game