Lab Home | Phone | Search
Center for Nonlinear Studies  Center for Nonlinear Studies
 Colloquia Archive 
 Postdoc Seminars Archive 
 Quantum Lunch 
 Quantum Lunch Archive 
 CMS Colloquia 
 Q-Mat Seminars 
 Q-Mat Seminars Archive 
 P/T Colloquia 
 Kac Lectures 
 Kac Fellows 
 Dist. Quant. Lecture 
 Ulam Scholar 
 CNLS Fellowship Application 
 Student Program 
 Past Visitors 
 History of CNLS 
 Maps, Directions 
 CNLS Office 
Tuesday, June 12, 2012
10:30 AM - 12:00 PM
CNLS Conference Room (TA-3, Bldg 1690)

Student Seminar

Marrying the Cluster Cumulant Expansion and Generalized BP

Andrew Gelfand
UC Irvine and T-4

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,, 665-8119