Questions: Markov Random Fields

Question 1

You are modeling whether neighboring pixels in a photograph should have similar colors. Which representation is most natural, and why?

• A. A Bayesian network, because pixel A causes pixel B to have a similar color
• B. A Markov random field, because the dependency between neighbors is symmetric — neither pixel causes the other
• C. A hidden Markov model, because pixels form a sequence across rows
• D. A naive Bayes classifier, because each pixel's color is conditionally independent of all others

Answer: (B)

Pixel dependencies in an image are symmetric: pixel A's value influences pixel B's, and B's influences A's equally — there is no causal direction. Bayesian networks require directed edges and encode causal stories ('A causes B'), which is unnatural here. MRFs use undirected edges that simply state 'these two are directly related,' exactly capturing the bidirectional smoothness prior. HMMs model sequential dependencies along a chain, not a 2D spatial grid. Naive Bayes assumes complete independence, which is the opposite of what we want.

Question 2

In a Markov random field, what is the role of the partition function Z?

• A. It counts the number of cliques in the graph
• B. It normalizes the product of potential functions so the result is a valid probability distribution summing to 1
• C. It stores the marginal probability of each variable
• D. It measures how much the graph structure deviates from a tree

Answer: (B)

Potential functions assign non-negative scores to clique configurations but are not themselves probabilities — their product can be any positive number. The partition function Z is the sum of these products over all possible configurations of all variables; dividing by Z normalizes the distribution so it sums (or integrates) to 1, making it a valid probability distribution. Computing Z exactly is the main reason inference is intractable: it requires summing over an exponential number of configurations.

Question 3

In a Markov random field, a variable is conditionally independent of all non-neighboring variables given the values of its immediate neighbors.

• T. True
• F. False

Answer: True

This is the defining local Markov property of an MRF. Given all of a variable's neighbors, knowing the values of variables further away in the graph adds no information about the variable's distribution. This property is what makes local inference algorithms like Gibbs sampling practical: to sample a new value for a variable, you only need to look at its neighborhood, not the entire graph. The Hammersley-Clifford theorem proves this Markov property is equivalent to the clique-factorization structure of the joint distribution.

Question 4

Potential functions in an MRF are probability distributions — each potential function should be non-negative and sum to 1 over its clique's configurations.

• T. True
• F. False

Answer: False

Potential functions are not probability distributions and have no normalization requirement. They are arbitrary non-negative functions that encode compatibility (how 'good' a particular assignment of values to a clique is) — they can take any positive real value. The full joint distribution is proportional to the product of all potential functions, and the partition function Z provides the global normalization. Confusing potentials with probabilities is a common source of confusion when first working with MRFs.

Question 5

Why is exact inference in a Markov random field generally intractable, and what structural property of the graph enables exact inference in special cases?

Model answer: Exact inference requires computing marginal probabilities, which involves the partition function Z — the sum of the unnormalized joint distribution over all possible configurations of all variables. With n binary variables, this sum has 2^n terms, making it exponential in the number of variables. Exact inference is tractable only when the graph is a tree (or can be converted to one via junction tree methods), because trees have no loops, allowing messages to propagate exactly from leaves to root without double-counting. Belief propagation is exact on trees and becomes approximate (loopy belief propagation) on graphs with cycles.

The hardness of inference in MRFs is one of the central challenges of probabilistic graphical models. The exponential partition function is the culprit: even evaluating the probability of a single configuration requires knowing Z, which is a sum over all configurations. Trees are the exception because their acyclic structure allows a dynamic programming decomposition that computes marginals in polynomial time. Most real problems involve graphs with loops (images, protein contact maps, spatial grids), where approximate methods — belief propagation, variational inference, MCMC — are essential.