Cumulated gain-based evaluation of IR techniques

ABSTRACT

Modern large retrieval environments tend to overwhelm their users by their large output. Since all documents are not of equal relevance to their users, highly relevant documents should be identified and ranked first for presentation. In order to develop IR techniques in this direction, it is necessary to develop evaluation approaches and methods that credit IR methods for their ability to retrieve highly relevant documents. This can be done by extending traditional evaluation methods, that is, recall and precision based on binary relevance judgments, to graded relevance judgments. Alternatively, novel measures based on graded relevance judgments may be developed. This article proposes several novel measures that compute the cumulative gain the user obtains by examining the retrieval result up to a given ranked position. The first one accumulates the relevance scores of retrieved documents along the ranked result list. The second one is similar but applies a discount factor to the relevance scores in order to devaluate late-retrieved documents. The third one computes the relative-to-the-ideal performance of IR techniques, based on the cumulative gain they are able to yield. These novel measures are defined and discussed and their use is demonstrated in a case study using TREC data: sample system run results for 20 queries in TREC-7. As a relevance base we used novel graded relevance judgments on a four-point scale. The test results indicate that the proposed measures credit IR methods for their ability to retrieve highly relevant documents and allow testing of statistical significance of effectiveness differences. The graphs based on the measures also provide insight into the performance IR techniques and allow interpretation, for example, from the user point of view.

REFERENCES

