En análisis numérico y estadística computacional , el muestreo por rechazo es una técnica básica que se utiliza para generar observaciones a partir de una distribución . También se denomina comúnmente método de aceptación-rechazo o "algoritmo de aceptación-rechazo " y es un tipo de método de simulación exacta. El método funciona para cualquier distribución encon una densidad .
El muestreo de rechazo se basa en la observación de que para muestrear una variable aleatoria en una dimensión, se puede realizar un muestreo aleatorio uniforme del gráfico cartesiano bidimensional y mantener las muestras en la región debajo del gráfico de su función de densidad. [1] [2] [3] Tenga en cuenta que esta propiedad se puede ampliar a funciones de dimensión N.
Descripción
Para visualizar la motivación detrás del muestreo de rechazo, imagine graficar la función de densidad de una variable aleatoria en un tablero rectangular grande y lanzarle dardos. Suponga que los dardos están distribuidos uniformemente alrededor del tablero. Ahora quite todos los dardos que están fuera del área debajo de la curva. Los dardos restantes se distribuirán uniformemente dentro del área bajo la curva, y las posiciones x de estos dardos se distribuirán de acuerdo con la densidad de la variable aleatoria. Esto se debe a que hay más espacio para que los dardos caigan donde la curva es más alta y, por lo tanto, la densidad de probabilidad es mayor.
La visualización como se acaba de describir es equivalente a una forma particular de muestreo de rechazo donde la "distribución de la propuesta" es uniforme (por lo tanto, su gráfico es un rectángulo). La forma general de muestreo de rechazo asume que el tablero no es necesariamente rectangular, sino que tiene la forma de la densidad de alguna distribución de propuesta de la que sabemos cómo muestrear (por ejemplo, usando muestreo de inversión ), y que es al menos igual de alta en cada caso. punto como la distribución de la que queremos muestrear, de modo que el primero encierre completamente al segundo. (De lo contrario, habría partes del área curva de la que queremos tomar muestras que nunca podrían alcanzarse).
El muestreo de rechazo funciona de la siguiente manera:
- Muestra un punto en el eje x de la distribución de la propuesta.
- Dibuje una línea vertical en esta posición x, hasta el valor y máximo de la función de densidad de probabilidad de la distribución propuesta.
- Muestre uniformemente a lo largo de esta línea desde 0 hasta el máximo de la función de densidad de probabilidad. Si el valor muestreado es mayor que el valor de la distribución deseada en esta línea vertical, rechace el valor x y vuelva al paso 1; de lo contrario, el valor x es una muestra de la distribución deseada.
Este algoritmo se puede utilizar para muestrear el área bajo cualquier curva, independientemente de si la función se integra a 1. De hecho, escalar una función por una constante no tiene ningún efecto sobre las posiciones x muestreadas. Por lo tanto, el algoritmo se puede utilizar para muestrear una distribución cuya constante de normalización se desconoce, lo que es común en la estadística computacional .
Teoría
El método de muestreo por rechazo genera valores de muestreo a partir de una distribución objetivo. con función de densidad de probabilidad arbitraria mediante el uso de una distribución de propuesta con densidad de probabilidad . La idea es que se pueda generar un valor de muestra a partir de en lugar de tomar muestras de y aceptando la muestra de con probabilidad , repitiendo los sorteos de hasta que se acepte un valor. aquí hay un límite finito constante en la razón de verosimilitud , satisfactorio sobre el apoyo de; en otras palabras, M debe satisfacer para todos los valores de . Tenga en cuenta que esto requiere que el apoyo de debe incluir el apoyo de -en otras palabras, cuando sea .
La validación de este método es el principio de la envolvente: al simular el par , se produce una simulación uniforme sobre el subgrafo de . Aceptando solo pares tales que luego produce pares distribuido uniformemente sobre el subgrafo de y así, marginalmente, una simulación de
Esto significa que, con suficientes réplicas, el algoritmo genera una muestra a partir de la distribución deseada. . Hay una serie de extensiones de este algoritmo, como el algoritmo Metropolis .
Este método se relaciona con el campo general de las técnicas de Monte Carlo , incluidos los algoritmos de Monte Carlo de cadena de Markov que también utilizan una distribución proxy para lograr la simulación a partir de la distribución de destino.. Constituye la base de algoritmos como el de Metropolis .
La probabilidad de aceptación incondicional es la proporción de muestras propuestas que se aceptan, que es
El número de muestras requeridas de para obtener un valor aceptado sigue una distribución geométrica con probabilidad, que tiene media . Intuitivamente, es el número esperado de iteraciones que se necesitan, como medida de la complejidad computacional del algoritmo.
Reescribe la ecuación anterior,
El muestreo de rechazo se utiliza con mayor frecuencia en los casos en que la forma de dificulta el muestreo. Una sola iteración del algoritmo de rechazo requiere un muestreo de la distribución de la propuesta, el dibujo de una distribución uniforme y la evaluación de laexpresión. Por tanto, el muestreo de rechazo es más eficiente que algún otro método siempre que M veces el costo de estas operaciones, que es el costo esperado de obtener una muestra con muestreo de rechazo, es menor que el costo de obtener una muestra utilizando el otro método.
Algoritmo
El algoritmo (utilizado por John von Neumann [ cita requerida ] y que se remonta a Buffon y su aguja [ cita requerida ] ) para obtener una muestra de la distribución con densidad usando muestras de distribución con densidad es como sigue:
- Obtener una muestra de la distribución y una muestra de (la distribución uniforme sobre el intervalo unitario).
- Compruebe si o no .
- Si esto se mantiene, acepta como muestra extraída de ;
- si no, rechace el valor de y vuelva al paso de muestreo.
El algoritmo tomará un promedio de iteraciones para obtener una muestra.
Ventajas sobre el muestreo con métodos ingenuos
El muestreo de rechazo puede ser mucho más eficiente en comparación con los métodos Naive en algunas situaciones. Por ejemplo, dado un problema como muestreo condicionalmente en dado el conjunto , es decir, , algunas veces se puede simular fácilmente, utilizando los métodos Naive (por ejemplo, mediante muestreo de transformación inversa ):
- Muestra de forma independiente, y dejar a los
- Producción:
El problema es que este muestreo puede ser difícil e ineficaz, si . El número esperado de iteraciones sería, que podría estar cerca del infinito. Además, incluso cuando aplica el método de muestreo de rechazo, siempre es difícil optimizar el límitepara la razón de verosimilitud. Más a menudo que no,es grande y la tasa de rechazo es alta, el algoritmo puede ser muy ineficaz. La familia exponencial natural (si existe), también conocida como inclinación exponencial, proporciona una clase de distribuciones propuestas que pueden reducir la complejidad del cálculo, el valor de y acelerar los cálculos (ver ejemplos: trabajar con familias exponenciales naturales).
Ejemplos: trabajar con familias exponenciales naturales
Dada una variable aleatoria , es la distribución de destino. Suponga, por simplicidad, que la función de densidad se puede escribir explícitamente como. Elija la propuesta como
- Elija la forma de distribución de la propuesta , con función de generación de momento de registro como , lo que implica además que es una distribución normal .
- Decide el bien elegido para la distribución de la propuesta. En esta configuración, la forma intuitiva de elegir es establecer , es decir
- Escriba explícitamente el objetivo, la propuesta y el índice de probabilidad.
- Derivar el límite para la razón de verosimilitud , que es una función decreciente para , por lo tanto
- Criterio de muestreo de rechazo: para , Si sostiene, acepta el valor de ; si no, continúe probando nuevos y nuevo hasta la aceptación.
Para el ejemplo anterior, como medida de la eficiencia, el número esperado de iteraciones del método de muestreo de rechazo basado en NEF es de orden b, es decir , mientras que bajo el método Naive, el número esperado de iteraciones es , que es mucho más ineficiente.
En general, la inclinación exponencial, una clase paramétrica de distribución de propuesta, resuelve convenientemente los problemas de optimización, con sus propiedades útiles que caracterizan directamente la distribución de la propuesta. Para este tipo de problema, para simular condicionalmente en , entre la clase de distribuciones simples, el truco consiste en utilizar NEF, lo que ayuda a obtener cierto control sobre la complejidad y acelera considerablemente el cálculo. De hecho, existen profundas razones matemáticas para usar NEF.
Inconvenientes
El muestreo de rechazo puede llevar a que se tomen muchas muestras no deseadas si la función que se muestrea está muy concentrada en una determinada región, por ejemplo, una función que tiene un pico en algún lugar. Para muchas distribuciones, este problema se puede resolver utilizando una extensión adaptativa (ver muestreo de rechazo adaptativo ). Además, a medida que aumentan las dimensiones del problema, la relación entre el volumen incrustado y las "esquinas" del volumen incrustado tiende a cero, por lo que pueden producirse muchos rechazos antes de que se genere una muestra útil, lo que hace que el algoritmo ineficaz y poco práctico. Vea la maldición de la dimensionalidad . En dimensiones elevadas, es necesario utilizar un enfoque diferente, típicamente un método Monte Carlo de cadena de Markov, como el muestreo de Metropolis o el muestreo de Gibbs . (Sin embargo, el muestreo de Gibbs, que descompone un problema de muestreo multidimensional en una serie de muestras de baja dimensión, puede utilizar el muestreo de rechazo como uno de sus pasos).
Muestreo de rechazo adaptativo
Para muchas distribuciones, es difícil encontrar una distribución de propuesta que incluya la distribución dada sin mucho espacio desperdiciado. Una extensión del muestreo de rechazo que se puede utilizar para superar esta dificultad y muestrear eficientemente de una amplia variedad de distribuciones (siempre que tengan funciones de densidad log-cóncavas , que es de hecho el caso para la mayoría de las distribuciones comunes, incluso aquellas cuya densidad ¡las funciones no son cóncavas en sí mismas!) se conoce como muestreo de rechazo adaptativo (ARS) .
Hay tres ideas básicas para esta técnica tal como la introdujo Gilks en 1992: [4]
- Si ayuda, defina la distribución de su envolvente en el espacio de registro (por ejemplo, probabilidad de registro o densidad de registro) en su lugar. Es decir, trabajar con en vez de directamente.
- A menudo, las distribuciones que tienen funciones de densidad algebraicamente desordenadas tienen funciones de densidad logarítmica razonablemente más simples (es decir, cuando es desordenado, puede ser más fácil trabajar con o, al menos, más cercano a lineal por partes).
- En lugar de una única función de densidad de envolvente uniforme, utilice una función de densidad lineal por partes como su envolvente.
- Cada vez que tenga que rechazar una muestra, puede utilizar el valor de que evaluó, para mejorar la aproximación por partes . Por lo tanto, esto reduce la posibilidad de que su próximo intento sea rechazado. Asintóticamente, la probabilidad de tener que rechazar su muestra debería converger a cero y, en la práctica, a menudo muy rápidamente.
- Como se propone, cada vez que elegimos un punto que se rechaza, ajustamos la envolvente con otro segmento de línea que sea tangente a la curva en el punto con la misma coordenada x que el punto elegido.
- Un modelo lineal por partes de la distribución logarítmica de la propuesta da como resultado un conjunto de distribuciones exponenciales por partes (es decir, segmentos de una o más distribuciones exponenciales, unidos de un extremo a otro). Las distribuciones exponenciales se comportan bien y se comprenden bien. El logaritmo de una distribución exponencial es una línea recta y, por lo tanto, este método implica esencialmente encerrar el logaritmo de la densidad en una serie de segmentos de línea. Esta es la fuente de la restricción logarítmica-cóncava: si una distribución es logarítmica-cóncava, entonces su logaritmo es cóncavo (con forma de U invertida), lo que significa que un segmento de línea tangente a la curva siempre pasará por encima de la curva.
- Si no se trabaja en el espacio logarítmico, también se puede muestrear una función de densidad lineal por partes mediante distribuciones triangulares [5]
- Podemos aprovechar aún más el requisito de concavidad (logarítmica), para evitar potencialmente el costo de evaluar cuando se acepta su muestra .
- Al igual que podemos construir un límite superior lineal por partes (la función "envolvente") utilizando los valores de que tuvimos que evaluar en la actual cadena de rechazos, también podemos construir un límite inferior lineal por partes (la función de "compresión") usando estos valores también.
- Antes de evaluar (lo potencialmente caro) para ver si su muestra será aceptada, es posible que ya sepamos si será aceptada comparándola con la (idealmente más barata) (o en este caso) exprimiendo la función que tenga disponible.
- Este paso de compresión es opcional, incluso cuando lo sugiere Gilks. En el mejor de los casos, le ahorra una sola evaluación adicional de su densidad objetivo (desordenada y / o costosa). Sin embargo, presumiblemente para funciones de densidad particularmente caras (y asumiendo la rápida convergencia de la tasa de rechazo hacia cero), esto puede marcar una diferencia considerable en el tiempo de ejecución final.
El método consiste esencialmente en determinar sucesivamente una envolvente de segmentos de línea recta que se aproxima cada vez mejor al logaritmo sin dejar de estar por encima de la curva, comenzando con un número fijo de segmentos (posiblemente una sola línea tangente). El muestreo de una variable aleatoria exponencial truncada es sencillo. Simplemente tome el logaritmo de una variable aleatoria uniforme (con el intervalo apropiado y el truncamiento correspondiente).
Desafortunadamente, ARS solo se puede aplicar a partir de un muestreo de densidades objetivo log-cóncavas. Por esta razón, se han propuesto varias extensiones de ARS en la literatura para abordar distribuciones objetivo no log-cóncavas. [6] [7] [8] Además, se han diseñado diferentes combinaciones de ARS y el método Metropolis-Hastings con el fin de obtener un sampler universal que construya una propuesta de autoajuste de densidades (es decir, una propuesta construida y adaptada automáticamente a la objetivo). Esta clase de métodos a menudo se denominan algoritmos de muestreo de metrópolis de rechazo adaptativo (ARMS) . [9] [10] Las técnicas adaptativas resultantes se pueden aplicar siempre, pero las muestras generadas están correlacionadas en este caso (aunque la correlación desaparece rápidamente a cero a medida que aumenta el número de iteraciones).
Ver también
Referencias
- ^ Casella, George; Robert, Christian P .; Wells, Martin T. (2004). Esquemas de muestreo generalizados de aceptación-rechazo . Instituto de Estadística Matemática. págs. 342–347. doi : 10.1214 / lnms / 1196285403 . ISBN 9780940600614.
- ^ Neal, Radford M. (2003). "Slice Sampling" . Annals of Statistics . 31 (3): 705–767. doi : 10.1214 / aos / 1056562461 . Señor 1994729 . Zbl 1051.65007 .
- ^ Obispo, Christopher (2006). "11.4: Muestreo de cortes". Reconocimiento de patrones y aprendizaje automático . Springer . ISBN 978-0-387-31073-2.
- ^ Muestreo de rechazo adaptativo para muestreo de Gibbs. https://stat.duke.edu/~cnk/Links/tangent.method.pdf
- ^ DB Thomas y W. Luk, Generación de números aleatorios no uniformes mediante aproximaciones lineales por partes, 2006. http://www.doc.ic.ac.uk/~wl/papers/iee07dt.pdf
- ^ Hörmann, Wolfgang (1 de junio de 1995). "Una técnica de rechazo para el muestreo de distribuciones cóncavas en T". ACM Trans. Matemáticas. Softw . 21 (2): 182-193. CiteSeerX 10.1.1.56.6055 . doi : 10.1145 / 203082.203089 . ISSN 0098-3500 .
- ^ Evans, M .; Swartz, T. (1 de diciembre de 1998). "Generación de variables aleatorias usando propiedades de concavidad de densidades transformadas". Revista de Estadística Computacional y Gráfica . 7 (4): 514-528. CiteSeerX 10.1.1.53.9001 . doi : 10.2307 / 1390680 . JSTOR 1390680 .
- ^ Görür, Dilan; Teh, Yee Whye (1 de enero de 2011). "Muestreo de rechazo adaptativo cóncavo-convexo". Revista de Estadística Computacional y Gráfica . 20 (3): 670–691. doi : 10.1198 / jcgs.2011.09058 . ISSN 1061-8600 .
- ^ Gilks, WR; Mejor, NG ; Tan, KKC (1 de enero de 1995). "Muestreo de metrópolis de rechazo adaptativo dentro del muestreo de Gibbs". Revista de la Royal Statistical Society. Serie C (Estadística aplicada) . 44 (4): 455–472. doi : 10.2307 / 2986138 . JSTOR 2986138 .
- ^ Meyer, Renate; Cai, Bo; Perron, François (15 de marzo de 2008). "Muestreo de Metrópolis de rechazo adaptativo mediante polinomios de interpolación de Lagrange de grado 2". Estadística computacional y análisis de datos . 52 (7): 3408–3423. doi : 10.1016 / j.csda.2008.01.005 .
- Robert, CP y Casella, G. "Monte Carlo Statistical Methods" (segunda edición). Nueva York: Springer-Verlag, 2004.
- J. von Neumann, "Varias técnicas utilizadas en relación con dígitos aleatorios. Métodos de Monte Carlo", Nat. Bureau Standards, 12 (1951), págs. 36–38.