Making Pairwise Binary Graphical Models Attractive
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.
Making Pairwise Binary Graphical Models AttractiveQuality - there are some surprising aspects to the experiments that are not discussed. See below. Clarity - paper covers a lot of ground many of the subparts are relatively well written, with references where necessary. But I found it surprisingly hard to get quickly a succinct overview of what is achieved. What would help is to emphasize in abstract and intro which claimed improvements are wrt approximating the Bethe free energy (in the direction of recent work by Weller and Jebara) and which wrt the true free energy. E.g. just from the introduction we get the statement "We then show that the computation of the Bethe partition function can approximated or in some cases found exactly by computing the Bethe partition function over this special cover." and " In these experiments, the proposed scheme converges signiﬁcantly more frequently than reweighted BP and provides a better estimate of the partition function than TRBP." The first is about approximations of the Bethe free energy, the second about the true free energy. Similarly for the assumptions about the model. Is the assumption of switching log-submodular models / signed graphs necessary? Originality - the paper follows a recent direction, but appears to make clear new contributions.Significance - finding better approximate inference algorithms is one of the most important challenges in the field. This paper makes advances and increases our understanding in a relatively fresh direction. Questions:- In Fig 5 in the appendix the BP-2 curve is non-smooth (assuming it is occluded by the other curve in the left part). Why is this? - Fig 3 seems to show a weird asymptote for BP-2 this does not seem to be discussed in the text. Did I miss this? What is going on here?