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:
- — a potential function scoring how "compatible" the values in clique are (higher = more agreeable). Unlike a CPT, it need not be a probability.
- — the partition function, normalizing everything to sum to 1.
Intuition
Potentials vote on configurations. A pairwise potential that is large when 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 Network | Markov Random Field | |
|---|---|---|
| Edges | Directed (causal) | Undirected (symmetric) |
| Local factor | : normalized | : unnormalized |
| Normalization | Automatic (CPTs sum to 1) | Global needed |
| Independence test | d-separation (colliders tricky) | Simple graph separation |
| Natural fit | Causal / generative stories | Spatial / relational symmetry |
Cleaner independence
MRF independence is refreshingly simple: whenever removing the nodes in disconnects from in the graph. No collider exceptions — undirected separation is just "is the path cut?"
The partition function: the hard part
sums over all joint configurations — of them for binary nodes. This single quantity makes MRFs harder to work with than Bayesian Networks:
- You can often evaluate unnormalized scores easily.
- But probabilities, the gradient of the log-likelihood (which needs ), and marginals all require 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 that prefer to align. Edge potential with coupling :
| +1 | +1 | +1 | |
| −1 | −1 | +1 | |
| +1 | −1 | −1 | |
| −1 | +1 | −1 |
. So each, each. The model puts total mass on the two aligned states — exactly the "neighbors agree" prior.
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 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:
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 has an observed (noisy) value . The energy function is:
- Smoothness term : assigns low energy when neighbouring pixels agree ( → product ). Larger = stronger smoothing.
- Data term : assigns low energy when each pixel matches its observed noisy value. Larger = more faithful to the noisy input.
The denoised image is . Work out when flipping one pixel pays: if of its 4 neighbours disagree with the observation , flipping away from changes the energy by . With that is : at the smoothness and data terms exactly tie (), and only a pixel contradicted by all four neighbours (, ) 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
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.
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 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. 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 (with fixed), gives 5.8% error against 2.3% at . The derivation is correct; what it hides is that "only corrects" describes a model tuned almost entirely toward the data term.
- Frame 6: sampling and optimization are different jobs. Gibbs at reaches worse energy and error than greedy ICM. That is not a failure: Gibbs draws from , 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 , 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 directly (labels given inputs) instead of the full joint. By conditioning on , 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 . 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
- Treating potentials as probabilities: they're unnormalized scores; only the product over cliques, divided by , is a distribution.
- Ignoring 's dependence on parameters: when learning, changes with the potentials; you cannot treat it as constant.
- 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 normalizes, and makes learning/inference hard.
- Independence is simple graph separation; no collider exceptions.
- CRFs are the discriminative cousin for sequence labeling.
Related concepts
- Bayesian Networks: the directed counterpart
- Hidden Markov Models: a tractable sequence model