Campo aleatorio de Markov

Conjunto de variables aleatorias

Ejemplo de un campo aleatorio de Markov. Cada arista representa una dependencia. En este ejemplo: A depende de B y D. B depende de A y D. D depende de A, B y E. E depende de D y C. C depende de E.

En el campo de la física y la probabilidad , un campo aleatorio de Markov ( MRF ), red de Markov o modelo gráfico no dirigido es un conjunto de variables aleatorias que tienen una propiedad de Markov descrita por un grafo no dirigido . En otras palabras, se dice que un campo aleatorio es un campo aleatorio de Markov si satisface las propiedades de Markov. El concepto se origina en el modelo de Sherrington-Kirkpatrick . ^[1]

Una red de Markov o MRF es similar a una red bayesiana en su representación de dependencias; las diferencias son que las redes bayesianas son dirigidas y acíclicas , mientras que las redes de Markov no son dirigidas y pueden ser cíclicas. Por lo tanto, una red de Markov puede representar ciertas dependencias que una red bayesiana no puede (como dependencias cíclicas ^{[ se necesita más explicación ]} ); por otro lado, no puede representar ciertas dependencias que una red bayesiana sí puede (como dependencias inducidas ^{[ se necesita más explicación ]} ). El gráfico subyacente de un campo aleatorio de Markov puede ser finito o infinito.

Cuando la densidad de probabilidad conjunta de las variables aleatorias es estrictamente positiva, también se denomina campo aleatorio de Gibbs , porque, según el teorema de Hammersley-Clifford , puede representarse mediante una medida de Gibbs para una función de energía apropiada (definida localmente). El campo aleatorio de Markov prototípico es el modelo de Ising ; de hecho, el campo aleatorio de Markov se introdujo como la configuración general para el modelo de Ising. ^[2] En el dominio de la inteligencia artificial , un campo aleatorio de Markov se utiliza para modelar varias tareas de nivel bajo a medio en el procesamiento de imágenes y la visión por computadora . ^[3]

Definición

Dado un gráfico no dirigido , un conjunto de variables aleatorias indexadas por   forman un campo aleatorio de Markov con respecto a   si satisfacen las propiedades locales de Markov: ${\displaystyle G=(V,E)}$ ${\displaystyle X=(X_{v})_{v\in V}}$ ${\displaystyle V}$ ${\displaystyle G}$

Propiedad de Markov por pares: dos variables no adyacentes son condicionalmente independientes dadas todas las demás variables:

${\displaystyle X_{u}\perp \!\!\!\perp X_{v}\mid X_{V\smallsetminus \{u,v\}}}$

Propiedad local de Markov: Una variable es condicionalmente independiente de todas las demás variables dados sus vecinos:

${\displaystyle X_{v}\perp \!\!\!\perp X_{V\smallsetminus \operatorname {N} [v]}\mid X_{\operatorname {N} (v)}}$

donde es el conjunto de vecinos de , y es el vecindario cerrado de . ${\textstyle \operatorname {N} (v)}$ ${\displaystyle v}$ ${\displaystyle \operatorname {N} [v]=v\cup \operatorname {N} (v)}$ ${\displaystyle v}$

Propiedad global de Markov: Dos subconjuntos cualesquiera de variables son condicionalmente independientes dado un subconjunto separador:

${\displaystyle X_{A}\perp \!\!\!\perp X_{B}\mid X_{S}}$

donde cada ruta desde un nodo en a un nodo en pasa por . ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle S}$

La propiedad global de Markov es más fuerte que la propiedad local de Markov, que a su vez es más fuerte que la propiedad de pares. ^[4] Sin embargo, las tres propiedades de Markov anteriores son equivalentes para distribuciones positivas ^[5] (aquellas que asignan solo probabilidades distintas de cero a las variables asociadas).

La relación entre las tres propiedades de Markov es particularmente clara en la siguiente formulación:

