Modeling score distributions for combining the outputs of search engines

ABSTRACT

In this paper the score distributions of a number of text search engines are modeled. It is shown empirically that the score distributions on a per query basis may be fitted using an exponential distribution for the set of non-relevant documents and a normal distribution for the set of relevant documents. Experiments show that this model fits TREC-3 and TREC-4 data for not only probabilistic search engines like INQUERY but also vector space search engines like SMART for English. We have also used this model to fit the output of other search engines like LSI search engines and search engines indexing other languages like Chinese.It is then shown that given a query for which relevance information is not available, a mixture model consisting of an exponential and a normal distribution can be fitted to the score distribution. These distributions can be used to map the scores of a search engine to probabilities. We also discuss how the shape of the score distributions arise given certain assumptions about word distributions in documents. We hypothesize that all 'good' text search engines operating on any language have similar characteristics.This model has many possible applications. For example, the outputs of different search engines can be combined by averaging the probabilities (optimal if the search engines are independent) or by using the probabilities to select the best engine for each query. Results show that the technique performs as well as the best current combination techniques.

REFERENCES

• 1: A. Arampatzis, J. Beney, C. H. A. Koster, and T. P. van der Weide. Incrementality, half-life and threshold optimization for adaptive document filtering. In Proc. of the 9th Text Retrieval Conference (TREC-9). NIST, Nov 2000, To be published in late 2001.
• 2: Javed A. Aslam , Mark Montague, Bayes optimal metasearch: a probabilistic model for combining the results of multiple retrieval systems (poster session), Proceedings of the 23rd annual international ACM SIGIR conference on Research and development in information retrieval, p.379-381, July 24-28, 2000, Athens, Greece [doi>10.1145/345508.345665]
• 3: Christopher M. Bishop, Neural networks for pattern recognition, Oxford University Press, Oxford, 1996
• 4: A. Bookstein. When the most Pertinent document should not be retrieved - an analysis of the Swets model. Information Processing and Management, 13:377-383, 1977.
• 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: K. W. Church and W. A. Gale. Poisson mixtures. Natural Language Engineering, 1(2):163-190, 1995.
• 7: W. B. Croft. Combining approaches to information retrieval. In W. B. Croft, editor, Advances in Information Retrieval, pages 1-36. Kluwer Academic Publishers, 2000.
• 8: Ronald Fagin, Fuzzy queries in multimedia database systems, Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.1-10, June 01-04, 1998, Seattle, Washington, United States [doi>10.1145/275487.275488]
• 9: Myron Flickner , Harpreet Sawhney , Wayne Niblack , Jonathan Ashley , Qian Huang , Byron Dom , Monika Gorkani , Jim Hafner , Denis Lee , Dragutin Petkovic , David Steele , Peter Yanker, Query by Image and Video Content: The QBIC System, Computer, v.28 n.9, p.23-32, September 1995 [doi>10.1109/2.410146]
• 10: E. Fox and J. Shaw. Combination of multiple searches. In the Proc. of the 2nd Text Retrieval Conference (TREC-2), pages 243-252. National Institute of Standards and Technology Special Publications 500-215, 1994.
• 11: W. Greiff. The use of exploratory data analysis in information retrieval research. In W. B. Croft, editor, Advances in Information Retrieval, pages 37-72. Kluwer Academic Publishers, 2000.
• 12: S. P. Harter. A probabilistic approach to automatic keyword indexing. Journal of the American Society for Information Science, 20:197-206, 1975.
• 13: Joon Ho Lee, Combining multiple evidence from different properties of weighting schemes, Proceedings of the 18th annual international ACM SIGIR conference on Research and development in information retrieval, p.180-188, July 09-13, 1995, Seattle, Washington, United States [doi>10.1145/215206.215358]
• 14: Joon Ho Lee, Analyses of multiple evidence combination, Proceedings of the 20th annual international ACM SIGIR conference on Research and development in information retrieval, p.267-276, July 27-31, 1997, Philadelphia, Pennsylvania, United States
• 15: G. McLachlan and D. Peel. Finite Mixture Models. John Wiley, 2000.
• 16: F. Mosteller and D. Wallace. Inference and Disputed Authorship: The Federalist. Addison Weseley, 1964.
• 17: 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
• 18: J. A. Swets. Information retrieval systems. Science, 141:245-250, 1963.
• 19: K. Tumer and J. Ghosh. Linear and order statistics combiners for pattern clasification. In A. Sharkey, editor, Combining Artificial Neural Networks, pages 127-162. Springer-Verlag, 1999.
• 20: C. J. Van Rijsbergen, Information Retrieval, Butterworth-Heinemann, Newton, MA, 1979
• 21: Christopher C. Vogt , Garrison W. Cottrell, Predicting the performance of linearly combined IR systems, Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval, p.190-196, August 24-28, 1998, Melbourne, Australia [doi>10.1145/290941.290991]
• 22: Ellen M. Voorhees , Narendra K. Gupta , Ben Johnson-Laird, Learning collection fusion strategies, Proceedings of the 18th annual international ACM SIGIR conference on Research and development in information retrieval, p.172-179, July 09-13, 1995, Seattle, Washington, United States [doi>10.1145/215206.215357]

INDEX TERMS

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

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Relevance feedback

General Terms:
Design, Experimentation, Performance