Markov Consistency

The luxury of employing local conditional PDFs--locality is defined by the neighborhood system $\mathcal{N}$--to make the statistical analysis tractable, demands a price. Besag's seminal paper [14] states that Hammersely and Clifford, in their unpublished work of 1971, found that these conditional PDFs must conform to specific functional forms, namely the Gibbs PDFs, in order to give a consistent structure to entire system; a consistent system is one where we can obtain each conditional PDF, $P (X_t \vert {\bf y}_t)$ ( $\forall t \in \mathcal{T}, \forall {\bf y}_t \in \Re^{\vert\mathcal{N}_t\vert}$) via rules of probabilistic inference from the joint PDF $P ({\bf X})$ of all the RVs in the system. Besag, later in 1974 [14], published the theorem and gave an elegant mathematical proof of the equivalence between the consistent Markov PDFs and Gibbs PDFs [14]. The consistency theorem is known as the Hammersely-Clifford theorem, or the MRF-Gibbs equivalence theorem. It states that every MRF is equivalent to a Gibbs random field (GRF) [14,99]. We define the GRF next.

The definition of a GRF requires the notion of a clique. A clique $c$, associated with a neighborhood system $\mathcal{N}$, is a subset of the index set $\mathcal{T}$ such that it either comprises a single index $c = \{ t \}$ or a set of indices where each each index is a neighbor of every other index. Let us call $\mathcal{C}_m$ as the set of all cliques comprising $m$ indexes. Then,

$$\mathcal{C}_1 = \{ \{ t \} \vert t \in \mathcal{T} \},$$ (73)

$$\mathcal{C}_2 = \{ \{ t_1, t_2 \} \vert t_1 \in \mathcal{T}, t_2 \in \mathcal{T}, t_2 \in \mathcal{N}_{t_1} \},$$ (74)

$$\mathcal{C}_3 = \{ \{ t_1, t_2, t_3 \} \vert t_1 \in \mathcal{T}, t_2 \in \mathca... ...\in \mathcal{N}_{t_1}, t_3 \in \mathcal{N}_{t_1}, t_3 \in \mathcal{N}_{t_2} \},$$ (75)

and so on. The collection of all cliques for the neighborhood system $\mathcal{N}$ is

$$\mathcal{C} = \mathcal{C}_1 \cup \mathcal{C}_2 \cup \mathcal{C}_3 \cup \ldots \cup \mathcal{C}_{\vert\mathcal{T}\vert},$$ (76)

where the $\vert\cdot\vert$ operator gives the cardinality of sets. Figure 2.9 shows all possible clique types for a 3-pixel $\times$ 3-pixel square neighborhood system depicted in Figure 2.8.

Figure 2.9: All possible clique types for a 3-pixel $\times$ 3-pixel square neighborhood system in Figure 2.8. The four rows (top to bottom) show cliques of types $\mathcal{C}_1$, $\mathcal{C}_2$, $\mathcal{C}_3$, and $\mathcal{C}_4$, respectively.

A GRF is a random field whose joint PDF is

$$P ({\bf x}) = \frac {1} {\eta} \exp \Bigg( - \frac {U ({\bf x})} {\tau} \Bigg),$$ (77)

where $\tau$ is the temperature,

$$U ({\bf x}) = \sum_{c \in \mathcal{C}} V_c ({\bf x})$$ (78)

is the energy function, $V_c (\cdot)$ is an arbitrary clique-potential function, and

$$\eta = \int_{{\bf x}} \exp \Bigg( - \frac {U ({\bf x})} {\tau} \Bigg) d{\bf x}$$ (79)

is the partition function. The temperature $\tau$ controls the probabilities--at high $\tau$ every instance ${\bf x}$ is almost equally probable, but at low values of $\tau$ it is the clique potentials that dictate the probabilities.