nach oben

Discover Computing

Erschienen in:

01.08.2009

Re-ranking search results using language models of query-specific clusters

verfasst von: Oren Kurland

Erschienen in: Discover Computing | Ausgabe 4/2009

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

To obtain high precision at top ranks by a search performed in response to a query, researchers have proposed a cluster-based re-ranking paradigm: clustering an initial list of documents that are the most highly ranked by some initial search, and using information induced from these (often called) query-specific clusters for re-ranking the list. However, results concerning the effectiveness of various automatic cluster-based re-ranking methods have been inconclusive. We show that using query-specific clusters for automatic re-ranking of top-retrieved documents is effective with several methods in which clusters play different roles, among which is the smoothing of document language models. We do so by adapting previously-proposed cluster-based retrieval approaches, which are based on (static) query-independent clusters for ranking all documents in a corpus, to the re-ranking setting wherein clusters are query-specific. The best performing method that we develop outperforms both the initial document-based ranking and some previously proposed cluster-based re-ranking approaches; furthermore, this algorithm consistently outperforms a state-of-the-art pseudo-feedback-based approach. In further exploration we study the performance of cluster-based smoothing methods for re-ranking with various (soft and hard) clustering algorithms, and demonstrate the importance of clusters in providing context from the initial list through a comparison to using single documents to this end.

Nächster Artikel A comparison of extrinsic clustering evaluation metrics based on formal constraints

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Some other work uses these language-model-based estimates for forming links between textual items and utilizing them with graph-based methods (Kurland and Lee 2005, 2006). We discuss the relation of our methods to these approaches in Sects. 3 and 4.

Such a constraint can potentially alleviate the computational cost of estimating the document-cluster association strength for all available clusters and documents; this cost is significant when using, for example, static overlapping clusters (Kurland and Lee 2004). An implicit assumption underlying this constraint is that the best clusters to use for representing a document are those that contain it. We return to this point later on.

The aspect-based models were originally termed “aspect-x” (Kurland and Lee 2004).

The original name of this algorithm was interpolation (Kurland and Lee 2004).

We hasten to point out that the models in Liu and Croft (2004) and Wei and Croft (2006) operate at the term-level, that is, interpolation is performed upon estimates of term probabilities. In contrast, interpolation-t operates at the score level by fusion of language-model-based similarity scores.

If two different parameter settings yield the same prec@5, we choose the one minimizing prec@10 so as to provide conservative estimates of expected performance. Similarly, in case of ties for both prec@5 and prec@10, we choose the setting minimizing MRR.

The performance of CQL can be improved if different cluster representations are used (Liu and Croft 2006b, 2008), as is the case for some other cluster-based retrieval algorithms (Kurland and Domshlak 2008). However, experimenting with different cluster representations is out of the scope of this paper.

In its original form, the CBDM method works at the term level, in contrast to the interpolation-t algorithm that fuses language-model-based similarity scores.

The presented results for all clustering approaches are based on the optimization criterion that was described in Sect. 4.1.

A similar conclusion with respect to the superiority of clusters to documents for providing (query-independent) corpus context was made in Kurland et al. (2005).

Abdul-Jaleel, N., Allan, J., Croft, W. B., Diaz, F., Larkey, L., Li, X., Smucker, M. D., & Wade, C. (2004). UMASS at TREC 2004—novelty and hard. In Proceedings of the Thirteenth Text Retrieval Conference (TREC-13) (pp. 715–725).

Azzopardi, L., Girolami, M., & van Rijsbergen, K. (2004). Topic based language models for ad hoc information retrieval. In Proceedings of International Conference on Neural Networks and IEEE International Conference on Fuzzy Systems (pp. 3281–3286).

Baliński, J., & Daniłowicz, C. (2005). Re-ranking method based on inter-document distances. Information Processing and Management, 41(4), 759–775.MATHCrossRef

Blei, D. M., Ng, A. Y., & Jordan, M. I. (2003). Latent dirichlet allocation. Journal of Machine Learning Research, 3, 993–1022.MATHCrossRef

Buckley, C., Salton, G., Allan, J., & Singhal, A. (1994). Automatic query expansion using SMART: TREC3. In Proceedings of the Third Text Retrieval Conference (TREC-3) (pp. 69–80).

Connell, M., Feng, A., Kumaran, G., Raghavan, H., Shah, C., & Allan, J. (2004). UMass at TDT 2004. TDT2004 System Description.

