The max-product algorithm, which attempts to compute the most probable assignment (MAP) of a given probability distribution via a distributed, local message passing scheme, has recently found applications in convex minimization and combinatorial optimization. Unfortunately, the max-product algorithm is not guaranteed to converge and, even if it does, is not guaranteed to produce the MAP assignment. Many alternative message passing schemes have been proposed to overcome these difficulties (e.g. TEMP, MPLP, max-sum diffusion). These algorithms can be viewed as coordinate ascent schemes over different duals of a linear programming formulation of the MAP problem. If these algorithms converge to a unique assignment, then this assignment is guaranteed to be the maximum of the objective function. Although these algorithms provide stronger guarantees than max-product upon convergence, they do not always converge to a unique assignment, and in some instances, the dual optimization problem that results provides a trivial upper bound on the maximizing assignment.
In this work, we provide a systematic study of message passing algorithms for the related problem of minimizing an arbitrary real-valued objective function: from graphical models to reparameterization, reparameterization to lower bounds, and from lower bounds to convergent message passing algorithms. We generalize the known results by providing conditions under which the assignments produced by message passing algorithms can correspond to local and global optima, by providing a combinatorial characterization of when these message passing schemes can actually solve the minimization problem, and by providing a new convergent and correct message passing algorithm, called the splitting algorithm, that contains many of the known convergent message passing algorithms as a special case.
These ideas allow us to expand the usefulness of the splitting algorithm beyond the limits of other message passing algorithms. We show that there are examples of convex minimization problems on which convergent message passing algorithms fail to produce a minimizing assignment but that the splitting algorithm succeeds. We use graph covers and our conditions for local optimality to provide conditions under which the splitting algorithm can be used to solve general convex (as well as submodular) minimization problems. These observations lead us to a generalization of diagonal dominance for arbitrary convex functions.
|School Location:||United States -- Connecticut|
|Source:||DAI-B 73/05, Dissertation Abstracts International|
|Keywords:||Belief propagation, Message passing|
Copyright in each Dissertation and Thesis is retained by the author. All Rights Reserved
The supplemental file or files you are about to download were provided to ProQuest by the author as part of a
dissertation or thesis. The supplemental files are provided "AS IS" without warranty. ProQuest is not responsible for the
content, format or impact on the supplemental file(s) on our system. in some cases, the file type may be unknown or
may be a .exe file. We recommend caution as you open such files.
Copyright of the original materials contained in the supplemental file is retained by the author and your access to the
supplemental files is subject to the ProQuest Terms and Conditions of use.
Depending on the size of the file(s) you are downloading, the system may take some time to download them. Please be