CCCP Algorithms to Minimize the Bethe and Kikuchi Free Energies: Convergent Alternatives to Belief Propagation

By Alan L. Yuille. 2002

254 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computer Networks and Communications, Optimization & Training, Probabilistic & Bayesian Methods

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Networks and Communications

In Optimization & Training

In Probabilistic & Bayesian Methods

Citations in the corpus

Discriminative Embeddings of Latent Variable Models for Structured Data (2016, neutral): “…variational inference methods, with different forms of free energies or different optimization algorithms, resulting different message update forms, e.g., double-loop BP (Yuille, 2002), damped BP (Minka, 2001), tree-reweightd BP (Wainwright et al., 2003), and generalized BP (Yedidia et al., 2001b).”
Graphical Models, Exponential Families, and Variational Inference (2008, background): “A parallel line of work [265, 249, 108] has explored alternatives to sum-product that are guaranteed to converge, albeit at the price of increased computational cost.”
Collective Classification in Network Data (2008, methodology): “Other examples of approximate inference algorithms include algorithms developed to extend and improve loopy belief propagation to remove some of its shortcomings such as alternatives with convergence guarantees [ 67 ] and alternatives that go beyond just using edge and node marginals to compute more”
Constructing free-energy approximations and generalized belief propagation algorithms (2005, background): “Besides the results that we now discuss, which were first reported in [17], the interested reader can find similar empirical results for GBP algorithms in [58], [59], [56], [33], [49].”
Graphical Model Inference in Optimal Control of Stochastic Multi-Agent Systems (2008, background): “This delayed choice is due to a symmetry breaking in the cost-togo as time increases.”
Residual Belief Propagation: Informed Scheduling for Asynchronous Message Passing (2006, methodology): “Propagation methods that are guaranteed to converge have been proposed by Yuille (2001) and Welling and Teh (2001).”
Learning in Markov Random Fields with Contrastive Free Energies (2005, background): “This objective is far more tractable than the ML criterion because it only depends on one dimensional normalization constants Z k |− k .”
Recovering Occlusion Boundaries from an Image (2011, methodology): “as suggested by Yuille [77] efficiently provides “soft-max” likelihood estimates.”
Stable Fixed Points of Loopy Belief Propagation Are Local Minima of the Bethe Free Energy (2002, background): “The crucial trick, implicit or explicit in recently suggested procedures is to bound [5] or clamp [6] the possibly concave part (outer loop: recompute the bound) and solve the remaining convex problem (inner loop: maximization with respect to Lagrange multipliers; see below).”
Convergent Propagation Algorithms via Oriented Trees (2007, methodology): “Finally, another algorithm which is guaranteed to converge to a global minimum of convexified free energies is the double loop CCCP algorithm of Yuille [17].”
Expectation propagation for approximate inference in dynamic Bayesian networks (2002, methodology): “We derived a convergent double-loop algorithm, similar to the one proposed in (Yuille, 2002) for loopy belief propagation.”
The variational Bayesian EM algorithm for incomplete data: with application to scoring graphical model structures (2003, methodology): “Furthermore, convergent algorithms for minimising the Bethe free energy have recently been derived (Yuille, 2001; Welling and Teh, 2001).”
The Concave-Convex Procedure (2003, methodology): “See, for example, recent work (Yuille, 2002) where CCCP was used to construct a double loop algorithm to minimize the Bethe and Kikuchi free energies (Yedidia, Freeman, & Weiss, 2000).”
Expectation Consistent Approximate Inference (2005, methodology): “However, this natural split allows us to develop a double loop algorithm similar to Yuille (2002); Heskes et al. (2003), which is guaranteed to converge to at least one of the stationary points, provided that the EC free energy is bounded from below.”
Distributed Bayesian Learning with Stochastic Natural Gradient Expectation Propagation and the Posterior Server (2015, methodology): “In the following we will use “EP” to refer to both EP and power EP for simplicity.”
Recovering Occlusion Boundaries from a Single Image (2007, methodology): “To do this, we combine the sum-product algorithm of Hes-kes et al. [9] (based on the Kikuchi free energy) with the mean ﬁeld approximation suggested by Yuille [31] (raise each factor to the 1 T , with T = 0 .”