A regression framework for learning ranking functions using relative relevance judgments

ABSTRACT

Effective ranking functions are an essential part of commercial search engines. We focus on developing a regression framework for learning ranking functions for improving relevance of search engines serving diverse streams of user queries. We explore supervised learning methodology from machine learning, and we distinguish two types of relevance judgments used as the training data: 1) absolute relevance judgments arising from explicit labeling of search results; and 2) relative relevance judgments extracted from user click throughs of search results or converted from the absolute relevance judgments. We propose a novel optimization framework emphasizing the use of relative relevance judgments. The main contribution is the development of an algorithm based on regression that can be applied to objective functions involving preference data, i.e., data indicating that a document is more relevant than another with respect to a query. Experimental results are carried out using data sets obtained from a commercial search engine. Our results show significant improvements of our proposed methods over some existing methods.

REFERENCES

• 1: Richard Atterer , Monika Wnuk , Albrecht Schmidt, Knowing the user's every move: user activity tracking for website usability evaluation and implicit interaction, Proceedings of the 15th international conference on World Wide Web, May 23-26, 2006, Edinburgh, Scotland [doi>10.1145/1135777.1135811]
• 2: Adam Berger , John Lafferty, Statistical machine learning for information retrieval, Carnegie Mellon University, Pittsburgh, PA, 2001
• 3: D. Bertsekas. Nonlinear programming Athena Scienti?c, second edition, 1999.
• 4: 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]
• 5: Hsinchun Chen, Machine learning for information retrieval: neural networks, symbolic learning, and genetic algorithms, Journal of the American Society for Information Science, v.46 n.3, p.194-216, April 1995 [doi>10.1002/(SICI)1097-4571(199504)46:3<194::AID-ASI4>3.0.CO;2-S]
• 6: W. Cooper, F. Gey and A. Chen. Probabilistic retrieval in the TIPSTER collections: an application of staged logistic regression. Proceedings of TREC 73--88, 1992.
• 7: D. Cossock and T. Zhang. Subset ranking using regression. COLT 2006.
• 8: Yoav Freund , Raj Iyer , Robert E. Schapire , Yoram Singer, An efficient boosting algorithm for combining preferences, The Journal of Machine Learning Research, 4, p.933-969, 12/1/2003
• 9: J. Friedman. Greedy function approximation: a gradient boosting machine. Ann. Statist. 29:1189--1232, 2001.
• 10: Norbert Fuhr, Optimum polynomial retrieval functions based on the probability ranking principle, ACM Transactions on Information Systems (TOIS), v.7 n.3, p.183-204, July 1989 [doi>10.1145/65943.65944]
• 11: F. Gey, A. Chen, J. He and J. Meggs. Logistic regression at TREC4: probabilistic retrieval from full text document collections. Proceedings of TREC 65--72, 1995.
• 12: Kalervo Järvelin , Jaana Kekäläinen, Cumulated gain-based evaluation of IR techniques, ACM Transactions on Information Systems (TOIS), v.20 n.4, p.422-446, October 2002 [doi>10.1145/582415.582418]
• 13: 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]
• 14: T. Joachims. Evaluating retrieval performance using clickthrough data. Proceedings of the SIGIR Workshop on Mathematical/Formal Methods in Information Retrieval 2002.
• 15: 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]
• 16: Jay M. Ponte , W. Bruce Croft, A language modeling approach to information retrieval, Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval, p.275-281, August 24-28, 1998, Melbourne, Australia [doi>10.1145/290941.291008]
• 17: Gerald Salton, Automatic text processing, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1988
• 18: H. Turtle , W. B. Croft, Inference networks for document retrieval, Proceedings of the 13th annual international ACM SIGIR conference on Research and development in information retrieval, p.1-24, September 05-07, 1990, Brussels, Belgium [doi>10.1145/96749.98006]
• 19: Hongyuan Zha , Zhaohui Zheng , Haoying Fu , Gordon Sun, Incorporating query difference for learning retrieval functions in world wide web search, Proceedings of the 15th ACM international conference on Information and knowledge management, November 06-11, 2006, Arlington, Virginia, USA [doi>10.1145/1183614.1183660]
• 20: Diane Kelly , Jaime Teevan, Implicit feedback for inferring user preference: a bibliography, ACM SIGIR Forum, v.37 n.2, p.18-28, Fall 2003 [doi>10.1145/959258.959260]
• 21: Filip Radlinski , Thorsten Joachims, Query chains: learning to rank from implicit feedback, Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, August 21-24, 2005, Chicago, Illinois, USA [doi>10.1145/1081870.1081899]
• 22: ChengXiang Zhai , John Lafferty, A risk minimization framework for information retrieval, Information Processing and Management: an International Journal, v.42 n.1, p.31-55, January 2006 [doi>10.1016/j.ipm.2004.11.003]

INDEX TERMS

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

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

General Terms:
Algorithms, Experimentation, Theory

Keywords:
absolute relevance judgment, clickthroughs, functional gradient descent, gradient boosting, machine learning, preferences, ranking function, regression, relative relevance judgment