Approximate recursive calculations of discrete Markov random fields

Abstract

In this thesis we present an approximate recursive algorithm for calculations of discrete Markov random fields defined on graphs. We write the probability distribution of a Markov random field as a function of interaction parameters, a representation well suited for approximations. The algorithm we establish is a forward-backward algorithm, where the forward part recursively decomposes the probability distribution into a product of conditional distributions. Next we establish two different backward parts to our algorithm. In the first one we are able to simulate from the probability distribution, using the decomposed system. The second one enables us to calculate the marginal distributions for all the nodes in the Markov random field. All the approximations in our algorithm are controlled by a positive parameter, and when this parameter is equal to 0, our algorithm is by definition an exact algorithm. We investigate the performance of our algorithm by the CPU time, and by evaluating the quality of the approximations in various ways. As an example of the usage of our algorithm, we estimate an unknown picture from a degenerated version, using the marginal posterior mode estimate. This is a classical Bayesian problem.