Bayesian Parameter Estimation for Latent Markov Random Fields and Social Networks

Abstract

Undirected graphical models are widely used in statistics, physics, and machine vision. However, Bayesian parameter estimation for undirected models is extremely challenging, since evaluation of the posterior typically involves the calculation of an intractable normalizing constant. This problem has received much attention, but very little of this has focused on the important practical case where the data consist of noisy or incomplete observations of the underlying hidden structure. This article specifically addresses this problem, comparing two alternate methodologies. In the first of these approaches, particle Markov chain Monte Carlo (Andrieu, Doucet, and Holenstein) is used to efficiently explore the parameter space, combined with the exchange algorithm (Murray, Ghahramani, and MacKay) for avoiding the calculation of the intractable normalizing constant (a proof showing that this combination targets the correct distribution is given in Appendix A available in the online supplementary materials). This approach is compared with approximate Bayesian computation (Pritchard et al.). Applications to estimating the parameters of Ising models and exponential random graphs from noisy data are presented. Each algorithm used in the article targets an approximation to the true posterior due to the use of Markov chain Monte Carlo method (MCMC) to simulate from the latent graphical model, in lieu of being able to do this exactly, in general. Appendix B (online supplementary materials) also describes the nature of the resulting approximation. Supplementary materials for this article are available online.

Key Words:

• Approximate Bayesian computation
• Exponential random graphs
• Graphical models
• Intractable normalizing constants
• Particle Markov chain Monte Carlo

ACKNOWLEDGMENTS

This work was funded by the Engineering and Physical Sciences Research Council’s (EPSRC) SuSTaIN program at the Department of Mathematics, University of Bristol. The author thanks Christophe Andrieu and Mark Briers for useful discussions and the three anonymous reviewers whose comments helped to improve the article.