Optimizing search engines using clickthrough data

ABSTRACT

This paper presents an approach to automatically optimizing the retrieval quality of search engines using clickthrough data. Intuitively, a good information retrieval system should present relevant documents high in the ranking, with less relevant documents following below. While previous approaches to learning retrieval functions from examples exist, they typically require training data generated from relevance judgments by experts. This makes them difficult and expensive to apply. The goal of this paper is to develop a method that utilizes clickthrough data for training, namely the query-log of the search engine in connection with the log of links the users clicked on in the presented ranking. Such clickthrough data is available in abundance and can be recorded at very low cost. Taking a Support Vector Machine (SVM) approach, this paper presents a method for learning retrieval functions. From a theoretical perspective, this method is shown to be well-founded in a risk minimization framework. Furthermore, it is shown to be feasible even for large sets of queries and features. The theoretical results are verified in a controlled experiment. It shows that the method can effectively adapt the retrieval function of a meta-search engine to a particular group of users, outperforming Google in terms of retrieval quality after only a couple of hundred training examples.

REFERENCES

• 1: Ricardo A. Baeza-Yates , Berthier Ribeiro-Neto, Modern Information Retrieval, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
• 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: Bernhard E. Boser , Isabelle M. Guyon , Vladimir N. Vapnik, A training algorithm for optimal margin classifiers, Proceedings of the fifth annual workshop on Computational learning theory, p.144-152, July 27-29, 1992, Pittsburgh, Pennsylvania, United States [doi>10.1145/130385.130401]
• 5: 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.
• 6: W. Cohen, R. Shapire, and Y. Singer. Learning to order things. Journal of Artificial Intelligence Research, 10, 1999.
• 7: Corinna Cortes , Vladimir Vapnik, Support-Vector Networks, Machine Learning, v.20 n.3, p.273-297, Sept. 1995 [doi>10.1023/A:1022627411411]
• 8: K. Crammer and Y. Singer. Pranking with ranking. In Advances in Neural Information Processing Systems (NIPS), 2001.
• 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: 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: N. Fuhr, S. Hartmann, G. Lustig, M. Schwantner, K. Tzeras, and G. Knorz. Air/x - a rule-based multistage indexing system for large subject fields. In RIAO, pages 606--623, 1991.
• 12: R. Herbrich, T. Graepel, and K. Obermayer. Large margin rank boundaries for ordinal regression. In Advances in Large Margin Classifiers, pages 115--132. MIT Press, Cambridge, MA, 2000.
• 13: Klaus-U. Höffgen , Hans-U. Simon , Kevin S. van Horn, Robust trainability of single neurons, Journal of Computer and System Sciences, v.50 n.1, p.114-125, Feb. 1995 [doi>10.1006/jcss.1995.1011]
• 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, Learning to Classify Text Using Support Vector Machines: Methods, Theory and Algorithms, Kluwer Academic Publishers, Norwell, MA, 2002
• 16: T. Joachims. Unbiased evaluation of retrieval quality using clickthrough data. Technical report, Cornell University, Department of Computer Science, 2002. http://www.joachims.org.
• 17: T. Joachims, D. Freitag, and T. Mitchell. WebWatcher: a tour guide for the world wide web. In Proceedings of International Joint Conference on Artificial Intelligence (IJCAI), volume 1, pages 770--777. Morgan Kaufmann, 1997.
• 18: J. Kemeny and L. Snell. Mathematical Models in the Social Sciences. Ginn & Co, 1962.
• 19: M. Kendall. Rank Correlation Methods. Hafner, 1955.
• 20: H. Lieberman. Letizia: An agent that assists Web browsing. In Proceedings of the Fifteenth International Joint Conference on Artificial Intelligence (IJCAI '95), Montreal, Canada, 1995. Morgan Kaufmann.
• 21: A. Mood, F. Graybill, and D. Boes. Introduction to the Theory of Statistics. McGraw-Hill, 3 edition, 1974.
• 22: L. Page and S. Brin. Pagerank, an eigenvector based ranking approach for hypertext. In 2lst Annual ACM/SIGIR International Conference on Research and Development in Information Retrieval, 1998.
• 23: Gerard Salton , Christopher Buckley, Term-weighting approaches in automatic text retrieval, Information Processing and Management: an International Journal, v.24 n.5, p.513-523, 1988 [doi>10.1016/0306-4573(88)90021-0]
• 24: C. Silverstein, M. Henzinger, H. Marais, and M. Moricz. Analysis of a very large altavista query log. Technical Report SRC 1998-014, Digital Systems Research Center, 1998.
• 25: V. Vapnik. Statistical Learning Theory. Wiley, Chichester, GB, 1998.
• 26: Y. Y. Yao, Measuring retrieval effectiveness based on user preference of documents, Journal of the American Society for Information Science, v.46 n.2, p.133-145, March 1995 [doi>10.1002/(SICI)1097-4571(199503)46:2<133::AID-ASI6>3.0.CO;2-Z]

INDEX TERMS

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

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Statistical computing

  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Analysis of algorithms

General Terms:
Algorithms, Design, Experimentation, Performance