Markov Random FieldsOpen in Colab
ML project loop
Data·Hypothesis space·Objective·Optimization·Evaluation·Deployment feedback

Markov Random Fields

Bayesian Networks use directed arrows to express causation. But some relationships are symmetric (neighboring pixels in an image tend to share a color, adjacent words tend to agree in tag) with no natural "cause." A Markov Random Field (MRF), or undirected graphical model, captures these mutual influences with undirected edges and potential functions.

Real-world examples: Image denoising and segmentation, the Ising model in physics, conditional random fields for named-entity recognition and POS tagging, social network analysis.

Undirected, factor-based

An MRF factorizes the joint over cliques (fully-connected subsets of nodes) rather than over parent–child conditionals:

P(X1,…,Xn)=1Z∏c∈Cψc(Xc)P(X_1, \dots, X_n) = \frac{1}{Z} \prod_{c \in \mathcal{C}} \psi_c(X_c)
  • ψc(Xc)≥0\psi_c(X_c) \ge 0 — a potential function scoring how "compatible" the values in clique cc are (higher = more agreeable). Unlike a CPT, it need not be a probability.
  • Z=∑x∏cψc(xc)Z = \sum_{\mathbf{x}} \prod_c \psi_c(\mathbf{x}_c) — the partition function, normalizing everything to sum to 1.

Intuition

Potentials vote on configurations. A pairwise potential ψ(xi,xj)\psi(x_i, x_j) that is large when xi=xjx_i = x_j says "these two neighbors like to agree." The joint distribution favors global configurations where many local votes are satisfied — exactly the right model for "smooth" structures like images.

Directed vs undirected

Bayesian NetworkMarkov Random Field
EdgesDirected (causal)Undirected (symmetric)
Local factorP(Xi∣Parents)P(X_i \mid \text{Parents}): normalizedψc(Xc)\psi_c(X_c): unnormalized
NormalizationAutomatic (CPTs sum to 1)Global ZZ needed
Independence testd-separation (colliders tricky)Simple graph separation
Natural fitCausal / generative storiesSpatial / relational symmetry

Cleaner independence

MRF independence is refreshingly simple: XA⊥XB∣XSX_A \perp X_B \mid X_S whenever removing the nodes in SS disconnects AA from BB in the graph. No collider exceptions — undirected separation is just "is the path cut?"

The partition function: the hard part

ZZ sums over all joint configurations — 2n2^n of them for nn binary nodes. This single quantity makes MRFs harder to work with than Bayesian Networks:

  • You can often evaluate unnormalized scores P~(x)=∏cψc\tilde P(\mathbf{x}) = \prod_c \psi_c easily.
  • But probabilities, the gradient of the log-likelihood (which needs ∇log⁡Z\nabla \log Z), and marginals all require ZZ or its expectations — generally intractable.

This is why MRF learning leans on approximations: contrastive divergence, pseudo-likelihood, or sampling.

Worked example: a 2-node Ising-style MRF

Two binary spins X1,X2∈{−1,+1}X_1, X_2 \in \{-1, +1\} that prefer to align. Edge potential ψ(x1,x2)=e βx1x2\psi(x_1, x_2) = e^{\,\beta x_1 x_2} with coupling β=1\beta = 1:

x1x_1x2x_2x1x2x_1 x_2ψ=ex1x2\psi = e^{x_1 x_2}
+1+1+1e1=2.72e^{1} = 2.72
−1−1+1e1=2.72e^{1} = 2.72
+1−1−1e−1=0.37e^{-1} = 0.37
−1+1−1e−1=0.37e^{-1} = 0.37

Z=2.72+2.72+0.37+0.37=6.18Z = 2.72 + 2.72 + 0.37 + 0.37 = 6.18. So P(aligned)=2.72/6.18=0.44P(\text{aligned}) = 2.72/6.18 = 0.44 each, P(disagree)=0.37/6.18=0.06P(\text{disagree}) = 0.37/6.18 = 0.06 each. The model puts 0.880.88 total mass on the two aligned states — exactly the "neighbors agree" prior.

Python
import numpy as np

