Source-linked AI summary
Convergent message passing algorithms - a unifying view
Talya Meltzer, Amir Globerson, Yair Weiss
TL;DR
Popular message-passing algorithms are not guaranteed to converge, motivating the search for convergent updates for graphical-model inference. The paper presents a unified framework for deriving such updates and reports that the original TRW algorithm converges with an appropriate update schedule.
Problem
Popular message-passing algorithms can have fixed points that are variational optima but are not guaranteed to converge.
Source: §1 · p. 1Method
The framework gives sufficient conditions for message-passing updates to decrease variational bounds monotonically, using related consistency conditions for marginals and MAP.
Source: §1 · p. 2Results
The original TRW algorithm for free-energy minimization converges when run with an appropriate message-update schedule.
Source: §1 · p. 2Takeaways & Limitations
The framework uses the analogy between sum- and max-consistency to derive convergent algorithms for both marginals and MAP, including new algorithms obtained by exchanging maximizations and summations.
Source: §1 · p. 2, §7 · p. 8The algorithms discussed update star graphs; obtaining general non-star tree updates that satisfy consistency and reparameterization simultaneously remains challenging, and the derivation focuses on non-negative counting numbers.
Source: §2.1 · p. 3, §7 · p. 8
Abstract
from arXiv · showhide
Message-passing algorithms have emerged as powerful techniques for approximate inference in graphical models. When these algorithms converge, they can be shown to find local (or sometimes even global) optima of variational formulations to the inference problem. But many of the most popular algorithms are not guaranteed to converge. This has lead to recent interest in convergent message-passing algorithms. In this paper, we present a unified view of convergent message-passing algorithms. We present a simple derivation of an abstract algorithm, tree-consistency bound optimization (TCBO) that is provably convergent in both its sum and max product forms. We then show that many of the existing convergent algorithms are instances of our TCBO algorithm, and obtain novel convergent algorithms "for free" by exchanging maximizations and summations in existing algorithms. In particular, we show that Wainwright's non-convergent sum-product algorithm for tree based variational bounds, is actually convergent with the right update order for the case where trees are monotonic chains.
1 Introduction
The introduction frames inference in graphical models as a variational optimization problem and highlights that popular message-passing algorithms are not guaranteed to converge. It presents a unified framework for deriving convergent updates across marginals and MAP approximations.
1 Introduction
- Popular message-passing algorithms can have fixed points corresponding to variational optima, yet are not guaranteed to converge.Damping is often used to improve their convergence.Source: §1 · p. 1
- The framework unifies marginals and MAP approximations by exploiting their mathematical similarities.These inference tasks involve calculating model marginals and finding the most likely assignment, respectively.Source: §1 · p. 1
- Sufficient update conditions make the variational bound decrease monotonically, guaranteeing a global optimum for marginals and a local optimum for the MAP LP approximation.The conditions apply to both sum- and max-consistency updates.Source: §1 · p. 2
- The variational setup uses local region entropies and may approximate the marginal polytope with a local polytope enforcing agreement between nested regions.For marginals, inference is framed as free-energy minimization; for MAP, it corresponds to an LP relaxation.Source: §1 · pp. 1–2
- The framework updates tree-structured subsets of regions and gives conditions for improvement rather than an explicit update algorithm, unlike Sontag et al.'s tree-edge method.The shared sum- and max-consistency conditions make it possible to derive algorithms for both inference problems.Source: §1 · p. 2
- The original TRW algorithm for free-energy minimization converges when run with an appropriate message-update schedule.The introduction contrasts this result with earlier, more involved convergent algorithms for the problem.Source: §1 · p. 2
2 Bounds for MAP and Log-Partition
The section frames marginal and MAP inference as variational optimization, then develops tree-based reparameterization updates for optimizing bounds under consistency constraints. It restricts the framework to nonnegative counting numbers and states when the log-partition bound is tight.
2 Bounds for MAP and Log-Partition
- A temperature parameter unifies the marginal and MAP formulations: T=1 for marginals and T=0 for MAP, with optimization framed as maximizing F(q).Here q ranges over distributions, and F(q) is the negative of the free energy.Source: §2 · p. 2
2.1 Positive Counting Numbers
- Because approximate entropy is generally nonconcave, the framework focuses on nonnegative double-counting numbers, noting that many negative-number free energies can be transformed on region graphs.The paper identifies tree-reweighted free energies as an important example.Source: §2.1 · p. 3
2.3 Bound minimization and reparameterizations
- Tree-reweighted entropy can use a nonnegative mixture of tree entropies or an edge-appearance representation, where singleton counting numbers may be negative; nonnegativity simplifies algorithm derivation.The tree mixture uses a probability distribution over trees; in the edge-appearance representation, singleton counting numbers can be negative.Source: §2.3 · p. 3
2.2 Optimization and Reparameterization
- TCBO updates tree-structured region-graph subgraphs while maintaining reparameterization and enforcing sum-consistency for log-partition bounds or max-consistency for MAP bounds.These updates monotonically decrease an upper bound on the optimization objective.Source: §2.2 · pp. 3–4
- The log-partition bound is tight when a reparameterization yields sum-consistent marginals; the paper gives a sufficient condition based on the maximum not occurring at an extreme point.The cited condition is for the maximum of the approximated negative free energy.Source: §2.2 · p. 4
3 Bound optimization and consistency
TCBO is a framework for minimizing approximate log-partition and MAP bounds through consistency updates on region-graph trees. Its updates monotonically decrease the bound, with global-optimum guarantees for the log-partition case but not generally for MAP.
3 Bound optimization and consistency
- Minimizing the MAP bound over reparameterizations yields the optimal value of the region-graph LP relaxation.The tightest bound coincides with that LP relaxation.Source: §3 · p. 4
- Updates preserve admissible reparameterizations and enforce sum- or max-consistency on a subtree, meeting the conditions for bound descent.When locally maximizing beliefs are sum-consistent and the reparameterization preserves the original energy, the affected bound reaches its optimum.Source: §3 · pp. 4–5
- TCBO updates monotonically decrease the bound; strict convexity makes the log-partition solution globally optimal, while MAP may converge to a non-global value.The MAP caveat is shared by most dual descent algorithms.Source: §3 · pp. 4–5
- For the log-partition bound, the updated subset need not be a tree; sum-consistency alone suffices.Enforcing consistency on trees may be easier in practice.Source: §3 · p. 5
- TCBO is a general scheme whose implementation can use different choices of tree subgraphs.The framework is proposed for approximate log-partition and MAP bounds in region graphs with positive counting numbers.Source: §3 · pp. 4–5
4 Existing bound minimizing algorithms
The section relates several established message-passing algorithms to TCBO tree updates. For TRW, it identifies an update schedule that makes the sum-product variant convergent, including for monotonic chains.
4 Existing bound minimizing algorithms
- Heskes’ algorithm, MPLP, TRW-S, and max-sum diffusion (MSD) are identified as TCBO instances for approximating MAP or marginals.Heskes’ algorithm uses direct substitution; MPLP messages can be obtained by transforming those of max-product Heskes, while MSD’s max-consistency is shown directly.Source: §4 · pp. 5–6
- Max-consistent beliefs minimize the bound for the corresponding reparameterization.The algorithms’ tree-subgraph updates enforce max- or sum-consistency, as appropriate.Source: §4 · pp. 5–6
- Figure 2 illustrates max-sum-diffusion (MSD) as an instance of the TCBO formalism: it operates on a region graph containing pair and singleton regions, with the TCBO update subgraph T shown in a blue dashed line.The regions correspond to a 2x2 grid.Source: Figure 2 · p. 6
- TRW-S can efficiently implement tree updates when its trees are monotonic chains, scanning nodes in the specified order forward and then backward.Monotonic chains respect a given node ordering, allowing messages to be reused across multiple trees.Source: §4 · p. 6
- The TRW sum-product algorithm is not generally provably convergent, but the TRW-S variant differs from it only in message scheduling.The section identifies TRW-S as a convergent variant for this case.Source: §4 · pp. 6–7
5 New bound minimizing algorithms
Two-way GBP with all double-counting numbers equal to 1 is a convergent algorithm in both sum and max forms. Its updates preserve reparameterization and enforce consistency, and the algorithm is identical to MSD.
5 New bound minimizing algorithms
- Two-way GBP with all double-counting numbers cα = 1 is convergent in both sum and max versions.At each iteration it updates the beliefs of a region and one of its subregions, which form a tree.Source: §5 · p. 7
- Two-way GBP with cα = 1 maintains reparameterization and enforces consistency at each update.The paper says these properties can be shown directly.Source: §5 · p. 7
- Two-way GBP with cα = 1 is identical to max-sum diffusion (MSD).Source: §5 · p. 7
6 Experiments
The experiments compare sum- and max-product TCBO algorithms on a 10×10 spin glass. TRW-S monotonically decreases the log-partition bound under its forward-then-backward schedule, while three MAP algorithms converge monotonically to the same value.
6 Experiments
- Exchanging maximizations and summations yields convergent counterparts: max-product Heskes and sum-product TRW-S, MPLP, and MSD.These variants are convergent with respect to the relevant bound.Source: §6 · p. 7
- The experiments use a 10×10 spin glass with random pairwise terms drawn from [−9, 9] and fields from [−1, 1].For the log-partition experiment, TRW uses a uniform distribution over two spanning forests: the horizontal and vertical chains.Source: §6 · p. 7
- Only TRW-S monotonically decreases the log-partition bound in the 10×10 spin-glass comparison with TRW.The algorithms differ only in update order; TRW-S scans forward and then backward, while TRW uses a forward scan.Source: §6 · p. 8, Figure 6 · p. 8
- The max-product Heskes algorithm, MPLP, and MSD monotonically converge to the same MAP bound value.The comparison uses pair regions with double-counting numbers 1 and singleton regions with numbers 0.Source: §6 · p. 8
7 Discussion
The discussion presents TCBO as a unified framework for convergent message passing and highlights update schedule as a route to convergence. It also notes that the discussed algorithms update stars, while general consistent tree updates remain a challenge.
7 Discussion
- The framework can handle negative counting numbers in some cases by using larger regions, and ordinary BP on a single cycle converges in both forms.Source: §7 · p. 8
- The framework unifies existing convergent algorithms and enables deriving variants by exchanging maximizations and summations.The discussion emphasizes enforcing consistency in both sum-product and max-product algorithms.Source: §7 · p. 8
- The algorithms discussed update only star graphs, while finding general tree updates that satisfy consistency constraints remains an open challenge.The paper notes that such updates should also achieve reparameterization and max- or sum-consistency.Source: §7 · p. 8
- A suitable update schedule can make an otherwise non-convergent algorithm convergent.The discussion identifies deriving convergent schedules for a larger class of algorithms as a future direction.Source: §7 · p. 8