• 1: David C. Blair , M. E. Maron, An evaluation of retrieval effectiveness for a full-text document-retrieval system, Communications of the ACM, v.28 n.3, p.289-299, March 1985 [doi>10.1145/3166.3197]
• 2: Borlund, P. 2000. Evaluation of interactive information retrieval systems. PhD Dissertation. Åbo University Press.
• 3: Pia Borlund , Peter Ingwersen, Measures of relative relevance and ranked half-life: performance indicators for interactive IR, Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval, p.324-331, August 24-28, 1998, Melbourne, Australia [doi>10.1145/290941.291019]
• 4: Conover, W. J. 1980. Practical Nonparametric Statistics, 2nd ed., Wiley, New York.
• 5: Cooper, W. S. 1968. Expected search length: A single measure of retrieval effectiveness based on weak ordering action of retrieval systems. J. Am. Soc. Inf. Sci. 19, 1, 30--41.
• 6: William R. Hersh , David H. Hickam, An evaluation of interactive Boolean and natural language searching with an online medical textbook, Journal of the American Society for Information Science, v.46 n.7, p.478-489, Aug. 1995 [doi>10.1002/(SICI)1097-4571(199508)46:7<478::AID-ASI2>3.0.CO;2-#]
• 7: David Hull, Using statistical testing in the evaluation of retrieval experiments, Proceedings of the 16th annual international ACM SIGIR conference on Research and development in information retrieval, p.329-338, June 27-July 01, 1993, Pittsburgh, Pennsylvania, United States [doi>10.1145/160688.160758]
• 8: Kalervo Järvelin , Jaana Kekäläinen, IR evaluation methods for retrieving highly relevant documents, Proceedings of the 23rd annual international ACM SIGIR conference on Research and development in information retrieval, p.41-48, July 24-28, 2000, Athens, Greece [doi>10.1145/345508.345545]
• 9: Jaana Kekäläinen , Kalervo Järvelin, The impact of query structure and query expansion on retrieval performance, Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval, p.130-137, August 24-28, 1998, Melbourne, Australia [doi>10.1145/290941.290978]
• 10: Jaana KekäläInen , Kalervo Järvelin, The Co-Effects of Query Structure and Expansion on RetrievalPerformance in Probabilistic Text Retrieval, Information Retrieval, v.1 n.4, p.329-344, January 2000 [doi>10.1023/A:1009983401464]
• 11: Jaana Kekäläinen , Kalervo Järvelin, Using graded relevance assessments in IR evaluation, Journal of the American Society for Information Science and Technology, v.53 n.13, p.1120-1129, November 2002 [doi>10.1002/asi.10137]
• 12: Kekäläinen, J. and Järvelin, K. 2002b. Evaluating information retrieval systems under the challenges of interaction and multidimensional dynamic relevance. In Proceedings of the CoLIS 4 Conference, H. Bruce, R. Fidel, P. Ingwersen, AND P. Vakkari, Eds., Libraries Unlimited: Greenwood Village, Colo., 253--270.
• 13: Robert R. Korfhage, Information storage and retrieval, John Wiley & Sons, Inc., New York, NY, 1997
• 14: Robert M. Losee, Text retrieval and filtering: analytic models of performance, Kluwer Academic Publishers, Norwell, MA, 1998
• 15: Sung H. Myaeng , Robert R. Korfhage, Integration of user profiles: models and experiments in information retrieval, Information Processing and Management: an International Journal, v.26 n.6, p.719-738, 1990 [doi>10.1016/0306-4573(90)90048-7]
• 16: Pollack, S. M. 1968. Measures for the comparison of information retrieval systems. Am. Doc. 19, 4, 387--397.
• 17: Over, P. 1999. TREC-7 interactive track report {On-line}. Available at http://trec.nist.gov/pubs/trec7/papers/t7irep.pdf.gz. In NIST Special Publication 500-242: The Seventh Text REtrieval Conference (TREC 7).
• 18: Robertson, S. E. and Belkin, N. J. 1978. Ranking in principle. J. Doc. 34, 2, 93--100.
• 19: Rocchio, J. J., Jr. 1966. Document retrieval systems---Optimization and evaluation. PhD Dissertation. Harvard Computation Laboratory, Harvard University.
• 20: Tetsuya Sakai , Karen Sparck-Jones, Generic summaries for indexing in information retrieval, Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval, p.190-198, September 2001, New Orleans, Louisiana, United States [doi>10.1145/383952.383987]
• 21: Gerard Salton , Michael J. McGill, Introduction to Modern Information Retrieval, McGraw-Hill, Inc., New York, NY, 1986
• 22: Saracevic, T. Kantor, P. Chamis, A., and Trivison, D. 1988. A study of information seeking and retrieving. I. Background and methodology. J. Am. Soc. Inf. Sci. 39, 3, 161--176.
• 23: Sormunen, E. 2000. A method for measuring wide range performance of Boolean queries in full-text databases {On-line}. Available at http://acta.uta.fi/pdf/951-44-4732-8.pdf. PhD Dissertation. Department of Information Studies, University of Tampere.
• 24: Eero Sormunen, Extensions to the STAIRS Study—Empirical Evidence for the Hypothesised Ineffectiveness of Boolean Queries in Large Full-Text Databases, Information Retrieval, v.4 n.3-4, p.257-273, September-December 2001 [doi>10.1023/A:1011950323099]
• 25: Eero Sormunen, Liberal relevance criteria of TREC -: counting on negligible documents?, 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.564433]
• 26: Sparck-Jones, K. 1974. Automatic indexing. J. Doc. 30, 393--432.
• 27: Amanda Spink , Howard Greisdorf , Judy Bateman, From highly relevant to not relevant: examining different regions of relevance, Information Processing and Management: an International Journal, v.34 n.5, p.599-621, Sept. 1998 [doi>10.1016/S0306-4573(98)00025-9]
• 28: Rong Tang , William M. Shaw, Jr. , Jack L. Vevea, Towards the identification of the optimal number of relevance categories, Journal of the American Society for Information Science, v.50 n.3, p.254-264, March 1999 [doi>10.1002/(SICI)1097-4571(1999)50:3<254::AID-ASI8>3.3.CO;2-P]
• 29: Trec Homepage 2001. Data---English relevance judgements {On-line}. Available at http://trec.nist.gov/data/reljudge_eng.html.
• 30: Vakkari, P. and Hakala, N. 2000. Changes in relevance criteria and problem stages in task performance. J. Doc. 56, 540--562.
• 31: 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]
• 32: Voorhees, E. and Harman, D. 1999. Overview of the Seventh Text REtrieval Conference (TREC-7) {On-line}. Available at http://trec.nist.gov/pubs/trec7/papers/overview7.pdf.gz. In NIST Special Publication 500-242: The Seventh Text REtrieval Conference (TREC 7).
• 33: 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.3 Information Search and Retrieval
          Subjects: Relevance feedback

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:
Algorithms, Experimentation, Measurement, Performance

Keywords:
Graded relevance judgments, cumulated gain