On modeling information retrieval with probabilistic inference

ABSTRACT

This article examines and extends the logical models of information retrieval in the context of probability theory. The fundamental notions of term weights and relevance are given probabilistic interpretations. A unified framework is developed for modeling the retrieval process with probabilistic inference. This new approach provides a common conceptual and mathematical basis for many retrieval models, such as the Boolean, fuzzy set, vector space, and conventional probabilistic models. Within this framework, the underlying assumptions employed by each model are identified, and the inherent relationships between these models are analyzed. Although this article is mainly a theoretical analysis of probabilistic inference for information retrieval, practical methods for estimating the required probabilities are provided by simple examples.

REFERENCES

• 1: ADAMS, E.W. 1975. The Logic ofCondtttonals. Reidel, Dordrecht.
• 2: BELLMAN, R. E. AND ZADEH, L.A. 1970 Decislon-making in fuzzy environment Manage. Sci. 17, 141-164.
• 3: Abraham Bookstein, Implications of Boolean structure for probabilistic retrieval, Proceedings of the 8th annual international ACM SIGIR conference on Research and development in information retrieval, p.11-17, June 05-07, 1985, Montreal, Quebec, Canada [doi>10.1145/253495.253505]
• 4: BUELL, D. A. AND KRAFT, D.H. 1981a. Threshold values and Boolean retrieval systems. Inf. Process. Manage. 17, 127-136
• 5: BUELL, D. A. AND KRAFT, D.H. 1981b. A model for a weighted retrieval system. J. Am. Soc. Inf. Sci. 32, 211-216.
• 6: CARNAP, R. 1971. Inductive logic and rational decision. In Studies m Inductive Logic and Probab~ltty. Vol. 1. University of California Press, Berkeley, Calif., 5-31.
• 7: CAR~, R. 1962. Logical Foundations of Probability. 2nd ed. University of Chicago Press, Chicago, Ill.
• 8: Y. Chiaramella , J. P. Chevallet, About retrieval models and logic, The Computer Journal, v.35 n.3, p.233-242, June 1992 [doi>10.1093/comjnl/35.3.233]
• 9: C~ow, C. K. AND LIu, C. N. 1968. Approximating discrete probability distributions with dependence trees. IEEE Trans. Inf. Theor. IT-14, 462-467.
• 10: COOPER, W.S. 1971. A definition of relevance for information retrieval. Inf. Storage Retriev. 7, 19-37
• 11: CROFT, W. B. AND HARPER, D. J. 1979. Using probabilistic models of document retrieval without relevance information. J. Doc. 35, 285 295.
• 12: W. B. Croft , T. J. Lucia , J. Cringean , P. Willett, Retrieving documents by plausible inference: an experimental study, Information Processing and Management: an International Journal, v.25 n.6, p.599-614, 1989 [doi>10.1016/0306-4573(89)90095-2]
• 13: DE FINET~I, B. 1974. Theory of Probability. Wiley, New York.
• 14: FINE, T L. 1973. Theorzes of Probability: An Examination of Foundatzons Academic Press, New York.
• 15: 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]
• 16: Norbert Fuhr, Two models of retrieval with probabilistic indexing, Proceedings of the 9th annual international ACM SIGIR conference on Research and development in information retrieval, p.249-257, September 1986, Palazzo dei Congressi, Pisa, Italy [doi>10.1145/253168.253221]
• 17: GILES, R. 1976. Lukasiewicz logic fuzzy theory. Int. J. Man-Machine Stud. 8, 313-327.
• 18: GOOD, I.J. 1983. Good Thinking: The Foundations of Probability and Its Application. University of Minnesota Press, Minneapolis.
• 19: Michael Gordon , Manfred Kochen, Recall-precision trade-off: a derivation, Journal of the American Society for Information Science, v.40 n.3, p.145-151, May 1989 [doi>10.1002/(SICI)1097-4571(198905)40:3<145::AID-ASI1>3.0.CO;2-I]
• 20: HACKING, I. 1975. The Emergence of Probability. Cambridge University Press, London.
• 21: HARRISON, M.A. 1965. Introduction to Switching and Automata Theory. McGraw-Hill Book Company, New York.
• 22: JAMES, E.T. 1979. Where do we stand on maximum entropy. In The Maximum Entropy Formalism. The MIT Press, Cambridge, Mass.
• 23: KLm, G. J. ANn FOLGER, T.A. 1988. Fuzzy sets, Uncertainty, and Information. Prentice-Hall, Englewood Cliffs, N. J.
• 24: M. E. Maron , J. L. Kuhns, On Relevance, Probabilistic Indexing and Information Retrieval, Journal of the ACM (JACM), v.7 n.3, p.216-244, July 1960 [doi>10.1145/321033.321035]
• 25: MARR, D. 1982. Vision. Freeman, San Francisco.
• 26: Jian-Yun Nie, Towards a probabilistic modal logic for semantic-based information retrieval, Proceedings of the 15th annual international ACM SIGIR conference on Research and development in information retrieval, p.140-151, June 21-24, 1992, Copenhagen, Denmark [doi>10.1145/133160.133188]
• 27: Nm, J. 1989. An information retrieval model based on modal logic. Inf. Process. Manage. 25, 477-491.
• 28: Z. Pawlak , S. K. M. Wong , W. Ziarko, Rough sets: probabilistic versus deterministic approach, International Journal of Man-Machine Studies, v.29 n.1, p.81-95, July 1988 [doi>10.1016/S0020-7373(88)80032-4]
• 29: Judea Pearl, Probabilistic reasoning in intelligent systems: networks of plausible inference, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1988
• 30: RADECKI, T. 1976. Mathematic model of information retrieval based on the concept of a fuzzy thesaurus. Inf. Process. Manage. 12,313-318.
• 31: RAGHAVAN, V. V. AND WONG, S. K. M. 1986. A critical analysis of vector space model in information retrieval. J. Am. Soc. Inf. Sc~. 37, 279-287.
• 32: ROBERTSON, S.E. 1977. The probability ranking principle in IR. J. Doc. 33, 294-304.
• 33: ROBERTSON, S. E. ANn SPARCK JONES, K. 1976. Relevance weighting of search terms. J. Am. Soc. Inf. Sci. 27, 129-146.
• 34: ROBERTSON, S. E., MARON, M. E., AND COOPER, W. S. 1982. Probability of relevance: A unification of two competing models for document retrieval. Inf. Tech. Res. Dev. 1, 1-21.
• 35: G. Salton, The SMART Retrieval System—Experiments in Automatic Document Processing, Prentice-Hall, Inc., Upper Saddle River, NJ, 1971
• 36: Gerard Salton , Michael J. McGill, Introduction to Modern Information Retrieval, McGraw-Hill, Inc., New York, NY, 1986
• 37: Gerard Salton , Edward A. Fox , Harry Wu, Extended Boolean information retrieval, Communications of the ACM, v.26 n.11, p.1022-1036, Nov. 1983 [doi>10.1145/182.358466]
• 38: SARACEVIC, T. 1975. Relevance: A review of and a framework for the thinking on the notion in information science. J. Am. Soc. Inf. Sci. 26, 321-343.
• 39: SAVAGE, L.J. 1972. The Foundations of Statistics. Dover, New York.
• 40: P. Schauble, Thesaurus based concept spaces, Proceedings of the 10th annual international ACM SIGIR conference on Research and development in information retrieval, p.254-262, June 03-05, 1987, New Orleans, Louisiana, United States [doi>10.1145/42005.42034]
• 41: SH~ER, G. 1987. Probability judgment in artificial and expert systems. Stat. Sci. 2, 3-16.
• 42: SHANNON, C.E. 1948. The mathematical theory of communication. Bell Syst. Tech. J. 27, 379-423,623-656.
• 43: P. Thompson, A combination of expert opinion approach to probabilistic information retrieval, part 1: The conceptual model, Information Processing and Management: an International Journal, v.26 n.3, p.371-382, 1990 [doi>10.1016/0306-4573(90)90097-L]
• 44: Paul Thompson, Subjective probability and information retrieval: a review of the psychological literature, Journal of Documentation, v.44 n.2, p.119-143, June 1988 [doi>10.1108/eb026821]
• 45: 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]
• 46: H. Turtle , W. B. Croft, Inference networks for document retrieval, Proceedings of the 13th annual international ACM SIGIR conference on Research and development in information retrieval, p.1-24, September 05-07, 1990, Brussels, Belgium [doi>10.1145/96749.98006]
• 47: C. J. van Rijsbergen, Probabilistic retrieval revisited, The Computer Journal, v.35 n.3, p.291-298, June 1992 [doi>10.1093/comjnl/35.3.291]
• 48: C. J. van Rijsbergen, Towards an information logic, Proceedings of the 12th annual international ACM SIGIR conference on Research and development in information retrieval, p.77-86, June 25-28, 1989, Cambridge, Massachusetts, United States
• 49: VAN RIJSBERGEN, C.J. 1986 A non-classical logic for information retrieval. Comput. J. 29, 481-485.
• 50: C. J. Van Rijsbergen, Information Retrieval, Butterworth-Heinemann, Newton, MA, 1979
• 51: Satosi Watanabe, Pattern recognition: human and mechanical, John Wiley & Sons, Inc., New York, NY, 1985
• 52: S. K. M. Wong , Y. Y. Yao, A probabilistic inference model for information retrieval, Information Systems, v.16 n.3, p.301-321, 1991 [doi>10.1016/0306-4379(91)90003-R]
• 53: WONG, S. K. M. AND YAO, Y.Y. 1990. A generalized binary probabilistic independence model. J. Am Soc. Inf. Sci. 41,324-329.
• 54: WONG, S. K. M., BOLLMANN, P., AND YAO, Y.Y. 1991. Information retrieval based on axiomatic decision theory. Int. J. Gen. Syst. 19,301-321.
• 55: S. K.M. Wong , W. Ziarko , V. V. Raghavan , P. C.N. Wong, On modeling of information retrieval concepts in vector spaces, ACM Transactions on Database Systems (TODS), v.12 n.2, p.299-321, June 1987 [doi>10.1145/22952.22957]
• 56: Y. Y. Yao , S. K. M. Wong, A decision theoretic framework for approximating concepts, International Journal of Man-Machine Studies, v.37 n.6, p.793-809, Dec. 1992 [doi>10.1016/0020-7373(92)90069-W]
• 57: C. T. Yu , G. Salton, Precision Weighting—An Effective Automatic Indexing Method, Journal of the ACM (JACM), v.23 n.1, p.76-88, Jan. 1976 [doi>10.1145/321921.321930]
• 58: ZADEH, L.A. 1965. Fuzzy sets. Inf. Contr. 8, 338-353.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Query formulation

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.3 Deduction and Theorem Proving
          Subjects: Uncertainty, "fuzzy," and probabilistic reasoning

General Terms:
Algorithms, Theory