Métodos de aproximación de Monte Carlo ¿Cuál deberías elegir y cuándo?

Métodos de aproximación de Monte Carlo ¿Cuál y cuándo?

¿Es Transformación Inversa, Random Walk Metropolis-Hastings o Gibbs? Un análisis enfocado en los fundamentos matemáticos, implementación en Python desde cero y ventajas/desventajas de cada método

Foto de Joakim Honkasalo en Unsplash

Introducción al muestreo de aproximación

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.

— Reconocimiento de Patrones y Aprendizaje Automático¹

Dado que la inferencia determinística suele ser intratable en modelos probabilísticos como acabamos de ver, ahora recurrimos a métodos de aproximación basados en muestreo numérico, conocidos como técnicas de Monte Carlo. La pregunta clave que examinaremos con estos métodos es cómo calcular la esperanza de una función objetivo f(z) dado una distribución de probabilidad p(z). Recordemos que la definición simple de esperanza se da como una integral:

Fuente: PRML¹ Ec. 11.1

Como veremos, estas integrales son demasiado complejas computacionalmente, por lo que recurriremos a métodos de muestreo en este artículo.

En este artículo, examinaremos 3 métodos principales de muestreo: transformación inversa, Monte Carlo con cadena de Markov (MCMC) y Muestreo de Gibbs. Al comprender las propiedades estadísticas subyacentes y los requisitos computacionales de estos métodos, aprenderemos que:

  • La transformación inversa es la mejor opción para simular datos con alta precisión a partir de distribuciones conocidas y simples, especialmente en dimensiones bajas.
  • El algoritmo de Random Walk Metropolis-Hastings es la mejor opción para distribuciones complejas, multimodales o desconocidas, donde la exploración y/o convergencia global es una prioridad; específicamente, el algoritmo de Metropolis — una instancia específica de Metropolis-Hastings — se puede usar para distribuciones simétricas.
  • El Muestreo de Gibbs es la mejor opción para problemas de alta dimensionalidad donde las distribuciones condicionales son fáciles de muestrear y la eficiencia es una prioridad.

Tabla de contenidos

  1. Transformación inversa del muestreo• ¿Cómo funciona el algoritmo?• Implementación en Python• Prerrequisitos• Ventajas y desventajas
  2. Monte Carlo con cadena de Markov• Algoritmo Metropolis-Hastings• Instancia especial: Algoritmo Metropolis para distribuciones simétricas• Ventajas/Desventajas
  3. Gibbs• Algoritmo• Condiciones• Relación de Gibbs con Metropolis-Hastings
  4. Comparación: Ventajas/Desventajas de Transformación vs. Met-Hastings vs. Gibbs

1. Método de transformación: Función inversa de la CDF

El muestreo por Transformación Inversa, como su nombre sugiere, utiliza la función de distribución acumulativa inversa (CDF) de una distribución objetivo para generar números aleatorios que siguen una distribución deseada. La idea básica es:

  1. Generar un número aleatorio uniforme: Se extrae un número U de una distribución uniforme entre 0 y 1.
  2. Aplicar la función inversa de la CDF: Usando la inversa de la CDF de la distribución objetivo, se transforma U en una muestra que sigue la distribución objetivo.

Aquí hay una ilustración rápida de cómo se generan las muestras (azul) a partir de la distribución (roja):

La función inversa de la CDF es un método simple y generalizable para muestrear de distribuciones para las cuales conocemos la CDF, como la distribución normal, exponencial, gamma o beta.

PDF, CDF y CDF inversa

(De izquierda a derecha): PDF, CDF y CDF inversa de la distribución normal estándar

En términos intuitivos, la CDF es el valor acumulativo de la PDF, que es igual a la integral de la PDF; luego tomamos la inversa de la función CDF para obtener la CDF inversa final utilizada para este método.

Formalmente, si a es una variable aleatoria, entonces la CDF de a está dada por:

PRML, Eq. 11.5–11.6

Una CDF F tiene las siguientes propiedades clave:

  • F es continua
  • F es no decreciente
  • F tiene rango 0 ≤ cdf(a) ≤ 1 para todo a ∈ R

¿Cómo funciona el algoritmo de la CDF inversa?

El algoritmo consta de los siguientes elementos:

Entrada:

  • U: U es una variable aleatoria uniforme entre 0 y 1.
  • Esto sirve como la probabilidad de entrada para la CDF inversa y es lo que se transformará en una muestra de la distribución deseada.

