Timezone: »

 
Poster
Making Pairwise Binary Graphical Models Attractive
Nicholas Ruozzi · Tony Jebara

Thu Dec 11 11:00 AM -- 03:00 PM (PST) @ Level 2, room 210D
in Poster Session »

Computing the partition function (i.e., the normalizing constant) of a given pairwise binary graphical model is NP-hard in general. As a result, the partition function is typically estimated by approximate inference algorithms such as belief propagation (BP) and tree-reweighted belief propagation (TRBP). The former provides reasonable estimates in practice but has convergence issues. The later has better convergence properties but typically provides poorer estimates. In this work, we propose a novel scheme that has better convergence properties than BP and provably provides better partition function estimates in many instances than TRBP. In particular, given an arbitrary pairwise binary graphical model, we construct a specific ``attractive'' 2-cover. We explore the properties of this special cover and show that it can be used to construct an algorithm with the desired properties.

[ PDF] 

Author Information

Nicholas Ruozzi (Columbia University)
Tony Jebara (Spotify)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors