Human-based computation

Human-based computation (HBC), human-assisted computation,[1] ubiquitous human computing or distributed thinking (by analogy to distributed computing) is a computer science technique in which a machine performs its function by outsourcing certain steps to humans, usually as microwork. 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[2] to solve a problem; a human provides a formalized problem description and an algorithm 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 (apart from the historical meaning of "computer") research has its origins in the early work on interactive evolutionary computation. 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 the 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 aesthetic selection or interactive evolutionary computation (Takagi, 2001), 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.

A concept of the automatic Turing test pioneered by Moni Naor (1996) is another precursor of human-based computation. In Naor's test, the machine can control the access of humans and computers to a service by challenging them with a natural language processing (NLP) or computer vision (CV) problem to identify humans among them. The set of problems is chosen in a way that they have no algorithmic solution that is both effective and efficient at the moment. If it existed, such an algorithm could be easily performed by a computer, thus defeating the test. In fact, Moni Naor was modest by calling this an automated Turing test. The Imitation Game described by Alan Turing (1950) didn't propose using CV problems. It was only proposing a specific NLP task, while the Naor test identifies and explores a large class of problems, not necessarily from the domain of NLP, that could be used for the same purpose in both automated and non-automated versions of the test.

Finally, Human-based genetic algorithm (HBGA) encourages human participation in multiple different roles. Humans are not limited to the role of evaluator or some other predefined role, but can choose to perform a more diverse set of tasks. 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 allows humans to participate in all operations of a typical genetic algorithm. As a result of this, HBGA can process solutions 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 also be viewed as novel forms of social organization coordinated by a computer (Kosorukoff and Goldberg, 2002).

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.

Division of labor in computation
Innovation agent
Computer Human
Selection
agent		 Computer Genetic algorithm Computerized tests
Human Interactive genetic algorithm Human-based genetic algorithm

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

Incentives to participation

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

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 (Howe, 2006). However, others have argued that crowdsourcing ought to be distinguished from true human-based computation.[8] Crowdsourcing does indeed involve the distribution of computation tasks across a number of human agents, but Michelucci argues that this is not sufficient for it to be considered human computation. Human computation requires not just that a task be distributed across different agents, but also that the set of agents across which the task is distributed be mixed: some of them must be humans, but others must be traditional computers. It is this mixture of different types of agents in a computational system that gives human-based computation its distinctive character. Some instances of crowdsourcing do indeed meet this criterion, but not all of them do.

Human Computation organizes workers through a task market with APIs, task prices, and software-as-a-service protocols that allow employers / requesters to receive data produced by workers directly in to IT systems. As a result, many employers attempt to manage worker automatically through algorithms rather than responding to workers on a case-by-case basis or addressing their concerns. Responding to workers is difficult to scale to the employment levels enabled by human computation microwork platforms.[9] Workers in the system Mechanical Turk, for example, have reported that human computation employers can be unresponsive to their concerns and needs [10]

Applications

Human assistance can be helpful in solving any AI-complete problem, which by definition is a task which is infeasible for computers to do but feasible for humans. Specific practical applications include:

Further information: List of crowdsourcing projects

Criticism

Human-based computation has been criticized as exploitative and deceptive with the potential to undermine collective action (Zittrain 2010; Jafarinaimi 2012).

See also

