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
Abstract:
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.
Keywords:
Pages: 858-867
PS Link:
PDF Link: /papers/14/p858-weller.pdf
BibTex:
@INPROCEEDINGS{Weller14,
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)",
PUBLISHER = "AUAI Press",
ADDRESS = "Corvallis, Oregon",
YEAR = "2014",
PAGES = "858--867"
}


hosted by DSL   •   site info   •   help