Uncertainty in Artificial Intelligence
First Name   Last Name   Password   Forgot Password   Log in!
    Proceedings   Proceeding details   Article details         Authors         Search    
Approximating the Bethe Partition Function
Adrian Weller, Tony Jebara
When belief propagation (BP) converges, it does so to a stationary point of the Bethe free en- ergy F , and is often strikingly accurate. How- ever, it may converge only to a local optimum or may not converge at all. An algorithm was recently introduced by Weller and Jebara for at- tractive binary pairwise MRFs which is guaran- teed to return an ǫ-approximation to the global minimum of F in polynomial time provided the maximum degree ?? = O(log n), where n is the number of variables. Here we extend their ap- proach and derive a new method based on an- alyzing first derivatives of F , which leads to much better performance and, for attractive mod- els, yields a fully polynomial-time approxima- tion scheme (FPTAS) without any degree restric- tion. Further, our methods apply to general (non- attractive) models, though with no polynomial time guarantee in this case, demonstrating that approximating log of the Bethe partition func- tion, log ZB = ?? min F , for a general model to additive ǫ-accuracy may be reduced to a discrete MAP inference problem. This allows the merits of the global Bethe optimum to be tested.
Pages: 858-867
PS Link:
PDF Link: /papers/14/p858-weller.pdf
AUTHOR = "Adrian Weller and Tony Jebara",
TITLE = "Approximating the Bethe Partition Function",
BOOKTITLE = "Proceedings of the Thirtieth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-14)",
ADDRESS = "Corvallis, Oregon",
YEAR = "2014",
PAGES = "858--867"

hosted by DSL   •   site info   •   help