An improved markov random field model for supporting verbose queries

ABSTRACT

Recent work in supervised learning of term-based retrieval models has shown significantly improved accuracy can often be achieved via better model estimation. In this paper, we show retrieval accuracy with Metzler and Croft's Markov random field (MRF) approach can be similarly improved via supervised learning. While the original MRF method estimates a parameter for each of its three feature classes from data, parameters within each class are set via a uniform weighting scheme adopted from the standard unigram. We conjecture greater MRF retrieval accuracy should be possible by better estimating within-class parameters, particularly for verbose queries employing natural language terms. Retrieval experiments with these queries on three TREC document collections show our improved MRF consistently out-performs both the original MRF and supervised unigram baselines. Additional experiments using blind-feedback and evaluation with optimal weighting demonstrate both the immediate value and further potential of our method.

REFERENCES

• 1: J. Allan, M. Connell, W.B. Croft, F. Feng, D. Fisher, and X. Li. INQUERY and TREC-9. In Proc. of TREC-9, pages 551--562, 2000.
• 2: Michael Bendersky , W. Bruce Croft, Discovering key concepts in verbose queries, 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.1390419]
• 3: T. Brants and A. Franz. Web 1T 5-gram v1, LDC Catalog No. LDC2006T13, 2006.
• 4: Sergey Brin , Lawrence Page, The anatomy of a large-scale hypertextual Web search engine, Computer Networks and ISDN Systems, v.30 n.1-7, p.107-117, April 1, 1998
• 5: Keke Cai , Chun Chen , Kangmiao Liu , Jiajun Bu , Peng Huang, MRF based approach for sentence retrieval, Proceedings of the 30th annual international ACM SIGIR conference on Research and development in information retrieval, July 23-27, 2007, Amsterdam, The Netherlands [doi>10.1145/1277741.1277913]
• 6: Charles L. A. Clarke , Gordon V. Cormack , Elizabeth A. Tudhope, Relevance ranking for one to three term queries, Information Processing and Management: an International Journal, v.36 n.2, p.291-311, Jan.1.2000 [doi>10.1016/S0306-4573(99)00017-5]
• 7: Jianfeng Gao , Jian-Yun Nie , Guangyuan Wu , Guihong Cao, Dependence language model for information retrieval, Proceedings of the 27th annual international ACM SIGIR conference on Research and development in information retrieval, July 25-29, 2004, Sheffield, United Kingdom [doi>10.1145/1008992.1009024]
• 8: D. Graff, J. Kong, K. Chen, and K. Maeda. English Gigaword. Linguistic Data Consortium catalog number LDC2005T12, 2005.
• 9: Thorsten Joachims , Hang Li , Tie-Yan Liu , ChengXiang Zhai, Learning to rank for information retrieval (LR4IR 2007), ACM SIGIR Forum, v.41 n.2, December 2007 [doi>10.1145/1328964.1328974]
• 10: G. Kumaran and J. Allan. A Case for Shorter Queries, and Helping Users Create Them. In Proceedings of NAACL HLT, pages 220--227, 2007.
• 11: Giridhar Kumaran , James Allan, Effective and efficient user interaction for long queries, 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.1390339]
• 12: 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]
• 13: J. Lafferty and C. Zhai. Probabilistic Relevance Models Based on Document and Query Generation. Language Modeling for Information Retrieval, pages 1--10, 2003.
• 14: Victor Lavrenko , W. Bruce Croft , James Allan, A generative theory of relevance, University of Massachusetts Amherst, 2004
• 15: Victor Lavrenko , W. Bruce Croft, Relevance based language models, Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval, p.120-127, September 2001, New Orleans, Louisiana, United States [doi>10.1145/383952.383972]
• 16: M. Lease. Brown at TREC'08 Relevance Feedback Track. In Proc. of the 17th Text Retrieval Conference (TREC), 2008.
• 17: Matthew Lease , James Allan , W. Bruce Croft, Regression Rank: Learning to Meet the Opportunity of Descriptive Queries, 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_11]
• 18: David McClosky , Eugene Charniak , Mark Johnson, Effective self-training for parsing, Proceedings of the main conference on Human Language Technology Conference of the North American Chapter of the Association of Computational Linguistics, p.152-159, June 04-09, 2006, New York, New York [doi>10.3115/1220835.1220855]
• 19: Donald Metzler , W. Bruce Croft, Latent concept expansion using markov random fields, Proceedings of the 30th annual international ACM SIGIR conference on Research and development in information retrieval, July 23-27, 2007, Amsterdam, The Netherlands [doi>10.1145/1277741.1277796]
• 20: Donald Metzler , W. Bruce Croft, A Markov random field model for term dependencies, Proceedings of the 28th annual international ACM SIGIR conference on Research and development in information retrieval, August 15-19, 2005, Salvador, Brazil [doi>10.1145/1076034.1076115]
• 21: Donald Metzler , W. Bruce Croft, Linear feature-based models for information retrieval, Information Retrieval, v.10 n.3, p.257-274, June 2007 [doi>10.1007/s10791-006-9019-z]
• 22: G. Mishne and M. de Rijke. Boosting web retrieval through query operations. In Proc. of ECIR, 2005.
• 23: Ramesh Nallapati , James Allan, The smoothed dirichlet distribution: understanding cross-entropy ranking in information retrieval, University of Massachusetts Amherst, 2006
• 24: 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]
• 25: M. Porter. The Porter Stemming Algorithm. Accessible at http://www. tartarus. org/martin/PorterStemmer.
• 26: Jeffrey C. Reynar , Adwait Ratnaparkhi, A maximum entropy approach to identifying sentence boundaries, Proceedings of the fifth conference on Applied natural language processing, p.16-19, March 31-April 03, 1997, Washington, DC [doi>10.3115/974557.974561]
• 27: Amit Singhal , Chris Buckley , Mandar Mitra, Pivoted document length normalization, Proceedings of the 19th annual international ACM SIGIR conference on Research and development in information retrieval, p.21-29, August 18-22, 1996, Zurich, Switzerland [doi>10.1145/243199.243206]
• 28: Mark D. Smucker , James Allan , Ben Carterette, A comparison of statistical significance tests for information retrieval evaluation, Proceedings of the sixteenth ACM conference on Conference on information and knowledge management, November 06-10, 2007, Lisbon, Portugal [doi>10.1145/1321440.1321528]
• 29: K. Sparck Jones , S. Walker , S. E. Robertson, A probabilistic model of information retrieval: development and comparative experiments, Information Processing and Management: an International Journal, v.36 n.6, p.779-808, Nov.06.2000 [doi>10.1016/S0306-4573(00)00015-7]
• 30: Munirathnam Srikanth , Rohini Srihari, Biterm language models for document retrieval, Proceedings of the 25th annual international ACM SIGIR conference on Research and development in information retrieval, August 11-15, 2002, Tampere, Finland [doi>10.1145/564376.564476]
• 31: T. Strohman, D. Metzler, H. Turtle, and W.B. Croft. Indri: A language model-based search engine for complex queries. In Proceedings of the International Conference on Intelligence Analysis, 2004.
• 32: Chengxiang Zhai , John Lafferty, A study of smoothing methods for language models applied to information retrieval, ACM Transactions on Information Systems (TOIS), v.22 n.2, p.179-214, April 2004 [doi>10.1145/984321.984322]

INDEX TERMS

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

General Terms:
Algorithms, Experimentation, Theory

Keywords:
information retrieval, markov random field, supervised learning