Campo aleatorio de Markov

En el ámbito de la física y la probabilidad, un Campo aleatorio de Markov (abreviado MRF por sus siglas en inglés), Red Markov o modelo gráfico no dirigido es un conjunto de variables aleatorias que poseen la propiedad de Markov descrito por un grafo no dirigido. Un MRF es similar a una red bayesiana en su representación de las dependencias entre variables aleatorias; la diferencia radica en que las redes bayesianas son dirigidas y acíclicas, mientras que en los MRF las redes son no dirigidas y pueden ser cíclicas. De esta manera, un MRF puede representar determinadas dependencias que una red bayesiana no puede (como dependencias cíclicas); por otro lado, existen dependencias que no puede representar (como dependencias inducidas). El grafo subyacente de un MRF puede ser finito o infinito.

Cuando la función de distribución conjunta de las variables aleatorias es estrictamente positiva, se le llama también campo aleatorio de Gibbs, porque, según el teorema Hammersley–Clifford, puede ser representado por una medida de Gibbs para un función de energía apropiada (localmente definida). El prototipico MRF es el modelo de Ising; de hecho, el MRF fue introducido como el entorno general para el modelo de Ising. En el ámbito de la inteligencia artificial, un MRF suele usarse para modelar varias fases de algoritmos de procesamiento de imagen y visión por computadora.

Definición

Dado un grafo no dirigido $G=(V,E)$, un conjunto de variables aleatorias $X=(X_v{)}_{v\in V}$ indexadas por $V$ constituyen un MRF con respecto a $G$ si satisfacen las propiedades de Markov locales:

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

$X_u\perp \perp X_v\mid X_{V\setminus \{u,v\}}\text{if }\{u,v\}\notin E$

Propiedad local de Markov: una variable es condicionalmente independiente de todas las otras variables dadas sus vecinos:

$X_v\perp \perp X_{V\setminus \mathrm{cl}(v)}\mid X_{\mathrm{ne}(v)}$

donde $\mathrm{ne}(v)$ es el conjunto de los vecinos $v$, y $\mathrm{cl}(v)=v\cup \mathrm{ne}(v)$ es la vecindad cerrada de $v$.

Propiedad global de Markov: dos subconjuntos de variables cualesquiera son condicionalmente independientes dado un subconjunto que las separa:

$X_A\perp \perp X_B\mid X_S$

donde todo camino de un nodo en $A$ a un nodo en $B$ pasa a través de $S$.

Las tres propiedades anteriores no son equivalentes: la primera es más débil que la segunda y esta es más débil que la tercera.

Factorización de un clique

Como las propiedades de Markov de una distribución de probabilidad arbitraria pueden ser difícil de establecer, una clase comúnmente usada de campos aleatorios de Markov son aquellos que pueden ser factorizados de acuerdo con el clique de la gráfica.

Dado un conjunto de variables aleatorias $X=(X_v{)}_{v\in V}$, sea $P(X=x)$ la probabilidad de una configuración de campo en particular $x$ en $X$. Es decir, $P(X=x)$ es la probabilidad de encontrar que las variables aleatorias $X$ asuman el valor particular de $x$. Porque $X$ es un conjunto, la probabilidad de $x$ deben tomarse con respecto a una distribución conjunta de $X_v$.

Si esta densidad conjunta se puede factorizar sobre el clique de $G$:

$P(X=x)=\prod _{C\in \mathrm{cl}(G)}{\varphi }_C(x_C)$

entonces $X$ forma un campo aleatorio de Markov con respecto a $G$. $\mathrm{cl}(G)$ es el conjunto de cliques de $G$. La definición es equivalente si solo se utiliza el máximo de los cliques. Las funciones φ_C a veces se conocen como factores potenciales potencial del clique. La palabra potencial se aplica a menudo al logaritmo de φ_C. Esto se debe a que, en la estadística mecánica log(φ_C) tiene una interpretación directa como la energía potencial de la configuración $x_C$.

A pesar de que algunos MRFs no factoricen (un ejemplo sencillo puede ser construido con un ciclo de 4 nodos), en algunos casos puede ser mostrado que son equivalentes bajo ciertas condiciones:

• Si la densidad es positiva (por el teorema Hammersley–Clifford),
• Si el grafo es cordal (por equivalencia con una red bayesiana).

Cuándo tal factorización existe, es posible de construir un grafo de factores para la red.

Modelo logístico

Cualquier MRF (con una densidad estrictamente positiva) puede ser reescrito como un modelo logístico con funciones de características $f_k$ tal que la distribución de probabilidad conjunta puede ser escrita:

$P(X=x)=\frac{1}{Z}\exp (\sum _k{w}_k^{\mathrm{\top }}{f}_k(x_{\{k\}}))$

donde la notación

$w_k^{\mathrm{\top }}{f}_k(x_{\{k\}})=\sum _{i=1}^{N_k}{w}_{k,i}\cdot f_{k,i}(x_{\{k\}})$

Es sencillamente un producto escalar sobre las configuraciones del campo, y Z es la función de partición:

$Z=\sum _{x\in 𝒳}\exp (\sum _k{w}_k^{\mathrm{\top }}{f}_k(x_{\{k\}})).$

