Clusters, language models, and ad hoc information retrieval

ABSTRACT

The language-modeling approach to information retrieval provides an effective statistical framework for tackling various problems and often achieves impressive empirical performance. However, most previous work on language models for information retrieval focused on document-specific characteristics, and therefore did not take into account the structure of the surrounding corpus, a potentially rich source of additional information. We propose a novel algorithmic framework in which information provided by document-based language models is enhanced by the incorporation of information drawn from clusters of similar documents. Using this framework, we develop a suite of new algorithms. Even the simplest typically outperforms the standard language-modeling approach in terms of mean average precision (MAP) and recall, and our new interpolation algorithm posts statistically significant performance improvements for both metrics over all six corpora tested. An important aspect of our work is the way we model corpus structure. In contrast to most previous work on cluster-based retrieval that partitions the corpus, we demonstrate the effectiveness of a simple strategy based on a nearest-neighbors approach that produces overlapping clusters.

REFERENCES

• 1: Abdul-Jaleel, N., Allan, J., Croft, W. B., Diaz, F., Larkey, L., Li, X., Smucker, M. D., and Wade, C. 2004. UMASS at TREC 2004—novelty and hard. In Proceedings of the 13th Text Retrieval Conference (TREC-13).
• 2: Allan, J., Connell, M. E., Croft, W. B., Feng, F.-F., Fisher, D., and Li, X. 2000. INQUERY and TREC-9. In Proceedings of the 9th Text Retrieval Conference (TREC-9). 551--562. NIST Special Publication 500-249. National Institute of Science and Technology, Gaithersburg, MD.
• 3: Azzopardi, L., Girolami, M., and van Rijsbergen, K. 2004. Topic based language models for ad hoc information retrieval. In Proceedings of the International Conference on Neural Networks and IEEE International Conference on Fuzzy Systems. 3281--3286.
• 4: Jaroslaw Baliński , Czeslaw Daniłowicz, Re-ranking method based on inter-document distances, Information Processing and Management: an International Journal, v.41 n.4, p.759-775, July 2005 [doi>10.1016/j.ipm.2004.01.006]
• 5: David M. Blei , Andrew Y. Ng , Michael I. Jordan, Latent dirichlet allocation, The Journal of Machine Learning Research, 3, p.993-1022, 3/1/2003 [doi>10.1162/jmlr.2003.3.4-5.993]
• 6: Peter F. Brown , Peter V. deSouza , Robert L. Mercer , Vincent J. Della Pietra , Jenifer C. Lai, Class-based n-gram models of natural language, Computational Linguistics, v.18 n.4, p.467-479, December 1992
• 7: Connell, M., Feng, A., Kumaran, G., Raghavan, H., Shah, C., and Allan, J. 2004. UMass at TDT 2004. TDT2004 System Description. In Proceedings of IDT 2004.
• 8: Croft, W. B. 1980. A model of cluster searching based on classification. Inform. Syst. 5, 189--195.
• 9: W. Bruce Croft , John Lafferty, Language Modeling for Information Retrieval, Kluwer Academic Publishers, Norwell, MA, 2003
• 10: Cronen-Townsend, S., Zhou, Y., and Croft, W. B. 2004. A language modeling framework for selective query expansion. Tech. rep. IR-338, Center for Intelligent Information Retrieval, University of Massachusetts, Amherst, MA.
• 11: Danilowicz, C. and Baliński, J. 2000. Document ranking based upon Markov chains. Inform. Process. Manage. 41, 4, 759--775.
• 12: Fernando Diaz, Regularizing ad hoc retrieval scores, Proceedings of the 14th ACM international conference on Information and knowledge management, October 31-November 05, 2005, Bremen, Germany [doi>10.1145/1099554.1099722]
• 13: Fernando Diaz, Regularizing query-based retrieval scores, Information Retrieval, v.10 n.6, p.531-562, December 2007 [doi>10.1007/s10791-007-9034-8]
• 14: Fernando Diaz , Donald Metzler, Improving the estimation of relevance models using large external corpora, 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.1148200]
• 15: P. Willett , A. El-Hamdouchi, Comparison of hierarchic agglomerative clustering methods for document retrieval, The Computer Journal, v.32 n.3, p.220-227, June 1989 [doi>10.1093/comjnl/32.3.220]
• 16: Alan Griffiths , H. Clair Luckhurst , Peter Willett, Using interdocument similarity information in document retrieval systems, Readings in information retrieval, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1997
• 17: Marti A. Hearst , Jan O. Pedersen, Reexamining the cluster hypothesis: scatter/gather on retrieval results, Proceedings of the 19th annual international ACM SIGIR conference on Research and development in information retrieval, p.76-84, August 18-22, 1996, Zurich, Switzerland [doi>10.1145/243199.243216]
• 18: Hiemstra, D. and Kraaij, W. 1999. Twenty-One at TREC7: Ad hoc and cross-language track. In Proceedings of the 7th Text Retrieval Conference (TREC-7). 227--238.
• 19: Thomas Hofmann, Unsupervised learning by probabilistic latent semantic analysis, Machine Learning, v.42 n.1/2, p.177-196, Jan. 2001 [doi>10.1023/A:1007617005950]
• 20: Hofmann, T. and Puzicha, J. 1998. Unsupervised learning from dyadic data. Tech. rep. TR-98-042. International Computer Science Institute (ICSI), Berkely, CA.
• 21: Xiao Hu , Sindhura Bandhakavi , Chengxiang Zhai, Error analysis of difficult TREC topics, 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.860524]
• 22: Indyk, P. 2004. Nearest neighbors in high-dimensional spaces, In Handbook of Discrete and Computational Geometry, 2nd ed., J. E. Goodman and J. O'Rourke, Eds. CRC Press, Boca Raton, FL, Chapter 39.
• 23: Iyer, R. and Ostendorf, M. 1999. Modeling long distance dependence in language: Topic mixtures vs. dynamic cache models. IEEE Trans. Speech Audio Process. 7, 1, 30--39.
• 24: Jardine, N. and van Rijsbergen, C. J. 1971. The use of hierarchic clustering in information retrieval. Inform. Stor. Retr. 7, 5, 217--240.
• 25: Jelinek, F. and Mercer, R. L. 1980. Interpolated estimation of Markov source parameters from sparse data. In Proceedings of the Workshop on Pattern Recognition in Practice. North-Holland, Amsterdam, The Netherlands, 381--397.
• 26: Kraaij, W. and Spitters, M. 2003. Language models for topic tracking: The importance of score normalization. In Language Modeling for Information Retrieval, W. B. Croft and J. Lafferty Eds., Kluwer, Norwell, MA, Chapter 5, 95--124.
• 27: Oren Kurland , Lillian Lee, Inter-document similarities, language models, and ad hoc information retrieval, Cornell University, Ithaca, NY, 2006
• 28: Oren Kurland , Lillian Lee, Corpus structure, language models, and ad hoc 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.1009027]
• 29: Oren Kurland , Lillian Lee, PageRank without hyperlinks: structural re-ranking using links induced by language models, 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.1076087]
• 30: Oren Kurland , Lillian Lee, Respect my authority!: HITS without hyperlinks, utilizing cluster-based language models, 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.1148188]
• 31: Oren Kurland , Lillian Lee , Carmel Domshlak, Better than the real thing?: iterative pseudo-query processing using cluster-based language models, 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.1076041]
• 32: 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]
• 33: Lavrenko, V. 2000. Localized smoothing of multinomial language models. Tech. rep. IR-222. Center for Intelligent Information Retrieval (CIIR), University of Massachusetts, Amherst, MA.
• 34: Victor Lavrenko, Optimal Mixture Models in IR, Proceedings of the 24th BCS-IRSG European Colloquium on IR Research: Advances in Information Retrieval, p.193-212, March 25-27, 2002
• 35: Victor Lavrenko , James Allan , Edward DeGuzman , Daniel LaFlamme , Veera Pollard , Stephen Thomas, Relevance models for topic detection and tracking, Proceedings of the second international conference on Human Language Technology Research, March 24-27, 2002, San Diego, California
• 36: 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]
• 37: Lavrenko, V. and Croft, W. B. 2003. Relevance models in information retrieval. In Language Modeling for Information Retrieval, W. B. Croft and J. Lafferty Eds., Kluwer, Norwell, MA, 11--56.
• 38: Anton Leuski, Evaluating document clustering for interactive information retrieval, Proceedings of the tenth international conference on Information and knowledge management, October 05-10, 2001, Atlanta, Georgia, USA [doi>10.1145/502585.502592]
• 39: 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]
• 40: Xiaoyong Liu , W. Bruce Croft, Cluster-based retrieval using language models, 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.1009026]
• 41: Xiaoyong Liu , W. Bruce Croft, Representing clusters for retrieval, 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.1148310]
• 42: Metzler, D. 2005. Direct maximization of rank-based metrics. Tech. rep. IR-338425. Center for Intelligent Information Retrieval, University of Massachusetts, Amherst, MA.
• 43: 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]
• 44: Metzler, D., Diaz, F., Strohman, T., and Croft, W. B. 2005. Using mixtures of relevance models for query expansion. In Proceedings of the 14th Text Retrieval Conference. (TREC)
• 45: 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]
• 46: Mandar Mitra , Amit Singhal , Chris Buckley, Improving automatic query expansion, Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval, p.206-214, August 24-28, 1998, Melbourne, Australia [doi>10.1145/290941.290995]
• 47: Morgan, W., Greiff, W., and Henderson, J. 2004. Direct maximization of average precision by hill-climbing, with a comparison to a maximum entropy approach. Tech. rep. 04-0367. The MITRE Corporation, Beckford, MA/McLean, VA.
• 48: Ng, K. 2000. A maximum likelihood ratio information retrieval model. In Proceedings of the 8th Text Retrieval Conference (TREC-8). 483--492.
• 49: Ogilvie, P. 2000. Nearest neighbor smoothing of language models in IR. Unpublished. http://www.cs.cmu.edu/People/pto/courses/11-743/nnlmsmooth.ps.
• 50: Fernando Pereira , Naftali Tishby , Lillian Lee, Distributional clustering of English words, Proceedings of the 31st annual meeting on Association for Computational Linguistics, p.183-190, June 22-26, 1993, Columbus, Ohio [doi>10.3115/981574.981598]
• 51: 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]
• 52: Rocchio, J. J. 1971. Relevance feedback in information retrieval. In The SMART Retrieval System: Experiments in Automatic Document Processing, G. Salton, Ed. Prentice Hall, Englewood Cliffs, NJ, 313--323.
• 53: Ian Ruthven , Mounia Lalmas, A survey on the use of relevance feedback for information access systems, The Knowledge Engineering Review, v.18 n.2, p.95-145, June 2003 [doi>10.1017/S0269888903000638]
• 54: Amit Singhal , Fernando Pereira, Document expansion for speech retrieval, Proceedings of the 22nd annual international ACM SIGIR conference on Research and development in information retrieval, p.34-41, August 15-19, 1999, Berkeley, California, United States [doi>10.1145/312624.312645]
• 55: Fei Song , W. Bruce Croft, A general language model for information retrieval (poster abstract), Proceedings of the 22nd annual international ACM SIGIR conference on Research and development in information retrieval, p.279-280, August 15-19, 1999, Berkeley, California, United States [doi>10.1145/312624.312698]
• 56: Spitters, M. and Kraaij, W. 2001. TNO at TDT2001: Language model-based topic detection. In Proceedings of the Topic Detection and Tracking TDT Workshop.
• 57: Tao Tao , Xuanhui Wang , Qiaozhu Mei , ChengXiang Zhai, Language model information retrieval with document expansion, Proceedings of the main conference on Human Language Technology Conference of the North American Chapter of the Association of Computational Linguistics, p.407-414, June 04-09, 2006, New York, New York [doi>10.3115/1220835.1220887]
• 58: Anastasios Tombros , Robert Villa , C. J. Van Rijsbergen, The effectiveness of query-specific hierarchic clustering in information retrieval, Information Processing and Management: an International Journal, v.38 n.4, p.559-582, July 2002 [doi>10.1016/S0306-4573(01)00048-6]
• 59: C. J. Van Rijsbergen, Information Retrieval, Butterworth-Heinemann, Newton, MA, 1979
• 60: Ellen M. Voorhees, The cluster hypothesis revisited, Proceedings of the 8th annual international ACM SIGIR conference on Research and development in information retrieval, p.188-196, June 05-07, 1985, Montreal, Quebec, Canada [doi>10.1145/253495.253524]
• 61: Xing Wei , W. Bruce Croft, LDA-based document models for ad-hoc retrieval, 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.1148204]
• 62: Willett, P. 1985. Query specific automatic document classification. Int. For. Inform. Documentat. 10, 2, 28--32.
• 63: Jinxi Xu , W. Bruce Croft, Cluster-based language models for distributed retrieval, Proceedings of the 22nd annual international ACM SIGIR conference on Research and development in information retrieval, p.254-261, August 15-19, 1999, Berkeley, California, United States [doi>10.1145/312624.312687]
• 64: 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]
• 65: 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]
• 66: Justin Zobel , Alistair Moffat, Exploring the similarity space, ACM SIGIR Forum, v.32 n.1, p.18-34, Spring 1998 [doi>10.1145/281250.281256]

INDEX TERMS

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

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Retrieval models

General Terms:
Algorithms, Experimentation

Keywords:
Language modeling, aspect models, cluster hypothesis, cluster-based language models, clustering, interpolation model, smoothing