Muestreo por Rechazo

El muestreo por rechazo extrae muestras exactas de una densidad objetivo proponiendo a partir de una distribución envolvente más sencilla y aceptando cada propuesta con una probabilidad proporcional a la relación entre el objetivo y la envolvente, descartando el resto.

Definition

El muestreo por rechazo es una técnica de Monte Carlo que genera un candidato a partir de una densidad propuesta que domina el objetivo hasta una constante, luego acepta el candidato con una probabilidad igual a la relación de la densidad objetivo a la densidad acotada, produciendo valores aceptados distribuidos exactamente como el objetivo.

Scope

Este tema cubre el algoritmo básico de aceptación-rechazo y su corrección, el papel de la envolvente y la constante de acotación en la determinación de la eficiencia, la técnica de compresión (squeeze technique) para evitar evaluaciones costosas de la densidad, y construcciones adaptativas como el muestreo por rechazo adaptativo para densidades log-cóncavas. Se conecta con los pasos de aceptación dentro de los métodos de cadena de Markov.

Core questions

• ¿Por qué los candidatos aceptados se distribuyen exactamente de acuerdo con la densidad objetivo?
• ¿Cómo controla la constante de acotación el número esperado de propuestas por extracción aceptada?
• ¿Cómo reducen las funciones de compresión (squeeze functions) el número de evaluaciones costosas de la densidad?
• ¿Cómo se puede construir y refinar la envolvente automáticamente para densidades log-cóncavas?

Key concepts

• Distribución envolvente
• Constante de acotación
• Probabilidad de aceptación
• Función de compresión (Squeeze function)
• Log-concavidad

Key theories

Principio de aceptación-rechazo

Si una densidad propuesta multiplicada por una constante domina el objetivo en todas partes, aceptar propuestas con una probabilidad igual a la relación objetivo-sobre-límite produce muestras objetivo exactas; la probabilidad de aceptación es igual al recíproco de la constante de acotación.

Muestreo por rechazo adaptativo

Para densidades log-cóncavas, una envolvente exponencial a trozos construida a partir de tangentes y cuerdas puede refinarse en cada punto rechazado, llevando la tasa de aceptación hacia uno sin requerir la constante de normalización.

Clinical relevance

El muestreo por rechazo genera variates a partir de densidades conocidas solo hasta una constante, lo que surge constantemente en la computación bayesiana; el muestreo por rechazo adaptativo, en particular, proporciona las extracciones condicionales completas dentro de muchos muestreadores de Gibbs, lo que lo convierte en un componente fundamental de la simulación posterior práctica.

History

Von Neumann describió la idea de aceptación-rechazo en los primeros días de la computación de Monte Carlo; trabajos posteriores generalizaron las envolventes, añadieron pasos de compresión (squeeze steps) para la eficiencia y desarrollaron esquemas adaptativos que ajustan automáticamente la envolvente para objetivos log-cóncavos utilizados en el muestreo bayesiano.

Key figures

• John von Neumann
• Luc Devroye
• Walter Gilks
• Christian P. Robert

Seminal works

• devroye1986
• gilks1992

Frequently asked questions

¿Qué hace que el muestreo por rechazo sea eficiente o ineficiente?

La eficiencia se rige por la forma en que la envolvente escalada se ajusta al objetivo. Una envolvente holgada significa una constante de acotación grande y muchas propuestas rechazadas; en altas dimensiones, la tasa de aceptación puede volverse imprácticamente pequeña.

¿Por qué es útil el muestreo por rechazo cuando la constante de normalización es desconocida?

El método solo necesita la densidad objetivo hasta una constante multiplicativa, porque esa constante se absorbe en la constante de acotación. Por eso se combina naturalmente con las posteriores bayesianas, que suelen conocerse solo hasta su normalizador.