Aquí, $𝒳$ denota el conjunto de todas las posible asignaciones de los valores de todas las variables aleatorias de la red. Usualmente, las funciones de características $f_{k,i}$ son definidas de forma que sean indicadoras de la configuración del clique, i.e. $f_{k,i}(x_{\{k\}})=1$ if $x_{\{k\}}$ corresponde a la i-ésima configuración posible del k-ésimo clique, o 0 en otro caso. Este modelo es equivalente al modelo descrito anteriormente (con factorización respecto a los cliques), si $N_k=|\mathrm{dom}(C_k)|$ es la cardinalidad del clique, y el peso correspondiente a una función $f_{k,i}$ se corresponde con el logaritmo del potencial del clique correspondiente, i.e. $w_{k,i}=\log \varphi (c_{k,i})$, donde $c_{k,i}$ la i-ésima configuración posible del k-ésimo clique, i.e. el i-ésimo valor en el dominio del clique $C_k$.

Como las propiedades de Markov de una distribución de probabilidad arbitraria pueden ser difíciles de establecer, una clase generalmente utilizada de MRF son los que pueden ser factorizados según los cliques del grafo.

La probabilidad P es llamada a menuda la medida de Gibbs. Esta representación de un MRF como un modelo logístico sólo es posible si todos los factores de un clique son no nulos, i.e. si a ninguno de los elementos de $𝒳$ le está asignado una probabilidad de 0. Esto permite que se puedan aplicar técnicas del álgebra matricial.

La importancia de la función de partición Z es que muchos conceptos de la estadística mecánica, como la entropía, se pueden generalizar directamente al caso de redes de Markov, obteniendo de esta manera una comprensión intuitiva. Además, la función de partición permite la aplicación de métodos variacionales para la solución del problema: se puede aplicar una fuerza de a una o más variables aleatorias, y estudiar la forma en que cambia la red en respuesta a esta perturbación. Así, por ejemplo, uno puede añadir un término J_v, a cada vértice v del grafo, obteniéndose:

$Z[J]=\sum _{x\in 𝒳}\exp (\sum _k{w}_k^{\mathrm{\top }}{f}_k(x_{\{k\}})+\sum _v{J}_v{x}_v)$

Formalmente diferenciando con respecto a J_v se obtiene el valor esperado de la variable aleatoria X_v asociada al vértice v:

$E[X_v]=\frac{1}{Z}{\frac{\partial Z[J]}{\partial J_v}|}_{J_v=0}.$

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

$C[X_u,X_v]=\frac{1}{Z}{\frac{{\partial }^{2}Z[J]}{\partial J_u\partial J_v}|}_{J_u=0,J_v=0}.$

Los modelos logísticos son especialmente convenientes debido a su interpretación. Un modelo logístico provee una forma mucho más compacta de representar muchas distribuciones, especialmente cuando las variables tienen dominios muy grandes. También son convenientes porque su función de verosimilitud es convexa. Desafortunadamente, aunque la verosimilitud de la logística de una red de Markov es convexa, la evaluación de la verosimilitud o su gradiente para un modelo requiere del cálculo de inferencia en el modelo, lo cual es, generalmente, impracticable computacionalmente.

Ejemplos

MRF Gausiano

Una distribución normal multivariante forma un MRF con respecto a un grafo $G=(V,E)$ si las aristas faltantes se corresponden con ceros en la matriz de precisión (la inversa de la matriz de covarianza):

$X=(X_v{)}_{v\in V}\sim 𝒩(\mathit{\mu },\mathrm{\Sigma })$

Tal que:

$({\mathrm{\Sigma }}^{-1}{)}_{uv}=0\text{if}\{u,v\}\notin E.$

Modelo Oculto de Markov

Los nodos X representan estados mientras que los nodos Y representan observaciones sobre esos estados

En el modelo oculto de Markov, el estado no es visible directamente, pero la observación, que depende del estado, es visible. Cada estado tiene una distribución de probabilidad sobre los posibles tokens de salida. Por lo tanto, la secuencia de tokens generada por un HMM proporciona información sobre la secuencia de estados.

Inferencia

Como en una red bayesiana se puede obtener la distribución condicional de un conjunto de nodos $V^{\prime }=\{v_1,\dots ,v_i\}$ dado otro conjunto de nodos $W^{\prime }=\{w_1,\dots ,w_j\}$ en el MRF, sumando sobre todas las posibles asignaciones de los $u\notin V^{\prime },W^{\prime }$; esto se llama inferencia exacta. Sin embargo esto es un problema NP-completo, y por tanto computacionalmente costoso para el caso general. Técnicas de aproximación como Monte Carlo sobre cadenas de Markov y propagación de creencias son más factibles en la práctica. Existen casos particulares de MRFs, como los árboles, que poseen algoritmos de inferencia polinomiales; encontrar estos casos particulares es un campo de investigación activo en la actualidad. Existen también subconjuntos de MRFs que permiten la inferencia del MAP o la asignación más verosímil, de manera eficiente; ejemplos de estos son las redes asociativas. Otro subconjunto interesante es el de los modelos descomponibles (cuando el grafo es cordal): existiendo en este caso una forma cerrada para MLE, es posible descubrir una estructura consistente para cientos de variables.