Muestreo de rebanadas

Algoritmo

El muestreo por cortes es un tipo de algoritmo de Monte Carlo de cadena de Markov para el muestreo de números pseudoaleatorios , es decir, para extraer muestras aleatorias de una distribución estadística. El método se basa en la observación de que para muestrear una variable aleatoria se puede muestrear uniformemente de la región bajo el gráfico de su función de densidad. ^{[1] [2] [3]}

Motivación

Supongamos que se desea muestrear una variable aleatoria X con distribución f ( x ). Supongamos que la siguiente es la gráfica de f ( x ). La altura de f ( x ) corresponde a la probabilidad en ese punto.

Si se muestrea uniformemente X , cada valor tendría la misma probabilidad de ser muestreado y la distribución tendría la forma f ( x ) = y para algún valor y en lugar de alguna función no uniforme f ( x ). En lugar de la línea negra original, la nueva distribución se parecería más a la línea azul.

Para muestrear X de una manera que mantenga la distribución f ( x ), se debe utilizar alguna técnica de muestreo que tenga en cuenta las distintas probabilidades para cada rango de f ( x ).

Método

El muestreo por cortes, en su forma más simple, toma muestras uniformemente desde debajo de la curva f ( x ) sin necesidad de rechazar ningún punto, de la siguiente manera:

1. Elija un valor inicial x ₀ para el cual f ( x ₀ ) > 0.
2. Muestrear un valor y uniformemente entre 0 y f ( x ₀ ).
3. Dibuje una línea horizontal a través de la curva en esta posición y .
4. Muestrear un punto ( x , y ) de los segmentos de línea dentro de la curva.
5. Repita desde el paso 2 utilizando el nuevo valor x .

La motivación aquí es que una forma de muestrear un punto de manera uniforme dentro de una curva arbitraria es primero dibujar cortes horizontales delgados de altura uniforme a lo largo de toda la curva. Luego, podemos muestrear un punto dentro de la curva seleccionando aleatoriamente un corte que caiga en la curva o debajo de ella en la posición x de la iteración anterior, y luego eligiendo aleatoriamente una posición x en algún lugar a lo largo del corte. Al usar la posición x de la iteración anterior del algoritmo, a largo plazo seleccionamos cortes con probabilidades proporcionales a las longitudes de sus segmentos dentro de la curva. La parte más difícil de este algoritmo es encontrar los límites del corte horizontal, lo que implica invertir la función que describe la distribución de la que se está muestreando. Esto es especialmente problemático para distribuciones multimodales, donde el corte puede constar de múltiples partes discontinuas. A menudo es posible usar una forma de muestreo de rechazo para superar esto, donde muestreamos de un corte más grande que se sabe que incluye el corte deseado en cuestión, y luego descartamos los puntos fuera del corte deseado. Este algoritmo se puede utilizar para tomar muestras del á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 efecto sobre las posiciones x muestreadas. Esto significa que el algoritmo se puede utilizar para tomar muestras de una distribución cuya función de densidad de probabilidad solo se conoce hasta una constante (es decir, cuya constante de normalización es desconocida), lo que es común en las estadísticas computacionales .

Implementación

El muestreo por rebanadas recibe su nombre del primer paso: definir una rebanada mediante el muestreo de una variable auxiliar . Esta variable se muestrea de , donde es la función de densidad de probabilidad (PDF) de X o es al menos proporcional a su PDF. Esto define una rebanada de X donde . En otras palabras, ahora estamos viendo una región de X donde la densidad de probabilidad es al menos . Luego, el siguiente valor de X se muestrea uniformemente de esta rebanada. Se muestrea un nuevo valor de , luego X , y así sucesivamente. Esto se puede visualizar como un muestreo alternativo de la posición y y luego de la posición x de los puntos bajo PDF, por lo tanto, las X son de la distribución deseada. Los valores no tienen consecuencias o interpretaciones particulares más allá de su utilidad para el procedimiento. ${\displaystyle Y}$ ${\displaystyle [0,f(x)]}$ ${\displaystyle f(x)}$ ${\displaystyle f(x)\geq Y}$ ${\displaystyle Y}$ ${\displaystyle Y}$ ${\displaystyle Y}$

Si tanto la PDF como su inversa están disponibles, y la distribución es unimodal, entonces encontrar la porción y tomar muestras de ella es simple. Si no, se puede utilizar un procedimiento de selección por pasos para encontrar una región cuyos puntos finales queden fuera de la porción. Luego, se puede extraer una muestra de la porción utilizando el muestreo de rechazo . Radford M. Neal describe en detalle varios procedimientos para esto . ^[2]

