In many real world phenomena, it is hard to determine the exact directionality of interaction between random variables, thus, Bayesian networks might not be the best choice to model such systems.

Instead, Markov Random Fields (MRFs) are described by undirected graphs and they also encode a factorization (a set of conditional independence relationships).

MRFs are often useful for modeling mutual relationships of compatibility among variables and in imaging and spatial applications.

MRFs (also) allow to graphically assess conditional independence properties by simple separation

Consider the MRF in Figure 2, the corresponding joint distribution is given by, $$ \begin{align*} p(\mathbf{x}) & = \frac{1}{Z} \prod_c \psi_c(\mathbf{\mathsf{x}}_c) \newline & = \frac{1}{Z} \psi_1(x_1, x_2, x_3) \psi_2(x_3, x_4, x_5) \psi_3(x_5, x_6) \end{align*} $$

So we have seen that MRFs allow us to easily assess the conditional independence properties (graph separation) and a factorization of the joint distribution.

But how do we connect conditional independence and factorization?

For the graph to represent conditional independence, $\psi_c(\mathbf{\mathsf{x}}_c) > 0$

Let $\mathcal{U}_I$ be the set of distributions $p(\mathbf{x})$ consistent with conditional independencies encoded by the graph structure. Let $\mathcal{U}_F$ be the set of distributions $p(\mathbf{x})$ that factorize as, $$ p(\mathbf{x}) = \frac{1}{Z} \prod_c \psi_c(\mathbf{\mathsf{x}}_c) $$

But how do we ensure that $\psi_c(\mathbf{\mathsf{x}}_c) > 0$?

Given a noisy image ($\mathbf{y}$), recover the original noise-free image ($\mathbf{x}$).

We can encode images using an array representing numerical values of pixles. Pixels take on values $+1, -1, x_i \in \{+1, -1\}$ (black and white). $\{y_i\}$ are the distorted version of $\{x_i\}$.

For graphical models we need to make some assumptions.

1. Neighboring (noiseless) pixels are strongly correlated (i.e., similar in value).

2. Noise acts independently on each pixel.

3. If the noise level is low, there should be a strong correlation between $x_i$ and $y_i$.

Further, there are two types of cliques $$\{x_i, x_j\}$$ and $$\{x_i, y_i\}$$, i.e., neighboring pixels and corresponding noisy pixels. Thus, factorization can be written as, $$ p(\mathbf{x}, \mathbf{y}) = \frac{1}{Z} \prod_{i \sim j} \psi_{i, j}(x_i, x_j) \prod_i \psi_i(x_i, y_i) $$ We will assume that $\mathsf{x}_i, \mathsf{y}_i \in \{+1, -1\}$ (Ising model) ²

The cliques $\{x_i, y_i\}$ and its corresponding energy $E(x_i, y_i)$ expresses the correlation between $\mathsf{x}_i$ and $\mathsf{y}_i$, $$ E(x_i, y_i) = -\eta x_i, y_i, \quad \eta > 0 \quad \implies \psi_i(x_i, y_i) = \exp(\eta x_i y_i) $$ The cliques $\{x_i, x_j\}$, $$ E(x_i, x_j) = -\beta x_i x_j, \quad \beta > 0 \quad \implies \psi_{i, j}(x_i, x_j) = \exp(\beta x_i x_j) $$ Further, an energy term $hx_i$ is often added for each pixel $i$ of $\mathbf{x}$ to biasing the model towawrd pixel values of a particular color (black or white), $$ p(\mathbf{x}, \mathbf{y}) = \frac{1}{Z} \prod_i \psi_i(x_i) \prod_{i \sim j} \psi_{i, j}(x_i, x_j) \prod_i \psi_i(x_i, y_i) $$ where $\psi_i(x_i) = \exp(-E(x_i)) = \exp(-h x_i)$. Thus, equivalently, $$ p(\mathbf{x}, \mathbf{y}) = \frac{1}{Z} \exp\left(-h \sum_i x_i + \beta \sum_{i, j} x_i x_j + \eta \sum_i x_i y_i\right) $$ Thus, connecting back to our original goal, this corresponds to maximizing, $$ p(\mathbf{x} \mid \mathbf{y}) \propto \exp\left(-h \sum_i x_i + \beta \sum_{i, j} x_i x_j + \eta \sum_i x_i y_i\right) = \exp(-E(\mathbf{x} \mid \mathbf{y})) $$

Bayesian networks and MRFs encode different types of statistical dependencies. A Bayesian network captures statistical dependencies while a MRF captures the mutal compatibility among variables.

Thus, independencies captured by a Bayesian network cannot always be captured by a MRF.

The Bayesian network with factorization, $$ p(\mathbf{x}) = \prod_{k=1}^{K} p(\mathsf{x}_k \mid \mathsf{x}_{\mathcal{P}(\mathsf{x}_k)}) $$ Defining, $$ \psi_k(\mathsf{x}_k, \mathsf{x}_{\mathcal{P}(\mathsf{x}_k)}) = p(\mathsf{x}_k \mid \mathsf{x}_{\mathcal{P}(\mathsf{x}_k)}) $$ we can obtain, $$ p(\mathbf{x}) = \frac{1}{Z} \prod_{k=1}^{K} \psi_k(\mathsf{x}_k, \mathsf{x}_{\mathcal{P}(\mathsf{x}_k)}) $$ Thus, to convert a Bayesian network to a MRF, we connect all pairs of parents by an undirected edge and make all edges undirected.