skip to main content
10.1145/1390334.1390438acmconferencesArticle/Chapter ViewAbstractPublication PagesirConference Proceedingsconference-collections
research-article

A general optimization framework for smoothing language models on graph structures

Published: 20 July 2008 Publication History

Abstract

Recent work on language models for information retrieval has shown that smoothing language models is crucial for achieving good retrieval performance. Many different effective smoothing methods have been proposed, which mostly implement various heuristics to exploit corpus structures. In this paper, we propose a general and unified optimization framework for smoothing language models on graph structures. This framework not only provides a unified formulation of the existing smoothing heuristics, but also serves as a road map for systematically exploring smoothing methods for language models. We follow this road map and derive several different instantiations of the framework. Some of the instantiations lead to novel smoothing methods. Empirical results show that all such instantiations are effective with some outperforming the state of the art smoothing methods.

References

[1]
M. Belkin and P. Niyogi. Laplacian eigenmaps for dimensionality reduction and data representation. Neural Comput., 15(6):1373--1396, 2003.
[2]
S. Brin and L. Page. The anatomy of a large-scale hypertextual web search engine. Comput. Netw. ISDN Syst., 30(1-7):107--117, 1998.
[3]
S. F. Chen and J. Goodman. An empirical study of smoothing techniques for language modeling. Technical Report TR-10-98, Harvard University, 1998.
[4]
K. W. Church and P. Hanks. Word association norms, mutual information, and lexicography. Comput. Linguist., 16(1):22--29, 1990.
[5]
W. B. Croft and J. Lafferty, editors. Language Modeling and Information Retrieval. Kluwer Academic Publishers, 2003.
[6]
F. Diaz. Regularizing ad hoc retrieval scores. In Proceedings of CIKM'05, pages 672--679, 2005.
[7]
D. Hiemstra and W. Kraaij. Twenty-one at TREC-7: Ad-hoc and cross-language track. In Proceedings of TREC 7, pages 227--238, 1998.
[8]
J. M. Kleinberg. Authoritative sources in a hyperlinked environment. J. ACM, 46(5):604--632.
[9]
O. Kurland and L. Lee. Corpus structure, language models, and ad hoc information retrieval. In Proceedings of SIGIR'04, pages 194--201.
[10]
O. Kurland and L. Lee. Pagerank without hyperlinks: structural re-ranking using links induced by language models. In Proceedings of SIGIR '05, pages 306--313.
[11]
O. Kurland and L. Lee. Respect my authority!: Hits without hyperlinks, utilizing cluster-based language models. In Proceedings of SIGIR '06, pages 83--90.
[12]
J. Lafferty and C. Zhai. Document language models, query models, and risk minimization for information retrieval. In Proceedings of SIGIR'01, pages 111--119.
[13]
V. Lavrenko and B. Croft. Relevance-based language models. In Proceedings of SIGIR'01, pages 120--127.
[14]
X. Liu and W. B. Croft. Cluster-based retrieval using language models. In Proceedings of SIGIR'04.
[15]
R. Mihalcea and D. R. Radev, editors. Textgraphs: Graph-based methods for NLP, 2006.
[16]
D. H. Miller, T. Leek, and R. Schwartz. A hidden Markov model information retrieval system. In Proceedings of SIGIR 1999, pages 214--221, 1999.
[17]
J. M. Ponte and W. B. Croft. A language modeling approach to information retrieval. In Proceedings of SIGIR 1998, pages 275--281, 1998.
[18]
T. Qin, T.-Y. Liu, X.-D. Zhang, Z. Chen, and W.-Y. Ma. A study of relevance propagation for web search. In Proceedings of SIGIR 2005, pages 408--415, 2005.
[19]
A. Shakery and C. Zhai. Smoothing document language models with probabilistic term count propagation. Information Retrieval, 11(2):139--164, 2008.
[20]
T. Tao, X. Wang, Q. Mei, and C. Zhai. Language model information retrieval with document expansion. In Proceedings of HLT/NAACL 2006, pages 407--414.
[21]
J. Xu and W. B. Croft. Cluster-based language models for distributed retrieval. In Proceedings of SIGIR'99, pages 254--261, 1999.
[22]
C. Zhai and J. Lafferty. A study of smoothing methods for language models applied to information retrieval. ACM Transactions on Information Systems.
[23]
C. Zhai and J. Lafferty. Model-based feedback in the language modeling approach to information retrieval. In Proceedings of CIKM'01, pages 403--410, 2001.
[24]
C. Zhai and J. Lafferty. A study of smoothing methods for language models applied to ad hoc information retrieval. In Proceedings of ACM SIGIR'01, pages 334--342, Sept 2001.
[25]
D. Zhou, O. Bousquet, T. N. Lal, J. Weston, and B. Schölkopf. Learning with local and global consistency. In NIPS, 2004.
[26]
D. Zhou and B. Schölkopf. Discrete regularization. Semi-supervised learning, pages 221--232, 2006.
[27]
X. Zhu, Z. Ghahramani, and J. D. Lafferty. Semi-supervised learning using gaussian fields and harmonic functions. In ICML, pages 912--919, 2003.