Tenga en cuenta que, a diferencia de muchos métodos disponibles para generar números aleatorios a partir de distribuciones no uniformes, las variables aleatorias generadas directamente por este enfoque exhibirán dependencia estadística serial. Esto se debe a que para extraer la siguiente muestra, definimos la porción en función del valor de f ( x ) para la muestra actual.

En comparación con otros métodos

El muestreo por cortes es un método de cadena de Markov y, como tal, cumple la misma función que el muestreo de Gibbs y Metropolis. A diferencia de Metropolis, no es necesario ajustar manualmente la función candidata ni la desviación estándar candidata.

Recuerde que Metropolis es sensible al tamaño del paso. Si el tamaño del paso es demasiado pequeño, el recorrido aleatorio provoca una decorrelación lenta. Si el tamaño del paso es demasiado grande, hay una gran ineficiencia debido a una alta tasa de rechazo.

A diferencia de Metropolis, el muestreo por cortes ajusta automáticamente el tamaño del paso para que coincida con la forma local de la función de densidad. Se podría decir que la implementación es más sencilla y eficiente que el muestreo de Gibbs o las actualizaciones simples de Metropolis.

Tenga en cuenta que, a diferencia de muchos métodos disponibles para generar números aleatorios a partir de distribuciones no uniformes, las variables aleatorias generadas directamente por este enfoque exhibirán dependencia estadística serial. En otras palabras, no todos los puntos tienen la misma probabilidad independiente de selección. Esto se debe a que para extraer la siguiente muestra, definimos la porción en función del valor de f(x) para la muestra actual. Sin embargo, las muestras generadas son markovianas y, por lo tanto, se espera que converjan a la distribución correcta en el largo plazo.

El muestreo por sectores requiere que la distribución que se va a muestrear sea evaluable. Una forma de flexibilizar este requisito es sustituir una distribución evaluable que sea proporcional a la distribución no evaluable real.

Caso univariado

Para una muestra dada x, se elige un valor para y entre [0, f ( x )], que define una "porción" de la distribución (mostrada por la línea horizontal continua). En este caso, hay dos porciones separadas por un área fuera del rango de la distribución.

Para muestrear una variable aleatoria X con densidad f ( x ) introducimos una variable auxiliar Y e iteramos de la siguiente manera:

• Dada una muestra x, elegimos y de manera uniforme y aleatoria del intervalo [0, f ( x )];
• dado y elegimos x uniformemente al azar del conjunto . ${\displaystyle f^{-1}[y,+\infty )}$
• La muestra de x se obtiene ignorando los valores de y .

Nuestra variable auxiliar Y representa una "porción" horizontal de la distribución. El resto de cada iteración se dedica a tomar una muestra de un valor x de la porción que sea representativa de la densidad de la región considerada.

En la práctica, el muestreo de una porción horizontal de una distribución multimodal es difícil. Existe una tensión entre obtener una región de muestreo grande y, por lo tanto, hacer posibles grandes movimientos en el espacio de distribución, y obtener una región de muestreo más simple para aumentar la eficiencia. Una opción para simplificar este proceso es la expansión y contracción regional.

• En primer lugar, se utiliza un parámetro de ancho w para definir el área que contiene el valor 'x' dado. Se prueba cada extremo de esta área para ver si se encuentra fuera de la porción dada. Si no es así, la región se extiende en la(s) dirección(es) apropiada(s) mediante w hasta que ambos extremos se encuentren fuera de la porción.
• Se selecciona una muestra candidata de manera uniforme dentro de esta región. Si la muestra candidata se encuentra dentro de la porción, se acepta como la nueva muestra. Si se encuentra fuera de la porción, el punto candidato se convierte en el nuevo límite de la región. Se toma una nueva muestra candidata de manera uniforme. El proceso se repite hasta que la muestra candidata se encuentra dentro de la porción. (Consulte el diagrama para ver un ejemplo visual).

Encontrar una muestra dado un conjunto de rebanadas (las rebanadas se representan aquí como líneas azules y corresponden a las rebanadas de línea sólida en el gráfico anterior de f ( x ) ). a) Se establece un parámetro de ancho w . b) Se identifica una región de ancho w alrededor de un punto dado . c) La región se expande por w hasta que ambos puntos finales estén fuera de la rebanada considerada. d) se selecciona uniformemente de la región. e) Dado que se encuentra fuera de la rebanada considerada, el límite izquierdo de la región se ajusta a . f) Se toma otra muestra uniforme y se acepta como la muestra ya que se encuentra dentro de la rebanada considerada. ${\displaystyle x_{0}}$ ${\displaystyle x_{1}}$ ${\displaystyle x_{1}}$ ${\displaystyle x_{1}}$ ${\displaystyle x}$

