Understanding the Bethe approximation: when and how can it go wrong?
Adrian Weller, Kui Tang, David A. Sontag, Tony Jebara · 2014
Belief propagation is a remarkably effective tool for inference, even when applied to networks with cycles. It may be viewed as a way to seek the minimum of the Bethe free energy, though with no convergence guarantee in general. A variational perspective shows that, compared to exact inference, this minimization employs two forms of approximation: (i) the true entropy is approximated by the Bethe entropy, and (ii) the minimization is performed over a relaxation of the marginal polytope termed the local polytope. Here we explore when and how the Bethe ap-proximation can fail for binary pairwise models by examining each aspect of the approximation, deriving results both analytically and with new experimental methods. 1