Cover, T. M., & Thomas, J. A. (1991). Elements of Information Theory. Wiley series in telecommunications. Wiley-Interscience, New York.

Croft, W. B. (1980). A model of cluster searching based on classification. Information Systems, 5, 189–195.CrossRef

Croft, W. B. (1995). What do people want from information retrieval? D-Lib magazine.

Croft, W. B., & Lafferty, J. (Eds.). (2003). Language modeling for information retrieval. In No. 13 in Information Retrieval Book Series. Kluwer.

Cronen-Townsend, S., Zhou, Y., & Croft, W. B. (2004). A language modeling framework for selective query expansion. Tech. Rep. IR-338, Center for Intelligent Information Retrieval, University of Massachusetts.

Cutting, D. R., Karger, D. R., Pedersen, J. O., & Tukey, J. W. (June 1992). Scatter/Gather: A cluster-based approach to browsing large document collections. In 15th Annual International SIGIR (pp. 318–329). Denmark.

Daniłowicz, C., & Baliński, J. (2000). Document ranking based upon Markov chains. Information Processing and Management, 41(4), 759–775.

Diaz, F. (2005). Regularizing ad hoc retrieval scores. In Proceedings of the Fourteenth International Conference on Information and Knowledge Managment (CIKM) (pp. 672–679).

Diaz, F., & Metzler, D. (2006). Improving the estimation of relevance models using large external corpora. In Proceedings of SIGIR (pp. 154–161).

El-Hamdouchi, A., & Willett, P. (1986). Hierarchic document clustering using ward’s method. In Proceedings of SIGIR (pp. 149–156).

Griffiths, A., Luckhurst, H. C., & Willett, P. (1986). Using interdocument similarity information in document retrieval systems. Journal of the American Society for Information Science (JASIS), 37(1), 3–11, reprinted in K. S. Jones & P. Willett (Eds.), Readings in information retrieval (pp. 365–373), Morgan Kaufmann, 1997.

Hearst, M. A., & Pedersen, J. O. (1996). Reexamining the cluster hypothesis: Scatter/Gather on retrieval results. In Proceedings of SIGIR (pp. 76–84).

Hofmann, T., & Puzicha, J. (1998). Unsupervised learning from dyadic data. Tech. Rep. TR-98-042, International Computer Science Institute (ICSI).

Hu, X., Bandhakavi, S., & Zhai, C. (2003). Error analysis of difficult TREC topics. In Proceedings of SIGIR (pp. 407–408), poster.

Kleinberg, J. (1998). Authoritative sources in a hyperlinked environment. In Proceedings of the 9th ACM-SIAM Symposium on Discrete Algorithms (SODA) (pp. 668–677), extended version in Journal of the ACM, 46, 604–632, 1999.

Kurland, O. (2006). Inter-document similarities, language models, and ad hoc retrieval. Ph.D. thesis, Cornell University.

Kurland, O. (2008). The opposite of smoothing: A language model approach to ranking query-specific document clusters. In Proceedings of SIGIR.

Kurland, O., & Domshlak, C. (2008). A rank-aggregation approach to searching for optimal query-specific clusters. In Proceedings of SIGIR.

