La inferencia probabilística implica la estimación de un valor o densidad esperada utilizando un modelo probabilístico.
A menudo, la inferencia directa de valores no es manejable con los modelos probabilísticos y, en su lugar, se deben utilizar métodos de aproximación.
El muestreo de Monte Carlo de cadenas de Markov proporciona una clase de algoritmos para el muestreo aleatorio sistemático de distribuciones de probabilidad de alta dimensión. A diferencia de los métodos de muestreo de Montecarlo que son capaces de extraer muestras independientes de la distribución, los métodos de Montecarlo de cadenas de Markov extraen muestras en las que la siguiente muestra depende de la muestra existente, lo que se denomina una cadena de Markov. Esto permite a los algoritmos acotar la cantidad que se está aproximando de la distribución, incluso con un gran número de variables aleatorias.
En este post, descubrirá una suave introducción a Markov Chain Monte Carlo para el aprendizaje automático.
Después de leer este post, sabrá:
- El muestreo de Monte Carlo no es eficaz y puede ser intratable para modelos probabilísticos de alta dimensión.
- Markov Chain Monte Carlo proporciona un enfoque alternativo para el muestreo aleatorio de una distribución de probabilidad de alta dimensión en la que la siguiente muestra depende de la muestra actual.
- El muestreo de Gibbs y el algoritmo más general de Metrópolis-Hastings son los dos enfoques más comunes para el muestreo de Markov Chain Monte Carlo.
Comienza tu proyecto con mi nuevo libro Probability for Machine Learning, que incluye tutoriales paso a paso y los archivos de código fuente de Python para todos los ejemplos.
Comencemos.
Una suave introducción a Markov Chain Monte Carlo para la probabilidad
Foto de Murray Foubister, algunos derechos reservados.
Resumen
Este tutorial está dividido en tres partes; son:
- Desafío de la inferencia probabilística
- Qué es el Monte Carlo de cadenas de Markov
- Algoritmos de Monte Carlo de cadenas de Markov
Desafío de la inferencia probabilística
Calcular una cantidad a partir de un modelo probabilístico se denomina de forma más general inferencia probabilística, o simplemente inferencia.
Por ejemplo, podemos estar interesados en calcular una probabilidad esperada, estimar la densidad, u otras propiedades de la distribución de probabilidad. Este es el objetivo del modelo probabilístico, y el nombre de la inferencia realizada suele adoptar el nombre del modelo probabilístico, por ejemplo, la inferencia bayesiana se realiza con un modelo probabilístico bayesiano.
El cálculo directo de la cantidad deseada a partir de un modelo de interés es intratable para todos los modelos probabilísticos, salvo los más triviales. En su lugar, la probabilidad o densidad esperada debe aproximarse por otros medios.
Para la mayoría de los modelos probabilísticos de interés práctico, la inferencia exacta es intratable, por lo que tenemos que recurrir a alguna forma de aproximación.
– Página 523, Pattern Recognition and Machine Learning, 2006.
El cálculo deseado es típicamente una suma de una distribución discreta de muchas variables aleatorias o integral de una distribución continua de muchas variables y es intratable de calcular. Este problema existe en ambas escuelas de probabilidad, aunque es quizás más frecuente o común con la probabilidad bayesiana y la integración sobre una distribución posterior para un modelo.
Los bayesianos, y a veces también los frecuentistas, necesitan integrar sobre distribuciones de probabilidad posiblemente de alta dimensión para hacer inferencia sobre los parámetros del modelo o para hacer predicciones. Los bayesianos necesitan integrar sobre la distribución posterior de los parámetros del modelo dados los datos, y los frecuentistas pueden necesitar integrar sobre la distribución de los observables dados los valores de los parámetros.
– Página 1, Markov Chain Monte Carlo in Practice, 1996.
La solución típica es extraer muestras independientes de la distribución de probabilidad, y luego repetir este proceso muchas veces para aproximar la cantidad deseada. Esto se conoce como muestreo de Montecarlo o integración de Montecarlo, llamado así por la ciudad de Mónaco que tiene muchos casinos.
El problema con el muestreo de Montecarlo es que no funciona bien en altas dimensiones. Esto se debe, en primer lugar, a la maldición de la dimensionalidad, en la que el volumen del espacio muestral aumenta exponencialmente con el número de parámetros (dimensiones).
En segundo lugar, y quizás lo más crítico, es que el muestreo de Montecarlo asume que cada muestra aleatoria extraída de la distribución objetivo es independiente y puede ser extraída independientemente. Esto no es típicamente el caso o es intratable para la inferencia con modelos probabilísticos estructurados o gráficos bayesianos.
Desea aprender probabilidad para el aprendizaje automático
Tome mi curso intensivo gratuito de 7 días por correo electrónico ahora (con código de muestra).
Haga clic para inscribirse y también obtenga una versión gratuita del curso en PDF Ebook.
Descargue su minicurso gratuito
Qué es Markov Chain Monte Carlo
La solución al muestreo de distribuciones de probabilidad en altas dimensiones es utilizar Markov Chain Monte Carlo, o MCMC para abreviar.
El método más popular para el muestreo de distribuciones de alta dimensión es el Monte Carlo de cadenas de Markov o MCMC
– Página 837, Machine Learning: A Probabilistic Perspective, 2012.
Al igual que los métodos de Monte Carlo, Markov Chain Monte Carlo se desarrolló por primera vez alrededor de la misma época en que se desarrollaron los primeros ordenadores y se utilizó en los cálculos para la física de partículas necesarios como parte del proyecto Manhattan para el desarrollo de la bomba atómica.
Monte Carlo
Monte Carlo es una técnica para muestrear aleatoriamente una distribución de probabilidad y aproximar una cantidad deseada.
Los algoritmos de Monte Carlo, se utilizan en muchas ramas de la ciencia para estimar cantidades que son difíciles de calcular con exactitud.
– Página 530, Artificial Intelligence: A Modern Approach, 3ª edición, 2009.
Los métodos de Monte Carlo suelen suponer que podemos extraer eficientemente muestras de la distribución objetivo. A partir de las muestras extraídas, podemos estimar la suma o la cantidad integral como la media o la varianza de las muestras extraídas.
Una forma útil de pensar en un proceso de muestreo de Montecarlo es considerar una forma bidimensional compleja, como una espiral. No podemos definir fácilmente una función que describa la espiral, pero podemos extraer muestras del dominio y determinar si forman parte de la espiral o no. En conjunto, un gran número de muestras extraídas del dominio nos permitirá resumir la forma (densidad de probabilidad) de la espiral.
Cadena de Markov
La cadena de Markov es un método sistemático para generar una secuencia de variables aleatorias donde el valor actual depende probabilísticamente del valor de la variable anterior. En concreto, la selección de la siguiente variable sólo depende de la última variable de la cadena.
Una cadena de Markov es un tipo especial de proceso estocástico, que se ocupa de la caracterización de secuencias de variables aleatorias. Se presta especial interés a los comportamientos dinámicos y limitantes de la secuencia.
– Página 113, Markov Chain Monte Carlo: Stochastic Simulation for Bayesian Inference, 2006.
Considere un juego de mesa que implique lanzar dados, como serpientes y escaleras (o toboganes y escaleras). La tirada de un dado tiene una distribución de probabilidad uniforme a lo largo de 6 etapas (números enteros del 1 al 6). Tienes una posición en el tablero, pero tu próxima posición en el tablero sólo se basa en la posición actual y en la tirada aleatoria de los dados. Tus posiciones específicas en el tablero forman una cadena de Markov.
Otro ejemplo de cadena de Markov es un paseo aleatorio en una dimensión, donde los posibles movimientos son 1, -1, elegidos con igual probabilidad, y el siguiente punto en la línea numérica del paseo sólo depende de la posición actual y del movimiento elegido al azar.
En un nivel alto, una cadena de Markov se define en términos de un gráfico de estados sobre el que el algoritmo de muestreo realiza un paseo aleatorio.
– Página 507, Probabilistic Graphical Models: Principles and Techniques, 2009.
Markov Chain Monte Carlo
La combinación de estos dos métodos, Markov Chain y Monte Carlo, permite el muestreo aleatorio de distribuciones de probabilidad de alta dimensión que honra la dependencia probabilística entre las muestras mediante la construcción de una cadena de Markov que componen la muestra de Monte Carlo.
MCMC es esencialmente la integración de Monte Carlo utilizando cadenas de Markov. La integración de Monte Carlo extrae muestras de la distribución requerida, y luego forma promedios muestrales para aproximar las expectativas. Markov Chain Monte Carlo extrae estas muestras ejecutando una cadena de Markov inteligentemente construida durante mucho tiempo.
– Página 1, Markov Chain Monte Carlo in Practice, 1996.
Específicamente, MCMC es para realizar inferencia (por ejemplo, estimar una cantidad o una densidad) para las distribuciones de probabilidad donde las muestras independientes de la distribución no se pueden extraer, o no se pueden extraer fácilmente.
Como tal, no se puede utilizar el muestreo de Monte Carlo.
En cambio, las muestras se extraen de la distribución de probabilidad mediante la construcción de una cadena de Markov, donde la siguiente muestra que se extrae de la distribución de probabilidad depende de la última muestra que se extrajo. La idea es que la cadena se establecerá (encontrará el equilibrio) en la cantidad deseada que estamos infiriendo.
Sin embargo, todavía estamos muestreando de la distribución de probabilidad objetivo con el objetivo de aproximar una cantidad deseada, por lo que es apropiado referirse a la colección resultante de muestras como una muestra de Monte Carlo, por ejemplo, la extensión de las muestras extraídas a menudo forma una larga cadena de Markov.
La idea de imponer una dependencia entre las muestras puede parecer extraña al principio, pero puede tener más sentido si consideramos dominios como el paseo aleatorio o los juegos de serpientes y escaleras, donde se requiere dicha dependencia entre las muestras.
Algoritmos de Monte Carlo de cadenas de Markov
Existen muchos algoritmos de Monte Carlo de cadenas de Markov que, en su mayoría, definen diferentes formas de construir la cadena de Markov al realizar cada muestra de Monte Carlo.
El paseo aleatorio proporciona una buena metáfora para la construcción de la cadena de Markov de muestras, sin embargo, es muy ineficiente. Consideremos el caso de que queramos calcular la probabilidad esperada; es más eficiente acercarse a esa cantidad o densidad, en lugar de deambular por el dominio. Los algoritmos Markov Chain Monte Carlo son intentos de aprovechar cuidadosamente las propiedades del problema para construir la cadena de forma eficiente.
Esta secuencia se construye de manera que, aunque la primera muestra puede generarse a partir del prior, las muestras sucesivas se generan a partir de distribuciones que se acercan cada vez más al posterior deseado.
– Página 505, Probabilistic Graphical Models: Principles and Techniques, 2009.
Los algoritmosMC son sensibles a su punto de partida, y a menudo requieren una fase de calentamiento o burn-in para avanzar hacia una parte fructífera del espacio de búsqueda, después de la cual se pueden descartar las muestras previas y recoger las muestras útiles.
Además, puede ser un reto saber si una cadena ha convergido y recogido un número suficiente de pasos. A menudo se requiere un número muy grande de muestras y se detiene una ejecución dado un número fijo de pasos.
… es necesario descartar algunas de las muestras iniciales hasta que la cadena de Markov se haya quemado, o entrado en su distribución estacionaria.
– Página 838, Machine Learning: A Probabilistic Perspective, 2012.
El algoritmo general de Monte Carlo de cadenas de Markov más común se llama muestreo de Gibbs; una versión más general de este muestreador se llama algoritmo de Metrópolis-Hastings.
Veamos con más detalle ambos métodos.
Algoritmo de muestreo de Gibbs
El algoritmo de muestreo de Gibbs es una aproximación a la construcción de una cadena de Markov en la que la probabilidad de la siguiente muestra se calcula como la probabilidad condicional dada la muestra anterior.
Las muestras se construyen cambiando una variable aleatoria cada vez, lo que significa que las muestras posteriores están muy cerca en el espacio de búsqueda, por ejemplo, local. Como tal, existe cierto riesgo de que la cadena se atasque.
La idea detrás del muestreo de Gibbs es que muestreamos cada variable a su vez, condicionada a los valores de todas las demás variables de la distribución.
– Página 838, Machine Learning: A Probabilistic Perspective, 2012.
El muestreo de Gibbs es apropiado para aquellos modelos probabilísticos en los que esta probabilidad condicional puede ser calculada, por ejemplo, la distribución es discreta en lugar de continua.
… El muestreo de Gibbs es aplicable sólo en ciertas circunstancias; en particular, debemos ser capaces de muestrear de la distribución P(Xi | x-i). Aunque este paso de muestreo es fácil para los modelos gráficos discretos, en los modelos continuos, la distribución condicional puede no ser una que tenga una forma paramétrica que permita el muestreo, por lo que Gibbs no es aplicable.
– Página 515, Probabilistic Graphical Models: Principles and Techniques, 2009.
Algoritmo de Metrópolis-Hastings
El Algoritmo de Metrópolis-Hastings es apropiado para aquellos modelos probabilísticos en los que no podemos muestrear directamente la llamada distribución de probabilidad del siguiente estado, como la distribución de probabilidad condicional utilizada por el Muestreo de Gibbs.
A diferencia de la cadena de Gibbs, el algoritmo no asume que podamos generar muestras del siguiente estado a partir de una distribución objetivo concreta.
– Página 517, Probabilistic Graphical Models: Principles and Techniques, 2009.
En cambio, el algoritmo de Metrópolis-Hastings implica el uso de una distribución de probabilidad sustituta o de propuesta que se muestrea (a veces llamada núcleo), y luego un criterio de aceptación que decide si la nueva muestra se acepta en la cadena o se descarta.
Se basan en una cadena de Markov cuya dependencia del predecesor se divide en dos partes: una propuesta y una aceptación de la propuesta. Las propuestas sugieren un siguiente paso arbitrario en la trayectoria de la cadena y la aceptación se asegura de que se mantenga la dirección límite adecuada rechazando los movimientos no deseados de la cadena.
– Página 6, Markov Chain Monte Carlo: Stochastic Simulation for Bayesian Inference, 2006.
El criterio de aceptación es probabilístico y se basa en la probabilidad de que la distribución de la propuesta difiera de la verdadera distribución de probabilidad del siguiente estado.
El Algoritmo Metrópolis-Hastings es un algoritmo de Monte Carlo de cadenas de Markov más general y flexible, que subsume muchos otros métodos.
Por ejemplo, si la distribución de probabilidad condicional del siguiente estado se utiliza como la distribución de la propuesta, entonces el Metrópolis-Hastings es generalmente equivalente al Algoritmo de Muestreo de Gibbs. Si se utiliza una distribución de propuesta simétrica como una gaussiana, el algoritmo es equivalente a otro método MCMC llamado algoritmo de Metrópolis.
Lectura adicional
Esta sección proporciona más recursos sobre el tema si se quiere profundizar.
Libros
- Markov Chain Monte Carlo in Practice, 1996.
- Markov Chain Monte Carlo: Stochastic Simulation for Bayesian Inference, 2006.
- Handbook of Markov Chain Monte Carlo, 2011.
- Probabilistic Graphical Models: Principles and Techniques, 2009.
Capítulos
- Capítulo 24 Markov chain Monte Carlo (MCMC) inference, Machine Learning: A Probabilistic Perspective, 2012.
- Sección 11.2. Markov Chain Monte Carlo, Pattern Recognition and Machine Learning, 2006.
- Sección 17.3 Markov Chain Monte Carlo Methods, Deep Learning, 2016.
- Método Monte Carlo, Wikipedia.
- Cadena de Markov, Wikipedia.
- Monte Carlo de cadena de Markov, Wikipedia.
- Muestreo de Gibbs, Wikipedia.
- Algoritmo de Metrópolis-Hastings, Wikipedia.
- Muestreo MCMC para dummies, 2015.
- ¿Cómo explicarías el método de Monte Carlo de cadena de Markov (MCMC) a un profano?
- El muestreo de Monte Carlo no es efectivo y puede ser intratable para modelos probabilísticos de alta dimensión.
- Markov Chain Monte Carlo proporciona un enfoque alternativo para el muestreo aleatorio de una distribución de probabilidad de alta dimensión donde la siguiente muestra depende de la muestra actual.
- El muestreo de Gibbs y el algoritmo más general de Metrópolis-Hastings son los dos enfoques más comunes para el muestreo de Monte Carlo de cadenas de Markov.
Artículos
Resumen
En este post, descubriste una suave introducción a Markov Chain Monte Carlo para el aprendizaje automático.
Específicamente, aprendiste:
¿Tienes alguna pregunta?
Haz tus preguntas en los comentarios de abajo y haré todo lo posible para responder.
¡Conoce la probabilidad para el aprendizaje automático!
Desarrolla tu comprensión de la probabilidad
…con sólo unas líneas de código python
Descubre cómo en mi nuevo Ebook:
Probabilidad para el Aprendizaje Automático
Proporciona tutoriales de autoaprendizaje y proyectos integrales sobre:
Teorema de Bayes, Optimización Bayesiana, Distribuciones, Máxima Verosimilitud, Entropía Cruzada, Calibración de Modelos
y mucho más…
Aproveche por fin la incertidumbre en sus proyectos
Olvídese de lo académico. Sólo resultados.Vea lo que hay dentro
0 comentarios