Parámetro:

  • F: la CDF de la distribución objetivo.
  • Con F, simplemente podemos calcular su inversa, F^-1, y usarla para mapear un valor de entrada al dominio deseado

Salida:

  • x: una muestra aleatoria obtenida de la distribución objetivo.
  • Esto se genera aplicando la CDF inversa al número aleatorio de la distribución uniforme (entrada).

Implementación en Python

Ahora, implementemos este método desde cero. Utilizaremos la función exponencial ya que será fácil visualizar nuestras muestras generadas por la CDF inversa y compararlas con la distribución exacta:

PDF de la función exponencial (distribución objetivo)

Utilizando técnicas estándar de integración de cálculo, encontramos que la CDF objetivo F(x) es:

CDF de la función exponencial

La inversa de esta CDF es:

CDF inversa de la función exponencial

Generaremos 5000 muestras utilizando el método de la CDF inversa:

import numpy as npimport matplotlib.pyplot as plt# CDF inversa para la distribución exponencial con lambda = 1def inverse_cdf(p):    return -np.log(1 - p)# Generar 1000 valores de muestra utilizando CDF inversasamples_uniformes = np.random.uniform(0, 1, 1000)muestras_transformadas = inverse_cdf(samples_uniformes)# Generar valores de x y PDF verdaderopuntos_x = np.linspace(0, np.max(muestras_transformadas), 1000)valores_pdf = np.exp(-puntos_x)

Requisitos para que el algoritmo de la función de distribución acumulativa inversa funcione

El método de la función de distribución acumulativa inversa hace una suposición clave:

  • La función de distribución acumulativa (CDF) F es invertible: La CDF F debe ser invertible, lo que significa que cada entrada en F debe tener una salida única

Esta restricción descarta varias funciones. Por ejemplo, a continuación se muestran algunos tipos de funciones comunes pero no invertibles (y, por lo tanto, no funcionarían con la función de distribución acumulativa inversa):

  1. Funciones constantes: Cualquier función constante en la forma de f(x) = c, donde c es una constante, no es invertible, ya que cada entrada se asigna a la misma salida y, por lo tanto, la función no es biyectiva.
Los puntos rojos muestran dos de los muchos valores de x que se asignan al mismo valor de y en f(x) = 5, lo que lo hace no invertible

2. Ciertas funciones cuadráticas: Por ejemplo, f(x) = x^2 no es invertible ya que es una relación muchos-a-uno (considera f(x) = 1, x podría ser 1 o -1).

Los puntos rojos muestran una de las muchas parejas de valores de x que se asignan al mismo valor de y en f(x) = x²

3. Ciertas funciones trigonométricas: Por ejemplo, f(x) = sin(x) no es invertible en todo su dominio ya que es periódica, aunque con dominios restringidos se puede hacer invertible.

Los puntos rojos muestran uno de los muchos conjuntos de valores de x que se asignan al mismo valor de y en f(x) = sin(x) debido a su periodicidad sobre el dominio dado

¿Por qué funciona la función de distribución acumulativa inversa?

La idea clave es que una variable aleatoria uniformemente distribuida entre 0 y 1 puede transformarse en una variable aleatoria con una cierta distribución aplicando la inversa de la CDF de la distribución objetivo, que se asume conocida y manejable.

Ventajas

  1. Simplicidad algorítmica: es muy fácil de implementar con datos de menor dimensionalidad, por lo que tiene una amplia área de aplicación en diferentes campos y tareas.
  2. Precisión de la muestra: asumiendo que la CDF y su inversa representan exactamente la distribución objetivo, el método proporciona una precisión relativamente alta en comparación con otros métodos como el MCMC que veremos pronto.

Desventajas

  1. Complejidad computacional: Para algunas distribuciones, la función de distribución acumulativa inversa puede no tener una expresión en forma cerrada, lo que dificulta o encarece el cálculo.
  2. Dificultad con la alta dimensionalidad: Puede ser difícil de aplicar en espacios de alta dimensionalidad, especialmente con dependencias entre variables.
  3. Restricción de invertibilidad: Cada vez que una CDF no sea invertible, este método se vuelve inválido. Esto excluye varias funciones como vimos anteriormente.
  4. Limitado a distribuciones conocidas: La función de distribución acumulativa inversa requiere la forma exacta de la CDF, lo que limita su aplicación solo a distribuciones conocidas.

