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, un campo aleatorio se dice que es un Markov campo aleatorio si satisface propiedades de Markov.
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 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 campo aleatorio apropiado (definido localmente). función energética. El campo aleatorio prototípico de Markov es el modelo de Ising ; de hecho, el campo aleatorio de Markov se introdujo como escenario general para el modelo de Ising. [1] 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 . [2]
Definición
Dado un gráfico no dirigido , un conjunto de variables aleatorias indexado por formar un campo aleatorio de Markov con respecto a si satisfacen las propiedades locales de Markov:
- Propiedad de Markov por pares: dos variables no adyacentes cualesquiera son condicionalmente independientes dadas todas las demás variables:
- Propiedad local de Markov: una variable es condicionalmente independiente de todas las demás variables dadas sus vecinas:
- dónde es el conjunto de vecinos de , y es el barrio cerrado de .
- Propiedad global de Markov: dos subconjuntos cualesquiera de variables son condicionalmente independientes dado un subconjunto separador:
- donde cada camino desde un nodo en a un nodo en atravesar .
La propiedad Global Markov es más fuerte que la propiedad Local Markov, que a su vez es más fuerte que la propiedad por pares. [3] Sin embargo, las tres propiedades de Markov anteriores son equivalentes para distribuciones positivas [4] (aquellas que asignan solo probabilidades distintas de cero a las variables asociadas).
Factorización de camarillas
Como la propiedad de Markov de una distribución de probabilidad arbitraria puede ser difícil de establecer, una clase de campos aleatorios de Markov comúnmente utilizada son aquellos que se pueden factorizar de acuerdo con las camarillas del gráfico.
Dado un conjunto de variables aleatorias , dejar ser la probabilidad de una configuración de campo particular en . Es decir, es la probabilidad de encontrar que las variables aleatorias tomar el valor particular . Porque es un conjunto, la probabilidad de debe entenderse que se toma con respecto a una distribución conjunta de la.
Si esta densidad conjunta se puede factorizar sobre las camarillas de :
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 funcionesa veces se les conoce como potenciales de factor 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 .
Algunos MRF no factorizan: se puede construir un ejemplo simple en un ciclo de 4 nodos con algunas energías infinitas, es decir, configuraciones de probabilidades cero, [5] incluso si una, más apropiadamente, permite que las energías infinitas actúen sobre el gráfico completo en. [6]
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 de Markov positivo se puede escribir como familia exponencial en forma canónica con funciones de características de modo que la distribución conjunta completa se pueda escribir como
donde la notación
es simplemente un producto escalar sobre configuraciones de campo, y Z es la función de partición :
Aquí, denota el conjunto de todas las posibles asignaciones de valores a todas las variables aleatorias de la red. Por lo general, la característica funcionase definen de tal manera que son 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 camarillas 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 es la i -ésima configuración posible de la k -ésima camarilla, es decir , el i -ésimo valor en el dominio de la camarilla.
La probabilidad P a menudo se denomina medida de Gibbs. Esta expresión de un campo de Markov como modelo logístico solo es posible si todos los factores de la camarilla son distintos de cero, es decir , si ninguno de los elementos dese les asigna una probabilidad de 0. Esto permite aplicar técnicas del álgebra matricial, por ejemplo , que la traza de una matriz sea logaritmo del determinante , con la representación matricial de un gráfico que surge de la matriz de incidencia del gráfico .
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, por lo tanto, 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 adjuntar 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 de conducción J v , para cada vértice v del gráfico, a la función de partición para obtener:
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 :
Las funciones de correlación se calculan de la misma forma; la correlación de dos puntos es:
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 una inferencia en el modelo, que generalmente es computacionalmente inviable (ver 'Inferencia' a continuación).
Ejemplos de
Gaussiano
Una distribución normal multivariante forma un campo aleatorio de Markov con respecto a un gráficosi los bordes faltantes corresponden a ceros en la matriz de precisión (la matriz de covarianza inversa ):
tal que
- [7]
Inferencia
Como en una red bayesiana, se puede calcular la distribución condicional de un conjunto de nodos 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 de # P-completo y, por lo 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 son a menudo 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; el descubrimiento de tales subclases es un tema de investigación activo. También hay subclases de MRF que permiten una MAP eficiente , o la asignación más probable, la inferencia; ejemplos de estos incluyen redes asociativas. [8] [9] 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. [10]
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ónes un mapeo de todas las asignaciones tanto a la camarilla k como a las observacionesa 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. [11]
Varias aplicaciones
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. [12] [13] Los MRF se utilizan en el procesamiento de imágenes para generar texturas, ya que se pueden utilizar 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 como para ser utilizados para la síntesis de imágenes y texturas, compresión y restauración de imágenes , segmentación de imágenes , imágenes en 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 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 discriminatorias, dentro de un marco de campo aleatorio de Markov, para predecir la categoría de la región. [14] Los campos aleatorios de Markov fueron una generalización sobre el modelo de Ising y, desde entonces, se han utilizado ampliamente en redes y optimizaciones combinatorias.
Ver también
- Gráfico compuesto de restricción
- Modelo grafico
- Red de dependencia (modelo gráfico)
- Teorema de Hammersley-Clifford
- Red Hopfield
- Sistema de partículas interactivas
- 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
- ^ 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 .
- ^ Li, SZ (2009). Modelado de campo aleatorio de Markov en análisis de imágenes . Saltador. ISBN 9781848002791.
- ^ Lauritzen, Steffen (1996). Modelos gráficos . Oxford: Clarendon Press. pag. 33. ISBN 978-0198522195.
- ^ Modelos gráficos probabilísticos .
- ^ Moussouris, John (1974). "Sistemas aleatorios de Gibbs y Markov con restricciones". Revista de física estadística . 10 (1): 11–33. Código Bibliográfico : 1974JSP .... 10 ... 11M . doi : 10.1007 / BF01011714 . hdl : 10338.dmlcz / 135184 . Señor 0432132 . S2CID 121299906 .
- ^ 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 .
- ^ Rue, Håvard; Held, Leonhard (2005). Campos aleatorios de Gauss de Markov: teoría y aplicaciones . Prensa CRC. ISBN 978-1-58488-432-3.
- ^ Taskar, Benjamin; Chatalbashev, Vassil; Koller, Daphne (2004), "Learning associative Markov networks", en Brodley, Carla E. (ed.), Proceedings of the Twenty-first International Conference on Machine Learning (ICML 2004), Banff, Alberta, Canadá, 4 de julio 8, 2004 , ACM International Conference Proceeding Series, 69 , Association for Computing Machinery , p. 102, CiteSeerX 10.1.1.157.329 , doi : 10.1145 / 1015330.1015444 , ISBN 978-1581138283, S2CID 11312524.
- ^ Duchi, John C .; Tarlow, Daniel; Elidan, Gal; Koller, Daphne (2006), "Uso de la optimización combinatoria dentro de la propagación de creencias de productos máximos " , 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-7 de diciembre de 2006 , Advances in Neural Information Processing Systems , 19 , MIT Press , págs. 369– 376.
- ^ Petitjean, F .; Webb, GI; Nicholson, AE (2013). Escalado del análisis log-lineal a datos de alta dimensión (PDF) . Congreso Internacional de Minería de Datos. Dallas, TX, Estados Unidos: IEEE.
- ^ "Dos premios clásicos de trabajos presentados en ICML 2013" . ICML . 2013 . Consultado el 15 de diciembre de 2014 .
- ^ 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.
- ^ Banf, Michael; Rhee, Seung Y. (1 de febrero de 2017). "Mejora de la inferencia de la red reguladora de genes a través de la integración de datos con campos aleatorios de Markov" . Informes científicos . 7 (1): 41174. Bibcode : 2017NatSR ... 741174B . doi : 10.1038 / srep41174 . ISSN 2045-2322 . PMC 5286517 . PMID 28145456 .
- ^ 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 .