Campo aleatorio de Markov

Dado un grafo no dirigido ${\displaystyle G=(V,E)}$, un conjunto de variables aleatorias ${\displaystyle X=(X_{v})_{v\in V}}$ indexadas por ${\displaystyle V}$ constituyen un MRF con respecto a ${\displaystyle 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:

${\displaystyle X_{u}\perp \!\!\!\perp X_{v}\mid X_{V\setminus \{u,v\}}\quad {\text{if }}\{u,v\}\notin E}$

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

${\displaystyle X_{v}\perp \!\!\!\perp X_{V\setminus \operatorname {cl} (v)}\mid X_{\operatorname {ne} (v)}}$

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

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

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

donde todo camino de un nodo en ${\displaystyle A}$ a un nodo en ${\displaystyle B}$ pasa a través de ${\displaystyle 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.

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

Si esta densidad conjunta se puede factorizar sobre el clique de ${\displaystyle G}$:

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

entonces ${\displaystyle X}$ forma un campo aleatorio de Markov con respecto a ${\displaystyle G}$. ${\displaystyle \operatorname {cl} (G)}$ es el conjunto de cliques de ${\displaystyle 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 ${\displaystyle 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:[3]

• 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.

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

${\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 sencillamente un producto escalar sobre las configuraciones del 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 posible asignaciones de los valores de todas las variables aleatorias de la red. Usualmente, las funciones de características ${\displaystyle f_{k,i}}$ son definidas de forma que sean indicadoras de la configuración del clique, i.e. ${\displaystyle f_{k,i}(x_{\{k\}})=1}$ if ${\displaystyle 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 ${\displaystyle N_{k}=|\operatorname {dom} (C_{k})|}$ es la cardinalidad del clique, y el peso correspondiente a una función ${\displaystyle f_{k,i}}$ se corresponde con el logaritmo del potencial del clique correspondiente, i.e. ${\displaystyle w_{k,i}=\log \phi (c_{k,i})}$, donde ${\displaystyle c_{k,i}}$ la i-ésima configuración posible del k-ésimo clique, i.e. el i-ésimo valor en el dominio del clique ${\displaystyle 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 ${\displaystyle {\mathcal {X}}}$ 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:

${\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)}$

Formalmente diferenciando 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 mima 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}.}$

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.

Como en una red bayesiana se puede obtener la distribución condicional de un conjunto de nodos ${\displaystyle V'=\{v_{1},\ldots ,v_{i}\}}$ dado otro conjunto de nodos ${\displaystyle W'=\{w_{1},\ldots ,w_{j}\}}$ en el MRF, sumando sobre todas las posibles asignaciones de los ${\displaystyle u\notin V',W'}$; 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.[5][6] 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.[7]