A Markov random field model for term dependencies

ABSTRACT

This paper develops a general, formal framework for modeling term dependencies via Markov random fields. The model allows for arbitrary text features to be incorporated as evidence. In particular, we make use of features based on occurrences of single terms, ordered phrases, and unordered phrases. We explore full independence, sequential dependence, and full dependence variants of the model. A novel approach is developed to train the model that directly maximizes the mean average precision rather than maximizing the likelihood of the training data. Ad hoc retrieval experiments are presented on several newswire and web collections, including the GOV2 collection used at the TREC 2004 Terabyte Track. The results show significant improvements are possible by modeling dependencies, especially on the larger web collections.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked 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	W. Bruce Croft , Howard R. Turtle , David D. Lewis, The use of phrases and structured queries in information retrieval, Proceedings of the 14th annual international ACM SIGIR conference on Research and development in information retrieval, p.32-45, October 13-16, 1991, Chicago, Illinois, United States [doi>10.1145/122860.122864]
	3	J. Fagan, Automatic phrase indexing for document retrieval, Proceedings of the 10th annual international ACM SIGIR conference on Research and development in information retrieval, p.91-101, June 03-05, 1987, New Orleans, Louisiana, United States [doi>10.1145/42005.42016]
	4	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]
	5	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]
	6	Thorsten Joachims, Optimizing search engines using clickthrough data, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada [doi>10.1145/775047.775067]
	7	John D. Lafferty , Andrew McCallum , Fernando C. N. Pereira, Conditional Random Fields: Probabilistic Models for Segmenting and Labeling Sequence Data, Proceedings of the Eighteenth International Conference on Machine Learning, p.282-289, June 28-July 01, 2001
	8	Victor Lavrenko , W. Bruce Croft , James Allan, A generative theory of relevance, University of Massachusetts Amherst, 2004
	9	D. Metzler. Direct maximization of rank-based metrics. Technical report, University of Massachusetts, Amherst, 2005.
	10	Donald Metzler , W. Bruce Croft, Combining the language model and inference network approaches to retrieval, Information Processing and Management: an International Journal, v.40 n.5, p.735-750, September 2004 [doi>10.1016/j.ipm.2004.05.001]
	11	D. Metzler, T. Strohman, H. Turtle, and W. B. Croft. Indri at terabyte track 2004. In Text REtrieval Conference (TREC 2004), 2004.
	12	G. Mishne and M. de Rijke. Boosting web retrieval through query operations. In Proc. 27th European Conf. on Information Retrieval, pages 502--516, 2005.
	13	W. Morgan, W. Greiff, and J. Henderson. Direct maximization of average precision by hill-climbing with a comparison to a maximum entropy approach. Technical report, MITRE, 2004.
	14	Ramesh Nallapati, Discriminative models 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.1009006]
	15	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]
	16	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]
	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	S. Robertson. The probability ranking principle in IR. Journal of Documentation, 33(4):294--303, 1977.
	19	Gerard Salton , Christopher Buckley, Term-weighting approaches in automatic text retrieval, Information Processing and Management: an International Journal, v.24 n.5, p.513-523, 1988 [doi>10.1016/0306-4573(88)90021-0]
	20	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]
	21	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]
	22	B. Taskar, C. Guestrin, and D. Koller. Max-margin markov networks. In Proc. of Advances in Neural Information Processing Systems (NIPS 2003), 2003.
	23	Howard Turtle , W. Bruce Croft, Evaluation of an inference network-based retrieval model, ACM Transactions on Information Systems (TOIS), v.9 n.3, p.187-222, July 1991 [doi>10.1145/125187.125188]
	24	C. J. van Rijsbergen. A theoretical basis for the use of cooccurrence data in information retrieval. Journal of Documentation, 33(2):106--119, 1977.
	25	C. T. Yu , Chris Buckley , K. Lam , Gerard Salton, A Generalized Term Dependence Model in Information Retrieval, Cornell University, Ithaca, NY, 1983
	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]