campo aleatorio de Markov

En el ámbito 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 poseen una propiedad de Markov y que se describe mediante 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 tiene su origen 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; la diferencia radica en 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 las dependencias cíclicas ); por otro lado, no puede representar ciertas dependencias que una red bayesiana sí puede (como las dependencias inducidas ). El grafo 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 la denomina campo aleatorio de Gibbs , ya que, 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 el marco general para el modelo de Ising. ^{[ 2 ]} En el ámbito de la inteligencia artificial , un campo aleatorio de Markov se utiliza para modelar diversas tareas de nivel bajo a medio en el procesamiento de imágenes y la visión por computadora . ^{[ 3 ]}

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

Propiedad de Markov por pares: Cualquier par de 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 de Markov local: 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)}}$

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

Propiedad global de Markov: Cualquier par de subconjuntos 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${\displaystyle A}$a un nodo en${\displaystyle B}$pasa por${\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 propiedad de Markov por 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 queda particularmente clara en la siguiente formulación:

• Por pares: Para cualquier${\displaystyle i,j\in V}$no iguales ni adyacentes,${\displaystyle X_{i}\perp \!\!\!\perp X_{j}|X_{V\smallsetminus \{i,j\}}}$.
• Local: Para cualquier${\displaystyle i\in V}$y${\displaystyle J\subset V}$que no contiene ni es adyacente a${\displaystyle i}$,${\displaystyle X_{i}\perp \!\!\!\perp X_{J}|X_{V\smallsetminus (\{i\}\cup J)}}$.
• Global: Para cualquier${\displaystyle I,J\subset V}$que no se intersecan ni son adyacentes,${\displaystyle X_{I}\perp \!\!\!\perp X_{J}|X_{V\smallsetminus (I\cup J)}}$.

Dado que 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 pueden factorizarse según las camarillas del grafo.

Dado un conjunto de variables aleatorias${\displaystyle X=(X_{v})_{v\in V}}$, dejar${\displaystyle P(X=x)}$sea ​​la probabilidad de una configuración de campo particular${\displaystyle x}$en${\displaystyle X}$-eso es,${\displaystyle P(X=x)}$es la probabilidad de encontrar que las variables aleatorias${\displaystyle X}$adquirir el valor particular${\displaystyle x}$. Porque${\displaystyle X}$es un conjunto, la probabilidad de${\displaystyle x}$debe entenderse que debe tomarse con respecto a una distribución conjunta de la${\displaystyle X_{v}}$.

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

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

entonces${\displaystyle X}$forma un campo aleatorio de Markov con respecto a${\displaystyle G}$. Aquí,${\displaystyle \operatorname {cl} (G)}$es el conjunto de camarillas de${\displaystyle G}$La definición es equivalente si solo se utilizan camarillas máximas. Las funciones${\displaystyle \varphi _{C}}$A veces se les denomina 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${\displaystyle \varphi _{C}}$Esto se debe a que, en mecánica estadística ,${\displaystyle \log(\varphi _ {C})}$tiene una interpretación directa como la energía potencial de una configuración${\displaystyle x_{C}}$.

Algunos MRF no se factorizan: un ejemplo simple se puede construir 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 grafo completo en${\displaystyle V}$. ^{[ 7 ]}

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

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

Cuando existe dicha factorización, es posible construir un grafo de factores para la red.

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

${\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í,${\displaystyle {\mathcal {X}}}$denota el conjunto de todas las posibles asignaciones de valores a todas las variables aleatorias de la red. Por lo general, las funciones de características${\displaystyle f_{k,i}}$se definen de tal manera que son indicadores de la configuración de la camarilla, es decir${\displaystyle f_{k,i}(x_{\{k\}})=1}$si${\displaystyle x_{\{k\}}}$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${\displaystyle N_{k}=|\operatorname {dom} (C_{k})|}$es la cardinalidad de la camarilla y el peso de una característica${\displaystyle f_{k,i}}$corresponde al logaritmo del factor de camarilla correspondiente, es decir${\displaystyle w_{k,i}=\log \varphi (c_{k,i})}$, dónde${\displaystyle c_{k,i}}$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 C_{k}}$.

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

La importancia de la función de partición Z radica en que muchos conceptos de la mecánica estadística , como la entropía , se generalizan directamente al caso de las redes de Markov, lo que permite 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 asignar una fuerza impulsora a una o más variables aleatorias y explorar la reacción de la red ante 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)}$

La diferenciación formal con respecto a J _v da como resultado 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 forma similar; 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 cual generalmente es computacionalmente inviable (ver 'Inferencia' más adelante).

Al igual que en una red bayesiana , se puede calcular la distribución condicional de un conjunto de nodos.${\displaystyle V'=\{v_{1},\ldots ,v_{i}\}}$valores asignados a otro conjunto de nodos${\displaystyle W'=\{w_{1},\ldots ,w_{j}\}}$en el campo aleatorio de Markov sumando sobre todas las asignaciones posibles a${\displaystyle u\notin V',W'}$Esto se denomina 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 método de Monte Carlo de cadenas de Markov y la propagación de creencias con bucles, suelen ser más factibles en la práctica. Algunas subclases particulares de MRF, como los árboles (véase el árbol de Chow-Liu ), tienen algoritmos de inferencia de tiempo polinomial; el descubrimiento de dichas subclases es un tema de investigación activo. También existen subclases de MRF que permiten una inferencia MAP eficiente , o más probablemente de asignación; ejemplos de estas 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 ]}

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.${\displaystyle o}$. En este modelo, cada función${\displaystyle \varphi _{k}}$es un mapeo de todas las asignaciones tanto al grupo k como a las observaciones${\displaystyle o}$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 ]}

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, ^{[ 13 ]} aprendizaje automático o biología computacional , ^{[ 2 ] [ 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 imagen 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 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 , correspondencia estéreo y recuperación de información . Los métodos estadístico-mecánicos también se han utilizado para analizar modelos MRF para restauración de imágenes bayesianas; Kazuyuki Tanaka y Tsuyoshi Horiguchi estudiaron modelos MRF resolubles para restauración de imágenes en color y métodos computacionales iterativos relacionados para restauración de niveles de gris. ^{[ 16 ] [ 17 ]} 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 donde 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. ^{[ 18 ]} 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.