Actualizado por ultima vez el 3 de septiembre de 2021, por Luis Benites.
Markov Chain Monte Carlo es una forma de muestrear una distribución complicada . ¿Qué es una “distribución complicada”? Uno para el que es difícil, o casi imposible, encontrar probabilidades. Este tipo de problemas se denominan problemas de “ alta dimensión ”. Un ejemplo de un problema de alta dimensión es calcular la importancia relativa de las páginas en la World Wide Web. No solo son sus miles de millones de páginas, sino que están en constante estado de cambio. Markov Chain Monte Carlo puede resolver este tipo de problemas en un tiempo razonable.
Markov Chain Monte Carlo no es una técnica específica: en realidad es una gran clase de algoritmos de muestreo que incluye:
el algoritmo Metropolis ,
el muestreo de Gibbs, el muestreo de
cortes .
¿Qué es «alta dimensión»?
La clave para entender MCMC es entender el espacio de alta dimensión . Es un capítulo completo en algunos libros de informática, por lo que no entraré en más que una breve descripción aquí.
Un hipercubo.
Básicamente, el espacio de alta dimensión es cualquier cosa más allá del mundo 2D y 3D al que estamos acostumbrados. El espacio de alta dimensión no se comporta de la manera que pensamos que debería. Por ejemplo, un cubo de 4 dimensiones, el hipercubo, colapsa sobre sí mismo a medida que gira. De manera similar, una esfera de radio unitario de alta dimensión tiene un volumen de cero; Se necesita Cubature (integración numérica) para encontrar estos volúmenes. Un problema matemático de alta dimensión tiene datos que se encuentran en espacios de alta dimensión. Por lo tanto, los datos no se “comportan” como pensamos que deberían hacerlo. Las dimensiones altas son difíciles de comprender (se dice que incluso Einstein tuvo problemas para visualizar hipercubos, aunque realizó las matemáticas detrás de cuatro y cinco dimensiones) y su espacio aumenta exponencialmente con cada dimensión adicional, lo que hace prácticamente imposible agregar cualquier significado numérico a los resultados. De ello se deduce, entonces, que encontrar probabilidades para datos de alta dimensión es extremadamente difícil. Las reglas de probabilidad habituales no se aplican, por lo que se necesitan otras nuevas, como MCMC.
Nota: si está interesado en obtener más información sobre el espacio de alta dimensión, le recomiendo leer los primeros dos capítulos de Fundamentos de la ciencia de datos (pdf descargable, gratuito) .
Cadenas de Markov
Un ejemplo de un modelo de Markov, donde los dados representan estados y las bolas de colores se utilizan para la transición entre estados.
Las cadenas de Markov se utilizan para modelar probabilidades, donde toda la información necesaria para predecir eventos futuros se puede codificar en el estado actual. Puede encontrar un ejemplo simple, paso a paso, usando dos dados para hacer predicciones, en el artículo Modelo oculto de Markov . Básicamente, dos dados de colores representan el estado actual (rojo o negro) y una bola de color elegida de una bolsa da la probabilidad de pasar al siguiente estado. ¡En la vida real, es probable que el número de estados sea mucho mayor que solo dos! Hopcraft da el ejemplo concreto del habla, donde la última k Se pueden analizar las sílabas pronunciadas por el hablante, dando la probabilidad de cuál podría ser la siguiente palabra. El discurso se mueve de un estado a otro de tal manera que la siguiente palabra depende únicamente del estado actual (es decir, lo que se dice en ese momento). El número de estados posibles para las últimas k-sílabas podría llegar a millones, lo que sería imposible de analizar a mano (o incluso con un algoritmo informático estándar).
Más técnicamente, esta información se puede colocar en una matriz y un vector (una matriz de columna) llamados vectores de probabilidad. Muchas, muchas, muchas iteraciones después y tienes una colección de vectores de probabilidad… formando las cadenas de Markov.
El propósito de la Cadena de Markov Monte Carlo es muestrear un espacio de muestra muy grande , uno que contenga googols de elementos de datos. Un ejemplo de un espacio de muestra de este tipo es la World Wide Web. El análisis de la web en busca de páginas importantes está detrás de los motores de búsqueda como Google , y utilizan las cadenas de Markov como parte de sus análisis. Esencialmente, envían un bot a una caminata aleatoria (literal) por la web, siguiendo los enlaces donde quiera que vayan. Estos recorridos aleatorios se registran en una matriz, junto con las probabilidades de llegar a una página determinada.
¿Por qué cadena de Markov Monte Carlo ?
Bien, entonces tenemos una distribución complicada, como la red mundial. MCMC es una forma de muestrear eficientemente de esta complicada distribución. El muestreo aleatorio simple o métodos similares (como elegir un nombre de un sombrero) no funcionarán porque no podrá definir fácilmente su población porque está creciendo exponencialmente. Incluso si encontrara una forma de definir las páginas en la WWW actual, los millones de nuevos contenidos generados en un minuto a partir de ahora tendrán cero probabilidades de ser elegidos. Desde un punto de vista estadístico, esto es inaceptable. Introduzca la cadena de Markov Monte Carlo.
La parte “ Monte Carlo ” de MCMC es solo un apodo para el tipo de muestreo que estamos haciendo, que es un muestreo basado en recorridos aleatorios. Monte Carlo es un complejo de juegos de azar en Mónaco, por lo que fácilmente podría haberse llamado «Markov Chain Las Vegas» o simplemente «Markov Chain Sampling».
MCMC y distribuciones limitantes
MCMC utiliza recorridos aleatorios (esencialmente, un gran generador de números aleatorios) para estimar probabilidades con la misma distribución límite que la variable aleatoria que intenta simular. Cuando el tiempo n > ∞, una cadena de Markov tiene una distribución límite π = (π j ) j∈s . Se puede encontrar un valor para π resolviendo una serie de ecuaciones lineales .
Referencias:
Blum, J. et. Alabama. (2011). Fundamentos de la ciencia de datos. Recuperado el 11 de agosto de 2017 de: https://www.cs.cornell.edu/jeh/bookMay2015.pdf
Agresti A. (1990) Categorical Data Analysis. John Wiley and Sons, Nueva York.
Jerrum, M. y Sinclair, A. (1996). El método Monte Carlo de la cadena de Markov: un enfoque para el conteo y la integración aproximados. En DS Hochbaum (Ed.), Algoritmos de aproximación para problemas NP-difíciles (págs. 482–519). Editorial PWS.
Kotz, S.; et al., editores. (2006), Enciclopedia de Ciencias Estadísticas , Wiley.
