Teorema de Hammersley-Clifford

El teorema de Hammersley-Clifford es un resultado en teoría de probabilidad , estadística matemática y mecánica estadística que da las condiciones necesarias y suficientes bajo las cuales una distribución de probabilidad estrictamente positiva (de eventos en un espacio de probabilidad ) ^{[ aclaración necesaria ]} puede ser representada como eventos generados por una red de Markov (también conocida como campo aleatorio de Markov ). Es el teorema fundamental de los campos aleatorios . ^[1] Establece que una distribución de probabilidad que tiene una masa o densidad estrictamente positiva satisface una de las propiedades de Markov con respecto a un grafo no dirigido G si y solo si es un campo aleatorio de Gibbs , es decir, su densidad puede factorizarse sobre los cliques (o subgrafos completos ) del grafo.

La relación entre los campos aleatorios de Markov y Gibbs fue iniciada por Roland Dobrushin ^[2] y Frank Spitzer ^[3] en el contexto de la mecánica estadística . El teorema recibe su nombre de John Hammersley y Peter Clifford, quienes demostraron la equivalencia en un artículo inédito en 1971. ^{[4] [5]} Geoffrey Grimmett , ^[6] Preston ^[7] y Sherman ^[8] dieron pruebas más simples de forma independiente utilizando el principio de inclusión-exclusión en 1973, con una prueba adicional de Julian Besag en 1974. ^[9]

Esquema de prueba

Una red de Markov simple para demostrar que cualquier campo aleatorio de Gibbs satisface todas las propiedades de Markov.

Es una cuestión trivial demostrar que un campo aleatorio de Gibbs satisface todas las propiedades de Markov . Como ejemplo de este hecho, véase lo siguiente:

En la imagen de la derecha, un campo aleatorio de Gibbs sobre el gráfico proporcionado tiene la forma . Si las variables y son fijas, entonces la propiedad global de Markov requiere que: (ver independencia condicional ), ya que forma una barrera entre y . ${\displaystyle \Pr(A,B,C,D,E,F)\propto f_{1}(A,B,D)f_{2}(A,C,D)f_{3}(C,D,F)f_{4}(C,E,F)}$ ${\displaystyle C}$ ${\displaystyle D}$ ${\displaystyle A,B\perp E,F|C,D}$ ${\displaystyle C,D}$ ${\displaystyle A,B}$ ${\displaystyle E,F}$

Con y constante, donde y . Esto implica que . ${\displaystyle C}$ ${\displaystyle D}$ ${\displaystyle \Pr(A,B,E,F|C=c,D=d)\propto [f_{1}(A,B,d)f_{2}(A,c,d)]\cdot [f_{3}(c,d,F)f_{4}(c,E,F)]=g_{1}(A,B)g_{2}(E,F)}$ ${\displaystyle g_{1}(A,B)=f_{1}(A,B,d)f_{2}(A,c,d)}$ ${\displaystyle g_{2}(E,F)=f_{3}(c,d,F)f_{4}(c,E,F)}$ ${\displaystyle A,B\perp E,F|C,D}$

Para establecer que toda distribución de probabilidad positiva que satisface la propiedad local de Markov es también un campo aleatorio de Gibbs, es necesario demostrar el siguiente lema, que proporciona un medio para combinar diferentes factorizaciones:

El lema 1 proporciona un medio para combinar factorizaciones como se muestra en este diagrama. Nótese que en esta imagen, se ignora la superposición entre conjuntos.

Lema 1

Sea α el conjunto de todas las variables aleatorias bajo consideración, y sea α el conjunto de variables arbitrarias. (Aquí, dado un conjunto arbitrario de variables α , α también denotará una asignación arbitraria a las variables de α ). ${\displaystyle U}$ ${\displaystyle \Theta ,\Phi _{1},\Phi _{2},\dots ,\Phi _{n}\subseteq U}$ ${\displaystyle \Psi _{1},\Psi _{2},\dots ,\Psi _{m}\subseteq U}$ ${\displaystyle X}$ ${\displaystyle X}$ ${\displaystyle X}$

Si

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

para las funciones y , entonces existen funciones y tales que ${\displaystyle f,g_{1},g_{2},\dots g_{n}}$ ${\displaystyle h_{1},h_{2},\dots ,h_{m}}$ ${\displaystyle h'_{1},h'_{2},\dots ,h'_{m}}$ ${\displaystyle g'_{1},g'_{2},\dots ,g'_{n}}$