Kurland, O., & Lee, L. (2004). Corpus structure, language models, and ad hoc information retrieval. In Proceedings of SIGIR (pp. 194–201.

Kurland, O., & Lee, L. (2005). PageRank without hyperlinks: Structural re-ranking using links induced by language models. In Proceedings of SIGIR (pp. 306–313).

Kurland, O., & Lee, L. (2006). Respect my authority! HITS without hyperlinks utilizing cluster-based language models. In Proceedings of SIGIR (pp. 83–90).

Kurland, O., Lee, L., & Domshlak, C. (2005). Better than the real thing? Iterative pseudo-query processing using cluster-based language models. In Proceedings of SIGIR (pp. 19–26).

Lafferty, J. D., & Zhai, C. (2001). Document language models, query models, and risk minimization for information retrieval. In Proceedings of SIGIR (pp. 111–119).

Lavrenko, V., Allan, J., DeGuzman, E., LaFlamme, D., Pollard, V., & Thomas, S. (2002). Relevance models for topic detection and tracking. In Proceedings of the Human Language Technology Conference (HLT) (pp. 104–110).

Lavrenko, V., & Croft, W. B. (2001). Relevance-based language models. In Proceedings of SIGIR (pp. 120–127).

Lavrenko, V., & Croft, W. B. (2003). Relevance models in information retrieval. In W. B. Croft & J. Lafferty (Eds.), No. 13 in Information Retrieval Book Series (pp. 11–56).

Lee, K.-S., Park, Y.-C., & Choi, K.-S. (2001). Re-ranking model based on document clusters. Information Processing and Management, 37(1), 1–14.MATHCrossRef

Leuski, A. (2001). Evaluating document clustering for interactive information retrieval. In Proceedings of the Tenth International Conference on Information and Knowledge Managment (CIKM) (pp. 33–40).

Liu, X., & Croft, W. B. (2004). Cluster-based retrieval using language models. In Proceedings of SIGIR (pp. 186–193).

Liu, X., & Croft, W. B. (2006a). Experiments on retrieval of optimal clusters. Tech. Rep. IR-478, Center for Intelligent Information Retrieval (CIIR), University of Massachusetts.

Liu, X., & Croft, W. B. (2006b). Representing clusters for retrieval. In Proceedings of SIGIR (pp. 671–672), poster.

Liu, X., & Croft, W. B. (2008). Evaluating text representations for retrieval of the best group of documents. In Proceedings of ECIR (pp. 454–462).

Metzler, D., Diaz, F., Strohman, T., & Croft, W. B. (2005). Using mixtures of relevance models for query expansion. In Proceedings of the Fourteenth Text Retrieval Conference (TREC).

Ponte, J. M., & Croft, W. B. (1998). A language modeling approach to information retrieval. In Proceedings of SIGIR (pp. 275–281).

Porter, M. F. (1980). An algorithm for suffix stripping. Program, 14(3), 130–137, reprinted in K. S. Jones & P. Willett (Eds.), Readings in information retrieval, Morgan Kaufmann, 1997.

Preece, S. E. (1973). Clustering as an output option. In Proceedings of the American Society for Information Science (pp. 189–190).

Ruthven, I., & Lalmas, M. (2003). A survey on the use of relevance feedback for information access systems. Knowledge Engineering Review, 18(2), 95–145.CrossRef

Shah, C., & Croft, W. B. (2004). Evaluating high accuracy retrieval techniques. In Proceedings of SIGIR (pp. 2–9).

Song, F., & Croft, W. B. (1999). A general language model for information retrieval (poster abstract). In Proceedings of SIGIR (pp. 279–280).

Tao, T., Wang, X., Mei, Q., & Zhai, C. (2006). Language model information retrieval with document expansion. In Proceedings of HLT/NAACL (pp. 407–414).

Tombros, A., Villa, R., & van Rijsbergen, C. (2002). The effectiveness of query-specific hierarchic clustering in information retrieval. Information Processing and Management, 38(4), 559–582.MATHCrossRef

van Rijsbergen, C. J. (1979). Information retrieval (2nd ed.). Butterworths.

Voorhees, E. M. (2005). Overview of the TREC 2005 robust retrieval task. In Proceedings of the Fourteenth Text Retrieval Conference (TREC).

Voorhees, E. M., & Harman, D. K. (2005). TREC: Experiments and evlautaion in information retrieval. The MIT Press.

Wei, X., & Croft, W. B. (2006). LDA-based document models for ad-hoc retrieval. In Proceedings of SIGIR (pp. 178–185).

Willett, P. (1985). Query specific automatic document classification. International Forum on Information and Documentation, 10(2), 28–32.

Zamir, O., & Etzioni, O. (1998). Web document clustering: a feasibility demonstration. In Proceedings of SIGIR (pp. 46–54).

Zhai, C., & Lafferty, J. D. (2001). A study of smoothing methods for language models applied to ad hoc information retrieval. In Proceedings of SIGIR (pp. 334–342).

Zhang, B., Li, H., Liu, Y., Ji, L., Xi, W., Fan, W., Chen, Z., & Ma, W.-Y. (2005). Improving web search results using affinity graph. In Proceedings of SIGIR (pp. 504–511).

Titel: Re-ranking search results using language models of query-specific clusters
verfasst von: Oren Kurland
Publikationsdatum: 01.08.2009
Verlag: Springer Netherlands
Erschienen in: Discover Computing / Ausgabe 4/2009
Print ISSN: 2948-2984
Elektronische ISSN: 2948-2992
DOI: https://doi.org/10.1007/s10791-008-9065-9

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"