Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

Work on evaluating and improving the relevance of web search engines typically use human relevance judgments or clickthrough data. Both these methods look at the problem of learning the mapping from queries to web pages. In this paper, we identify some issues with this approach, and suggest an alternative approach, namely, learning a mapping from web pages to queries. In particular, we use human computation games to elicit data about web pages from players that can be used to improve search. We describe three human computation games that we developed, with a focus on Page Hunt, a single-player game. We describe experiments we conducted with several hundred game players, highlight some interesting aspects of the data obtained and define the 'findability' metric. We also show how we automatically extract query alterations for use in query refinement using techniques from bitext matching. The data that we elicit from players has several other applications including providing metadata for pages and identifying ranking issues.

REFERENCES

• 1: Paul N. Bennett , David Maxwell Chickering , Anton Mityagin, Learning consensus opinion: mining data from a labeling game, Proceedings of the 18th international conference on World wide web, April 20-24, 2009, Madrid, Spain [doi>10.1145/1526709.1526727]
• 2: Peter F. Brown , Vincent J. Della Pietra , Stephen A. Della Pietra , Robert L. Mercer, The mathematics of statistical machine translation: parameter estimation, Computational Linguistics, v.19 n.2, June 1993
• 3: A. Dempster, N. Laird, and D. Rubin. Likelihood from incomplete data via the EM algorithm. Journal of the Royal Statistical Society, Series B, 39(1):1--38, 1977.
• 4: D. Edery and E. Mollick. Changing the Game: How Video Games Are Transforming the Future of Business. Pearson Education Inc., 2009.
• 5: Nigel Ford , T. D. Wilson , Allen Foster , David Ellis , Amanda Spink, Information seeking and mediated searching. Part 4: cognitive styles in information seeking, Journal of the American Society for Information Science and Technology, v.53 n.9, p.728-735, August 2002 [doi>10.1002/asi.10084]
• 6: Philipp Koehn , Franz Josef Och , Daniel Marcu, Statistical phrase-based translation, Proceedings of the 2003 Conference of the North American Chapter of the Association for Computational Linguistics on Human Language Technology, p.48-54, May 27-June 01, 2003, Edmonton, Canada [doi>10.3115/1073445.1073462]
• 7: E. Law, A. Mityagin, and M. Chickering. Building human-computation games for search. In Submission.
• 8: Edith Law , Anton Mityagin , Max Chickering, Intentions: a game for classifying search query intent, Proceedings of the 27th international conference extended abstracts on Human factors in computing systems, April 04-09, 2009, Boston, MA, USA [doi>10.1145/1520340.1520575]
• 9: E. Law, L. von Ahn, R. B. Dannenberg, and M. Crawford. Tagatune: A game for music and sound annotation. In Proceedings of the Eighth International Conference on Music Information Retrieval, pages 361--364, Vienna, Austria, 2007. Austrian Computer Society.
• 10: Thomas W. Malone, What makes things fun to learn? heuristics for designing instructional computer games, Proceedings of the 3rd ACM SIGSMALL symposium and the first SIGPC symposium on Small systems, p.162-169, September 18-19, 1980, Palo Alto, California, United States [doi>10.1145/800088.802839]
• 11: Thomas W. Malone, Heuristics for designing enjoyable user interfaces: Lessons from computer games, Proceedings of the 1982 conference on Human factors in computing systems, p.63-68, March 15-17, 1982, Gaithersburg, Maryland, United States [doi>10.1145/800049.801756]
• 12: Marc McDonald , Robert Musson , Ross Smith, The practical guide to defect prevention, Microsoft Press, Redmond, WA, 2007
• 13: NIST 2008 Machine Translation Evaluation. http://www.nist.gov/speech/tests/mt/2008/doc/mt08_official_results_v0.html
• 14: T. Paek, Y.-C. Ju, and Chris Meek. People watcher: A game for eliciting human-transcribed data for automated directory assistance. In INTERSPEECH '07, pages 1322--1325, 2007.
• 15: C. Quirk, C. Brockett, and W. B. Dolan. Monolingual Machine Translation for Paraphrase Generation. In EMNLP '04. Barcelona, Spain, 2004.
• 16: Stephan Vogel , Hermann Ney , Christoph Tillmann, HMM-based word alignment in statistical translation, Proceedings of the 16th conference on Computational linguistics, August 05-09, 1996, Copenhagen, Denmark [doi>10.3115/993268.993313]
• 17: Luis von Ahn, Games with a Purpose, Computer, v.39 n.6, p.92-94, June 2006 [doi>10.1109/MC.2006.196]
• 18: Luis von Ahn , Laura Dabbish, Labeling images with a computer game, Proceedings of the SIGCHI conference on Human factors in computing systems, p.319-326, April 24-29, 2004, Vienna, Austria [doi>10.1145/985692.985733]
• 19: Luis von Ahn , Laura Dabbish, Designing games with a purpose, Communications of the ACM, v.51 n.8, August 2008 [doi>10.1145/1378704.1378719]
• 20: L. von Ahn, S. Ginosar, M. Kedia, and M. Blum. Improving image search with phetch. In ICASSP '07, pages 15 -- 20, April 2007.
• 21: Luis von Ahn , Shiry Ginosar , Mihir Kedia , Ruoran Liu , Manuel Blum, Improving accessibility of the web with a computer game, Proceedings of the SIGCHI conference on Human Factors in computing systems, April 22-27, 2006, Montréal, Québec, Canada [doi>10.1145/1124772.1124785]
• 22: Luis von Ahn , Mihir Kedia , Manuel Blum, Verbosity: a game for collecting common-sense facts, Proceedings of the SIGCHI conference on Human Factors in computing systems, April 22-27, 2006, Montréal, Québec, Canada [doi>10.1145/1124772.1124784]
• 23: Luis von Ahn , Ruoran Liu , Manuel Blum, Peekaboom: a game for locating objects in images, Proceedings of the SIGCHI conference on Human Factors in computing systems, April 22-27, 2006, Montréal, Québec, Canada [doi>10.1145/1124772.1124782]
• 24: I. Weber, S. Robertson and M. Vojnovic. Rethinking the ESP Game. Technical Report, Microsoft Research, MSR-TR-2008-132, Sept. 2008.
• 25: Eugene Agichtein , Eric Brill , Susan Dumais, Improving web search ranking by incorporating user behavior information, Proceedings of the 29th annual international ACM SIGIR conference on Research and development in information retrieval, August 06-11, 2006, Seattle, Washington, USA [doi>10.1145/1148170.1148177]
• 26: Georg Buscher , Andreas Dengel , Ludger van Elst, Query expansion using gaze-based feedback on the subdocument level, Proceedings of the 31st annual international ACM SIGIR conference on Research and development in information retrieval, July 20-24, 2008, Singapore, Singapore [doi>10.1145/1390334.1390401]
• 27: Leif Azzopardi , Vishwa Vinay, Retrievability: an evaluation measure for higher order information access tasks, Proceeding of the 17th ACM conference on Information and knowledge management, October 26-30, 2008, Napa Valley, California, USA [doi>10.1145/1458082.1458157]
• 28: L. Azzopardi, V. Vinay. Accessibility in Information Retrieval. In ECIR '08, pages 482--489, Glasgow, Scotland, 2008.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.m Miscellaneous

Additional Classification:
  H. Information Systems
  H.5 INFORMATION INTERFACES AND PRESENTATION (I.7)
      H.5.3 Group and Organization Interfaces
          Subjects: Web-based interaction

General Terms:
Design, Experimentation, Human Factors, Measurement

Keywords:
findability, human computation games, query alterations, relevance, web search