Hammersley–Clifford theorem

The Hammersley–Clifford theorem is a result in probability theory, mathematical statistics and statistical mechanics, that gives necessary and sufficient conditions under which a positive probability distribution can be represented as a Markov network (also known as a Markov random field). It is the fundamental theorem of random fields.^[1] It states that a probability distribution that has a positive mass or density satisfies one of the Markov properties with respect to an undirected graph G if and only if it is a Gibbs random field, that is, its density can be factorized over the cliques (or complete subgraphs) of the graph.

The relationship between Markov and Gibbs random fields was initiated by Roland Dobrushin^[2] and Frank Spitzer^[3] in the context of statistical mechanics. The theorem is named after John Hammersley and Peter Clifford who proved the equivalence in an unpublished paper in 1971.^[4][5] Simpler proofs using the inclusion-exclusion principle were given independently by Geoffrey Grimmett,^[6] Preston^[7] and Sherman^[8] in 1973, with a further proof by Julian Besag in 1974.^[9]

Proof Outline

It is a trivial matter to show that a Gibbs random field satisfies every Markov property.

To establish that every positive probability distribution that satisfies the local Markov property is also a Gibbs random field, the following lemma, which provides a means for combining different factorizations, needs to be proven:

Lemma 1

Let $U$ denote the set of all random variables under consideration, and let ${\displaystyle \Theta ,\Phi _{1},\Phi _{2},\dots ,\Phi _{n}\subseteq U}$ and ${\displaystyle \Psi _{1},\Psi _{2},\dots ,\Psi _{m}\subseteq U}$.

If

${\displaystyle \Pr(U)=f(\Theta )\prod _{i=1}^{n}g_{i}(\Phi _{i})=\prod _{j=1}^{m}h_{j}(\Psi _{j})}$

for functions ${\displaystyle f,g_{1},g_{2},\dots g_{n}}$ and ${\displaystyle h_{1},h_{2},\dots ,h_{m}}$, then there exist functions ${\displaystyle h'_{1},h'_{2},\dots ,h'_{m}}$ and ${\displaystyle g'_{1},g'_{2},\dots ,g'_{n}}$ such that

${\displaystyle \Pr(U)={\bigg (}\prod _{j=1}^{m}h'_{j}(\Theta \cap \Psi _{j}){\bigg )}{\bigg (}\prod _{i=1}^{n}g'_{i}(\Phi _{i}){\bigg )}}$

Proof of Lemma 1

Let ${\bar {\theta }}$ be an arbitrary assignment to the variables from ${\displaystyle U\setminus \Theta }$. For an arbitrary set of variables $X$, let ${\displaystyle {\bar {\theta }}[X]}$ denote the assignment ${\bar {\theta }}$ restricted to the variables from $X$. It is then the case that

${\displaystyle \Pr(U)={\bigg (}f(\Theta )\prod _{i=1}^{n}g_{i}(\Phi _{i}\cap \Theta ,{\bar {\theta }}[\Phi _{i}]){\bigg )}{\bigg (}\prod _{i=1}^{n}{\frac {g_{i}(\Phi _{i})}{g_{i}(\Phi _{i}\cap \Theta ,{\bar {\theta }}[\Phi _{i}])}}{\bigg )}}$

Let ${\displaystyle f'(\Theta )=f(\Theta )\prod _{i=1}^{n}g_{i}(\Phi _{i}\cap \Theta ,{\bar {\theta }}[\Phi _{i}])}$ and ${\displaystyle g'_{i}(\Phi _{i})={\frac {g_{i}(\Phi _{i})}{g_{i}(\Phi _{i}\cap \Theta ,{\bar {\theta }}[\Phi _{i}])}}}$ for each $i = 1, 2, \dots, n$ so

${\displaystyle \Pr(U)=f'(\Theta )\prod _{i=1}^{n}g'_{i}(\Phi _{i})=\prod _{j=1}^{m}h_{j}(\Psi _{j})}$

hence

