Query chains: learning to rank from implicit feedback

ABSTRACT

This paper presents a novel approach for using clickthrough data to learn ranked retrieval functions for web search results. We observe that users searching the web often perform a sequence, or chain, of queries with a similar information need. Using query chains, we generate new types of preference judgments from search engine logs, thus taking advantage of user intelligence in reformulating queries. To validate our method we perform a controlled user study comparing generated preference judgments to explicit relevance judgments. We also implemented a real-world search engine to test our approach, using a modified ranking SVM to learn an improved ranking function from preference data. Our results demonstrate significant improvements in the ranking given by the search engine. The learned rankings outperform both a static ranking function, as well as one trained without considering query chains.

REFERENCES

• 1: B. Bartell and G. W. Cottrell. Learning to retrieve information. In Proceedings of the Swedish Conference on Connectionism, 1995.
• 2: Brian T. Bartell , Garrison W. Cottrell , Richard K. Belew, Automatic combination of multiple ranked retrieval systems, Proceedings of the 17th annual international ACM SIGIR conference on Research and development in information retrieval, p.173-181, July 03-06, 1994, Dublin, Ireland
• 3: Doug Beeferman , Adam Berger, Agglomerative clustering of a search engine query log, Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, p.407-416, August 20-23, 2000, Boston, Massachusetts, United States [doi>10.1145/347090.347176]
• 4: J. Boyan, D. Freitag, and T. Joachims. A machine learning architecture for optimizing web search engines. In AAAI Workshop on Internet Based Information Systems, August 1996.
• 5: Andrei Broder, A taxonomy of web search, ACM SIGIR Forum, v.36 n.2, Fall 2002 [doi>10.1145/792550.792552]
• 6: W. W. Cohen, R. E. Shapire, and Y. Singer. Learning to order things. Journal of Artificial Intelligence Research, 10:243--270, 1999.
• 7: K. Crammer and Y. Singer. Pranking with ranking. In Proceedings of the Conference on Neural Information Processing Systems (NIPS), 2001.
• 8: S. Cucerzan and E. Brill. Spelling correction as an iterative process that exploits the collective knowledge of web users. In Proceedings of Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 293--300, 2004.
• 9: Yoav Freund , Raj D. Iyer , Robert E. Schapire , Yoram Singer, An Efficient Boosting Algorithm for Combining Preferences, Proceedings of the Fifteenth International Conference on Machine Learning, p.170-178, July 24-27, 1998
• 10: George W. Furnas, Experience with an adaptive indexing scheme, Proceedings of the SIGCHI conference on Human factors in computing systems, p.131-135, April 1985, San Francisco, California, United States
• 11: L. Granka. Eye tracking analysis of user behaviors in online search. Master's thesis, Cornell University, 2004.
• 12: Laura A. Granka , Thorsten Joachims , Geri Gay, Eye-tracking analysis of user behavior in WWW search, Proceedings of the 27th annual international ACM SIGIR conference on Research and development in information retrieval, July 25-29, 2004, Sheffield, United Kingdom [doi>10.1145/1008992.1009079]
• 13: R. Herbrich, T. Graepel, and K. Obermayer. Large margin rank boundaries for ordinal regression. In A. S. et al., editor, Advances in Large Margin Classifiers, pages 115--132, 2000.
• 14: Thorsten Joachims, Making large-scale support vector machine learning practical, Advances in kernel methods: support vector learning, MIT Press, Cambridge, MA, 1999
• 15: 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]
• 16: T. Joachims. Evaluating retrieval performance using clickthrough data. In J. Franke, G. Nakhaeizadeh, and I. Renz, editors, Text Mining, pages 79--96. Physica/Springer Verlag, 2003.
• 17: 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]
• 18: Rosie Jones , Daniel C. Fain, Query word deletion prediction, Proceedings of the 26th annual international ACM SIGIR conference on Research and development in informaion retrieval, July 28-August 01, 2003, Toronto, Canada [doi>10.1145/860435.860538]
• 19: Charles Kemp , Kotagiri Ramamohanarao, Long-Term Learning for Web Search Engines, Proceedings of the 6th European Conference on Principles of Data Mining and Knowledge Discovery, p.263-274, August 19-23, 2002
• 20: Tessa Lau , Eric Horvitz, Patterns of search: analyzing and modeling Web query refinement, Proceedings of the seventh international conference on User modeling, p.119-128, June 1999, Banff, Canada
• 21: B. Uygar Oztekin , George Karypis , Vipin Kumar, Expert agreement and content based reranking in a meta search environment using Mearf, Proceedings of the 11th international conference on World Wide Web, May 07-11, 2002, Honolulu, Hawaii, USA [doi>10.1145/511446.511490]
• 22: S. Rajaram, A. Garg, Z. S. Zhou, and T. S. Huang. Classification approach towards ranking and sorting problems. In Lecture Notes in Artificial Intelligence, volume 2837, pages 301--312, September 2003.
• 23: Falk Scholer , Hugh E. Williams, Query association for effective retrieval, Proceedings of the eleventh international conference on Information and knowledge management, November 04-09, 2002, McLean, Virginia, USA [doi>10.1145/584792.584846]
• 24: C. Silverstein, M. Henzinger, H. Marais, and M. Moricz. Analysis of a very large AltaVista query log. Technical Report 1998-014, Digital SRC, 1998.
• 25: Q. Tan, X. Chai, W. Ng, and D.-L. Lee. Applying co-training to clickthrough data for search engine adaptation. In Proceedings of the 9th International Conference on Database Systems for Advanced Applications (DASFAA), 2004.

INDEX TERMS

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

General Terms:
Algorithms, Experimentation, Measurement

Keywords:
clickthrough data, implicit feedback, machine learning, search engines, support vector machines