Probabilistic models of information retrieval based on measuring the divergence from randomness

ABSTRACT

We introduce and create a framework for deriving probabilistic models of Information Retrieval. The models are nonparametric models of IR obtained in the language model approach. We derive term-weighting models by measuring the divergence of the actual term distribution from that obtained under a random process. Among the random processes we study the binomial distribution and Bose--Einstein statistics. We define two types of term frequency normalization for tuning term weights in the document--query matching process. The first normalization assumes that documents have the same length and measures the information gain with the observed term once it has been accepted as a good descriptor of the observed document. The second normalization is related to the document length and to other statistics. These two normalization methods are applied to the basic models in succession to obtain weighting formulae. Results show that our framework produces different nonparametric models forming baseline alternatives to the standard tf-idf model.

REFERENCES

• 1: Allan, J., Callan, J. P., Croft, W. B., Ballesteros, L., Broglio, J., Xu, J., and Shu, H. 1996. INQUERY at TREC-5. In Proceedings of the Fifth Text REtrieval Conference (TREC-5). NIST Special Publication 500-238, Gaithersburg, Md., 119--132.
• 2: Amati, G., Carpineto, C., and Romano, G. 2001. FUB at TREC 10 web track: A probabilistic framework for topic relevance term weighting. In Proceedings of the Tenth Text Retrieval Conference (TREC-10). NIST Special Publication 500-250, Gaithersburg, Md.
• 3: Bookstein, A. and Swanson, D. 1974. Probabilistic models for automatic indexing. J. Am. Soc. Inf. Sci. 25, 312--318.
• 4: Carpineto, C. and Romano, G. 2000. Trec-8 automatic ad-hoc experiments at fub. In Proceedings of the Eighth Text REtrieval Conference (TREC-8). NIST Special Publication 500-246, Gaithersburg, Md., 377--380.
• 5: W. S. Cooper , M. E. Maron, Foundations of Probabilistic and Utility-Theoretic Indexing, Journal of the ACM (JACM), v.25 n.1, p.67-80, Jan. 1978 [doi>10.1145/322047.322053]
• 6: Cox, R. T. 1961. The Algebra of Probable Inference. Johns Hopkins Press, Baltimore, Md.
• 7: Croft, W. and Harper, D. 1979. Using probabilistic models of document retrieval without relevance information. J. Doc. 35, 285--295.
• 8: Damerau, F. 1965. An experiment in automatic indexing. Am. Doc. 16, 283--289.
• 9: Feller, W. 1968. An Introduction to Probability Theory and Its Applications, Vol. I, third ed. Wiley, New York.
• 10: Norbert Fuhr, Models for retrieval with probabilistic indexing, Information Processing and Management: an International Journal, v.25 n.1, p.55-72, 1989 [doi>10.1016/0306-4573(89)90091-5]
• 11: Good, I. J. 1968. The Estimation of Probabilities: An Essay on Modern Bayesian Methods, Vol. 30. MIT Press, Cambridge, Mass.
• 12: Donna Harman, Overview of the second text retrieval conference (TREC-2), Proceedings of the second conference on Text retrieval conference, p.271-289, May 1995, Washington, D.C., United States
• 13: Harter, S. P. 1974. A probabilistic approach to automatic keyword indexing. PhD Thesis, Graduate Library, The University of Chicago, Thesis No. T25146.
• 14: Harter, S. P. 1975a. A probabilistic approach to automatic keyword indexing. Part I: On the distribution of specialty words in a technical literature. J. ASIS 26, 197--216.
• 15: Harter, S. P. 1975b. A probabilistic approach to automatic keyword indexing. Part II: An algorithm for probabilistic indexing. J. ASIS 26, 280--289.
• 16: Hiemstra, D. and de Vries, A. 2000. Relating the new language models of information retrieval to the traditional retrieval models. Res. Rep. TR--CTIT--00--09, Centre for Telematics and Information Technology.
• 17: Hintikka, J. 1970. On semantic information. In Information and Inference, J. Hintikka, and P. Suppes, Eds., Synthese Library. D. Reidel, Dordrecht, Holland, 3--27.
• 18: K. L. Kwok, Experiments with a component theory of probabilistic information retrieval based on single terms as document components, ACM Transactions on Information Systems (TOIS), v.8 n.4, p.363-386, Oct. 1990 [doi>10.1145/102675.102677]
• 19: John Lafferty , Chengxiang Zhai, Document language models, query models, and risk minimization for information retrieval, Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval, p.111-119, September 2001, New Orleans, Louisiana, United States [doi>10.1145/383952.383970]
• 20: Eugene L. Margulis, N-Poisson document modelling, Proceedings of the 15th annual international ACM SIGIR conference on Research and development in information retrieval, p.177-189, June 21-24, 1992, Copenhagen, Denmark [doi>10.1145/133160.133195]
• 21: 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]
• 22: Popper, K. 1995. The Logic of Scientific Discovery (The bulk of the work was first published in Vienna in 1935; this reprint was first published by Hutchinson in 1959, new notes and footnotes in the present reprint). Routledge, London.
• 23: Renyi, A. 1969. Foundations of Probability. Holden-Day, San Francisco.
• 24: Robertson, S. 1986. On relevance weight estimation and query expansion. J. Doc. 42, 3, 288--297.
• 25: 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
• 26: Robertson, S., Walker, S., Beaulieu, M., Gatford, M., and Payne, A. 1996. Okapi at Trec-4. In NIST Special Publication 500-236: The Fourth Text REtrieval Conference (TREC-4), D. Harman, Ed., Department of Commerce, National Institute of Standards and Technology, Gaithersburg, Md., 182--191.
• 27: Robertson, S. E. and Sparck-Jones, K. 1976. Relevance weighting of search terms. J. Am. Soc. Inf. Sci. 27, 129--146.
• 28: S. E. Robertson , C. J. van Rijsbergen , M. F. Porter, Probabilistic models of indexing and searching, Proceedings of the 3rd annual ACM conference on Research and development in information retrieval, p.35-56, June 23-27, 1980, Cambridge, England
• 29: 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]
• 30: Amit Singhal , Gerard Salton , Mandar Mitra , Chris Buckley, Document length normalization, Information Processing and Management: an International Journal, v.32 n.5, p.619-633, Sept. 1996 [doi>10.1016/0306-4573(96)00008-8]
• 31: Solomonoff, R. 1964a. A formal theory of inductive inference. Part I. Inf. Control 7, 1 (March), 1--22.
• 32: Solomonoff, R. 1964b. A formal theory of inductive inference. Part II. Inf. Control 7, 2 (June), 224--254.
• 33: Titterington, D. M., Smith, A. F. M., and Makov, U. E. 1985. Statistical Analysis of Finite Mixture Distributions. Wiley, Chichester.
• 34: Howard R. Turtle , W. Bruce Croft, A comparison of text retrieval models, The Computer Journal, v.35 n.3, p.279-290, June 1992 [doi>10.1093/comjnl/35.3.279]
• 35: van Rijsbergen, C. 1977. A theoretical basis for the use of co-occurrence data in information retrieval. J. Doc. 33, 106--119.
• 36: David G. Willis, Computational Complexity and Probability Constructions, Journal of the ACM (JACM), v.17 n.2, p.241-259, April 1970 [doi>10.1145/321574.321578]
• 37: Witten, I. H., Moffat, A., and Bell, T. C. 1999. Managing Gigabytes, second ed. Morgan Kaufmann, San Francisco.
• 38: 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]

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:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS

General Terms:
Algorithms, Experimentation, Measurement, Theory

Keywords:
Aftereffect model, BM25, Bose--Einstein statistics, Laplace, Poisson, binomial law, document length normalization, eliteness, idf, information retrieval, probabilistic models, randomness, succession law, term frequency normalization, term weighting