On the fixed points of the max-product algorithm

    •  William T. Freeman, Yair Weiss, "On the fixed points of the max-product algorithm", Tech. Rep. TR99-39, Mitsubishi Electric Research Laboratories, Cambridge, MA, December 1999.
      BibTeX TR99-39 PDF
      • @techreport{MERL_TR99-39,
      • author = {William T. Freeman, Yair Weiss},
      • title = {On the fixed points of the max-product algorithm},
      • institution = {MERL - Mitsubishi Electric Research Laboratories},
      • address = {Cambridge, MA 02139},
      • number = {TR99-39},
      • month = dec,
      • year = 1999,
      • url = {}
      • }
  • Research Area:

    Computer Vision


Graphical models, such as Bayesian networks and Markov random fields represent statistical dependencies of variables by a graph. The max-product \"belief propagation\" algorithm is a local-message passing algorithm on this graph that is known to converge to a unique fixed point when the graph is a tree. Furthermore, when the graph is a tree, the assignment based on the fixed-point is guaranteed to yields the most probable a posteriori (MAP) values of the unobserved variables given the observed ones. Here we prove a result on the fixed points of max-product on a graph with arbitrary toplogy and with arbitrary probability distributions (discrete or continuous valued nodes). We show that the assignment based on the fixed-point is a \"neighborhood maximum\" of the posterior probability: the posterior probability of the max-product assignment is guaranteed to be greater than all other assignments in a particular large region around that assignment. The region includes all assignments that differ from the max-product assignment in any subset of nodes that form no more than a single loop in the graph. In some graphs this neighborhood is exponentially large. We illustrate the analysis with examples.