→

Muestreo de corte dentro de Gibbs

En un muestreador de Gibbs , es necesario extraer datos de manera eficiente de todas las distribuciones totalmente condicionales. Cuando no es fácil muestrear a partir de una densidad totalmente condicional, se puede utilizar una única iteración de muestreo por cortes o el algoritmo Metropolis-Hastings dentro de Gibbs para muestrear a partir de la variable en cuestión. Si la densidad totalmente condicional es logarítmicamente cóncava, una alternativa más eficiente es la aplicación de métodos de muestreo de rechazo adaptativo (ARS). ^{[4] [5]} Cuando no se pueden aplicar las técnicas ARS (ya que la totalmente condicional no es logarítmicamente cóncava), a menudo se emplean los algoritmos de muestreo de rechazo adaptativo de Metropolis . ^{[6] [7]}

Métodos multivariados

Tratando cada variable independientemente

El muestreo por sectores de una sola variable se puede utilizar en el caso multivariado muestreando cada variable una a una repetidamente, como en el muestreo de Gibbs. Para ello, es necesario que podamos calcular, para cada componente, una función que sea proporcional a . ${\displaystyle x_{i}}$ ${\displaystyle p(x_{i}|x_{0}...x_{n})}$

Para evitar un comportamiento de caminata aleatoria, se pueden utilizar métodos de sobrerelajación para actualizar cada variable a su vez. ^{[ cita requerida ]} La sobrerelajación elige un nuevo valor en el lado opuesto de la moda del valor actual, en lugar de elegir un nuevo valor independiente de la distribución como se hace en Gibbs.

Muestreo de cortes hiperrectangulares

Este método adapta el algoritmo univariado al caso multivariado sustituyendo un hiperrectángulo por la región w unidimensional utilizada en el original. El hiperrectángulo H se inicializa en una posición aleatoria sobre la porción. Luego, H se encoge a medida que se rechazan los puntos que lo componen.

Muestreo de cortes reflexivos

El muestreo de rebanadas reflexivo es una técnica para suprimir el comportamiento de caminata aleatoria en el cual las muestras candidatas sucesivas de la distribución f ( x ) se mantienen dentro de los límites de la rebanada al "reflejarse" la dirección del muestreo hacia adentro de la rebanada una vez que se ha alcanzado el límite.

En esta representación gráfica del muestreo reflexivo, la forma indica los límites de una porción de muestreo. Los puntos indican los puntos de inicio y de finalización de un recorrido de muestreo. Cuando las muestras alcanzan los límites de la porción, la dirección del muestreo se "refleja" nuevamente en la porción.

Ejemplo

Consideremos un ejemplo de una sola variable. Supongamos que nuestra distribución real es una distribución normal con media 0 y desviación estándar 3, . Por lo tanto: . El pico de la distribución está obviamente en , en cuyo punto . ${\displaystyle g(x)\sim N(0,3^{2})}$ ${\displaystyle f(x)={\frac {1}{\sqrt {2\pi \cdot 3^{2}}}}\ e^{-{\frac {(x-0)^{2}}{2\cdot 3^{2}}}}}$ ${\displaystyle x=0}$ ${\displaystyle f(x)\approx 0.1330}$

1. Primero extraemos un valor aleatorio uniforme y del rango de f ( x ) para definir nuestra(s) porción(es). f ( x ) varía de 0 a ~0,1330, por lo que cualquier valor entre estos dos extremos es suficiente. Supongamos que tomamos y = 0,1. El problema es cómo muestrear puntos que tienen valores y > 0,1.
2. A continuación, establecemos nuestro parámetro de ancho w, que utilizaremos para ampliar nuestra región de consideración. Este valor es arbitrario. Supongamos que w = 2.
3. A continuación, necesitamos un valor inicial para x . Extraemos x de la distribución uniforme dentro del dominio de f ( x ) que satisface f ( x ) > 0,1 (nuestro parámetro y ). Supongamos que x = 2. Esto funciona porque f (2) = ~0,1065 > 0,1. ^[8]
4. Como x = 2 y w = 2, nuestra región de interés actual está limitada por (1, 3).
5. Ahora, se prueba cada punto final de esta área para ver si se encuentra fuera de la porción dada. Nuestro límite derecho se encuentra fuera de nuestra porción ( f (3) = ~0.0807 < 0.1), pero el valor izquierdo no ( f (1) = ~0.1258 > 0.1). Expandimos el límite izquierdo agregándole w hasta que se extienda más allá del límite de la porción. Después de este proceso, los nuevos límites de nuestra región de interés son (−3, 3).
6. A continuación, tomamos una muestra uniforme dentro de (−3, 3). Supongamos que esta muestra arroja x = −2,9. Aunque esta muestra está dentro de nuestra región de interés, no se encuentra dentro de nuestra porción (f(2,9) = ~0,08334 < 0,1), por lo que modificamos el límite izquierdo de nuestra región de interés hasta este punto. Ahora tomamos una muestra uniforme de (−2,9, 3). Supongamos que esta vez nuestra muestra arroja x = 1, que está dentro de nuestra porción y, por lo tanto, es la muestra de salida aceptada por el muestreo por porción. Si nuestra nueva x no hubiera estado dentro de nuestra porción, continuaríamos el proceso de reducción/remuestreo hasta que se encuentre una x válida dentro de los límites.

