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. |
