Extraction of coherent relevant passages using hidden Markov models

ABSTRACT

In information retrieval, retrieving relevant passages, as opposed to whole documents, not only directly benefits the end user by filtering out the irrelevant information within a long relevant document, but also improves retrieval accuracy in general. A critical problem in passage retrieval is to extract coherent relevant passages accurately from a document, which we refer to as passage extraction. While much work has been done on passage retrieval, the passage extraction problem has not been seriously studied. Most existing work tends to rely on presegmenting documents into fixed-length passages which are unlikely optimal because the length of a relevant passage is presumably highly sensitive to both the query and document.In this article, we present a new method for accurately detecting coherent relevant passages of variable lengths using hidden Markov models (HMMs). The HMM-based method naturally captures the topical boundaries between passages relevant and nonrelevant to the query. Pseudo-feedback mechanisms can be naturally incorporated into such an HMM-based framework to improve parameter estimation. We show that with appropriate parameter estimation, the HMM method outperforms a number of strong baseline methods on two datasets. We further show how the HMM method can be applied on top of any basic passage extraction method to improve passage boundaries.

REFERENCES

• 1: Allan, J. 2003. Hard track overview in trec 2003: High accuracy retrieval from documents. In Proceedings of the 12th Text REtrieval Conference. 24--37.
• 2: James P. Callan, Passage-level evidence in document retrieval, Proceedings of the 17th annual international ACM SIGIR conference on Research and development in information retrieval, p.302-310, July 03-06, 1994, Dublin, Ireland
• 3: Charles L. A. Clarke , Egidio L. Terra, Passage retrieval vs. document retrieval for factoid question answering, 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.860534]
• 4: Conroy, J. and O'Leary, D. P. 2001. Text summarization via hidden Markov models and pivoted QR matrix decomposition. Tech. Rep., University of Maryland, College Park.
• 5: Cormack, G. V., Clarke, C. L. A., Palmer, C. R., and To, S. S. L. 1998. Passage-based refinement (MultiText experiments for TREC-6). In Proceedings of the 6th Text REtrieval Conference. 303--320.
• 6: Andrés Corrada-Emmanuel , W. Bruce Croft, Answer models for question answering passage 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.1009098]
• 7: Denoyer, L. and Zaragoza, H. 2001. HMM-based passage models for document classification and ranking. In Proceedings of the 23rd BCS European Annual Colloquium on Information Retrieval.
• 8: Dayne Freitag , Andrew McCallum, Information Extraction with HMM Structures Learned by Stochastic Optimization, Proceedings of the Seventeenth National Conference on Artificial Intelligence and Twelfth Conference on Innovative Applications of Artificial Intelligence, p.584-589, July 30-August 03, 2000
• 9: Pascale Fung , Grace Ngai , Chi-Shun Cheung, Combining optimal clustering and Hidden Markov models for extractive summarization, Proceedings of the ACL 2003 workshop on Multilingual summarization and question answering, p.21-28, July 11, 2003 [doi>10.3115/1119312.1119315]
• 10: He, D., Demner-Fushman, D., Oard, D. W., Karakos, D., and Khudanpur, S. 2004. Improving passage retrieval using interactive elicitation and statistical modeling. In Proceedings of the 13th Text REtrieval Conference.
• 11: Marti A. Hearst, TextTiling: segmenting text into multi-paragraph subtopic passages, Computational Linguistics, v.23 n.1, p.33-64, March 1997
• 12: Jiang, J. and Zhai, C. 2004. UIUC in HARD 2004--Passage retrieval using HMMs. In Proceedings of the 13th Text REtrieval Conference.
• 13: Marcin Kaszkiel , Justin Zobel, Passage retrieval revisited, Proceedings of the 20th annual international ACM SIGIR conference on Research and development in information retrieval, p.178-185, July 27-31, 1997, Philadelphia, Pennsylvania, United States
• 14: Marcin Kaszkiel , Justin Zobel, Effective ranking with arbitrary passages, Journal of the American Society for Information Science and Technology, v.52 n.4, p.344-364, Feb. 2001 [doi>10.1002/1532-2890(2000)9999:9999<::AID-ASI1075>3.3.CO;2-R]
• 15: Knaus, D., Mittendorf, E., Schäuble, P., and Sheridan, P. 1996. Highlighting relevant passages for users of the interactive SPIDER retrieval system. In Proceedings of the 4th Text REtrieval Conference.
• 16: 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]
• 17: Xiaoyong Liu , W. Bruce Croft, Passage retrieval based on language models, Proceedings of the eleventh international conference on Information and knowledge management, November 04-09, 2002, McLean, Virginia, USA [doi>10.1145/584792.584854]
• 18: Elke Mittendorf , Peter Schäuble, Document and passage retrieval based on hidden Markov models, Proceedings of the 17th annual international ACM SIGIR conference on Research and development in information retrieval, p.318-327, July 03-06, 1994, Dublin, Ireland
• 19: Rabiner, L. R. 1989. A tutorial on hidden Markov models and selected applications in speech recognition. Proc. IEEE 77, 2, 257--286.
• 20: Gerard Salton , J. Allan , Chris Buckley, Approaches to passage retrieval in full text information systems, Proceedings of the 16th annual international ACM SIGIR conference on Research and development in information retrieval, p.49-58, June 27-July 01, 1993, Pittsburgh, Pennsylvania, United States [doi>10.1145/160688.160693]
• 21: Stefanie Tellex , Boris Katz , Jimmy Lin , Aaron Fernandes , Gregory Marton, Quantitative evaluation of passage retrieval algorithms for question answering, 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.860445]
• 22: Zajic, D., Dorr, B., and Schwartz, R. 2005. Headline generation for written and broadcast news. Tech. Rep. LAMP-TR-120, CS-TR-4698, UMIACS-TR-2005-07, University of Maryland, College Park.
• 23: Chengxiang Zhai , John Lafferty, Model-based feedback in the language modeling approach to information retrieval, Proceedings of the tenth international conference on Information and knowledge management, October 05-10, 2001, Atlanta, Georgia, USA [doi>10.1145/502585.502654]
• 24: 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]

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:
Algorithms

Keywords:
Hidden Markov models, passage retrieval