Si nos interesa el pico de la distribución, podemos seguir repitiendo este proceso ya que el nuevo punto corresponde a un f ( x ) mayor que el punto original.

Otro ejemplo

Para tomar una muestra de la distribución normal, primero elegimos una x inicial, digamos 0. Después de cada muestra de x, elegimos y de manera uniforme al azar de , que está acotada por la función de densidad de probabilidad de . Después de cada muestra de y, elegimos x de manera uniforme al azar de donde . Esta es la porción donde . ${\displaystyle N(0,1)}$ ${\displaystyle (0,e^{-x^{2}/2}/{\sqrt {2\pi }}]}$ ${\displaystyle N(0,1)}$ ${\displaystyle [-\alpha ,\alpha ]}$ ${\displaystyle \alpha ={\sqrt {-2\ln(y{\sqrt {2\pi }})}}}$ ${\displaystyle f(x)>y}$

Una implementación en el lenguaje Macsyma es:

rebanada ( x ) :=  bloque ([ y ,  alfa ] ,  y: aleatorio ( exp ( - x ^ 2  /  2.0 ) /  sqrt ( 2.0  *  dfloat ( % pi ))) ,  alfa: sqrt ( -2.0  *  ln ( y  *  sqrt ( 2.0  *  dfloat ( % pi )))) ,  x: signo ( aleatorio ()) *  aleatorio ( alfa )) ;

Véase también

• Cadena de Markov Monte Carlo

Referencias

1. Damlen, P., Wakefield, J. y Walker, S. (1999). Muestreo de Gibbs para modelos bayesianos no conjugados y jerárquicos mediante el uso de variables auxiliares. Journal of the Royal Statistical Society, Serie B (Metodología estadística), 61(2), 331-344. Chicago
2. Neal, Radford M. (2003). "Muestreo por cortes". Anales de estadística . 31 (3): 705–767. doi : 10.1214/aos/1056562461 . MR  1994729. Zbl  1051.65007.
3. Bishop, Christopher (2006). "11.4: Muestreo por sectores". Reconocimiento de patrones y aprendizaje automático . Springer . ISBN 978-0387310732.
4. Gilks, WR; Wild, P. (1 de enero de 1992). "Muestreo de rechazo adaptativo para el muestreo de Gibbs". Revista de la Royal Statistical Society. Serie C (Estadística aplicada) . 41 (2): 337–348. doi :10.2307/2347565. JSTOR  2347565.
5. Hörmann, Wolfgang (1995-06-01). "Una técnica de rechazo para el muestreo de distribuciones T-cóncavas". ACM Trans. Math. Softw . 21 (2): 182–193. CiteSeerX 10.1.1.56.6055 . doi :10.1145/203082.203089. ISSN  0098-3500. S2CID  592740. 
6. Gilks, WR; Best, NG ; Tan, KKC (1 de enero de 1995). "Muestreo de metrópolis con 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.
7. Meyer, Renate; Cai, Bo; Perron, François (15 de marzo de 2008). "Muestreo de Metropolis de rechazo adaptativo utilizando polinomios de interpolación de Lagrange de grado 2". Computational Statistics & Data Analysis . 52 (7): 3408–3423. doi :10.1016/j.csda.2008.01.005.
8. Tenga en cuenta que si no supiéramos cómo seleccionar x de modo que f ( x ) > y , aún podemos elegir cualquier valor aleatorio para x , evaluar f ( x ) y usarlo como nuestro valor de y . y solo inicializa el algoritmo; a medida que el algoritmo progresa, encontrará valores cada vez más altos de y .

Enlaces externos

• http://www.probability.ca/jeff/java/slice.html