Approximate Inference and Constrained Optimization
arXiv:1212.2480
Abstract
Loopy and generalized belief propagation are popular algorithms for approximate inference in Markov random fields and Bayesian networks. Fixed points of these algorithms correspond to extrema of the Bethe and Kikuchi free energy. However, belief propagation does not always converge, which explains the need for approaches that explicitly minimize the Kikuchi/Bethe free energy, such as CCCP and UPS. Here we describe a class of algorithms that solves this typically nonconvex constrained minimization of the Kikuchi free energy through a sequence of convex constrained minimizations of upper bounds on the Kikuchi free energy. Intuitively one would expect tighter bounds to lead to faster algorithms, which is indeed convincingly demonstrated in our simulations. Several ideas are applied to obtain tight convex bounds that yield dramatic speed-ups over CCCP.
Appears in Proceedings of the Nineteenth Conference on Uncertainty in Artificial Intelligence (UAI2003)
Cited by in corpus (16)
- Optimal control as a graphical model inference problem
- Sufficient conditions for convergence of the Sum-Product Algorithm
- Low-Complexity Detection/Equalization in Large-Dimension MIMO-ISI Channels Using Graphical Models
- Convexifying the Bethe Free Energy
- Message passing and Monte Carlo algorithms: connecting fixed points with metastable states
- Approximate inference on planar graphs using Loop Calculus and Belief Propagation
- Variable Elimination in the Fourier Domain
- Finding Non-overlapping Clusters for Generalized Inference Over Graphical Models
- Loop corrections for approximate inference
- State Estimation of Power Flows for Smart Grids via Belief Propagation
- A belief propagation algorithm based on domain decomposition
- Computational Sociolinguistics: A Survey
- Clamping Improves TRW and Mean Field Approximations
- Towards Efficient Discrete Integration via Adaptive Quantile Queries
- Improving variational methods via pairwise linear response identities
- Inconsistent parameter estimation in Markov random fields: Benefits in the computation-limited setting