next up previous index
Next: Normalized and Canonical Forms Up: Markov Random Fields Previous: Gibbs Random Fields


Markov-Gibbs Equivalence


An MRF is characterized by its local property (the Markovianity) whereas a GRF is characterized by its global property (the Gibbs distribution). The Hammersley-Clifford theorem   [Hammersley and Clifford 1971] establishes the equivalence of these two types of properties. The theorem states that F is an MRF on with respect to if and only if F is a GRF on with respect to .   Many proofs of the theorem exist, e.g. in [Besag 1974 ; Moussouris 1974 ; Kindermann and Snell 1980].

A proof that a GRF is an MRF is given as follows. Let be a Gibbs distribution on with respect to the neighborhood system . Consider the conditional probability

where is any configuration which agrees with f at all sites except possibly i. Writing out gives (This also provides a formula for calculating the conditional probability from potential functions.)

Divide into two set and with consisting of cliques containing i and cliques not containing i. Then the above can be written as

Because for any clique c that does not contain i, cancels from both the numerator and denominator. Therefore, this probability depends only on the potentials of the cliques containing i,

that is, it depends on labels at i's neighbors. This proves that a Gibbs random field is a Markov random field. The proof that an MRF is a GRF is much more involved; a result to be described in the next subsection, which is about the unique GRF representation [Griffeath 1976], provides such a proof.

The practical value of the theorem is that it provides a simple way of specifying the joint probability. One can specify the joint probability by specifying the clique potential functions and chooses appropriate potential functions for desired system behavior. In this way, he encodes the a priori knowledge or preference about interactions between labels.

How to choose the forms and parameters of the potential functions for a proper encoding of constraints is a major topic in MRF modeling. The forms of the potential functions determine the form of the Gibbs distribution. When all the parameters involved in the potential functions are specified, the Gibbs distribution is completely defined. Defining the functional forms is the theme in Chapters 2 -- 5 while estimating parameters is the subject in Chapters 6 and 7.

To calculate the joint probability of an MRF, which is a Gibbs distribution, it is necessary to evaluate the partition function ( 1.25). Because it is the sum over a combinatorial number of configurations in , the computation is usually intractable. The explicit evaluation can be avoided in maximum-probability based MRF vision models when contains no unknown parameters, as we will see subsequently. However, this is not true when the parameter estimation is also a part of the problem. In the latter case, the energy function is also a function of parameters and so is the partition function . The evaluation of is required. To circumvent the formidable difficulty therein, the joint probability is often approximated in practice. Several approximate formulae will be introduced in Chapter 6 where the problem of MRF parameter estimation is the subject.

next up previous index
Next: Normalized and Canonical Up: Markov Random Fields Previous: Gibbs Random Fields