The maximum entropy approach and probabilistic IR models

ABSTRACT

This paper takes a fresh look at modeling approaches to information retrieval that have been the basis of much of the probabilistically motivated IR research over the last 20 years. We shall adopt a subjectivist Bayesian view of probabilities and argue that classical work on probabilistic retrieval is best understood from this perspective. The main focus of the paper will be the ranking formulas corresponding to the Binary Independence Model (BIM), presented originally by Roberston and Sparck Jones [1977] and the Combination Match Model (CMM), developed shortly thereafter by Croft and Harper [1979]. We will show how these same ranking formulas can result from a probabilistic methodology commonly known as Maximum Entropy (MAXENT).

REFERENCES

• 1: BEEFERMAN, D., BERGER, A., AND LAFFERTY, J. 1997. Text segmentation using exponential models. In Proceedings of Empirical Methods in Natural Language Processing.
• 2: BRETTHORST, G. L. 1988. Excerpts from bayesian spectrum analysis and parameter estima-tion. In Maximum Entropy and Bayesian Methods in Science and Engineering,G.J. Erickson and C. R. Smith, Eds. Kluwer Academic Publishers, Norwell, MA, 75-146.
• 3: CHIANG, A. C. 1967. Fundamental Methods of Mathematical Economics. McGraw-Hill, New York.
• 4: COOPER, W. S. 1983. Exploiting the maximum entropy principle to increase retrieval effectiveness. Journal of the American Society for Information Science 34, 1, 31-39.
• 5: William S. Cooper, Some inconsistencies and misnomers in probabilistic information retrieval, Proceedings of the 14th annual international ACM SIGIR conference on Research and development in information retrieval, p.57-61, October 13-16, 1991, Chicago, Illinois, United States [doi>10.1145/122860.122866]
• 6: COOPER,W.S.AND HUIZINGA, P. 1982. The maximum entropy principle and its application to the design of probabilistic retrieval systems. Information Technology, Research & Devel-opment 1, 99-112.
• 7: CROFT,W.B.AND HARPER, D. J. 1979. Using probabilistic models of document retrieval without relevance information. Journal of Documentation 35, 4 (Dec.), 285-295.
• 8: DARROCH,J.AND RATCLIFF, D. 1972. Generalized iterative scaling for log-linear models. Annals of Mathematical Statistics 43, 1470-1480.
• 9: DAWID, A. P. 1989. Probability forecasting. In Encyclopedia of Statistical Sciences, S. Kotz and N. L. Johnson, Eds. Vol. 7. Wiley, New York, 210-218.
• 10: DEGROOT,M.AND FEINBERG, S. 1982. The comparison and evaluation of forecasters. The Statistician 32, 12-22.
• 11: Stephen Della Pietra , Vincent Della Pietra , John Lafferty, Inducing Features of Random Fields, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.19 n.4, p.380-393, April 1997 [doi>10.1109/34.588021]
• 12: ERICKSON,G.J.AND SMITH, C. R. 1988. Maximum Entropy and Bayesian Methods in Science and Engineering. Kluwer Academic Publishers, Norwell, MA.
• 13: FINE, T. L. 1973. Theories of Probability: An Examination of Foundations. Academic Press,New York.
• 14: GOLAN, A., JUDGE,G.G.,AND MILLER, D. 1996. Maximum Entropy Econometrics: Robust Estimation with Limited Data. John Wiley and Sons, New York.
• 15: GOOD, I. J. 1950. Probability and the Weighing of Evidence. Charles Griffin, London.
• 16: GOOD, I. J. 1960. Weight of evidence, corroboration, explanatory power, information and the utility of experiments. Journal of the Royal Statistical Society:Series B. 22, 319-331.
• 17: GULL,S.F.AND DANIELL, G. J. 1978. Image reconstruction from incomplete and noisy data. Nature 272, 686-690.
• 18: HACKING, I. 1965. Logic of Statistical Inference. Cambridge University Press, Cambridge.
• 19: HARPER,D.J.AND VAN RIJSBERGEN, C. J. 1978. An evaluation of feedback in document retrieval using co-occurrence data. Journal of Documentation 34, 3 (Sept.), 189-216.
• 20: JAYNES, E. T. 1957a. Information theory and statistical mechanics: Part I. Physical Review 106, 620-630.
• 21: JAYNES, E. T. 1957b. Information theory and statistical mechanics: Part II. Physical Review 108, 171.
• 22: JAYNES, E. T. 1963. Information theory and statistical mechanics. In Statistical Physics: Brandeis Summer Institute Lectures in Theoretical Physics, G. E. Uhlenbeck, Ed. Brandeis Summer Institute Lectures in Theoretical Physics, vol. 3. W. A. Benjamin, New York, 182-218.
• 23: JAYNES, E. T. 1979. Where do we stand on maximum entropy. In The Maximum Entropy Formalism, R. D. Levine and M. Tribus, Eds. MIT Press, Cambridge, Massachusetts, 15-118.
• 24: JAYNES, E. T. 1994. Probability theory: The logic of science. Available via ftp://bayes. wustl.edu/pub/Jaynes/book.probability.theory/.
• 25: KANTOR, P. B. 1984. Maximum entropy and the optimal design of automated information retrieval systems. Information Technology, Research and Development 3, 2 (Apr.), 88-94.
• 26: Paul B. Kantor , Jung Jin Lee, The maximum entropy principle in information retrieval, Proceedings of the 9th annual international ACM SIGIR conference on Research and development in information retrieval, p.269-274, September 1986, Palazzo dei Congressi, Pisa, Italy [doi>10.1145/253168.253225]
• 27: Paul B. Kantor , Jung Jin Lee, Testing the maximum entropy principle for information retrieval, Journal of the American Society for Information Science, v.49 n.6, p.557-566, May 1, 1998 [doi>10.1002/(SICI)1097-4571(19980501)49:6<557::AID-ASI7>3.0.CO;2-S]
• 28: LEE,J.J.AND KANTOR, P. B. 1991. A study of probabilistic information retrieval in the case of inconsistent expert judgments. Journal of the American Society for Information Science 42, 3, 166-172.
• 29: MARSHALL,K.T.AND OLIVER, R. M. 1995. Decision Making and Forecasting: with Emphasis on Model Building and Policy Analysis. McGraw-Hill, New York.
• 30: ROBERTSON, S. E. 1977. The probability ranking principle in IR. Journal of Documentation 33, 294-304.
• 31: ROBERTSON,S.E.AND SPARCK JONES, K. 1977. Relevance weighting of search terms. Journal of the American Society for Information Science 27, 129-146.
• 32: SALTON, G., WONG, A., AND YU, C. T. 1976. Automatic indexing using term discrimination and term precision measurements. Information Processing and Management 12, 43-51.
• 33: SHANNON, C. E. 1948. A mathematical theory of communication. The Bell System Technical Journal 27, 379-423 & 623-656.
• 34: SMEATON,A.F.AND VAN RIJSBERGEN, C. J. 1983. The retrieval effects of query expansion on a feedback document retrieval system. The Computer Journal 25, 3, 239-246.
• 35: SPARCK JONES, K. 1972. A statistical interpretation of term specificity and its application in retrieval. Journal of Documentation 28, 11-21.
• 36: TRIBUS, M. 1969. Rational Descriptions, Decisions, and Designs. Pergamon-Hall, New York.
• 37: TRIBUS, M. 1979. Thirty years of information theory. In The Maximum Entropy Formalism, R. D. Levine and M. Tribus, Eds. MIT Press, Cambridge, Massachusetts, 1-14.
• 38: VAN RIJSBERGEN, C. J. 1977. A theoretical basis for the use of co-occurrence data in information retrieval. Journal of Documentation 33, 106-119.
• 39: C. J. Van Rijsbergen, Information Retrieval, Butterworth-Heinemann, Newton, MA, 1979

INDEX TERMS

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

General Terms:
Theory

Keywords:
idf weighting, binary independence model, combination match, linked dependence, probability ranking principle