Tree-reweighted Belief Propagation Algorithms and Approximate ML Estimation by Pseudo-Moment Matching

Martin J. Wainwright, Tommi S. Jaakkola, Alan S. Willsky
Proceedings of the Ninth International Workshop on Artificial Intelligence and Statistics, PMLR R4:308-315, 2003.

Abstract

In previous work [10] 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 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 pseudo-moment-matching. We present preliminary results illustrating the behavior of this approximate ML estimator.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR4-wainwright03a, title = {Tree-reweighted Belief Propagation Algorithms and Approximate {ML} Estimation by Pseudo-Moment Matching}, author = {Wainwright, Martin J. and Jaakkola, Tommi S. and Willsky, Alan S.}, booktitle = {Proceedings of the Ninth International Workshop on Artificial Intelligence and Statistics}, pages = {308--315}, year = {2003}, editor = {Bishop, Christopher M. and Frey, Brendan J.}, volume = {R4}, series = {Proceedings of Machine Learning Research}, month = {03--06 Jan}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/r4/wainwright03a/wainwright03a.pdf}, url = {https://proceedings.mlr.press/r4/wainwright03a.html}, abstract = {In previous work [10] 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 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 pseudo-moment-matching. We present preliminary results illustrating the behavior of this approximate ML estimator.}, note = {Reissued by PMLR on 01 April 2021.} }
Endnote
%0 Conference Paper %T Tree-reweighted Belief Propagation Algorithms and Approximate ML Estimation by Pseudo-Moment Matching %A Martin J. Wainwright %A Tommi S. Jaakkola %A Alan S. Willsky %B Proceedings of the Ninth International Workshop on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2003 %E Christopher M. Bishop %E Brendan J. Frey %F pmlr-vR4-wainwright03a %I PMLR %P 308--315 %U https://proceedings.mlr.press/r4/wainwright03a.html %V R4 %X In previous work [10] 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 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 pseudo-moment-matching. We present preliminary results illustrating the behavior of this approximate ML estimator. %Z Reissued by PMLR on 01 April 2021.
APA
Wainwright, M.J., Jaakkola, T.S. & Willsky, A.S.. (2003). Tree-reweighted Belief Propagation Algorithms and Approximate ML Estimation by Pseudo-Moment Matching. Proceedings of the Ninth International Workshop on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research R4:308-315 Available from https://proceedings.mlr.press/r4/wainwright03a.html. Reissued by PMLR on 01 April 2021.

Related Material