• Por pares: Para cualquier valor no igual o adyacente, . ${\displaystyle i,j\in V}$ ${\displaystyle X_{i}\perp \!\!\!\perp X_{j}|X_{V\smallsetminus \{i,j\}}}$
• Local: Para cualquier y que no contenga o sea adyacente a , . ${\displaystyle i\in V}$ ${\displaystyle J\subset V}$ ${\displaystyle i}$ ${\displaystyle X_{i}\perp \!\!\!\perp X_{J}|X_{V\smallsetminus (\{i\}\cup J)}}$
• Global: Para cualquier no intersecante o adyacente, . ${\displaystyle I,J\subset V}$ ${\displaystyle X_{I}\perp \!\!\!\perp X_{J}|X_{V\smallsetminus (I\cup J)}}$

Factorización de camarillas

Como la propiedad de Markov de una distribución de probabilidad arbitraria puede ser difícil de establecer, una clase comúnmente utilizada de campos aleatorios de Markov son aquellos que se pueden factorizar de acuerdo con las camarillas del gráfico.

Dado un conjunto de variables aleatorias , sea la probabilidad de una configuración de campo particular en  —es decir, es la probabilidad de encontrar que las variables aleatorias toman el valor particular . Debido a que es un conjunto, la probabilidad de debe entenderse como tomada con respecto a una distribución conjunta de . ${\displaystyle X=(X_{v})_{v\in V}}$ ${\displaystyle P(X=x)}$ ${\displaystyle x}$ ${\displaystyle X}$ ${\displaystyle P(X=x)}$ ${\displaystyle X}$ ${\displaystyle x}$ ${\displaystyle X}$ ${\displaystyle x}$ ${\displaystyle X_{v}}$

Si esta densidad conjunta se puede factorizar sobre las camarillas de como ${\displaystyle G}$

${\displaystyle P(X=x)=\prod _{C\in \operatorname {cl} (G)}\varphi _{C}(x_{C})}$

luego forma un campo aleatorio de Markov con respecto a . Aquí, es el conjunto de camarillas de . La definición es equivalente si solo se utilizan camarillas máximas. Las funciones a veces se denominan potenciales factoriales o potenciales de camarilla . Sin embargo, tenga en cuenta que se utiliza una terminología contradictoria: la palabra potencial se aplica a menudo al logaritmo de . Esto se debe a que, en mecánica estadística , tiene una interpretación directa como la energía potencial de una configuración . ${\displaystyle X}$ ${\displaystyle G}$ ${\displaystyle \operatorname {cl} (G)}$ ${\displaystyle G}$ ${\displaystyle \varphi _{C}}$ ${\displaystyle \varphi _{C}}$ ${\displaystyle \log(\varphi _{C})}$  ${\displaystyle x_{C}}$

Algunas MRF no se factorizan: se puede construir un ejemplo simple en un ciclo de 4 nodos con algunas energías infinitas, es decir, configuraciones de probabilidades cero, ^[6] incluso si uno, más apropiadamente, permite que las energías infinitas actúen sobre el gráfico completo en . ^[7] ${\displaystyle V}$

Los MRF se factorizan si se cumple al menos una de las siguientes condiciones:

• La densidad es positiva (según el teorema de Hammersley-Clifford )
• El gráfico es cordal (por equivalencia a una red bayesiana )

Cuando existe tal factorización, es posible construir un gráfico de factores para la red.

Familia exponencial

Cualquier campo aleatorio positivo de Markov se puede escribir como una familia exponencial en forma canónica con funciones características tales que la distribución conjunta completa se puede escribir como ${\displaystyle f_{k}}$

${\displaystyle P(X=x)={\frac {1}{Z}}\exp \left(\sum _{k}w_{k}^{\top }f_{k}(x_{\{k\}})\right)}$

donde la notación

${\displaystyle w_{k}^{\top }f_{k}(x_{\{k\}})=\sum _{i=1}^{N_{k}}w_{k,i}\cdot f_{k,i}(x_{\{k\}})}$

es simplemente un producto escalar sobre configuraciones de campo, y Z es la función de partición :

${\displaystyle Z=\sum _{x\in {\mathcal {X}}}\exp \left(\sum _{k}w_{k}^{\top }f_{k}(x_{\{k\}})\right).}$

