Toward Complexity Measures for Systems Involving Human Computation
DOI:
https://doi.org/10.15346/hc.v1i1.4Keywords:
Human Computation, Complexity TheoryAbstract
This paper introduces the Human Oracle Model as a method for characterizing and quantifying the use of human processing power as part of an algorithmic process. The utility of this model is demonstrated through a comparative algorithmic analysis of several well-known human computation systems, as well as the definition of a preliminary characterization of the space of human computation under this model. Through this research, we hope to gain insight about the challenges unique to human computation and direct the search for efficient human computation algorithms.References
Bertini, E and Lalanne, D. (2010). Investigating and reflecting on the integration of automatic data analysis and visualization in knowledge discovery. SIGKDD Explorations Newsletter 11, 2 (2010), 9–18.
Cooper, S, Khatib, F, Treuille, A, Barbero, J, Lee, J, Beenen, M, Leaver-Fay, A, Baker, D, Popovic, Z, and others, . (2010). Predicting protein structures with a multiplayer online game. Nature 466, 7307 (2010), 756–760.
Crouser, R and Chang, R. (2012). An Affordance-Based Framework for Human Computation and Human-Computer Collaboration. Visualization and Computer Graphics, IEEE Trans. on 18, 12 (2012), 2859–2868.
Donmez, P and Carbonell, J. (2008). Proactive learning: cost-sensitive active learning with multiple imperfect oracles. In Proc. 17th ACM Conf. on Information and knowledge management. ACM, 619–628.
Girouard, A, Solovey, E, Hirshfield, L, Chauncey, K, Sassaroli, A, Fantini, S, and Jacob, R. (2009). Distinguishing difficulty levels with non-invasive brain activity measurements. In Human-Computer Interaction. Springer, 440–452.
Ho, C, Chang, T, Lee, J, Hsu, J, and Chen, K. (2009). KissKissBan: a competitive human computation game for image annotation. In Proc. SIGKDD Workshop on Human Computation. ACM, 11–14.
Law, E and von Ahn, L. (2009). Input-agreement: a new mechanism for collecting data using human computation games. In Proc. 27th SIGCHI Conf. on Human factors in computing systems. 1197–1206.
Law, E, von Ahn, L, Dannenberg, R, and Crawford, M. (2007). Tagatune: A game for music and sound annotation. Proc. of ISMIR (Vienna, Austria) (2007).
Mason, W and Watts, D. (2010). Financial incentives and the performance of crowds. ACM SigKDD Explorations Newsletter 11, 2 (2010), 100–108.
Quinn, A and Bederson, B. (2011). Human computation: a survey and taxonomy of a growing field. In Proc. 29th SIGCHI Conf. on Human factors in computing systems. ACM, 1403–1412.
Shahaf, D and Amir, E. (2007). Towards a theory of AI completeness.. In Logical Formalizations of Commonsense Reasoning. 150– 155.
Singer, Y and Mittal, M. (2011). Pricing Tasks in Online Labor Markets.. In Proc. Workshop on Human Computation at the 25th AAAI Conf. on AI.
Turing, A. (1938). Systems of logic based on ordinals: a dissertation. Ph.D. Dissertation. Cambridge.
von Ahn, L. (2006). Games with a purpose. Computer 39, 6 (2006), 92–94.
von Ahn, L and Dabbish, L. (2004). Labeling images with a computer game. In Proc. 22nd SIGCHI Conf. on Human factors in computing systems. ACM, 319–326.
von Ahn, L, Liu, R, and Blum, M. (2006). Peekaboom: a game for locating objects in images. In Proc. 24th SIGCHI Conf. on Human factors in computing systems. ACM, 55–64.
von Ahn, L, Maurer, B, McMillen, C, Abraham, D, and Blum, M. (2008). reCAPTCHA: human-based character recognition via web security measures. Science 321, 5895 (2008), 1465–1468.
Wallace, B, Small, K, Brodley, C, and Trikalinos, T. (2011). Who Should Label What? Instance Allocation in Multiple Expert Active Learning. In SDM. 176–187.
Downloads
Published
How to Cite
Issue
Section
License
Authors who publish with this journal agree to the following terms:- Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).
