Incorporating query difference for learning retrieval functions in world wide web search

ABSTRACT

We discuss information retrieval methods that aim at serving a diverse stream of user queries such as those submitted to commercial search engines. We propose methods that emphasize the importance of taking into consideration of query difference in learning effective retrieval functions. We formulate the problem as a multi-task learning problem using a risk minimization framework. In particular, we show how to calibrate the empirical risk to incorporate query difference in terms of introducing nuisance parameters in the statistical models, and we also propose an alternating optimization method to simultaneously learn the retrieval function and the nuisance parameters. We work out the details for both L₁ and L₂ regularization cases, and provide convergence analysis for the alternating optimization method for the special case when the retrieval functions belong to a reproducing kernel Hilbert space. We illustrate the effectiveness of the proposed methods using modeling data extracted from a commercial search engine. We also point out how the current framework can be extended in future research.

REFERENCES

• 1: Adam Berger , John Lafferty, Statistical machine learning for information retrieval, Carnegie Mellon University, Pittsburgh, PA, 2001
• 2: D. Bertsekas. Nonlinear programming. Athena Scientific, second edition, 1999.
• 3: 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]
• 4: 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]
• 5: R. D. Cook and S. Weisberg. Residuals and influence in regression. Chapman & Hall, 1982.
• 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. Method and apparatus for machine learning a document relevance function. US patent application, 20040215606, 2003.
• 8: D. Cossock and T. Zhang. Subset ranking using regression. Technical Report, Yahoo! Research Laboratory, 2006.
• 9: F. Cucker and S. Smale. On the mathematical foundations of learning. Bull. Amer. Math. Soc., 39:1--49, 2002.
• 10: Y. Freund and R. Schapire. Experiments with a new boosting algorithm. Proceedings of the international conference on Machine learning, 148--156, 1996.
• 11: J. Friedman. Multivariate adaptive regression splines (with discussion). Ann. Statist., 19:1--141, 1991.
• 12: J. Friedman. Greedy function approximation: a gradient boosting machine. Ann. Statist., 29:1189--1232, 2001.
• 13: 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]
• 14: 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]
• 15: Norbert Fuhr , Ulrich Pfeifer, Probabilistic information retrieval as a combination of abstraction, inductive learning, and probabilistic assumptions, ACM Transactions on Information Systems (TOIS), v.12 n.1, p.92-115, Jan. 1994 [doi>10.1145/174608.174612]
• 16: Jianfeng Gao , Haoliang Qi , Xinsong Xia , Jian-Yun Nie, Linear discriminant model for information retrieval, 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.1076085]
• 17: 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.
• 18: M. Hollander and D. A. Wolfe. Nonparametric statistical methods. Wiley-Interscience, 2nd edition, 1999.
• 19: 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]
• 20: 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]
• 21: T. Joachims. Evaluating retrieval performance using clickthrough data. Proceedings of the SIGIR Workshop on Mathematical/Formal Methods in Information Retrieval, 2002.
• 22: 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]
• 23: K. L. Kwok, A neural network for probabilistic information retrieval, Proceedings of the 12th annual international ACM SIGIR conference on Research and development in information retrieval, p.21-30, June 25-28, 1989, Cambridge, Massachusetts, United States
• 24: Xiaoyong Liu , W. Bruce Croft, Cluster-based retrieval using language models, 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.1009026]
• 25: Ramesh Nallapati, Discriminative models for information retrieval, 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.1009006]
• 26: J. Nocedal and S. Wright. Numerical Optimization. Springer, 1999.
• 27: 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]
• 28: Gerald Salton, Automatic text processing, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1988
• 29: 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]
• 30: G. Wahba. Spline models for observational data. SIAM press, 1990.
• 31: Chengxiang Zhai , John Lafferty, A study of smoothing methods for language models applied to information retrieval, ACM Transactions on Information Systems (TOIS), v.22 n.2, p.179-214, April 2004 [doi>10.1145/984321.984322]
• 32: 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

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

General Terms:
Algorithms, Experimentation, Theory

Keywords:
WWW search, alternating optiminization, discounted cumulative gain, gradient boosting, least-squares regression, machine learning, quadratic programming, query dependence, query document feature, query specific feature, regularization, relevance, relevance judgment, retrieval function, risk minimization