Global ranking by exploiting user clicks

ABSTRACT

It is now widely recognized that user interactions with search results can provide substantial relevance information on the documents displayed in the search results. In this paper, we focus on extracting relevance information from one source of user interactions, i.e., user click data, which records the sequence of documents being clicked and not clicked in the result set during a user search session. We formulate the problem as a global ranking problem, emphasizing the importance of the sequential nature of user clicks, with the goal to predict the relevance labels of all the documents in a search session. This is distinct from conventional learning to rank methods that usually design a ranking model defined on a single document; in contrast, in our model the relational information among the documents as manifested by an aggregation of user clicks is exploited to rank all the documents jointly. In particular, we adapt several sequential supervised learning algorithms, including the conditional random field (CRF), the sliding window method and the recurrent sliding window method, to the global ranking problem. Experiments on the click data collected from a commercial search engine demonstrate that our methods can outperform the baseline models for search results re-ranking.

REFERENCES

• 1: Sergey Brin , Lawrence Page, The anatomy of a large-scale hypertextual Web search engine, Proceedings of the seventh international conference on World Wide Web 7, p.107-117, April 1998, Brisbane, Australia
• 2: Chris Burges , Tal Shaked , Erin Renshaw , Ari Lazier , Matt Deeds , Nicole Hamilton , Greg Hullender, Learning to rank using gradient descent, Proceedings of the 22nd international conference on Machine learning, p.89-96, August 07-11, 2005, Bonn, Germany [doi>10.1145/1102351.1102363]
• 3: B. Carterette and R. Jones. Evaluating search engines by modeling the relationship between relevance and clicks. In NIPS, 2007.
• 4: Nick Craswell , Onno Zoeter , Michael Taylor , Bill Ramsey, An experimental comparison of click position-bias models, Proceedings of the international conference on Web search and web data mining, February 11-12, 2008, Palo Alto, California, USA [doi>10.1145/1341531.1341545]
• 5: Thomas G. Dietterich, Machine Learning for Sequential Data: A Review, Proceedings of the Joint IAPR International Workshop on Structural, Syntactic, and Statistical Pattern Recognition, p.15-30, August 06-09, 2002
• 6: Georges E. Dupret , Benjamin Piwowarski, A user browsing model to predict search engine click data from past observations., 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.1390392]
• 7: J. Friedman. Greedy function approximation: a gradient boosting machine. Ann. Statist., 29:1189--1232, 2001.
• 8: Norbert Fuhr , Chris Buckley, A probabilistic learning approach for document indexing, ACM Transactions on Information Systems (TOIS), v.9 n.3, p.223-248, July 1991 [doi>10.1145/125187.125189]
• 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: Thorsten Joachims , Laura Granka , Bing Pan , Helene Hembrooke , Geri Gay, Accurately interpreting clickthrough data as implicit feedback, Proceedings of the 28th annual international ACM SIGIR conference on Research and development in information retrieval, August 15-19, 2005, Salvador, Brazil [doi>10.1145/1076034.1076063]
• 11: A. Kulesza and F. Pereira. Structured learning with approximate inference. In NIPS, 2007.
• 12: John D. Lafferty , Andrew McCallum , Fernando C. N. Pereira, Conditional Random Fields: Probabilistic Models for Segmenting and Labeling Sequence Data, Proceedings of the Eighteenth International Conference on Machine Learning, p.282-289, June 28-July 01, 2001
• 13: P. Li, C. Burges, and Q. Wu. Mcrank: Learning to rank using multiple classifications and gradient boosting. In NIPS, 2008.
• 14: T. Qin, T. Liu, X. Zhang, D. Wang, and H. Li. Global ranking using continuous conditional random fields. In NIPS, 2008.
• 15: L.R. Rabiner. A tutorial on hidden markov models and selected applications in speech recognition. In Proceedings of the IEEE, pages 257--286, 1989.
• 16: F. Radlinski and T. Joachims. Evaluating the robustness of learning from implicit feedback. In ICML Workshop on Learning In Web Search, 2005.
• 17: Filip Radlinski , Thorsten Joachims, Active exploration for learning rankings from clickthrough data, Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, August 12-15, 2007, San Jose, California, USA [doi>10.1145/1281192.1281254]
• 18: Gerald Salton, Automatic text processing, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1988
• 19: C. Sutton and A. McCallum. An introduction to conditional random fields for relational learning, chapter Book chapter in Introduction to Statistical Relational Learning. MIT Press, 2006.
• 20: Vladimir N. Vapnik, The nature of statistical learning theory, Springer-Verlag New York, Inc., New York, NY, 1995
• 21: H.M. Wallach. Conditional random fields: An introduction. Technical report, Dept. of Computer and Information Science, University of Pennsylvania, 2004.
• 22: Xuanhui Wang , ChengXiang Zhai, Learn from web search logs to organize search results, Proceedings of the 30th annual international ACM SIGIR conference on Research and development in information retrieval, July 23-27, 2007, Amsterdam, The Netherlands [doi>10.1145/1277741.1277759]
• 23: Zhaohui Zheng , Keke Chen , Gordon Sun , Hongyuan Zha, A regression framework for learning ranking functions using relative relevance judgments, Proceedings of the 30th annual international ACM SIGIR conference on Research and development in information retrieval, July 23-27, 2007, Amsterdam, The Netherlands [doi>10.1145/1277741.1277792]

INDEX TERMS

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

Additional Classification:
  H. Information Systems
  H.4 INFORMATION SYSTEMS APPLICATIONS
      H.4.m Miscellaneous

General Terms:
Algorithms, Experimentation, Human Factors

Keywords:
conditional random field, experimental evaluation, implicit relevance feedback, learning to rank, sequential supervised learning, user clicks