beta = 1.0
states = [(+1,+1), (-1,-1), (+1,-1), (-1,+1)]
psi = np.array([np.exp(beta * a * b) for a, b in states])
Z = psi.sum()
for (a, b), p in zip(states, psi / Z):
    print(f"x1={a:+d}, x2={b:+d}: P = {p:.3f}")
print("P(aligned) =", (psi[0] + psi[1]) / Z)

Gibbs / Boltzmann form

Potentials are usually written as exponentiated energies, giving the Gibbs (Boltzmann) distribution. An energy function E(x)E(\mathbf{x}) is a scalar cost assigned to each configuration — high energy means the configuration is "unlikely," low energy means it is "favored." This is the opposite convention from probability, borrowed from statistical physics:

P(x)=1Zexp⁡ ⁣(−E(x)),E(x)=∑cEc(xc)P(\mathbf{x}) = \frac{1}{Z}\exp\!\big(-E(\mathbf{x})\big), \qquad E(\mathbf{x}) = \sum_c E_c(\mathbf{x}_c)

Low energy = high probability. This connects MRFs to statistical physics (the Ising model) and to energy-based models in deep learning (Hopfield nets, Boltzmann machines).

Image denoising

A noisy binary image is the textbook MRF. Each pixel xi∈{−1,+1}x_i \in \{-1, +1\} has an observed (noisy) value yiy_i. The energy function is:

E(x)=−η∑{i,j}∈Exixj  −  β∑iyixiE(\mathbf{x}) = -\eta \sum_{\{i,j\} \in \mathcal{E}} x_i x_j \;-\; \beta \sum_i y_i x_i
  • Smoothness term −η∑{i,j}xixj-\eta \sum_{\{i,j\}} x_i x_j: assigns low energy when neighbouring pixels agree (xi=xjx_i = x_j → product +1+1). Larger η\eta = stronger smoothing.
  • Data term −β∑iyixi-\beta \sum_i y_i x_i: assigns low energy when each pixel matches its observed noisy value. Larger β\beta = more faithful to the noisy input.

The denoised image is arg⁡min⁡xE(x)\arg\min_\mathbf{x} E(\mathbf{x}). Work out when flipping one pixel pays: if dd of its 4 neighbours disagree with the observation yiy_i, flipping xix_i away from yiy_i changes the energy by ΔE=2η(4−2d)+2β\Delta E = 2\eta(4 - 2d) + 2\beta. With η=1.0,β=2.0\eta=1.0, \beta=2.0 that is ΔE=12−4d\Delta E = 12 - 4d: at d=3d = 3 the smoothness and data terms exactly tie (ΔE=0\Delta E = 0), and only a pixel contradicted by all four neighbours (d=4d = 4, ΔE=−4\Delta E = -4) is strictly corrected — otherwise the data term wins.

Step through both the greedy and the sampling version:

ICM and Gibbs — the denoiser the lesson's parameters do not build

1/6

A binary image and a noisy observation of it: every pixel was flipped independently with probability 15%, giving an observed error rate of 14.2%. Red marks a pixel that disagrees with the truth. The MRF prior says neighbouring pixels like to agree, and the data term says each pixel should resemble what was observed — so denoising is a fight between those two, and the ratio η/β decides who wins.

python
1# E(x) = -eta * sum_ij x_i x_j
2# - beta * sum_i y_i x_i
3
4for sweep in range(n_sweeps):
5 for i in pixels:
6
7 # local energy of each label
8 nb = sum(x[j] for j in neigh(i))
9 dE = 2*eta*nb + 2*beta*y[i]
10
11 if method == "icm":
12 # greedy: take the better one
13 x[i] = +1 if dE > 0 else -1
14 else:
15 # Gibbs: sample it
16 p = sigmoid(dE / temp)
17 x[i] = +1 if rand() < p else -1
state
the observation y (14.2% wrong)
setup
image → 20×20flip probability → 15%observed error → 14.2%E(y) → -1150

