 |
Center for Nonlinear Studies |
Belief Propagation (BP) is a popular method for computing approximate marginal probabilities (beliefs) and approximating the partition function of graphical models with loopy factor graphs. One of the primary virtues of BP is its computational efficiency - in practice, if BP converges it often does so very quickly. However, BP does not always converge and even when it does, it may yield poor approximations. Generalized BP (GBP) and the Cluster Cumulant Expansion (CCE) are two methods that seek to improve the quality of BP approximations. Rather than passing messages between neighboring nodes in a graph, GBP passes messages between collections of nodes, or regions. GBP can greatly improve the accuracy of BP estimates without much additional computational burden, but it is highly sensitive to region choice. Alternatively, the CCE is a method that computes modifications to the partition function estimate provided by BP in a manner similar to Chertkov and Chernyak's Loop Series. The CCE is defined on a partially ordered set of clusters of factors and, as with GBP, the rate at which the CCE improves upon BP's estimates is also sensitive to the choice of clusters. In this talk, I will describe some initial work on tightening the relationship between GBP and the CCE and share my initial exploration on how to marry the choice of regions and clusters for accurate, anytime approximate inference.
Host: Misha Chertkov, chertkov@lanl.gov, 665-8119