Cited By

View all
  • (2024)Building Shortcuts between Distant Nodes with Biaffine Mapping for Graph Convolutional NetworksACM Transactions on Knowledge Discovery from Data10.1145/365011318:6(1-21)Online publication date: 12-Apr-2024
  • (2024)A Dual-channel Semi-supervised Learning Framework on Graphs via Knowledge Transfer and Meta-learningACM Transactions on the Web10.1145/357703318:2(1-26)Online publication date: 8-Jan-2024
  • (2023)Graph-Based Semi-Supervised Learning: A Comprehensive ReviewIEEE Transactions on Neural Networks and Learning Systems10.1109/TNNLS.2022.315547834:11(8174-8194)Online publication date: Nov-2023
  • Show More Cited By

Index Terms

  1. A general optimization framework for smoothing language models on graph structures

    Recommendations

    Comments

    Information & Contributors

    Information

    Published In

    cover image ACM Conferences
    SIGIR '08: Proceedings of the 31st annual international ACM SIGIR conference on Research and development in information retrieval
    July 2008
    934 pages
    ISBN:9781605581644
    DOI:10.1145/1390334
    Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

    Sponsors

    Publisher

    Association for Computing Machinery

    New York, NY, United States

    Publication History

    Published: 20 July 2008

    Permissions

    Request permissions for this article.

    Check for updates

    Author Tags

    1. Language modeling
    2. document and word graph
    3. graph structure
    4. smoothing

    Qualifiers

    • Research-article

    Conference

    SIGIR '08
    Sponsor:

    Acceptance Rates

    Overall Acceptance Rate 792 of 3,983 submissions, 20%

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)7
    • Downloads (Last 6 weeks)2
    Reflects downloads up to 27 Jan 2025

    Other Metrics

    Citations

    Cited By

    View all
    • (2024)Building Shortcuts between Distant Nodes with Biaffine Mapping for Graph Convolutional NetworksACM Transactions on Knowledge Discovery from Data10.1145/365011318:6(1-21)Online publication date: 12-Apr-2024
    • (2024)A Dual-channel Semi-supervised Learning Framework on Graphs via Knowledge Transfer and Meta-learningACM Transactions on the Web10.1145/357703318:2(1-26)Online publication date: 8-Jan-2024
    • (2023)Graph-Based Semi-Supervised Learning: A Comprehensive ReviewIEEE Transactions on Neural Networks and Learning Systems10.1109/TNNLS.2022.315547834:11(8174-8194)Online publication date: Nov-2023
    • (2021)Directed probabilistic watershedProceedings of the 35th International Conference on Neural Information Processing Systems10.5555/3540261.3541797(20076-20088)Online publication date: 6-Dec-2021
    • (2021)Time segment language model for microblog retrievalNeural Computing and Applications10.1007/s00521-020-05534-xOnline publication date: 3-Jan-2021
    • (2020)Graph random neural networks for semi-supervised learning on graphsProceedings of the 34th International Conference on Neural Information Processing Systems10.5555/3495724.3497577(22092-22103)Online publication date: 6-Dec-2020
    • (2019)A flexible generative framework for graph-based semi-supervised learningProceedings of the 33rd International Conference on Neural Information Processing Systems10.5555/3454287.3454582(3281-3290)Online publication date: 8-Dec-2019
    • (2018)Entity-Based Language Model Smoothing Approach for Smart SearchIEEE Access10.1109/ACCESS.2017.27884176(9991-10002)Online publication date: 2018
    • (2016)Socialized Language Model Smoothing via Bi-directional Influence Propagation on Social NetworksProceedings of the 25th International Conference on World Wide Web10.1145/2872427.2874811(1395-1406)Online publication date: 11-Apr-2016
    • (2016)A Two-Stage Ranking Scheme for Pseudo Relevance Feedback2016 3rd International Conference on Information Science and Control Engineering (ICISCE)10.1109/ICISCE.2016.38(129-133)Online publication date: Jul-2016
    • Show More Cited By

    View Options

    Login options

    View options

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    Figures

    Tables

    Media

    Share

    Share

    Share this Publication link

    Share on social media