Estimating average precision with incomplete and imperfect judgments

ABSTRACT

We consider the problem of evaluating retrieval systems using incomplete judgment information. Buckley and Voorhees recently demonstrated that retrieval systems can be efficiently and effectively evaluated using incomplete judgments via the bpref measure [6]. When relevance judgments are complete, the value of bpref is an approximation to the value of average precision using complete judgments. However, when relevance judgments are incomplete, the value of bpref deviates from this value, though it continues to rank systems in a manner similar to average precision evaluated with a complete judgment set. In this work, we propose three evaluation measures that (1) are approximations to average precision even when the relevance judgments are incomplete and (2) are more robust to incomplete or imperfect relevance judgments than bpref. The proposed estimates of average precision are simple and accurate, and we demonstrate the utility of these estimates using TREC data.

REFERENCES

• 1: J. Allan. HARD track overview in TREC 2004: High accuracy retrieval from documents. In Proceedings of the Thirteenth Text REtrieval Conference (TREC 2004), 2004.
• 2: Javed A. Aslam , Virgiliu Pavlu , Robert Savell, A unified model for metasearch, pooling, and system evaluation, Proceedings of the twelfth international conference on Information and knowledge management, November 03-08, 2003, New Orleans, LA, USA [doi>10.1145/956863.956953]
• 3: Javed A. Aslam , Robert Savell, On the effectiveness of evaluating retrieval systems in the absence of relevance judgments, Proceedings of the 26th annual international ACM SIGIR conference on Research and development in informaion retrieval, July 28-August 01, 2003, Toronto, Canada [doi>10.1145/860435.860501]
• 4: Javed A. Aslam , Emine Yilmaz , Virgiliu Pavlu, The maximum entropy method for analyzing retrieval measures, 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.1076042]
• 5: Chris Buckley , Ellen M. Voorhees, Evaluating evaluation measure stability, Proceedings of the 23rd annual international ACM SIGIR conference on Research and development in information retrieval, p.33-40, July 24-28, 2000, Athens, Greece [doi>10.1145/345508.345543]
• 6: Chris Buckley , Ellen M. Voorhees, Retrieval evaluation with incomplete information, 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.1009000]
• 7: Stanley F. Chen , Joshua Goodman, An empirical study of smoothing techniques for language modeling, Proceedings of the 34th annual meeting on Association for Computational Linguistics, p.310-318, June 24-27, 1996, Santa Cruz, California [doi>10.3115/981863.981904]
• 8: C. L. A. Clarke, F. Scholer, and I. Soboroff. The TREC 2005 terabyte track. In Proceedings of the Fourteenth Text REtrieval Conference (TREC 2005), 2005.
• 9: Cyril Cleverdon, The Cranfield tests on index language devices, Readings in information retrieval, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1997
• 10: Gordon V. Cormack , Christopher R. Palmer , Charles L. A. Clarke, Efficient construction of large test collections, Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval, p.282-289, August 24-28, 1998, Melbourne, Australia [doi>10.1145/290941.291009]
• 11: W. B. Croft, A. Moffat, C. J. van Rijsbergen, R. Wilkinson, and J. Zobel, editors. Proceedings of the 21th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, Melbourne, Australia, Aug. 1998. ACM Press, New York.
• 12: D. Harman. Overview of the third text REtreival conference (TREC-3). In D. Harman, editor, Overview of the Third Text REtrieval Conference (TREC-3), pages 1--19, Gaithersburg, MD, USA, Apr. 1995. U.S. Government Printing Office, Washington D.C.
• 13: David Hawking , Stephen Robertson, On Collection Size and Retrieval Effectiveness, Information Retrieval, v.6 n.1, p.99-105, January 2003 [doi>10.1023/A:1022904715765]
• 14: Rabia Nuray , Fazli Can, Automatic ranking of retrieval systems in imperfect environments, Proceedings of the 26th annual international ACM SIGIR conference on Research and development in informaion retrieval, July 28-August 01, 2003, Toronto, Canada [doi>10.1145/860435.860510]
• 15: 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]
• 16: Ellen M. Voorhees, Evaluation by highly relevant documents, Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval, p.74-82, September 2001, New Orleans, Louisiana, United States [doi>10.1145/383952.383963]
• 17: Justin Zobel, How reliable are the results of large-scale information retrieval experiments?, Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval, p.307-314, August 24-28, 1998, Melbourne, Australia [doi>10.1145/290941.291014]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.4 Systems and Software
          Subjects: Performance evaluation (efficiency and effectiveness)

General Terms:
Experimentation, Measurement, Theory

Keywords:
Bpref, average precision, evaluation, incomplete judgments, sampling