Risky business: modeling and exploiting uncertainty in information retrieval

ABSTRACT

Most retrieval models estimate the relevance of each document to a query and rank the documents accordingly. However, such an approach ignores the uncertainty associated with the estimates of relevancy. If a high estimate of relevancy also has a high uncertainty, then the document may be very relevant or not relevant at all. Another document may have a slightly lower estimate of relevancy but the corresponding uncertainty may be much less. In such a circumstance, should the retrieval engine risk ranking the first document highest, or should it choose a more conservative (safer) strategy that gives preference to the second document? There is no definitive answer to this question, as it depends on the risk preferences of the user and the information retrieval system. In this paper we present a general framework for modeling uncertainty and introduce an asymmetric loss function with a single parameter that can model the level of risk the system is willing to accept. By adjusting the risk preference parameter, our approach can effectively adapt to users' different retrieval strategies.

We apply this asymmetric loss function to a language modeling framework and a practical risk-aware document scoring function is obtained. Our experiments on several TREC collections show that our "risk-averse" approach significantly improves the Jelinek-Mercer smoothing language model, and a combination of our "risk-averse" approach and the Jelinek-Mercer smoothing method generally outperforms the Dirichlet smoothing method. Experimental results also show that the "risk-averse" approach, even without smoothing from the collection statistics, performs as well as three commonly-adopted retrieval models, namely, the Jelinek-Mercer and Dirichlet smoothing methods, and BM25 model.

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: D.M. Blei, A.Y. Ng, and M.I. Jordan. Latent Dirichlet allocation. In Proc. of NIPS, pages 601--608, 2001.
• 3: Harr Chen , David R. Karger, Less is more: probabilistic models for retrieving fewer relevant documents, Proceedings of the 29th annual international ACM SIGIR conference on Research and development in information retrieval, August 06-11, 2006, Seattle, Washington, USA [doi>10.1145/1148170.1148245]
• 4: K. Church and W. Gale. Poisson mixtures. Journal of Natural Language Engineering, 1995.
• 5: A. Gelman, J.B. Carlin, H.S. Stern, and D.B. Rubin. Bayesian Data Analysis. Chapman and Hall, 2003.
• 6: D. Hiemstra. Using language models for information retrieval. Doctoral thesis, University of Twente, 2001.
• 7: Thomas Hofmann, Latent semantic models for collaborative filtering, ACM Transactions on Information Systems (TOIS), v.22 n.1, p.89-115, January 2004 [doi>10.1145/963770.963774]
• 8: F. Jelinek and R. Mercer. Interpolated estimation of markov source parameters from sparse data. Pattern Recognition in Practice, pages 381--402, 1980.
• 9: M. Kendall and A. Stuart, editors. The Advanced Theory of Statistics Volume 1, 3rd Edition (Section 3.12). Griffin, London, 1969.
• 10: 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]
• 11: E. Lukacs, editor. Characteristic Functions, 2nd Edition (Page 27). Griffin, London, 1970.
• 12: Rasmus E. Madsen , David Kauchak , Charles Elkan, Modeling word burstiness using the Dirichlet distribution, Proceedings of the 22nd international conference on Machine learning, p.545-552, August 07-11, 2005, Bonn, Germany [doi>10.1145/1102351.1102420]
• 13: 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]
• 14: 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]
• 15: John Risson , Tim Moors, Survey of research towards robust peer-to-peer networks: search methods, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.50 n.17, p.3485-3521, 5 December 2006 [doi>10.1016/j.comnet.2006.02.001]
• 16: S. E. Robertson, The probability ranking principle in IR, Readings in information retrieval, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1997
• 17: S.E. Robertson, M.E. Maron, and W. Cooper. Probability of relevance: a unification of two competing models for document retrieval. Information Technology: Research and Development, 1(1):1--21, 1982.
• 18: S.E. Robertson and K. Sparck Jones. Relevance weighting of search terms. Journal of the American Society for Information Science, 27(3):129--146, 1976.
• 19: 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
• 20: S.E. Robertson, S. Walker, M. Hancock-Beaulieu, M. Gatford, and A. Payne. Okapi at trec-4. In Text REtrieval Conference (TREC), 1995.
• 21: J.A. Thom and F. Scholer. A comparison of evaluation measures given how users perform on search tasks. In Australasian Document Computing Symposium, pages 100--103, 2007.
• 22: C. J. Van Rijsbergen, Information Retrieval, Butterworth-Heinemann, Newton, MA, 1979
• 23: Jun Wang , Jianhan Zhu, Portfolio theory of information retrieval, Proceedings of the 32nd international ACM SIGIR conference on Research and development in information retrieval, July 19-23, 2009, Boston, MA, USA [doi>10.1145/1571941.1571963]
• 24: Hugo Zaragoza , Djoerd Hiemstra , Michael Tipping, Bayesian extension to the language model for ad hoc information retrieval, Proceedings of the 26th annual international ACM SIGIR conference on Research and development in informaion retrieval, July 28-August 01, 2003, Toronto, Canada [doi>10.1145/860435.860439]
• 25: A. Zellner. Bayesian estimation and prediction using asymmetric loss functions. Journal of the American Statistical Association, 81(394):446--451, 1986.
• 26: 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]
• 27: ChengXiang Zhai , John Lafferty, A risk minimization framework for information retrieval, Information Processing and Management: an International Journal, v.42 n.1, p.31-55, January 2006 [doi>10.1016/j.ipm.2004.11.003]
• 28: Jianhan Zhu , Jun Wang , Michael Taylor , Ingemar J. Cox, Risk-Aware Information Retrieval, Proceedings of the 31th European Conference on IR Research on Advances in Information Retrieval, April 06-09, 2009, Toulouse, France [doi>10.1007/978-3-642-00958-7_5]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.1 Content Analysis and Indexing

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

General Terms:
Algorithms, Experimentation, Measurement, Performance

Keywords:
language models, loss functions, probabilistic retrieval models, probability ranking principle, risk adjustment