${\displaystyle \Pr(\Theta ,{\bar {\theta }})=f'(\Theta )\prod _{i=1}^{n}g'_{i}(\Phi _{i}\cap \Theta ,{\bar {\theta }}[\Phi _{i}])=\prod _{j=1}^{m}h_{j}(\Psi _{j}\cap \Theta ,{\bar {\theta }}[\Psi _{j}])}$

Since ${\displaystyle g'_{i}(\Phi _{i}\cap \Theta ,{\bar {\theta }}[\Phi _{i}])=1}$,

${\displaystyle f'(\Theta )=\prod _{j=1}^{m}h_{j}(\Psi _{j}\cap \Theta ,{\bar {\theta }}[\Psi _{j}])}$

Letting ${\displaystyle h'_{j}(\Theta \cap \Psi _{j})=h_{j}(\Psi _{j}\cap \Theta ,{\bar {\theta }}[\Psi _{j}])}$ finally gives:

${\displaystyle \Pr(U)={\bigg (}\prod _{j=1}^{m}h'_{j}(\Theta \cap \Psi _{j}){\bigg )}{\bigg (}\prod _{i=1}^{n}g'_{i}(\Phi _{i}){\bigg )}}$

End of Lemma 1

Lemma 1 provides a means of combining two different factorizations of ${\displaystyle \Pr(U)}$. The local Markov property implies that for any random variable $x\in U$, that there exists factors $f_{x}$ and ${\displaystyle f_{-x}}$ such that:

${\displaystyle \Pr(U)=f_{x}(x,\delta x)f_{-x}(U\setminus \{x\})}$

where $\delta x$ are the neighbors of node $x$. Applying Lemma 1 repeatedly eventually factors ${\displaystyle \Pr(U)}$ into a product of clique potentials.

End of Proof

See also

• Markov random field
• Conditional random field

Notes

1. Lafferty, John D.; Mccallum, Andrew (2001). "Conditional Random Fields: Probabilistic Models for Segmenting and Labeling Sequence Data". ICML. Retrieved 14 December 2014. by the fundamental theorem of random fields (Hammersley & Clifford, 1971)
2. Dobrushin, P. L. (1968), "The Description of a Random Field by Means of Conditional Probabilities and Conditions of Its Regularity", Theory of Probability and its Applications, 13 (2): 197–224, doi:10.1137/1113026
3. Spitzer, Frank (1971), "Markov Random Fields and Gibbs Ensembles", The American Mathematical Monthly, 78 (2): 142–154, doi:10.2307/2317621, JSTOR 2317621
4. Hammersley, J. M.; Clifford, P. (1971), Markov fields on finite graphs and lattices (PDF)
5. Clifford, P. (1990), "Markov random fields in statistics", in Grimmett, G.R.; Welsh, D.J.A., Disorder in Physical Systems: A Volume in Honour of John M. Hammersley, Oxford University Press, pp. 19–32, ISBN 0-19-853215-6, MR 1064553, retrieved 2009-05-04
6. Grimmett, G. R. (1973), "A theorem about random fields", Bulletin of the London Mathematical Society, 5 (1): 81–84, doi:10.1112/blms/5.1.81, MR 0329039
7. Preston, C. J. (1973), "Generalized Gibbs states and Markov random fields", Advances in Applied Probability, 5 (2): 242–261, doi:10.2307/1426035, JSTOR 1426035, MR 0405645
8. Sherman, S. (1973), "Markov random fields and Gibbs random fields", Israel Journal of Mathematics, 14 (1): 92–103, doi:10.1007/BF02761538, MR 0321185
9. Besag, J. (1974), "Spatial interaction and the statistical analysis of lattice systems", Journal of the Royal Statistical Society, Series B, 36 (2): 192–236, JSTOR 2984812, MR 0373208

Further reading

• Bilmes, Jeff (Spring 2006), Handout 2: Hammersley–Clifford (PDF), course notes from University of Washington course.
• Grimmett, Geoffrey, Probability on Graphs, Chapter 7
• Langseth, Helge, The Hammersley–Clifford Theorem and its Impact on Modern Statistics (PDF)