We study worst-case bounds on the quality of any fixed point assignment of the max-product algorithm for Markov Random Fields (MRF). We start proving a bound
independent of the MRF structure and parameters. Afterwards, we show how this bound can be improved for MRFs with particular structures such as bipartite graphs or grids.
Our results provide interesting insight into the behavior of max-product. For example, we prove that max-product provides very good results (at least 90% of the optimal) on MRFs
with large variable-disjoint cycles (MRFs in which all cycles are variable-disjoint, namely that they do not share any edge and in which each cycle contains at least 20 variables).
Meritxell Vinyals (IIIA-CSIC)
Jesús Cerquides (IIIA-CSIC)
Alessandro Farinelli (University of Verona)
Juan A Rodríguez-Aguilar (IIIA-CSIC)
Related Events (a corresponding poster, oral, or spotlight)
2010 Poster: Worst-case bounds on the quality of max-product fixed-points »
Tue Dec 7th 08:00 -- 08:00 AM Room None