Dependence language model for information retrieval

ABSTRACT

This paper presents a new dependence language modeling approach to information retrieval. The approach extends the basic language modeling approach based on unigram by relaxing the independence assumption. We integrate the linkage of a query as a hidden variable, which expresses the term dependencies within the query as an acyclic, planar, undirected graph. We then assume that a query is generated from a document in two stages: the linkage is generated first, and then each term is generated in turn depending on other related terms according to the linkage. We also present a smoothing method for model parameter estimation and an approach to learning the linkage of a sentence in an unsupervised manner. The new approach is compared to the classical probabilistic retrieval model and the previously proposed language models with and without taking into account term dependencies. Results show that our model achieves substantial and significant improvements on TREC collections.

REFERENCES

• 1: Chris Buckley , James Allan , Gerard Salton, Automatic routing and retrieval using Smart: TREC-2, Information Processing and Management: an International Journal, v.31 n.3, p.315-326, May-June 1995
• 2: Eugene Charniak, Immediate-head parsing for language models, Proceedings of the 39th Annual Meeting on Association for Computational Linguistics, p.124-131, July 06-11, 2001, Toulouse, France [doi>10.3115/1073012.1073029]
• 3: Chelba, Ciprian and Frederick Jelinek. 2000. Structured Language Modeling. In: Computer Speech and Language, Vol. 14, No. 4. pp 283--332.
• 4: Chelba, C, D. Engle, F. Jelinek, V. Jimenez, S. Khudanpur, L. Mangu, H. Printz, E. S. Ristad, R. Rosenfeld, A. Stolcke and D. Wu. 1997. Structure and performance of a dependency language model. In: Processing of Eurospeech, Vol. 5, pp 2775--2778.
• 5: Michael John Collins, A new statistical parser based on bigram lexical dependencies, Proceedings of the 34th annual meeting on Association for Computational Linguistics, p.184-191, June 24-27, 1996, Santa Cruz, California [doi>10.3115/981863.981888]
• 6: William S. Cooper, Some inconsistencies and misnomers in probabilistic information retrieval, Proceedings of the 14th annual international ACM SIGIR conference on Research and development in information retrieval, p.57-61, October 13-16, 1991, Chicago, Illinois, United States [doi>10.1145/122860.122866]
• 7: Croft, W. B. 1986. Boolean queries and term dependencies in probabilistic retrieval models. In: JASIS, 37(2): 71--77.
• 8: Stephen D Pietra , Vincent D Pietra , John Gillett , John Lafferty , Harry Printz , Lubos Ures, Inference and Estimation of a Long-Range Trigram Model, Carnegie Mellon University, Pittsburgh, PA, 1994
• 9: 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]
• 10: Harper, D. J. and C. J. van Rijsbergen. 1978. An evaluation of feedback in document retrieval using co-occurrence data. In: Journal of Documentation, 34: 189--216.
• 11: Jianfeng Gao , Ming Zhou , Jian-Yun Nie , Hongzhao He , Weijun Chen, Resolving query translation ambiguity using a decaying co-occurrence model and syntactic dependence relations, 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.564409]
• 12: Jianfeng Gao , Hisami Suzuki, Unsupervised learning of dependency structure for language modeling, Proceedings of the 41st Annual Meeting on Association for Computational Linguistics, p.521-528, July 07-12, 2003, Sapporo, Japan [doi>10.3115/1075096.1075162]
• 13: Harman, D. K. 1995. Overview of the fourth Text REtrieval Conference (TREC-4). In: TREC-4, pp 1--24.
• 14: Frederick Jelinek, Statistical methods for speech recognition, MIT Press, Cambridge, MA, 1998
• 15: Katz, S. M. 1987. Estimation of probabilities from sparse data for other language component of a speech recognizer. In: IEEE transactions on Acoustics, Speech and Signal Processing, 35(3): 400--401.
• 16: David D. Lewis, Naive (Bayes) at Forty: The Independence Assumption in Information Retrieval, Proceedings of the 10th European Conference on Machine Learning, p.4-15, April 21-23, 1998
• 17: Robert M. Losee, Jr., Term dependence: truncating the Bahadur Lazarsfeld expansion, Information Processing and Management: an International Journal, v.30 n.2, p.293-303, March-April 1994 [doi>10.1016/0306-4573(94)90071-X]
• 18: Jones, K. S., S. Walker and S. Robertson. 1998. A probabilistic model of information retrieval: development and status. Technical Report TR-446, Cambridge University Computer Laboratory.
• 19: Katz, S. M. 1987. Estimation of probabilities from sparse data for other language component of a speech recognizer. In: IEEE transactions on Acoustics, Speech and Signal Processing, 35(3): 400--401.
• 20: Lafferty, J., Sleator, D. and Temperley, D. 1992. Grammatical trigrams: a probabilistic model of link grammar. In: Proc. of the 1992 AAAI Fall Symposium on Probabilistic Approaches to Natural Language.
• 21: 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]
• 22: David R. H. Miller , Tim Leek , Richard M. Schwartz, A hidden Markov model information retrieval system, Proceedings of the 22nd annual international ACM SIGIR conference on Research and development in information retrieval, p.214-221, August 15-19, 1999, Berkeley, California, United States [doi>10.1145/312624.312680]
• 23: Ramesh Nallapati , James Allan, Capturing term dependencies using a language model based on sentence trees, Proceedings of the eleventh international conference on Information and knowledge management, November 04-09, 2002, McLean, Virginia, USA [doi>10.1145/584792.584855]
• 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: 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
• 26: Robertson, S. E. and Walker, S. 2000. Microsoft Cambridge at TREC-9: Filtering track. In: TREC-9, pp. 361--368.
• 27: Fei Song , W. Bruce Croft, A general language model for information retrieval, Proceedings of the eighth international conference on Information and knowledge management, p.316-321, November 02-06, 1999, Kansas City, Missouri, United States [doi>10.1145/319950.320022]
• 28: Sparck Jones, K. 1998. What is the role of NLP in text retrieval? In: Naturnal language information retrieval (Ed. T. Strzalkowski), Dordrecht: Kluwer.
• 29: 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]
• 30: van Rijsbergen, C. J. 1977. A theoretical basis for the use of co-occurrence data in information retrieval. In: Journal of Documentation, 33(2): 106--119.
• 31: Jinxi Xu , W. Bruce Croft, Improving the effectiveness of information retrieval with local context analysis, ACM Transactions on Information Systems (TOIS), v.18 n.1, p.79-112, Jan. 2000 [doi>10.1145/333135.333138]
• 32: Deniz Yuret , Patrick H. Winston, Discovery of linguistic relations using lexical attraction, 1998
• 33: ChengXiang Zhai , John Lafferty, Two-stage language models for information 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.564387]

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, Measurement, Theory

Keywords:
dependence, information retrieval, language model, parser