Exact and Approximate Recursive Calculations for Binary Markov Random Fields Defined on Graphs

Abstract

In this article, we propose computationally feasible approximations to binary Markov random fields (MRFs). The basis of the approximation is the forward-backward algorithm. The exact forward-backward algorithm is computationally feasible only for fields defined on small lattices. The forward part of the algorithm computes a series of joint marginal distributions by summing out each variable in turn. We represent these joint marginal distributions by interaction parameters of different orders. The approximation is defined by approximating to zero all interaction parameters that are sufficiently close to zero. In addition, an interaction parameter is approximated to zero whenever all associated lower-level interactions are (approximated to) zero. If sufficiently many interaction parameters are set to zero, the algorithm is computationally feasible both in terms of computation time and memory requirements. The resulting approximate forward part of the forward-backward algorithm defines an approximation to the intractable normalizing constant, and the corresponding backward part of the algorithm defines a computationally feasible approximation to the MRF. We present numerical examples demonstrating the quality of the approximation. The supplementary materials for this article, which are available online, include two appendices and R and C codes for the proposed recursive algorithms.

Key Words:

• Approximate inference
• Approximate normalizing constant
• Autologistic model
• Forward-backward algorithm
• Ising model
• Recursive computation

ACKNOWLEDGMENTS

The authors are grateful to the editors and two anonymous referees for their helpful suggestions. The authors thank Nial Friel for providing the dataset used in Section 7. The authors also gratefully acknowledge the support from the Research Council of Norway, Statoil, and ENI.