Aquí, denota el conjunto de todas las asignaciones posibles de valores a todas las variables aleatorias de la red. Por lo general, las funciones de característica se definen de modo que sean indicadores de la configuración de la camarilla, es decir , si corresponde a la i -ésima configuración posible de la k -ésima camarilla y 0 en caso contrario. Este modelo es equivalente al modelo de factorización de camarilla dado anteriormente, si es la cardinalidad de la camarilla y el peso de una característica corresponde al logaritmo del factor de camarilla correspondiente, es decir , donde es la i -ésima configuración posible de la k -ésima camarilla, es decir, el i -ésimo valor en el dominio de la camarilla . ${\displaystyle {\mathcal {X}}}$ ${\displaystyle f_{k,i}}$ ${\displaystyle f_{k,i}(x_{\{k\}})=1}$ ${\displaystyle x_{\{k\}}}$ ${\displaystyle N_{k}=|\operatorname {dom} (C_{k})|}$ ${\displaystyle f_{k,i}}$ ${\displaystyle w_{k,i}=\log \varphi (c_{k,i})}$ ${\displaystyle c_{k,i}}$ ${\displaystyle C_{k}}$

La probabilidad P se denomina a menudo medida de Gibbs. Esta expresión de un campo de Markov como modelo logístico solo es posible si todos los factores de clique son distintos de cero, es decir , si a ninguno de los elementos de se les asigna una probabilidad de 0. Esto permite aplicar técnicas del álgebra matricial, por ejemplo , que la traza de una matriz sea el logaritmo del determinante , y que la representación matricial de un gráfico surja de la matriz de incidencia del gráfico . ${\displaystyle {\mathcal {X}}}$

La importancia de la función de partición Z es que muchos conceptos de la mecánica estadística , como la entropía , se generalizan directamente al caso de las redes de Markov, y de ese modo se puede obtener una comprensión intuitiva . Además, la función de partición permite aplicar métodos variacionales a la solución del problema: se puede asociar una fuerza impulsora a una o más de las variables aleatorias y explorar la reacción de la red en respuesta a esta perturbación . Así, por ejemplo, se puede añadir un término impulsor J _v , para cada vértice v del grafo, a la función de partición para obtener:

${\displaystyle Z[J]=\sum _{x\in {\mathcal {X}}}\exp \left(\sum _{k}w_{k}^{\top }f_{k}(x_{\{k\}})+\sum _{v}J_{v}x_{v}\right)}$

Derivando formalmente con respecto a J _v se obtiene el valor esperado de la variable aleatoria X _v asociada al vértice v :

${\displaystyle E[X_{v}]={\frac {1}{Z}}\left.{\frac {\partial Z[J]}{\partial J_{v}}}\right|_{J_{v}=0}.}$

Las funciones de correlación se calculan de la misma manera; la correlación de dos puntos es:

${\displaystyle C[X_{u},X_{v}]={\frac {1}{Z}}\left.{\frac {\partial ^{2}Z[J]}{\partial J_{u}\,\partial J_{v}}}\right|_{J_{u}=0,J_{v}=0}.}$

Desafortunadamente, aunque la probabilidad de una red logística de Markov es convexa, evaluar la probabilidad o el gradiente de la probabilidad de un modelo requiere inferencia en el modelo, lo que generalmente es computacionalmente inviable (ver "Inferencia" a continuación).

Ejemplos

Gaussiano

Una distribución normal multivariada forma un campo aleatorio de Markov con respecto a un gráfico si los bordes faltantes corresponden a ceros en la matriz de precisión (la matriz de covarianza inversa ): ${\displaystyle G=(V,E)}$

${\displaystyle X=(X_{v})_{v\in V}\sim {\mathcal {N}}({\boldsymbol {\mu }},\Sigma )}$

de tal manera que

${\displaystyle (\Sigma ^{-1})_{uv}=0\quad {\text{iff}}\quad \{u,v\}\notin E.}$^[8]

Inferencia