The lesson's image-denoising MRF, run. Its ΔE = 12 − 4d derivation is confirmed exactly, and then its consequence is measured: at η = 1, β = 2 only a pixel contradicted by all four neighbours is ever corrected, so ICM removes almost none of the noise. Sweeping η/β shows a clean U with the lesson's setting far up the wrong side of it. The second payoff runs three optimisers on the same energy — greedy ICM, Gibbs at T = 1, and annealed Gibbs — and the Gibbs result is the interesting one: it is worse on both energy and error, because sampling from exp(−E) is a different job from minimising E.

What to notice:

  • Frame 3: the d=3d=3 tie is a live defect, not a boundary case. ICM reaches its final energy after one sweep and never moves again, yet the error keeps drifting 4.5% → 5.5% over later sweeps. ΔE\Delta E is exactly zero for those pixels, so the tie-break flips them back and forth for free: converged in energy, still wandering in image space, and getting slightly worse.
  • Frame 4: the parameters above are not the good ones. Sweeping η/β\eta/\beta (with β\beta fixed), η/β=0.5\eta/\beta = 0.5 gives 5.8% error against 2.3% at η/β≥1\eta/\beta \ge 1. The ΔE=12−4d\Delta E = 12 - 4d derivation is correct; what it hides is that "only d=4d=4 corrects" describes a model tuned almost entirely toward the data term.
  • Frame 6: sampling and optimization are different jobs. Gibbs at T=1T=1 reaches worse energy and error than greedy ICM. That is not a failure: Gibbs draws from exp⁡(−E)\exp(-E), and a typical draw from a distribution is not its mode. Annealing narrows the gap but, on this landscape, still does not beat ICM.

One expected result the trace could not reproduce: there is no over-smoothing arm. Error plateaus at 2.3% and stays flat out to η/β=40\eta/\beta = 40, because this test image is genuinely piecewise-constant with thick regions — the prior's assumption is true, so more of it never costs anything. An image with one-pixel-wide detail would show the other side of that curve.

Exact minimization is NP-hard for general graphs. Graph cuts find the global optimum in polynomial time for binary MRFs with submodular pairwise potentials (the image denoising case qualifies). Loopy belief propagation is an approximate iterative method for higher-order or non-submodular cases.

Conditional Random Fields (CRFs)

A CRF is the discriminative cousin: it models P(y∣x)P(\mathbf{y} \mid \mathbf{x}) directly (labels given inputs) instead of the full joint. By conditioning on x\mathbf{x}, it sidesteps modeling the inputs and is the standard for sequence labeling (NER, POS) — often stacked on top of an LSTM or Transformer to enforce valid label transitions.

Z is why MRFs are hard

Almost every MRF difficulty traces back to the partition function ZZ. Evaluating a configuration's relative probability is cheap; getting an absolute probability or a likelihood gradient is not. Plan for approximate inference from the start.

Exercise

What makes the partition function Z hard to compute in a Markov Random Field?

Need a hint?

Think about how many joint configurations it sums over.

Exercise

When is a Markov Random Field (undirected) a more natural choice than a Bayesian Network (directed)?

Need a hint?

Think about symmetric vs causal relationships.

Exercise

How do MRF potential functions ψ differ from the conditional probability tables in a Bayesian Network?

Need a hint?

Are potentials required to be valid probabilities?

Common mistakes

  1. Treating potentials as probabilities: they're unnormalized scores; only the product over cliques, divided by ZZ, is a distribution.
  2. Ignoring ZZ's dependence on parameters: when learning, ZZ changes with the potentials; you cannot treat it as constant.
  3. Forcing direction onto symmetric relations: if there's no causal story, an undirected MRF is the honest model.

Key takeaways

  • MRFs use undirected edges and potential functions over cliques.
  • The partition function ZZ normalizes, and makes learning/inference hard.
  • Independence is simple graph separation; no collider exceptions.
  • CRFs are the discriminative cousin for sequence labeling.

Related concepts

Concept neighbourhood

How this concept connects — click any node to jump there, or explore the whole concept map.

Builds onRelated
Markov Random FieldsProbabilistic Models & EMProbability & StatisticsBayesian NetworksHidden Markov Models