Red de Markov

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 2 de febrero de 2018; las comprobaciones requieren 8 ediciones .

Una red de Markov, un campo aleatorio de Markov o un modelo de gráfico no dirigido es un modelo de gráfico en el que el conjunto de variables aleatorias tiene la propiedad de Markov descrita por un gráfico no dirigido . Una red de Markov difiere de otro modelo gráfico, la red bayesiana , en su representación de dependencias entre variables aleatorias. Puede expresar algunas dependencias que la red bayesiana no puede expresar (por ejemplo, dependencias cíclicas); en cambio, no puede expresar algunas otras. El prototipo de la red de Markov fue el modelo Ising de magnetización de materiales en física estadística : la red de Markov se presentó como una generalización de este modelo. [una]

Definición

Dado un gráfico no dirigido G = ( V , E ), entonces el conjunto de variables aleatorias ( X v ) v ∈ V indexadas por V forman un campo aleatorio de Markov con respecto a G si cumplen las siguientes propiedades de Markov equivalentes:

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

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

Propiedad local : la variable es condicionalmente independiente de todos los demás valores, dados sus vecinos:

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

donde ne( v ) es el conjunto de vecinos de V , y cl( v ) = { v } ∪ ne( v ) es una vecindad cerrada de v . Propiedad global : Cualquier par de subconjuntos de variables son condicionalmente independientes dado el subconjunto de separación:

{\displaystyle X_{A}\perpecado \!\!\!\perpecado X_{B}|X_{S))

donde todo camino desde un nodo en A hasta un nodo en B pasa por S .

En otras palabras, se dice que un grafo G es un campo aleatorio de Markov con respecto a las probabilidades distribuidas conjuntas P ( X = x ) en un conjunto de variables aleatorias X si y solo si dividir el grafo G implica independencia condicional: Si dos nodos y son dividido en G después de ser eliminado de G conjunto de nodos Z , entonces P ( x = x ) debe afirmar que y son condicionalmente independientes dadas las variables aleatorias correspondientes a Z. Si se cumple esta condición, se dice que G es un mapa independiente (o mapa I) de la distribución de probabilidad . $X_{yo}$ $X_{j}$

Muchas definiciones también requieren que G sea un I-map mínimo, es decir, un I-map del que se elimina un borde, deja de ser un I-map. (Este es un requisito razonable, ya que conduce a la representación más compacta que incluye la menor cantidad de dependencias posible; tenga en cuenta que el gráfico completo es un I-map trivial). En el caso de que G no sea solo un I-map (que es decir, no representa independencias que no se especifican en P ( X = x )), pero tampoco representa dependencias que no se especifican en P ( X = x ), G se denomina aplicación perfecta (perfect map) P ( X = x ). Representa el conjunto de independencias especificadas por P ( X = x ).

Factorización de camarillas

Dado que las propiedades de Markov de una distribución de probabilidad arbitraria son difíciles de establecer, existe una clase ampliamente utilizada de campos aleatorios de Markov que se pueden factorizar de acuerdo con las camarillas del gráfico. El conjunto de variables aleatorias X = ( X v ) v ∈ V para las cuales la densidad conjunta se puede factorizar en camarillas G :

p(x)=\prod_{C\in \operatorname {cl} (G)}\phi_{C}(x_{C})

forma un campo aleatorio de Markov con respecto a G , donde cl( G ) es el conjunto de camarillas de G (la definición es equivalente si solo se usan camarillas máximas). Las funciones φ C a menudo se denominan potenciales de factor o potenciales de camarilla. Aunque hay MRF que no se descomponen (un ejemplo simple se puede construir en un bucle de 4 nodos [2] ), en algunos casos se puede demostrar que están en estados equivalentes:

si la densidad es positiva
si la gráfica es armónica

Cuando existe tal descomposición, se puede construir un gráfico de factores para la red.

Ejemplo

Modelo logístico

El modelo logístico de un campo aleatorio de Markov que usa la función como una función de la distribución conjunta completa se puede escribir como $f_{k}$