References

  • Turing, A. M. (1950). Computing machinery and intelligence. Mind, 59, 433-460.
  • Dawkins, R. (1986) The Blind Watchmaker, Longman, 1986; Penguin Books 1988.
  • 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) U.S. Patent 5,375,195
  • 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) U.S. Patent 6,088,510
  • 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, 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 archive description
  • Lillibridge, M.D., et al. (1998) Method for selectively restricting access to computer systems, US Patent U.S. Patent 6,195,698
  • Burgener (1999) Twenty questions: the neural-net on the Internet archive 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 online
  • Kosorukoff, A. (2000) Human-based genetic algorithm online
  • 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 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 online
  • Fogarty, T.C., (2003) Automatic concept evolution, Proceedings of The Second IEEE International Conference on Cognitive Informatics.
  • von Ahn, L., Blum, M., Hopper, N., and Langford, J. (2003) CAPTCHA: Using Hard AI Problems for Security, in Advances in Cryptology, E. Biham, Ed., vol. 2656 of Lecture Notes in Computer Science (Springer, Berlin, 2003), pp. 294–311. online
  • von Ahn, L. (2003) Method for labeling images through a computer game US Patent Application 10/875913
  • von Ahn, L. and Dabbish, L. (2004) Labeling Images with a Computer Game. Proceedings of the SIGCHI Conference on Human Factors in Computing Systems (Association for Computing Machinery, New York, 2004), pp. 319–326. online
  • Estrada, D. and Lawhead, J. (2014) Gaming the Attention Economy. In The Handbook of Human Computation, Pietro Michelucci (ed.), (Springer, 2014) online
  • Fogarty, T.C. and Hammond, M.O. (2005) Co-operative OuLiPian Generative Literature using Human Based Evolutionary Computing, GECCO 2005, Washington DC.
  • Jafarinaimi, Nassim. "Exploring the character of participation in social media: the case of Google Image Labeler." Proceedings of the 2012 iConference. ACM, 2012. online
  • von Hippel, E. (2005) Democratizing Innovation, MIT Press online
  • Gentry, C., et al. (2005) Secure Distributed Human Computation In Ninth International Conference on Financial Cryptography and Data Security FC'2005 online
  • Howe, J. (2006) The Rise of Crowdsourcing, Wired Magazine, June 2006. online
  • von Ahn, L., Kedia, M., and Blum, M. (2006) Verbosity: A Game for Collecting Common-Sense Facts, ACM CHI Notes 2006 online
  • von Ahn, L., Ginosar, S., Kedia, M., and Blum, M. (2006) Improving Accessibility of the Web with a Computer Game, ACM CHI Notes 2006 online
  • Sunstein, C. (2006) Infotopia: How Many Minds Produce Knowledge, Oxford University Press, website
  • Tapscott, D., Williams, A. D. (2007) Wikinomics, Portfolio Hardcover website
  • Shahaf, D., Amir, E. (2007) Towards a theory of AI completeness. Commonsense 2007, 8th International Symposium on Logical Formalizations of Commonsense Reasoning online.
  • von Ahn, L., Maurer, B., McMillen, C., Abraham, D., and Blum, M. (2008) reCAPTCHA: Human-Based Character Recognition via Web Security Measures. Science, September 12, 2008. Pages 1465-1468. online
  • Malone, T.W., Laubacher, R., Dellarocas (2009) Harnessing Crowds: Mapping the Genome of Collective Intelligence online
  • Yu, L. and Nickerson, J. V. (2011) Cooks or Cobblers? Crowd Creativity through Combination online
  • Zittrain, J., Minds for Sale., March 2010. online

Footnotes

  1. ↑ Shahaf, 2007
  2. ↑ the term "computer" is used the modern usage of computer, not the one of human computer
  3. ↑ Estrada and Lawhead, "Gaming the Attention Economy" in The Springer Handbook of Human Computation, Pietro Michelucci (ed.), (Springer, 2014)
  4. ↑ http://sites.lsa.umich.edu/collectiveintelligence/wp-content/uploads/sites/176/2015/05/Rosenberg-CI-2015-Abstract.pdf
  5. ↑ https://mitpress.mit.edu/sites/default/files/titles/content/ecal2015/ch117.html
  6. ↑ http://news.discovery.com/human/life/swarms-of-humans-power-a-i-platform-150603.htm
  7. ↑ (Q&A) Your Assignment: Art
  8. ↑ Michelucci, Pietro (2014), "Foundations of Human Computation" in The Springer Handbook of Human Computation
  9. ↑ Irani, Lilly (forthcoming). "The Cultural Work of Microwork". New Media & Society. doi:10.1177/1461444813511926. Check date values in: |date= (help)
  10. ↑ Irani, Lilly; Silberman, Six (2013). "Turkopticon:Interrupting Workers Invisibility on Amazon Mechanical Turk". Proceedings of SIGCHI 2013. doi:10.1145/2470654.2470742.
  11. ↑ Yahoo!: US awarded 7,599,911
This article is issued from Wikipedia - version of the Saturday, March 19, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.