2013 Reports
Approximating the Bethe partition function
When belief propagation (BP) converges, it does so to a stationary point of the Bethe free energy F, and is often strikingly accurate. However, it may converge only to a local optimum or may not converge at all. An algorithm was recently introduced for attractive binary pairwise MRFs which is guaranteed to return an ϵ-approximation to the global minimum of F in polynomial time provided the maximum degree Δ=O(logn), where n is the number of variables. Here we significantly improve this algorithm and derive several results including a new approach based on analyzing first derivatives of F, which leads to performance that is typically far superior and yields a fully polynomial-time approximation scheme (FPTAS) for attractive models without any degree restriction. Further, the method applies to general (non-attractive) models, though with no polynomial time guarantee in this case, leading to the important result that approximating log of the Bethe partition function, logZB=−minF, for a general model to additive ϵ-accuracy may be reduced to a discrete MAP inference problem. We explore an application to predicting equipment failure on an urban power network and demonstrate that the Bethe approximation can perform well even when BP fails to converge.
Subjects
Files
- cucs-031-13.pdf application/pdf 357 KB Download File
More About This Work
- Academic Units
- Computer Science
- Publisher
- Department of Computer Science, Columbia University
- Series
- Columbia University Computer Science Technical Reports, CUCS-031-14
- Published Here
- February 21, 2014