A formal study of information retrieval heuristics

ABSTRACT

Empirical studies of information retrieval methods show that good retrieval performance is closely related to the use of various retrieval heuristics, such as TF-IDF weighting. One basic research question is thus what exactly are these "necessary" heuristics that seem to cause good retrieval performance. In this paper, we present a formal study of retrieval heuristics. We formally define a set of basic desirable constraints that any reasonable retrieval function should satisfy, and check these constraints on a variety of representative retrieval functions. We find that none of these retrieval functions satisfies all the constraints unconditionally. Empirical results show that when a constraint is not satisfied, it often indicates non-optimality of the method, and when a constraint is satisfied only for a certain range of parameter values, its performance tends to be poor when the parameter is out of the range. In general, we find that the empirical performance of a retrieval formula is tightly related to how well it satisfies these constraints. Thus the proposed constraints provide a good explanation of many empirical observations and make it possible to evaluate any existing or new retrieval formula analytically.

REFERENCES

• 1: Gianni Amati , Cornelis Joost Van Rijsbergen, Probabilistic models of information retrieval based on measuring the divergence from randomness, ACM Transactions on Information Systems (TOIS), v.20 n.4, p.357-389, October 2002 [doi>10.1145/582415.582416]
• 2: N. Fuhr. Language models and uncertain inference in information retrieval. In Proceedings of the Language Modeling and IR workshop.
• 3: Norbert Fuhr, Probabilistic models in information retrieval, The Computer Journal, v.35 n.3, p.243-255, June 1992 [doi>10.1093/comjnl/35.3.243]
• 4: J. Kleinberg. An impossibility theorem for clustering. In Advances in NIPS 15, 2002.
• 5: J. Lafferty and C. Zhai.Probabilistic relevance models based on document and query generation. In W. B. Croft and J. Lafferty, editors, Language Modeling and Information Retrieval. Kluwer Academic Publishers, 2003.
• 6: Jay M. Ponte , W. Bruce Croft, A language modeling approach to information retrieval, Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval, p.275-281, August 24-28, 1998, Melbourne, Australia [doi>10.1145/290941.291008]
• 7: S. Robertson and K. Sparck Jones. Relevance weighting of search terms. Journal of the American Society for Information Science, 27:129--146, 1976.
• 8: S. E. Robertson , S. Walker, Some simple effective approximations to the 2-Poisson model for probabilistic weighted retrieval, Proceedings of the 17th annual international ACM SIGIR conference on Research and development in information retrieval, p.232-241, July 03-06, 1994, Dublin, Ireland
• 9: S. E. Robertson , S. Walker, On relevance weights with little relevance information, Proceedings of the 20th annual international ACM SIGIR conference on Research and development in information retrieval, p.16-24, July 27-31, 1997, Philadelphia, Pennsylvania, United States
• 10: Gerard Salton, Automatic text processing: the transformation, analysis, and retrieval of information by computer, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1989
• 11: 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]
• 12: Gerard Salton , Michael J. McGill, Introduction to Modern Information Retrieval, McGraw-Hill, Inc., New York, NY, 1986
• 13: G. Salton, C. S. Yang, and C. T. Yu. A theory of term importance in automatic text analysis. Journal of the American Society for Information Science, 26(1):33--44, Jan-Feb 1975.
• 14: A. Singhal. Modern information retrieval: A brief overview. Bulletin of the IEEE Computer Society Technical Committee on Data Engineering, 24(4):35--43, 2001.
• 15: Howard Turtle , W. Bruce Croft, Evaluation of an inference network-based retrieval model, ACM Transactions on Information Systems (TOIS), v.9 n.3, p.187-222, July 1991 [doi>10.1145/125187.125188]
• 16: C. J. van Rijbergen. A theoretical basis for theuse of co-occurrence data in information retrieval. Journal of Documentation, pages 106--119, 1977.
• 17: C. J. van Rijsbergen. A non-classical logic for information retrieval. The Computer Journal, 29(6), 1986.
• 18: E. Voorhees and D. Harman, editors. Proceedings of Text RE trieval Conference(TREC1-9). NIST Special Publications, 2001. http://trec.nist.gov/pubs.html.
• 19: S. K. M. Wong , Y. Y. Yao, On modeling information retrieval with probabilistic inference, ACM Transactions on Information Systems (TOIS), v.13 n.1, p.38-68, Jan. 1995 [doi>10.1145/195705.195713]
• 20: Chengxiang Zhai , John Lafferty, A study of smoothing methods for language models applied to Ad Hoc information retrieval, Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval, p.334-342, September 2001, New Orleans, Louisiana, United States [doi>10.1145/383952.384019]
• 21: Justin Zobel , Alistair Moffat, Exploring the similarity space, ACM SIGIR Forum, v.32 n.1, p.18-34, Spring 1998 [doi>10.1145/281250.281256]

INDEX TERMS

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

General Terms:
Experimentation

Keywords:
TF-IDF weighting, constraints, formal models, retrieval heuristics