${\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 )}}$

En otras palabras, proporciona una plantilla para una mayor factorización de . ${\displaystyle \prod _{j=1}^{m}h_{j}(\Psi _{j})}$ ${\displaystyle f(\Theta )}$

La camarilla formada por los vértices , , y , es la intersección de , , y . ${\displaystyle x_{1}}$ ${\displaystyle x_{2}}$ ${\displaystyle x_{3}}$ ${\displaystyle \{x_{1}\}\cup \partial x_{1}}$ ${\displaystyle \{x_{2}\}\cup \partial x_{2}}$ ${\displaystyle \{x_{3}\}\cup \partial x_{3}}$

El lema 1 proporciona un medio para combinar dos factorizaciones diferentes de . La propiedad local de Markov implica que para cualquier variable aleatoria , existen factores y tales que: ${\displaystyle \Pr(U)}$ ${\displaystyle x\in U}$ ${\displaystyle f_{x}}$ ${\displaystyle f_{-x}}$

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

¿Dónde están los vecinos del nodo ? La aplicación repetida del Lema 1 finalmente se convierte en un producto de potenciales de camarilla (ver la imagen de la derecha). ${\displaystyle \partial x}$ ${\displaystyle x}$ ${\displaystyle \Pr(U)}$

Fin de la prueba

Véase también

• Campo aleatorio de Markov
• Campo aleatorio condicional

Notas

1. Lafferty, John D.; Mccallum, Andrew (2001). "Campos aleatorios condicionales: modelos probabilísticos para segmentar y etiquetar datos de secuencias". Actas de la 18.ª Conferencia Internacional sobre Aprendizaje Automático (ICML-2001) . Morgan Kaufmann. ISBN 9781558607781. Recuperado el 14 de diciembre de 2014. por el teorema fundamental de campos aleatorios (Hammersley y Clifford 1971)
2. Dobrushin, PL (1968), "La descripción de un campo aleatorio por medio de probabilidades condicionales y condiciones de su regularidad", Teoría de la probabilidad y sus aplicaciones , 13 (2): 197–224, doi :10.1137/1113026
3. Spitzer, Frank (1971), "Campos aleatorios de Markov y conjuntos de Gibbs", The American Mathematical Monthly , 78 (2): 142–154, doi :10.2307/2317621, JSTOR  2317621
4. Hammersley, JM; Clifford, P. (1971), Campos de Markov en grafos y redes finitos (PDF)
5. Clifford, P. (1990), "Campos aleatorios de Markov en estadística", en Grimmett, GR; Welsh, DJA (eds.), Desorden en sistemas físicos: un volumen en honor a John M. Hammersley, Oxford University Press, págs. 19-32, ISBN 978-0-19-853215-6, MR  1064553 , consultado el 4 de mayo de 2009
6. Grimmett, GR (1973), "Un teorema sobre campos aleatorios", Boletín de la Sociedad Matemática de Londres , 5 (1): 81–84, CiteSeerX 10.1.1.318.3375 , doi :10.1112/blms/5.1.81, MR  0329039 
7. Preston, CJ (1973), "Estados de Gibbs generalizados y campos aleatorios de Markov", Advances in Applied Probability , 5 (2): 242–261, doi :10.2307/1426035, JSTOR  1426035, MR  0405645
8. Sherman, S. (1973), "Campos aleatorios de Markov y campos aleatorios de Gibbs", Israel Journal of Mathematics , 14 (1): 92–103, doi :10.1007/BF02761538, MR  0321185
9. Besag, J. (1974), "Interacción espacial y análisis estadístico de sistemas reticulares", Journal of the Royal Statistical Society, Serie B , 36 (2): 192–236, JSTOR  2984812, MR  0373208

Lectura adicional

• Grimmett, Geoffrey (2018), "7.", Probabilidad en gráficos (2.ª ed.), Cambridge University Press, ISBN 9781108438179
• Langseth, Helge, El teorema de Hammersley-Clifford y su impacto en las estadísticas modernas (PDF) , Departamento de Ciencias Matemáticas, Universidad Noruega de Ciencia y Tecnología