Al igual que en una red bayesiana , se puede calcular la distribución condicional de un conjunto de nodos a partir de valores dados en otro conjunto de nodos en el campo aleatorio de Markov sumando todas las asignaciones posibles a ; esto se llama inferencia exacta . Sin embargo, la inferencia exacta es un problema #P-completo y, por lo tanto, computacionalmente intratable en el caso general. Las técnicas de aproximación como el Monte Carlo de cadena de Markov y la propagación de creencias en bucle suelen ser más factibles en la práctica. Algunas subclases particulares de MRF, como los árboles (ver árbol de Chow-Liu ), tienen algoritmos de inferencia de tiempo polinomial; descubrir tales subclases es un tema de investigación activo. También hay subclases de MRF que permiten una inferencia MAP eficiente , o más probablemente de asignación; ejemplos de estos incluyen redes asociativas. ^{[9] [10]} Otra subclase interesante es la de los modelos descomponibles (cuando el grafo es cordal ): al tener una forma cerrada para el MLE , es posible descubrir una estructura consistente para cientos de variables. ^[11] ${\displaystyle V'=\{v_{1},\ldots ,v_{i}\}}$ ${\displaystyle W'=\{w_{1},\ldots ,w_{j}\}}$ ${\displaystyle u\notin V',W'}$

Campos aleatorios condicionales

Una variante notable de un campo aleatorio de Markov es un campo aleatorio condicional , en el que cada variable aleatoria también puede estar condicionada a un conjunto de observaciones globales . En este modelo, cada función es una aplicación de todas las asignaciones tanto a la clique k como de las observaciones a los números reales no negativos. Esta forma de la red de Markov puede ser más apropiada para producir clasificadores discriminativos , que no modelan la distribución sobre las observaciones. Los CRF fueron propuestos por John D. Lafferty , Andrew McCallum y Fernando CN Pereira en 2001. ^[12] ${\displaystyle o}$ ${\displaystyle \varphi _{k}}$ ${\displaystyle o}$

Aplicaciones variadas

Los campos aleatorios de Markov encuentran aplicación en una variedad de campos, que van desde gráficos de computadora hasta visión por computadora, aprendizaje automático o biología computacional , ^{[13] [14]} y recuperación de información . ^[15] Los MRF se utilizan en el procesamiento de imágenes para generar texturas, ya que pueden usarse para generar modelos de imágenes flexibles y estocásticos. En el modelado de imágenes, la tarea es encontrar una distribución de intensidad adecuada de una imagen dada, donde la idoneidad depende del tipo de tarea y los MRF son lo suficientemente flexibles para usarse para síntesis de imágenes y texturas, compresión y restauración de imágenes, segmentación de imágenes , inferencia de imágenes 3D a partir de imágenes 2D, registro de imágenes , síntesis de texturas , superresolución , coincidencia estéreo y recuperación de información . Se pueden usar para resolver varios problemas de visión por computadora que pueden plantearse como problemas de minimización de energía o problemas en los que se deben distinguir diferentes regiones utilizando un conjunto de características discriminantes, dentro de un marco de campo aleatorio de Markov, para predecir la categoría de la región. ^[16] Los campos aleatorios de Markov fueron una generalización del modelo de Ising y, desde entonces, se han utilizado ampliamente en optimizaciones y redes combinatorias.

Véase también

• Gráfico compuesto con restricciones
• Modelo gráfico
• Red de dependencia (modelo gráfico)
• Teorema de Hammersley-Clifford
• Red de Hopfield
• Sistema de partículas interactuantes
• Modelo de Ising
• Análisis log-lineal
• Cadena de Markov
• Red lógica de Markov
• Método de máxima entropía
• Autómata celular estocástico

Referencias

