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