campo aleatorio de Markov

Conjunto de variables aleatorias

Un ejemplo de campo aleatorio de Markov. Cada borde representa 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 dominio de la física y la probabilidad , un campo aleatorio de Markov ( MRF ), una red de Markov o un modelo gráfico no dirigido es un conjunto de variables aleatorias que tienen una propiedad de Markov descrita por un gráfico 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 tiene su origen en el modelo 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 están 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 puede (como las 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 un valor apropiado (definido localmente). función energética. El campo aleatorio de Markov prototípico es el modelo de Ising ; de hecho, el campo aleatorio de Markov se introdujo como escenario general para el modelo de Ising. ^[2] En el dominio de la inteligencia artificial , se utiliza un campo aleatorio de Markov 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 cualesquiera 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 la vecindad cerrada 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 de separación:

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

por donde pasa cada camino desde un nodo hacia otro nodo . ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle S}$

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

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

• Por pares: para cualquiera que no sea igual o adyacente, . ${\displaystyle i,j\in V}$ ${\displaystyle X_{i}\perp \!\!\!\perp X_{j}|X_{V\smallsetminus \{i,j\}}}$
• Local: Para cualquiera y que no contenga ni 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 cualquiera que no se cruce o sea adyacente, . ${\displaystyle I,J\subset V}$ ${\displaystyle X_{I}\perp \!\!\!\perp X_{J}|X_{V\smallsetminus (I\cup J)}}$

Factorización de camarilla

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, la probabilidad de encontrar que las variables aleatorias tomen el valor particular . Debido a que es un conjunto, debe entenderse que la probabilidad de se toma 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í, está el conjunto de camarillas de . La definición es equivalente si sólo se utilizan camarillas máximas. Las funciones a veces se denominan potenciales de factor o potenciales de camarilla . Sin embargo, tenga en cuenta que se utiliza terminología contradictoria: la palabra potencial a menudo se aplica 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}}$

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

Las 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 tal factorización existe, es posible construir un gráfico de factores para la red.

familia exponencial

Cualquier campo aleatorio de Markov positivo 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 posibles asignaciones de valores a todas las variables aleatorias de la red. Por lo general, las funciones características se definen de manera 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 , ¿dónde está la i -ésima configuración posible de 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 a menudo se denomina medida de Gibbs. Esta expresión de un campo de Markov como modelo logístico sólo es posible si todos los factores de camarilla son distintos de cero, es decir, si a ninguno de los elementos de se le asigna una probabilidad de 0. Esto permite aplicar técnicas del álgebra matricial, por ejemplo , que la traza de una matriz es log del determinante , y la representación matricial de un gráfico surge 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 este 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 agregar un término determinante J _v , para cada vértice v del gráfico, 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)}$

La diferenciación formal con respecto a J _v da el valor esperado de la variable aleatoria X _v asociada con el 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 probabilidad de un modelo requiere inferencia en el modelo, que generalmente es computacionalmente inviable (consulte '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 )}$

tal que

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

Inferencia

Como en una red bayesiana , se puede calcular la distribución condicional de un conjunto de nodos con valores dados a 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 tanto, computacionalmente intratable en el caso general. Las técnicas de aproximación como la cadena de Markov Monte Carlo y la propagación de creencias descabelladas 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 una asignación; ejemplos de estos incluyen redes asociativas. ^{[9] [10]} Otra subclase interesante es la de los modelos descomponibles (cuando el gráfico 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 un mapeo de todas las asignaciones tanto al clique k como de las observaciones a los números reales no negativos. Esta forma de red de Markov puede ser más apropiada para producir clasificadores discriminativos , que no modelan la distribución de 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 por 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 determinada, donde la idoneidad depende del tipo de tarea y los MRF son lo suficientemente flexibles como para usarse para síntesis de imágenes y texturas, compresión y restauración de imágenes, segmentación de imágenes , imágenes 3D. inferencia 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 utilizar para resolver diversos problemas de visión por computadora que pueden plantearse como problemas de minimización de energía o problemas en los que es necesario 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 combinatorias y redes.

Ver también

• Gráfico compuesto de restricciones
• modelo grafico
• Red de dependencia (modelo gráfico)
• Teorema de Hammersley-Clifford
• Red Hopfield
• Sistema de partículas interactivas
• modelo 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 solucionable de un Spin-Glass", 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. SEÑOR  0620955. Archivado desde el original (PDF) el 10 de agosto de 2017 . Consultado el 9 de abril de 2012 .
3. Li, SZ (2009). Modelado de campos aleatorios de Markov en análisis de imágenes. Saltador. 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". Revista de Física Estadística . 10 (1): 11–33. Código Bib : 1974JSP....10...11M. doi :10.1007/BF01011714. hdl : 10338.dmlcz/135184 . SEÑOR  0432132. S2CID  121299906.
7. Gandolfi, Alberto; Lenarda, Pietro (2016). "Una nota sobre Gibbs y Markov Random Fields con limitaciones 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; Celebrado, Leonhard (2005). Campos aleatorios gaussianos de Markov: teoría y aplicaciones . Prensa CRC. ISBN 978-1-58488-432-3.
9. Taskar, Benjamín; Chatalbashev, Vassil; Koller, Daphne (2004), "Learning associative Markov Networks", en Brodley, Carla E. (ed.), Actas de la XXII Conferencia Internacional sobre Aprendizaje Automático (ICML 2004), Banff, Alberta, Canadá, 4 de julio. 8, 2004 , Serie de actas de conferencias internacionales de ACM, vol. 69, Asociación de Maquinaria de Computación , pág. 102, CiteSeerX 10.1.1.157.329 , doi :10.1145/1015330.1015444, ISBN  978-1581138283, S2CID  11312524.
10. Duchi, John C.; Tarlow, Daniel; Elidan, Gal; Koller, Daphne (2006), "Uso de la optimización combinatoria dentro de la propagación de creencias del producto máximo", en Schölkopf, Bernhard; Platt, John C.; Hoffman, Thomas (eds.), Actas de la vigésima conferencia anual sobre sistemas de procesamiento de información neuronal, Vancouver, Columbia Británica, Canadá, 4 al 7 de diciembre de 2006 , Avances en sistemas de procesamiento de información neuronal , 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) . Congreso Internacional sobre Minería de Datos. Dallas, TX, Estados Unidos: IEEE.
12. "Dos premios de artículos clásicos para artículos aparecidos en 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: Sociedad Matemática Estadounidense. 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". Informes científicos . 7 (1): 41174. Código bibliográfico : 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. págs. 472–479. doi :10.1145/1076034.1076115.
16. Zhang y Zakhor, Richard y Avideh (2014). "Identificación automática de regiones de ventanas en nubes de puntos interiores mediante cámaras y LiDAR". Publicaciones del Laboratorio VIP . CiteSeerX 10.1.1.649.303 .