Learning to estimate query difficulty: including applications to missing content detection and distributed information retrieval

ABSTRACT

In this article we present novel learning methods for estimating the quality of results returned by a search engine in response to a query. Estimation is based on the agreement between the top results of the full query and the top results of its sub-queries. We demonstrate the usefulness of quality estimation for several applications, among them improvement of retrieval, detecting queries for which no relevant content exists in the document collection, and distributed information retrieval. Experiments on TREC data demonstrate the robustness and the effectiveness of our learning algorithms.

REFERENCES

• 1: G. Amati, C. Carpineto, and G. Romano. Query difficulty, robustness and selective application of query expansion. In Proceedings of the 25th European Conference on Information Retrieval (ECIR 2004), pages 127--137, Sunderland, Great Britain, 2004.
• 2: Leo Breiman, Random Forests, Machine Learning, v.45 n.1, p.5-32, October 1 2001 [doi>10.1023/A:1010933404324]
• 3: L. Breiman, J. H. Friedman, R. A. Olshen, and C. J. Stone. Classification and regression trees. Chapman and Hall, 1993.
• 4: Chris Buckley, Why current IR engines fail, 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.1009132]
• 5: James P. Callan , Zhihong Lu , W. Bruce Croft, Searching distributed collections with inference networks, Proceedings of the 18th annual international ACM SIGIR conference on Research and development in information retrieval, p.21-28, July 09-13, 1995, Seattle, Washington, United States [doi>10.1145/215206.215328]
• 6: David Carmel , Eitan Farchi , Yael Petruschka , Aya Soffer, Automatic query wefinement using lexical affinities with maximal information gain, Proceedings of the 25th annual international ACM SIGIR conference on Research and development in information retrieval, August 11-15, 2002, Tampere, Finland [doi>10.1145/564376.564427]
• 7: J. Cohen. A coefficient of agreement for nominal scales. Educational and Psychological Measurement, pages 37--46, 1960.
• 8: Steve Cronen-Townsend , Yun Zhou , W. Bruce Croft, Predicting query performance, Proceedings of the 25th annual international ACM SIGIR conference on Research and development in information retrieval, August 11-15, 2002, Tampere, Finland [doi>10.1145/564376.564429]
• 9: Fernando Diaz , Rosie Jones, Using temporal profiles of queries for precision prediction, 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.1008998]
• 10: Richard O. Duda , Peter E. Hart , David G. Stork, Pattern Classification (2nd Edition), Wiley-Interscience, 2000
• 11: Donna Harman , Chris Buckley, The NRRC reliable information access (RIA) workshop, 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.1009104]
• 12: B. He and I. Ounis. Inferring query performance using pre-retrieval predictors. In A. Apostolico and M. Melucci, editors, String Processing and Information Retrieval, 11th International Conference, SPIRE 2004, volume 3246 of Lecture Notes in Computer Science, 2004.
• 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: K. Kwok, L. Grunfeld, H. Sun, P. Deng, and N. Dinstl. TREC 2004 Robust Track Experiments using PIRCS. In Proceedings of the 13th Text REtrieval Conference (TREC2004), 2004.
• 15: C. Piatko, J. Mayfield, P. McNamee, and S. Cost. JHU/APL at TREC 2004: Robust and Terabyte Tracks. In Proceedings of the 13th Text REtrieval Conference (TREC2004), 2004.
• 16: Bernhard Scholkopf , Alexander J. Smola, Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond, MIT Press, Cambridge, MA, 2001
• 17: David G. Stork , Elad Yom-Tov, Computer Manual in MATLAB to Accompany Pattern Classification, Second Edition, Wiley-Interscience, 2004
• 18: B. Swen, X.-Q. Lu, H.-Y. Zan, Q. Su, Z.-G. Lai, K. Xiang, and J.-H. Hu. Part-of-Speech Sense Matrix Model Experiments in the TREC 2004 Robust Track at ICL, PKU. In Proceedings of the 13th Text REtrieval Conference (TREC2004), 2004.
• 19: S. Tomlinson. Robust, Web and Terabyte Retrieval with Hummingbird SearchServer at TREC 2004. In Proceedings of the 13th Text REtrieval Conference (TREC2004), 2004.
• 20: G. Upton and I. Cook. Oxford dictionary of statistics. Oxford university press, Oxford, UK, 2002.
• 21: B. H. Vassilis~Plachouras and I. Ounis. University of Glasgow at TREC 2004: Experiments in Web, Robust and Terabyte tracks with Terrier. In Proceedings of the 13th Text REtrieval Conference (TREC2004), 2004.
• 22: E. M. Voorhees. Overview of the TREC 2004 Robust Retrieval Track. In Proceedings of the 13th Text Retrieval Conference (TREC-13). National Institute of Standards and Technology (NIST), 2004.
• 23: Jinxi Xu , W. Bruce Croft, Cluster-based language models for distributed retrieval, Proceedings of the 22nd annual international ACM SIGIR conference on Research and development in information retrieval, p.254-261, August 15-19, 1999, Berkeley, California, United States [doi>10.1145/312624.312687]
• 24: E. Yom-Tov, S. Fine, D. Carmel, A. Darlow, and E. Amitay. Juru at TREC 2004: Experiments with Prediction of Query Difficulty. In Proceedings of the 13th Text REtrieval Conference (TREC2004), 2004.

INDEX TERMS

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

General Terms:
Algorithms

Keywords:
query difficulty estimation