The opposite of smoothing: a language model approach to ranking query-specific document clusters

ABSTRACT

Exploiting information induced from (query-specific) clustering of top-retrieved documents has long been proposed as means for improving precision at the very top ranks of the returned results. We present a novel language model approach to ranking query-specific clusters by the presumed percentage of relevant documents that they contain. While most previous cluster ranking approaches focus on the cluster as a whole, our model also exploits information induced from documents associated with the cluster. Our model substantially outperforms previous approaches for identifying clusters containing a high relevant-document percentage. Furthermore, using the model to produce document ranking yields precision-at-top-ranks performance that is consistently better than that of the initial ranking upon which clustering is performed; the performance also favorably compares with that of a state-of-the-art pseudo-feedback retrieval method.

REFERENCES

• 1: N. Abdul-Jaleel, J. Allan, W. B. Croft, F. Diaz, L. Larkey, X. Li, M. D. Smucker, and C. Wade. UMASS at TREC 2004 - novelty and hard. In Proceedings of the Thirteenth Text Retrieval Conference (TREC-13), 2004.
• 2: L. Azzopardi, M. Girolami, and K. van Rijsbergen. Topic based language models for ad hoc information retrieval. In Proceedings of International Conference on Neural Networks and IEEE International Conference on Fuzzy Systems, pages 3281--3286, 2004.
• 3: Sergey Brin , Lawrence Page, The anatomy of a large-scale hypertextual Web search engine, Proceedings of the seventh international conference on World Wide Web 7, p.107-117, April 1998, Brisbane, Australia
• 4: C. Buckley, G. Salton, J. Allan, and A. Singhal. Automatic query expansion using SMART: TREC3. In Proceedings of the Third Text Retrieval Conference (TREC-3), pages 69--80, 1994.
• 5: http://www.clusty.com.
• 6: M. Connell, A. Feng, G. Kumaran, H. Raghavan, C. Shah, and J. Allan. UMass at TDT 2004. TDT2004 System Description, 2004.
• 7: W. B. Croft. A model of cluster searching based on classification. Information Systems, 5:189--195, 1980.
• 8: W. Bruce Croft , John Lafferty, Language Modeling for Information Retrieval, Kluwer Academic Publishers, Norwell, MA, 2003
• 9: 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]
• 10: 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]
• 11: F. Geraci, M. Pellegrini, M. Maggini, and F. Sebastiani. Cluster generation and cluster labeling for Web snippets: A fast and accurate hierarchical solution. In Proceedings of the 13th international conference on string processing and information retrieval (SPIRE), pages 25--37, 2006.
• 12: G. H. Golub and C. F. Van Loan. Matrix Computations. The Johns Hopkins University Press, third edition, 1996.
• 13: A. Griffiths, H. C. Luckhurst, and P. Willett. Using interdocument similarity information in document retrieval systems. Journal of the American Society for Information Science (JASIS), 37(1):3--11, 1986. Reprinted in Karen Sparck Jones and Peter Willett, eds., Readings in Information Retrieval, Morgan Kaufmann, pp. 365--373, 1997.
• 14: 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]
• 15: N. Jardine and C. J. van Rijsbergen. The use of hierarchic clustering in information retrieval. Information Storage and Retrieval, 7(5):217--240, 1971.
• 16: J. Kleinberg. Authoritative sources in a hyperlinked environment. Technical Report Research Report RJ 10076, IBM, May 1997.
• 17: Oren Kurland , Lillian Lee, Inter-document similarities, language models, and ad hoc information retrieval, Cornell University, Ithaca, NY, 2006
• 18: Oren Kurland , Carmel Domshlak, A rank-aggregation approach to searching for optimal query-specific clusters, 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.1390428]
• 19: 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]
• 20: 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]
• 21: 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]
• 22: 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]
• 23: 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]
• 24: 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
• 25: 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]
• 26: V. Lavrenko and W. B. Croft. Relevance models in information retrieval. In Croft and Lafferty {8}, pages 11--56.
• 27: 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]
• 28: Anton Leouski , James Allan, Evaluating a Visual Navigation System for a Digital Library, Proceedings of the Second European Conference on Research and Advanced Technology for Digital Libraries, p.535-554, September 21-23, 1998
• 29: 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]
• 30: X. Liu and W. B. Croft. Experiments on retrieval of optimal clusters. Technical Report IR-478, Center for Intelligent Information Retrieval (CIIR), University of Massachusetts, 2006.
• 31: 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]
• 32: Qiaozhu Mei , Xuehua Shen , ChengXiang Zhai, Automatic labeling of multinomial topic models, Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, August 12-15, 2007, San Jose, California, USA [doi>10.1145/1281192.1281246]
• 33: C. R. Palmer , J. Pesenti , R. E. Valdes-Perez , M. G. Christel , A. G. Hauptmann , D. Ng , H. D. Wactlar, Demonstration of hierarchical document clustering of digital library retrieval results, Proceedings of the 1st ACM/IEEE-CS joint conference on Digital libraries, p.451, January 2001, Roanoke, Virginia, United States [doi>10.1145/379437.379770]
• 34: 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]
• 35: S. E. Preece. Clustering as an output option. In Proceedings of the American Society for Information Science, pages 189--190, 1973.
• 36: J. G. Shanahan, J. Bennett, D. A. Evans, D. A. Hull, and J. Montgomery. Clairvoyance Corporation experiments in the TREC 2003. High accuracy retrieval from documents (HARD) track. In Proceedings of the Twelfth Text Retrieval Conference (TREC-12), pages 152--160, 2003.
• 37: Luo Si , Rong Jin , Jamie Callan , Paul Ogilvie, A language modeling framework for resource selection and results merging, Proceedings of the eleventh international conference on Information and knowledge management, November 04-09, 2002, McLean, Virginia, USA [doi>10.1145/584792.584856]
• 38: 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]
• 39: Pucktada Treeratpituk , Jamie Callan, Automatically labeling hierarchical clusters, Proceedings of the 2006 international conference on Digital government research, May 21-24, 2006, San Diego, California [doi>10.1145/1146598.1146650]
• 40: C. J. Van Rijsbergen, Information Retrieval, Butterworth-Heinemann, Newton, MA, 1979
• 41: 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]
• 42: 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]
• 43: P. Willett. Query specific automatic document classification. International Forum on Information and Documentation, 10(2):28--32, 1985.
• 44: Jinxi Xu , W. Bruce Croft, Query expansion using local and global document analysis, Proceedings of the 19th annual international ACM SIGIR conference on Research and development in information retrieval, p.4-11, August 18-22, 1996, Zurich, Switzerland [doi>10.1145/243199.243202]
• 45: Oren Zamir , Oren Etzioni, Web document clustering: a feasibility demonstration, Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval, p.46-54, August 24-28, 1998, Melbourne, Australia [doi>10.1145/290941.290956]
• 46: 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

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

General Terms:
Algorithms, Experimentation

Keywords:
ad hoc retrieval, cluster-based language models, cluster-ranking, language models, query-specific clusters