Advances in Message-Passing Algorithms in Propositional and Lifted Graphical Models

dc.contributor.advisorGogate, Vibhav
dc.creatorSmith, David B.
dc.date.accessioned2018-05-31T20:31:21Z
dc.date.available2018-05-31T20:31:21Z
dc.date.created2017-05
dc.date.issued2017-05
dc.date.submittedMay 2017
dc.date.updated2018-05-31T20:31:21Z
dc.description.abstractWith the profusion of data across new and complicated domains, the compactness and expressivity of PGMs have made them a cornerstone of modern, data-driven technologies. Unfortunately, PGMs suffer one substantial drawback; inference is known to be intractable. Many inference tasks in real-world problems are beyond the reach of existing technology. This dissertation focuses on the message-passing framework, a family of iterative algorithms for performing exact and approximate inference in probabilistic graphical models (PGMs). The message-passing approach is to (1) divide the global inference problem into tractable local problems that can be computed exactly, and (2) iteratively pass messages between local problems until agreement on a global solution is reached. The facility and flexibility of the message-passing framework has made it a popular choice for both exact and approximate inference in PGMs. However, message-passing algorithms suffer from some drawbacks. Exact local inference can be expensive, messages are not guaranteed to converge, and even if they do converge, there are no guarantees on the accuracy of the approximation. In this dissertation, we propose several advances to the message-passing framework that can take advantage of structural properties of a PGM in order to make message-passing based inference faster and more accurate. This document contains the following contributions. First, we propose an alternate representation of the junction-tree algorithm that can take advantage of highly-clustered graph structures in order to perform exact inference more efficiently. Second we investigate the behavior of the loopy belief propagation algorithm in PGMs containing hard constraints; we show that the accuracy of the approximation can be dramatically improved via a preprocessing step that rewrites the PGM in a format more amenable to message-passing. Third, we present a novel message-passing algorithm that allows evaluation of complex queries based on the order statistics of a graphical model. Fourth, we propose a representation for applying the AND/OR search framework to statistical relational graphical models; our representation allows yields tight bounds on the cost of inference in these models. Finally, we outline a method for utilizing the lifted AND/OR framework as the exact inference step in a region-based belief propagation algorithm for statistical relational models.
dc.format.mimetypeapplication/pdf
dc.identifier.urihttp://hdl.handle.net/10735.1/5789
dc.language.isoen
dc.rights©2018 The Author. Digital access to this material is made possible by the Eugene McDermott Library. Further transmission, reproduction or presentation (such as public display or performance) of protected items is prohibited except with permission of the author.
dc.subjectGraphical modeling (Statistics)
dc.subjectInference
dc.subjectInformation theory
dc.titleAdvances in Message-Passing Algorithms in Propositional and Lifted Graphical Models
dc.typeDissertation
dc.type.materialtext
thesis.degree.departmentComputer Science
thesis.degree.grantorThe University of Texas at Dallas
thesis.degree.levelDoctoral
thesis.degree.namePHD

Files

Original bundle

Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
ETD-5608-011-SMITH-7874.21.pdf
Size:
3.82 MB
Format:
Adobe Portable Document Format
Description:

License bundle

Now showing 1 - 2 of 2
No Thumbnail Available
Name:
LICENSE.txt
Size:
1.84 KB
Format:
Plain Text
Description:
No Thumbnail Available
Name:
PROQUEST_LICENSE.txt
Size:
5.84 KB
Format:
Plain Text
Description: