Improving probabilistic inference in graphical models with determinism and cycles.
Saved in:
| Title: | Improving probabilistic inference in graphical models with determinism and cycles. |
|---|---|
| Authors: | Ibrahim, Mohamed-Hamza1 mohamed.ibrahim@polymtl.ca, Pal, Christopher1 christopher.pal@polymtl.ca, Pesant, Gilles1 gilles.pesant@polymtl.ca |
| Source: | Machine Learning. Jan2017, Vol. 106 Issue 1, p1-54. 54p. |
| Subjects: | Probabilistic inference, Determinism (Physics), Graphic methods, Algorithms, Constraint programming, Gibbs sampling |
| Abstract: | Many important real-world applications of machine learning, statistical physics, constraint programming and information theory can be formulated using graphical models that involve determinism and cycles. Accurate and efficient inference and training of such graphical models remains a key challenge. Markov logic networks (MLNs) have recently emerged as a popular framework for expressing a number of problems which exhibit these properties. While loopy belief propagation (LBP) can be an effective solution in some cases; unfortunately, when both determinism and cycles are present, LBP frequently fails to converge or converges to inaccurate results. As such, sampling based algorithms have been found to be more effective and are more popular for general inference tasks in MLNs. In this paper, we introduce Generalized arc-consistency Expectation Maximization Message-Passing (GEM-MP), a novel message-passing approach to inference in an extended factor graph that combines constraint programming techniques with variational methods. We focus our experiments on Markov logic and Ising models but the method is applicable to graphical models in general. In contrast to LBP, GEM-MP formulates the message-passing structure as steps of variational expectation maximization. Moreover, in the algorithm we leverage the local structures in the factor graph by using generalized arc consistency when performing a variational mean-field approximation. Thus each such update increases a lower bound on the model evidence. Our experiments on Ising grids, entity resolution and link prediction problems demonstrate the accuracy and convergence of GEM-MP over existing state-of-the-art inference algorithms such as MC-SAT, LBP, and Gibbs sampling, as well as convergent message passing algorithms such as the concave-convex procedure, residual BP, and the L2-convex method. [ABSTRACT FROM AUTHOR] |
| Copyright of Machine Learning is the property of Springer Nature and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) | |
| Database: | Engineering Source |
| FullText | Links: – Type: pdflink Text: Availability: 0 |
|---|---|
| Header | DbId: egs DbLabel: Engineering Source An: 120548736 AccessLevel: 6 PubType: Academic Journal PubTypeId: academicJournal PreciseRelevancyScore: 0 |
| IllustrationInfo | |
| Items | – Name: Title Label: Title Group: Ti Data: Improving probabilistic inference in graphical models with determinism and cycles. – Name: Author Label: Authors Group: Au Data: <searchLink fieldCode="AR" term="%22Ibrahim%2C+Mohamed-Hamza%22">Ibrahim, Mohamed-Hamza</searchLink><relatesTo>1</relatesTo><i> mohamed.ibrahim@polymtl.ca</i><br /><searchLink fieldCode="AR" term="%22Pal%2C+Christopher%22">Pal, Christopher</searchLink><relatesTo>1</relatesTo><i> christopher.pal@polymtl.ca</i><br /><searchLink fieldCode="AR" term="%22Pesant%2C+Gilles%22">Pesant, Gilles</searchLink><relatesTo>1</relatesTo><i> gilles.pesant@polymtl.ca</i> – Name: TitleSource Label: Source Group: Src Data: <searchLink fieldCode="JN" term="%22Machine+Learning%22">Machine Learning</searchLink>. Jan2017, Vol. 106 Issue 1, p1-54. 54p. – Name: Subject Label: Subjects Group: Su Data: <searchLink fieldCode="DE" term="%22Probabilistic+inference%22">Probabilistic inference</searchLink><br /><searchLink fieldCode="DE" term="%22Determinism+%28Physics%29%22">Determinism (Physics)</searchLink><br /><searchLink fieldCode="DE" term="%22Graphic+methods%22">Graphic methods</searchLink><br /><searchLink fieldCode="DE" term="%22Algorithms%22">Algorithms</searchLink><br /><searchLink fieldCode="DE" term="%22Constraint+programming%22">Constraint programming</searchLink><br /><searchLink fieldCode="DE" term="%22Gibbs+sampling%22">Gibbs sampling</searchLink> – Name: Abstract Label: Abstract Group: Ab Data: Many important real-world applications of machine learning, statistical physics, constraint programming and information theory can be formulated using graphical models that involve determinism and cycles. Accurate and efficient inference and training of such graphical models remains a key challenge. Markov logic networks (MLNs) have recently emerged as a popular framework for expressing a number of problems which exhibit these properties. While loopy belief propagation (LBP) can be an effective solution in some cases; unfortunately, when both determinism and cycles are present, LBP frequently fails to converge or converges to inaccurate results. As such, sampling based algorithms have been found to be more effective and are more popular for general inference tasks in MLNs. In this paper, we introduce Generalized arc-consistency Expectation Maximization Message-Passing (GEM-MP), a novel message-passing approach to inference in an extended factor graph that combines constraint programming techniques with variational methods. We focus our experiments on Markov logic and Ising models but the method is applicable to graphical models in general. In contrast to LBP, GEM-MP formulates the message-passing structure as steps of variational expectation maximization. Moreover, in the algorithm we leverage the local structures in the factor graph by using generalized arc consistency when performing a variational mean-field approximation. Thus each such update increases a lower bound on the model evidence. Our experiments on Ising grids, entity resolution and link prediction problems demonstrate the accuracy and convergence of GEM-MP over existing state-of-the-art inference algorithms such as MC-SAT, LBP, and Gibbs sampling, as well as convergent message passing algorithms such as the concave-convex procedure, residual BP, and the L2-convex method. [ABSTRACT FROM AUTHOR] – Name: AbstractSuppliedCopyright Label: Group: Ab Data: <i>Copyright of Machine Learning is the property of Springer Nature and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract.</i> (Copyright applies to all Abstracts.) |
| PLink | https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=120548736 |
| RecordInfo | BibRecord: BibEntity: Identifiers: – Type: doi Value: 10.1007/s10994-016-5585-5 Languages: – Code: eng Text: English PhysicalDescription: Pagination: PageCount: 54 StartPage: 1 Subjects: – SubjectFull: Probabilistic inference Type: general – SubjectFull: Determinism (Physics) Type: general – SubjectFull: Graphic methods Type: general – SubjectFull: Algorithms Type: general – SubjectFull: Constraint programming Type: general – SubjectFull: Gibbs sampling Type: general Titles: – TitleFull: Improving probabilistic inference in graphical models with determinism and cycles. Type: main BibRelationships: HasContributorRelationships: – PersonEntity: Name: NameFull: Ibrahim, Mohamed-Hamza – PersonEntity: Name: NameFull: Pal, Christopher – PersonEntity: Name: NameFull: Pesant, Gilles IsPartOfRelationships: – BibEntity: Dates: – D: 01 M: 01 Text: Jan2017 Type: published Y: 2017 Identifiers: – Type: issn-print Value: 08856125 Numbering: – Type: volume Value: 106 – Type: issue Value: 1 Titles: – TitleFull: Machine Learning Type: main |
| ResultId | 1 |
