Performance prediction using spatial autocorrelation

ABSTRACT

Evaluation of information retrieval systems is one of the core tasks in information retrieval. Problems include the inability to exhaustively label all documents for a topic, generalizability from a small number of topics, and incorporating the variability of retrieval systems. Previous work addresses the evaluation of systems, the ranking of queries by difficulty, and the ranking of individual retrievals by performance. Approaches exist for the case of few and even no relevance judgments. Our focus is on zero-judgment performance prediction of individual retrievals. One common shortcoming of previous techniques is the assumption of uncorrelated document scores and judgments. If documents are embedded in a high-dimensional space (as they often are), we can apply techniques from spatial data analysis to detect correlations between document scores. We find that the low correlation between scores of topically close documents often implies a poor retrieval performance. When compared to a state of the art baseline, we demonstrate that the spatial analysis of retrieval scores provides significantly better prediction performance. These new predictors can also be incorporated with classic predictors to improve performance further. We also describe the first large-scale experiment to evaluate zero-judgment performance prediction for a massive number of retrieval systems over a variety collections in several languages.

REFERENCES

• 1: J. Aslam and V. Pavlu. Query hardness estimation using jensen-shannon divergence among multiple scoring functions. In ECIR 2007: Proceedings of the 29th European Conference on Information Retrieval, 2007.
• 2: Javed A. Aslam , Virgil Pavlu , Emine Yilmaz, A statistical method for system evaluation using incomplete judgments, Proceedings of the 29th annual international ACM SIGIR conference on Research and development in information retrieval, August 06-11, 2006, Seattle, Washington, USA [doi>10.1145/1148170.1148263]
• 3: David Carmel , Elad Yom-Tov , Adam Darlow , Dan Pelleg, What makes a query difficult?, Proceedings of the 29th annual international ACM SIGIR conference on Research and development in information retrieval, August 06-11, 2006, Seattle, Washington, USA [doi>10.1145/1148170.1148238]
• 4: Ben Carterette , James Allan , Ramesh Sitaraman, Minimal test collections for retrieval evaluation, Proceedings of the 29th annual international ACM SIGIR conference on Research and development in information retrieval, August 06-11, 2006, Seattle, Washington, USA [doi>10.1145/1148170.1148219]
• 5: A. D. Cliff and J. K. Ord. Spatial Autocorrelation. Pion Ltd., 1973.
• 6: M. Connell, A. Feng, G. Kumaran, H. Raghavan, C. Shah, and J. Allan. Umass at tdt 2004. Technical Report CIIR Technical Report IR -- 357, Department of Computer Science, University of Massachusetts, 2004.
• 7: Steve Cronen-Townsend , Yun Zhou , W. Bruce Croft, Precision prediction based on ranked list coherence, Information Retrieval, v.9 n.6, p.723-755, December 2006 [doi>10.1007/s10791-006-9006-4]
• 8: Fernando Diaz, Regularizing ad hoc retrieval scores, Proceedings of the 14th ACM international conference on Information and knowledge management, October 31-November 05, 2005, Bremen, Germany [doi>10.1145/1099554.1099722]
• 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: D. A. Griffith. Spatial Autocorrelation and Spatial Filtering. Springer Verlag, 2003.
• 11: B. He and I. Ounis. Inferring Query Performance Using Pre-retrieval Predictors. In The Eleventh Symposium on String Processing and Information Retrieval (SPIRE), 2004.
• 12: N. Jardine and C. J. V. Rijsbergen. The use of hierarchic clustering in information retrieval. Information Storage and Retrieval, 7:217--240, 1971.
• 13: David Jensen , Jennifer Neville, Linkage and Autocorrelation Cause Feature Selection Bias in Relational Learning, Proceedings of the Nineteenth International Conference on Machine Learning, p.259-266, July 08-12, 2002
• 14: Oren Kurland , Lillian Lee, Corpus structure, language models, and ad hoc 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.1009027]
• 15: Mark Montague , Javed A. Aslam, Relevance score normalization for metasearch, Proceedings of the tenth international conference on Information and knowledge management, October 05-10, 2001, Atlanta, Georgia, USA [doi>10.1145/502585.502657]
• 16: Tao Qin , Tie-Yan Liu , Xu-Dong Zhang , Zheng Chen , Wei-Ying Ma, A study of relevance propagation for web search, 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.1076105]
• 17: Ian Soboroff , Charles Nicholas , Patrick Cahan, Ranking retrieval systems without relevance judgments, Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval, p.66-73, September 2001, New Orleans, Louisiana, United States [doi>10.1145/383952.383961]
• 18: Vishwa Vinay , Ingemar J. Cox , Natasa Milic-Frayling , Ken Wood, On ranking the effectiveness of searches, Proceedings of the 29th annual international ACM SIGIR conference on Research and development in information retrieval, August 06-11, 2006, Seattle, Washington, USA [doi>10.1145/1148170.1148239]
• 19: Yun Zhou , W. Bruce Croft, Ranking robustness: a novel framework to predict query performance, Proceedings of the 15th ACM international conference on Information and knowledge management, November 06-11, 2006, Arlington, Virginia, USA [doi>10.1145/1183614.1183696]

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.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.4 Systems and Software
          Subjects: Performance evaluation (efficiency and effectiveness)

General Terms:
Design, Experimentation, Performance, Reliability

Keywords:
autocorrelation, performance prediction, regularization