1. Sherrington, David; Kirkpatrick, Scott (1975), "Modelo resoluble de un vidrio de espín", Physical Review Letters , 35 (35): 1792–1796, Bibcode :1975PhRvL..35.1792S, doi :10.1103/PhysRevLett.35.1792
2. Kindermann, Ross; Snell, J. Laurie (1980). Campos aleatorios de Markov y sus aplicaciones (PDF) . Sociedad Matemática Estadounidense. ISBN 978-0-8218-5001-5. MR  0620955. Archivado desde el original (PDF) el 2017-08-10 . Consultado el 2012-04-09 .
3. Li, SZ (2009). Modelado de campos aleatorios de Markov en análisis de imágenes. Springer. ISBN 9781848002791.
4. Lauritzen, Steffen (1996). Modelos gráficos . Oxford: Prensa de Clarendon. pag. 33.ISBN​ 978-0198522195.
5. Koller, Dafne; Friedman, Nir (2009). Modelos gráficos probabilísticos . Prensa del MIT. pag. 114-122. ISBN 9780262013192.
6. Moussouris, John (1974). "Sistemas aleatorios de Gibbs y Markov con restricciones". Journal of Statistical Physics . 10 (1): 11–33. Bibcode :1974JSP....10...11M. doi :10.1007/BF01011714. hdl : 10338.dmlcz/135184 . MR  0432132. S2CID  121299906.
7. Gandolfi, Alberto; Lenarda, Pietro (2016). "Una nota sobre campos aleatorios de Gibbs y Markov con restricciones y sus momentos". Matemáticas y mecánica de sistemas complejos . 4 (3–4): 407–422. doi : 10.2140/memocs.2016.4.407 .
8. Rue, Håvard; Held, Leonhard (2005). Campos aleatorios gaussianos de Markov: teoría y aplicaciones . CRC Press. ISBN 978-1-58488-432-3.
9. Taskar, Benjamin; Chatalbashev, Vassil; Koller, Daphne (2004), "Aprendizaje de redes asociativas de Markov", en Brodley, Carla E. (ed.), Actas de la vigésimo primera conferencia internacional sobre aprendizaje automático (ICML 2004), Banff, Alberta, Canadá, 4-8 de julio de 2004 , ACM International Conference Proceeding Series, vol. 69, Association for Computing Machinery , p. 102, CiteSeerX 10.1.1.157.329 , doi :10.1145/1015330.1015444, ISBN  978-1581138283, Número de identificación del sujeto  11312524.
10. Duchi, John C.; Tarlow, Daniel; Elidan, Gal; Koller, Daphne (2006), "Uso de optimización combinatoria en la propagación de creencias de Max-Product", en Schölkopf, Bernhard; Platt, John C.; Hoffman, Thomas (eds.), Actas de la Vigésima Conferencia Anual sobre Sistemas de Procesamiento de Información Neural, Vancouver, Columbia Británica, Canadá, 4-7 de diciembre de 2006 , Advances in Neural Information Processing Systems , vol. 19, MIT Press , págs. 369–376.
11. Petitjean, F.; Webb, GI; Nicholson, AE (2013). Escalado del análisis log-lineal a datos de alta dimensión (PDF) . Conferencia internacional sobre minería de datos. Dallas, TX, EE. UU.: IEEE.
12. "Dos premios a trabajos clásicos para trabajos que aparecieron en el ICML 2013". ICML . 2013 . Consultado el 15 de diciembre de 2014 .
13. Kindermann y Snell, Ross y Laurie (1980). Campos aleatorios de Markov y sus aplicaciones . Rhode Island: American Mathematical Society. ISBN 978-0-8218-5001-5.
14. Banf, Michael; Rhee, Seung Y. (1 de febrero de 2017). "Mejora de la inferencia de la red reguladora de genes mediante la integración de datos con campos aleatorios de Markov". Scientific Reports . 7 (1): 41174. Bibcode :2017NatSR...741174B. doi :10.1038/srep41174. ISSN  2045-2322. PMC 5286517 . PMID  28145456. 
15. Metzler, Donald; Croft, W.Bruce (2005). Un modelo de campo aleatorio de Markov para dependencias de términos . Actas de la 28.ª Conferencia ACM SIGIR. Salvador, Brasil: ACM. pp. 472–479. doi :10.1145/1076034.1076115.
16. Zhang y Zakhor, Richard y Avideh (2014). "Identificación automática de regiones de ventana en nubes de puntos interiores utilizando LiDAR y cámaras". Publicaciones de VIP Lab . CiteSeerX 10.1.1.649.303 .