@TechReport{Werner-TR-2011-14, IS = { zkontrolovano 13 Jan 2012 }, UPDATE = { 2011-12-29 }, author = {Werner, Tom{\'a}{\v s}}, title = {Zero-Temperature Limit of a Convergent Algorithm to Minimize the Bethe Free Energy}, institution = {Center for Machine Perception, K13133 FEE Czech Technical University}, address = {Prague, Czech Republic}, year = {2011}, month = {December}, type = {Research Report}, number = {CTU--CMP--2011--14}, issn = {1213-2365}, pages = {12}, figures = {1}, authorship = {100}, psurl = {[PDF]}, project = {GACR P103/10/0783}, annote = {After the discovery that fixed points of loopy belief propagation coincide with stationary points of the Bethe free energy, several reseachers proposed provably convergent algorithms to directly minimize the Bethe free energy. These algorithms were formulated only for non-zero temperature (thus finding fixed points of the sum-product algorithm) and their possible extension to zero temperature is not obvious. We present the zero-temperature limit of the double-loop algorithm by Heskes, which converges a max-product fixed point. The inner loop of this algorithm turns out to be known as max-sum diffusion. Under certain conditions, the algorithm combines the complementary advantages of the max-product algorithm and max-sum diffusion: it yields good approximation of both ground states and max-marginals.}, keywords = {belief propagation, bethe free energy, max-product, sum-product, max-sum}, }