Teniendo en cuenta todas estas limitaciones, solo hay algunas categorías de distribuciones a las que podemos aplicar la función inversa de la función de distribución acumulativa (CDF). En realidad, con Big Data y distribuciones desconocidas, este método puede volverse rápidamente no disponible.

Con estas ventajas y desventajas en mente, ahora veamos otro marco de muestreo aleatorio que aborda estas limitaciones: Markov Chain Monte Carlo (MCMC).

2. Markov Chain Monte Carlo (MCMC)

Como vimos recién, el método de transformación de la función inversa de la CDF es altamente limitado, especialmente con espacios de muestra de alta dimensionalidad. Markov Chain Monte Carlo (MCMC), por otro lado, se escala bien con la dimensionalidad, lo que nos permite muestrear de una familia mucho más amplia de distribuciones.

Un ejemplo de Metropolis-Hastings explorando una distribución Gaussiana mixta (izquierda), generando muestras (derecha)

¿Cómo funciona el algoritmo Metropolis-Hastings?

En términos intuitivos, el algoritmo funciona en los siguientes pasos: Similar a la CDF inversa, tenemos una distribución objetivo de la cual estamos muestreando. Sin embargo, necesitamos un ingrediente adicional: el estado actual z*, y q(z|z*) depende de z*, creando una cadena de Markov con muestras z¹, z², z³,. Cada muestra es aceptada en la cadena solo si cumple con cierto criterio, que definiremos a continuación, ya que este criterio difiere en las variaciones del algoritmo.

Veámoslo de manera más algorítmica.

El algoritmo se ejecuta en ciclos, y cada ciclo sigue estos pasos:

  1. Generar una muestra z* de la distribución de propuesta.
  2. Aceptar la muestra con probabilidad Luego aceptaremos este valor con una probabilidad de aceptación, que en Metropolis-Hastings se define como:
PRML¹ Eq 11.44

donde

  • z* es el estado actual.
  • z^T es el nuevo estado propuesto.
  • p(z*) es la probabilidad del estado z* según la distribución deseada.
  • p(z^T) es la probabilidad del estado z^T según la distribución deseada.

La lógica detrás de este umbral de aceptación es que asegura que los estados más probables (según la distribución deseada) sean visitados con mayor frecuencia.

Ahora, esta es la versión más generalizada del algoritmo; si se sabe que la distribución de propuesta es simétrica, lo que significa que la probabilidad de proponer un movimiento del estado x al estado x′ es la misma que proponer un movimiento de x′ a x, es decir, q(x′|x) = q(x|x′), entonces podemos usar un caso especial de Metropolis-Hastings que requiere un umbral de aceptación más simple.

Algoritmo de Metropolis para Distribuciones Simétricas

Este es un algoritmo específico de MCMC que elegimos usar si la distribución de propuesta es simétrica, es decir, q(z⁰ | z¹) = q(z¹ | z⁰) para todos los valores de 1 y 0, interpretado como “la probabilidad de transición desde cualquier estado A al estado B es igual a la probabilidad de transición desde B a A”. Entonces, cada paso del algoritmo se vuelve:

  1. Generar una muestra z* de la distribución de propuesta.
  2. Aceptar la muestra con probabilidad:
Umbral de aceptación del algoritmo Metropolis. Fuente: PRML¹ Eq. 11.33

Algoritmos Metropolis-Hastings y Metropolis

Veamos los algoritmos lado a lado. Como vimos antes, la única diferencia es el umbral de aceptación; todos los demás pasos de los algoritmos se ejecutan de manera idéntica:

Algoritmo Metropolis vs Metropolis-Hastings

Ventajas

  1. Convergencia a la distribución de equilibrio: En ciertos casos, el paseo aleatorio puede converger a una distribución de equilibrio deseada, aunque probablemente lleve mucho tiempo en espacios de alta dimensión.
  2. Bajo costo computacional: El paseo aleatorio a menudo requiere menos recursos computacionales en comparación con otros métodos de muestreo complejos, lo que lo hace adecuado para problemas donde la eficiencia computacional es una prioridad.
  3. Versatilidad de aplicación: Debido a su alta similitud con patrones que ocurren naturalmente, el paseo aleatorio tiene aplicaciones en una amplia variedad de campos:• Física: Movimiento browniano de moléculas en líquidos y gases.• Análisis de redes• Mercados financieros: para modelar movimientos de precios de acciones.• Genética de poblaciones

