CUED Publications database

Approximating the Bethe partition function

Weller, A and Jebara, T Approximating the Bethe partition function. (Unpublished)

Full text not available from this repository.


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 $\epsilon$-approximation to the global minimum of $F$ in polynomial time provided the maximum degree $\Delta=O(\log n)$, 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, $\log Z_B=-\min F$, for a general model to additive $\epsilon$-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.

Item Type: Article
Uncontrolled Keywords: cs.LG cs.LG
Divisions: Div F > Computational and Biological Learning
Depositing User: Cron Job
Date Deposited: 15 Nov 2017 20:14
Last Modified: 18 Feb 2021 18:14