P(X=x)={\frac {1}{Z}}\exp \left(\sum_k}w_{k}^{\top }f_{k}(x_{\{k \)))\right)={\frac {1}{Z}}\exp \left(\sum_{k}\sum_{i=1}^{N_{k}}w_{k,i} \cdot f_{k,i}(x_{\{k\)))\right)

con función de distribución

Z=\sum_{x\in {\mathcal {X))}\exp \left(\sum_{k}w_{k}^{\top }f_{k}(x_{\{k \)))\Correcto)

donde es el conjunto de posibles distribuciones de valores de variables aleatorias de todas las redes. ${\mathcal {X}}$

Campo aleatorio gaussiano de Markov

Formas de la distribución normal multivariada de un campo aleatorio de Markov con respecto a un gráfico G = ( V , E ) si los bordes faltantes corresponden a ceros en la matriz de precisión (matriz de covarianza inversa ):

X=(X_{v})_{v\in V}\sim {\mathcal {N))({\boldsymbol {\mu )),\Sigma )\qquad {\text{tal que)) \qquad (\Sigma ^{-1})_{uv}=0\quad {\text{if))\quad \{u,v\}\notin E.

[3]

Notas

↑ Kindermann, Ross; Snell, J. Laurie. Campos aleatorios de Markov y sus aplicaciones . - Sociedad Matemática Americana, 1980. - ISBN 0-8218-5001-6 .
↑ Moussouris, John. Sistemas aleatorios de Gibbs y Markov con restricciones // Journal of Statistical Physics : diario. - 1974. - vol. 10 , núm. 1 . - P. 11-33 . -doi : 10.1007/ BF01011714 .
↑ Rue, Havard; Retenido, Leonhard. Campos aleatorios gaussianos de Markov : teoría y aplicaciones . - CRC Press , 2005. - ISBN 1584884320 .

Graficar modelos probabilísticos
red bayesiana Red causal bayesiana Red de Markov Modelo oculto de Markov

Aprendizaje automático y minería de datos
Tareas	Problema de clasificación Aprender sin un maestro Aprendizaje asistido por profesores Análisis de regresión AutoML reglas de asociación Extracción de características entrenamiento de rasgos Entrenamiento de clasificación Derivación gramatical Aprender en línea
Aprendiendo con un maestro	método del k-vecino más cercano Clasificador bayesiano ingenuo árbol de decisión Máquinas de vectores soporte Regresión lineal Regresión logística perceptrón conjuntos de modelos Harpillera impulsar bosque aleatorio Método de vector relevante
análisis de conglomerados	método k-medias método de agrupamiento difuso Agrupación jerárquica algoritmo EM ABEDUL CURAR DBSCAN ÓPTICA Desplazamiento medio
Reducción de dimensionalidad	Análisis factorial Método de componentes principales CCA ACI LDA Expansión de matriz no negativa t-SNE
Pronóstico estructural	Graficar modelo probabilístico red bayesiana Modelo oculto de Markov FRC
Detección de anomalías	método del k-vecino más cercano Nivel de emisión local
Graficar modelos probabilísticos	red bayesiana Red de Markov Modelo oculto de Markov
Redes neuronales	Máquina Boltzmann limitada mapa autoorganizado Función de activación Sigmoideo softmax Funcion de base radial Método de propagación hacia atrás Aprendizaje profundo perceptrón multicapa Red neuronal recurrente memoria a corto plazo Bloque recurrente controlado Red neuronal convolucional U-red Codificador automático
Aprendizaje reforzado	proceso de Markov Ecuación de Bellman Algoritmo codicioso Q-aprendizaje SARAS Diferencia temporal (DT)
Teoría	Teoría de Vapnik-Chervonenkis Dilema de dispersión de sesgo Teoría del aprendizaje computacional Minimización empírica del riesgo El aprendizaje de Occam aprendizaje PAC Teoría del aprendizaje estadístico
revistas y congresos	NeurIPS ICML ML JMLR ArXiv:cs.LG