Desventajas:

  1. Sensibilidad a la inicialización: El rendimiento del algoritmo puede ser sensible a la elección de los valores iniciales, especialmente si los valores inicializados están lejos de las áreas de alta densidad.
  2. Trampas de localidad: Dependiendo de la complejidad de la distribución propuesta, el algoritmo podría quedar atrapado en óptimos locales y tener dificultades para recorrer otras áreas a lo largo de la distribución.

Ahora, teniendo en cuenta el algoritmo Metropolis-Hastings, veamos otra instancia especial de él: el Muestreo de Gibbs.

3. Muestreo de Gibbs

El Muestreo de Gibbs es una instancia especial de Metropolis-Hastings donde cada paso siempre es aceptado. Primero veamos el algoritmo de muestreo de Gibbs en sí mismo.

¿Cómo funciona el algoritmo de Gibbs?

La idea es relativamente simple y se ilustra mejor mediante un ejemplo micro en el que se realiza un muestreo de una distribución p(z1, z2, z3) sobre 3 variables. El algoritmo se ejecutaría en los siguientes pasos:

  1. En el paso de tiempo T, inicializar los valores iniciales a:
PRML¹

2. Obtener el nuevo valor para z1:

PRML¹ Eq 11.46

3. Obtener un nuevo valor para la segunda posición, z2, a partir de la condicional:

PRML¹ Eq 11.47

4. Finalmente, obtener un nuevo valor para la última posición, z3:

PRML¹ Eq 11.48

5. Repetir este proceso, recorriendo las tres variables z1…z3 hasta alcanzar un umbral satisfactorio determinado.

Algoritmo generalizado

Formalmente, el algoritmo se representa mediante la inicialización de las posiciones iniciales y luego tomando T pasos consecutivos.

Fuente de imagen: PRML¹ Ch11.3 Muestreo de Gibbs

Condiciones para que el muestreo de Gibbs muestre correctamente una distribución objetivo

  1. Invariante. La distribución objetivo p(z) es invariante en cada paso de Gibbs, por lo tanto p(z) es invariante en toda la cadena de Markov.
  2. Ergodicidad. Si las distribuciones condicionales son todas diferentes de cero, entonces la ergodicidad está implícita, ya que cualquier punto en el espacio z es alcanzable en un número finito de pasos.
  3. Quemado suficiente. Como vimos con cualquier método que requiere una inicialización aleatoria, las primeras muestras dependen de la inicialización, y esta dependencia se debilita después de muchas iteraciones.

¿Cómo se relaciona esto con Metropolis-Hastings?

En Metropolis-Hastings, definimos el umbral de aceptación de la siguiente manera:

Así, los pasos de propuesta de Metropolis-Hastings siempre son aceptados, como vimos en el algoritmo de Gibbs.

Variaciones

Dado que el método de Gibbs actualiza una variable a la vez, existen fuertes dependencias entre muestras consecutivas. Para superar esto, podríamos utilizar una estrategia intermedia para muestrear de grupos de variables en lugar de variables individuales, conocida como Gibbs bloqueante.

De manera similar, debido a la naturaleza de las cadenas de Markov, los ejemplos dibujados sucesivamente estarán correlacionados. Para generar muestras independientes, podríamos utilizar el submuestreo dentro de la secuencia.

4. Pros/Contras: Inversa de CDF vs Metropolis-Hastings vs Gibbs

Ahora que hemos recorrido cómo funciona cada algoritmo y sus áreas de aplicación, resumamos las características definitorias de cada método.

1. Muestreo de Transformación Inversa

  • Tamaño de datos: Mejor para conjuntos de datos de tamaño moderado.
  • Tiempo: Generalmente eficiente para distribuciones univariadas.
  • Complejidad de datos: Útil para distribuciones simples donde la función de distribución acumulativa (CDF) y su inversa son conocidas y fáciles de calcular.
  • Considerar evitar si: Se están muestreando variables/distribuciones de alta dimensionalidad.
  • Mayor ventaja: Alta precisión si la CDF refleja con precisión la distribución objetivo.
  • Requisito: Se debe conocer e invertir la CDF.

