Tree-reweighted belief propagation algorithms and approximate ML estimation via pseudo-moment matching

M. J. Wainwright, T. S. Jaakkola, and A. S. Willsky

Published in:
Workshop on Artificial Intelligence and Statistics, January, 2003

In previous work~\cite{Wainwright02a}, we presented a class of upper bounds on the log partition function of an arbitrary undirected graphical model based on solving a convex variational problem. Here we develop a class of local message-passing algorithms, which we call {\em tree-reweighted belief propagation}, for efficiently computing the value of these upper bounds, as well as the associated pseudomarginals. We also consider the uses of our bounds for the problem of maximum likelihood (ML) parameter estimation. For a completely observed model, our analysis gives rise to a concave lower bound on the log likelihood of the data. Maximizing this lower bound yields an approximate ML estimate which, in analogy to the moment-matching of exact ML estimation, can be interpreted in terms of {\em pseudo-moment-matching}. We present preliminary results illustrating the behavior of this approximate ML estimator.
Download: Full Text (438K  ps / Full Text (286K  pdf