Approximations and bounds for binary Markov random fields

The formulation of discrete Markov random fields (MRFs) include a computationally intractable normalising constant, which limits the applicability of the model class. The normalising constant can in principle be computed by marginalising out each variable in turn, but in practice this is computationally feasible for small lattices only. We propose an approximate marginalisation operation, which can be used to obtain an approximation of the normalisation constant and an approximate probability distribution with an easy to compute normalising constant. In turn these can be used to find an approximation of the maximum likelihood estimators, or can be used in stead of the corresponding exact quantity in a fully Bayesian setting. We also discuss how the approximate marginalisation operation can be modified to give upper and lower bounds for the normalising constant. The same approximation strategy can be used to define an approximate maximisation operation, which in turn can be used to find an approximation of, or lower and upper bounds for, the maximum value of the MRF probability.