2. Metropolis-Hastings (MCMC)

  • Tamaño de datos: Escalable y adecuado para conjuntos de datos grandes.
  • Tiempo: Puede ser intensivo en cómputo, dependiendo de la complejidad de la distribución objetivo.
  • Complejidad de datos: Ideal para distribuciones complejas o multimodales.
  • Mayores ventajas: – Puede muestrear de una distribución sin conocer su constante de normalización (la forma completa)- Excelente para explorar la estructura global de una distribución y garantizar la convergencia
  • Desventaja: Puede sufrir de una convergencia muy lenta con – distribuciones objetivo complejas o multimodales, ya que el algoritmo puede quedar atrapado en modos locales y tener dificultad para hacer transiciones entre ellos;- las variables están altamente correlacionadas;- espacios de alta dimensionalidad; – valores iniciales o elecciones de tamaño de paso pobres

3. Muestreo de Gibbs

  • Tamaño de datos: Adecuado para conjuntos de datos pequeños y grandes.
  • Tiempo: A menudo más eficiente que el Muestreo de Caminata Aleatoria Metropolis-Hastings ya que no requiere pasos de aceptación/rechazo.
  • Complejidad de datos: Mejor utilizado cuando se trata de distribuciones de alta dimensionalidad donde se puede muestrear de la distribución condicional de cada variable.
  • Mayores ventajas: – Puede calcular fácilmente las distribuciones condicionales;- Menos propenso a caer en mínimos locales en comparación con el Muestreo Aleatorio.
  • Requisitos: – Ergodicidad de la cadena de Markov – Se deben conocer y ser tratables las distribuciones condicionales completas

En resumen:

Tabla resumen de ventajas y desventajas de la función de distribución acumulativa inversa, Metropolis-Hastings y Gibbs

Conclusión

¡Gracias por acompañarme hasta aquí! En este artículo, analizamos 3 métodos clave de muestreo por aproximación: la función de distribución acumulativa inversa, Metropolis Hastings MCMC y Gibbs Sampling MCMC. Exploramos cómo funciona cada algoritmo, sus respectivas ventajas y desventajas, y los casos de uso típicos.

La función de distribución acumulativa inversa proporciona un método sencillo para muestrear de una distribución conocida cuando su función de distribución acumulativa es invertible. Es computacionalmente eficiente, pero menos adecuado para distribuciones de alta dimensión o complejas. Metropolis Hastings MCMC ofrece un enfoque más general que permite muestrear de distribuciones que de otra manera serían difíciles de abordar. Sin embargo, requiere más recursos computacionales y puede ser sensible a parámetros de ajuste como la distribución de propuesta. Gibbs Sampling MCMC es especialmente eficiente cuando la distribución conjunta es compleja pero se puede descomponer en distribuciones condicionales más simples. Se utiliza ampliamente en aprendizaje automático, aunque puede ser lento en converger y requerir mucha memoria para problemas de alta dimensión.

[1] Bishop, C. M. (2016). Pattern Recognition and Machine Learning (Reimpresión en rústica de la edición original de 2006 (corregida en la octava impresión de 2009)). Springer Nueva York.

*Salvo que se indique lo contrario, todas las imágenes son creadas por el autor.

We will continue to update Zepes; if you have any questions or suggestions, please contact us!

Share:

Was this article helpful?

93 out of 132 found this helpful

Discover more

Inteligencia Artificial

Conoce a Watsonx Code Assistant de IBM Revolucionando la codificación empresarial con asistencia impulsada por IA

En el mundo actual de desarrollo de software, uno de los desafíos clave que enfrentan las empresas es la necesidad de...

Inteligencia Artificial

La cirugía cerebral impulsada por IA se convierte en una realidad en Hong Kong

El Centro de Inteligencia Artificial y Robótica, bajo la Academia China de Ciencias, completó pruebas exitosas de un ...

Noticias de Inteligencia Artificial

AI Ahora en el Aire Conoce a Ashley, el Primer Bot de DJ del Mundo.

Live 95.5, una popular estación de radio con sede en Portland, Oregón, ha dado un paso audaz hacia el futuro al prese...

Inteligencia Artificial

4 gigantes tecnológicos - OpenAI, Google, Microsoft y Anthropic se unen para la IA segura

En un movimiento histórico, cuatro de los nombres más importantes en el mundo de la inteligencia artificial se unen p...