Title: Belief Propagation, Bethe Approximation and Polynomials,
Abstract: Factor graphs are important models for succinctly representing probability
distributions in machine learning, coding theory, and statistical physics.
Several computational problems, such as computing marginals and partition
functions, arise naturally when working with factor graphs. Belief propagation
is a widely deployed iterative method for solving these problems. However,
despite its significant empirical success, not much is known about the
correctness and efficiency of belief propagation.
Bethe approximation is an optimization-based framework for approximating
partition functions. While it is known that the stationary points of the Bethe
approximation coincide with the fixed points of belief propagation, in general,
the relation between the Bethe approximation and the partition function is not
well understood. It has been observed that for a few classes of factor graphs,
the Bethe approximation always gives a lower bound to the partition function,
which distinguishes them from the general case, where neither a lower bound,
nor an upper bound holds universally. This has been rigorously proved for
permanents and for attractive graphical models.
Here we consider bipartite normal factor graphs and show that if the local
constraints satisfy a certain analytic property, the Bethe approximation is a
lower bound to the partition function. We arrive at this result by viewing
factor graphs through the lens of polynomials. In this process, we reformulate
the Bethe approximation as a polynomial optimization problem. Our sufficient
condition for the lower bound property to hold is inspired by recent
developments in the theory of real stable polynomials. We believe that this way
of viewing factor graphs and its connection to real stability might lead to a
better understanding of belief propagation and factor graphs in general.