Learning consensus opinion: mining data from a labeling game

ABSTRACT

We consider the problem of identifying the consensus ranking for the results of a query, given preferences among those results from a set of individual users. Once consensus rankings are identified for a set of queries, these rankings can serve for both evaluation and training of retrieval and learning systems. We present a novel approach to collecting the individual user preferences over image-search results: we use a collaborative game in which players are rewarded for agreeing on which image result is best for a query. Our approach is distinct from other labeling games because we are able to elicit directly the preferences of interest with respect to image queries extracted from query logs. As a source of relevance judgments, this data provides a useful complement to click data. Furthermore, the data is free of positional biases and is collected by the game without the risk of frustrating users with non-relevant results; this risk is prevalent in standard mechanisms for debiasing clicks. We describe data collected over 34 days from a deployed version of this game that amounts to about 18 million expressed preferences between pairs. Finally, we present several approaches to modeling this data in order to extract the consensus rankings from the preferences and better sort the search results for targeted queries.

REFERENCES

• 1: R. Bradley and M. Terry. Rank analysis of incomplete block designs, i. the method of paired comparisons. Biometrika, pages 324--345, 1952.
• 2: B. Carterette, P. N. Bennett, D. M. Chickering, and S. T. Dumais. Here or there: Preference judgments for relevance. In ECIR 2008, 2008.
• 3: Wei Chu , Zoubin Ghahramani, Preference learning with Gaussian processes, Proceedings of the 22nd international conference on Machine learning, p.137-144, August 07-11, 2005, Bonn, Germany [doi>10.1145/1102351.1102369]
• 4: Cyril W. Cleverdon, The significance of the Cranfield tests on index languages, Proceedings of the 14th annual international ACM SIGIR conference on Research and development in information retrieval, p.3-12, October 13-16, 1991, Chicago, Illinois, United States [doi>10.1145/122860.122861]
• 5: W. Cohen, R. Schapire, and Y. Singer. Learning to order things. Journal of Artificial Intelligence Research, 10:243--270, 1999.
• 6: Cynthia Dwork , Ravi Kumar , Moni Naor , D. Sivakumar, Rank aggregation methods for the Web, Proceedings of the 10th international conference on World Wide Web, p.613-622, May 01-05, 2001, Hong Kong, Hong Kong [doi>10.1145/371920.372165]
• 7: J. Fürnkranz and E. Hüllermeier. Pairwise preference learning and ranking. In ECML 2003, 2003.
• 8: R. Herbrich and T. Graepel. Trueskill: A bayesian skill rating system. Technical Report MSR-TR-2006-80, Microsoft Research, June 2006. ftp://ftp.research.microsoft.com/pub/tr/TR-2006-80.pdf.
• 9: Thorsten Joachims, Optimizing search engines using clickthrough data, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada [doi>10.1145/775047.775067]
• 10: E. Law, L. von Ahn, R. Dannenberg, and M. Crawford. Tagatune: A game for music and sound annotation. In Proceedings of the 8th International Conference on Music Information Retrieval, 2007.
• 11: R. Luce. Individual Choice Behaviours: A Theoretical Analysis. J. Wiley, New York, 1959.
• 12: F. Radlinski and T. Joachims. Minimally invasive randomization for collecting unbiased preferences from clickthrough logs. In AAAI 2005, 2005.
• 13: Filip Radlinski , Robert Kleinberg , Thorsten Joachims, Learning diverse rankings with multi-armed bandits, Proceedings of the 25th international conference on Machine learning, p.784-791, July 05-09, 2008, Helsinki, Finland [doi>10.1145/1390156.1390255]
• 14: S. E. Robertson, The probability ranking principle in IR, Readings in information retrieval, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1997
• 15: David Stern , Ralf Herbrich , Thore Graepel, Bayesian pattern ranking for move prediction in the game of Go, Proceedings of the 23rd international conference on Machine learning, p.873-880, June 25-29, 2006, Pittsburgh, Pennsylvania [doi>10.1145/1143844.1143954]
• 16: L. Thurstone. A law of comparative judgment. Psychological Review, pages 273--286, 1927.
• 17: L. Thurstone. Essays in Philosophy by Seventeen Doctors of Philosophy of the University of Chicago, chapter The Measurement of Psychological Value. Open Court, Chicago, 1929.
• 18: L. Thurstone. The Measurement of Values. The University of Chicago Press, Chicago, 1959.
• 19: 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]
• 20: 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]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Selection process

General Terms:
Algorithms, Performance

Keywords:
learning preferences, preference judgments