SUMMARY

Belief propagation may be viewed as a heuristic to optimize the Bethe free energy FB, and often performs strikingly well. Here we focus on binary pairwise MRFs, and generalize important results on the Bethe approximation to the broad family of related pairwise entropy approximations with arbitrary counting numbers. We make observations that shed light on the success of the Bethe approximation. KEY RESULTS, FOR ANY COUNTING NUMBERS All extend earlier results that were specifically for the Bethe approximation: •Given singleton marginals, we provide an analytic solution for optimum pairwise pseudomarginals. •Thus, the approximate free energy FA may be considered a function only of singleton pseudomarginals {qi = q(Xi = 1)}. •We provide upper and lower bounds on first derivatives ∂FA∂qi as a function of qi, that hold for all values of other marginals {qj: j 6 = i}, see Figure. •We use these derivative bounds to construct an -sufficient mesh over pseudomarginals such that the optimum of FA on the mesh is guaranteed to have value within of the global optimum, see Figures. •We derive all second derivatives of the approximate free energy ∂2FA∂qi∂qj. •Using second derivatives, we show that for attractive models, the discrete optimization problem is submodular, hence may be solved efficiently leading to a FPTAS for the approximate log-partition function log ZA (extends to balanced models). BACKGROUND We consider a binary pairwise model with variables V and edges E. p(x) = e−E (x