Portfolio theory of information retrieval

ABSTRACT

This paper studies document ranking under uncertainty. It is tackled in a general situation where the relevance predictions of individual documents have uncertainty, and are dependent between each other. Inspired by the Modern Portfolio Theory, an economic theory dealing with investment in financial markets, we argue that ranking under uncertainty is not just about picking individual relevant documents, but about choosing the right combination of relevant documents. This motivates us to quantify a ranked list of documents on the basis of its expected overall relevance (mean) and its variance; the latter serves as a measure of risk, which was rarely studied for document ranking in the past. Through the analysis of the mean and variance, we show that an optimal rank order is the one that balancing the overall relevance (mean) of the ranked list against its risk level (variance). Based on this principle, we then derive an efficient document ranking algorithm. It generalizes the well-known probability ranking principle (PRP) by considering both the uncertainty of relevance predictions and correlations between retrieved documents. Moreover, the benefit of diversification is mathematically quantified; we show that diversifying documents is an effective way to reduce the risk of document ranking. Experimental results in text retrieval confirm performance.

REFERENCES

• 1: Christopher M. Bishop, Pattern Recognition and Machine Learning (Information Science and Statistics), Springer-Verlag New York, Inc., Secaucus, NJ, 2006
• 2: Stephen Boyd , Lieven Vandenberghe, Convex Optimization, Cambridge University Press, New York, NY, 2004
• 3: Jaime Carbonell , Jade Goldstein, The use of MMR, diversity-based reranking for reordering documents and producing summaries, Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval, p.335-336, August 24-28, 1998, Melbourne, Australia [doi>10.1145/290941.291025]
• 4: 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]
• 5: Charles L.A. Clarke , Maheedhar Kolla , Gordon V. Cormack , Olga Vechtomova , Azin Ashkan , Stefan Büttcher , Ian MacKinnon, Novelty and diversity in information retrieval evaluation, Proceedings of the 31st annual international ACM SIGIR conference on Research and development in information retrieval, July 20-24, 2008, Singapore, Singapore [doi>10.1145/1390334.1390446]
• 6: W.S. Cooper. The inadequacy of probability of usefulness as a ranking criterion for retrieval system output. University of California, Berkeley, 1971.
• 7: E.J. Elton and M.J. Gruber. Modern portfolio theory and investment analysis. J. Wiley and Sons, 2006.
• 8: M.D. Gordon and P. Lenk. A utility theoretic examination of the probability ranking principle in information retrieval. JASIS, 42(10):703--714, 1991.
• 9: Kalervo Järvelin , Jaana Kekäläinen, Cumulated gain-based evaluation of IR techniques, ACM Transactions on Information Systems (TOIS), v.20 n.4, p.422-446, October 2002 [doi>10.1145/582415.582418]
• 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: H. Markowitz. Portfolio selection. Journal of Finance, 1952.
• 12: D. Metzler, T. Strohman, Y. Zhou, and W.B. Croft. Indri at TREC 2005: Terabyte track. In TREC, 2005.
• 13: S.E. Robertson. The probability ranking principle in IR. Journal of Documentation, pages 294--304, 1977.
• 14: S.E. Robertson and N. Belkin. Ranking in principle. Journal of Documentation, pages 93--100, 1978.
• 15: S.E. Robertson and K. Spärck Jones. Relevance weighting of search terms. Journal of the American Society for Information Science, 27(3):129--46, 1976.
• 16: 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
• 17: Badrul Sarwar , George Karypis , Joseph Konstan , John Reidl, Item-based collaborative filtering recommendation algorithms, Proceedings of the 10th international conference on World Wide Web, p.285-295, May 01-05, 2001, Hong Kong, Hong Kong [doi>10.1145/371920.372071]
• 18: J.A. Thom and F. Scholer. A comparison of evaluation measures given how users perform on search tasks. In Twelfth Australasian Document Computing Symposium, 2007.
• 19: Stephen Tomlinson, Early precision measures: implications from the downside of blind feedback, 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.1148327]
• 20: Jun Wang, Mean-Variance Analysis: A New Document Ranking Theory in 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_4]
• 21: Jun Wang , Arjen P. de Vries , Marcel J. T. Reinders, Unifying user-based and item-based collaborative filtering approaches by similarity fusion, 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.1148257]
• 22: A. Zellner. Bayesian estimation and prediction using asymmetric loss functions. Journal of the American Statistical Association, 81(394):446--451, 1986.
• 23: 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]
• 24: 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]
• 25: Jianhan Zhu , Jun Wang , Ingemar J. Cox , Michael J. Taylor, Risky business: modeling and exploiting uncertainty in 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.1571961]

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:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Selection process; Search process

General Terms:
Algorithms, Experimentation, Measurement, Performance, Theory

Keywords:
document ranking under uncertainty, mean-variance analysis, modern portfolio theory, risk management, the probability ranking principle