Muestreo por Significancia

El muestreo por importancia ( en adelante OT) es uno de los métodos para reducir la varianza de una variable aleatoria, que se utiliza para mejorar la convergencia del proceso de modelización de cualquier cantidad por el método de Monte Carlo . La idea de VZ se basa en que algunos valores de una variable aleatoria en el proceso de modelado tienen una mayor significancia (probabilidad) para la función evaluada (parámetro) que otros. Si estos valores “más probables” aparecen con mayor frecuencia durante la selección de una variable aleatoria, la varianza de la función estimada disminuirá. Por tanto, la metodología subyacente de la EOI es elegir una distribución que favorezca la selección de valores “más probables” de la variable aleatoria. Tal distribución "sesgada" cambia la función estimada si se aplica directamente en el proceso de cálculo. Sin embargo, el resultado del cálculo se vuelve a ponderar de acuerdo con esta distribución sesgada, y esto asegura que la nueva función OT estimada no esté sesgada. El peso en sí viene dado por la relación de verosimilitud , es decir, la derivada de Radon-Nikodym de la distribución inicial verdadera con respecto a la distribución sesgada elegida.

Una tarea fundamental en la implementación de la EOI es la elección de una distribución sesgada que identifique regiones con valores “más probables” de la función estimada.

VZ es efectivo si dicha distribución se elige y construye con éxito, ya que reducirá significativamente el tiempo de cálculo. Con una distribución sesgada desafortunada, incluso el método estándar de Monte Carlo puede dar mejores resultados.

Fundamentos matemáticos

Considere modelar la probabilidad de un evento , donde es una variable aleatoria con una distribución y una densidad de probabilidad , donde la prima significa la derivada de . Deje que se genere una estadística de longitud K, una secuencia de K eventos independientes y uniformemente distribuidos , basada en la distribución de , y queremos estimar el número de variables aleatorias en K cuyos valores se encuentran por encima de algunos . La variable aleatoria se caracteriza por la distribución binomial $p_{t}$ ${ X \ge t\ }$ $X$ $F$ ${\ estilo de visualización f (x) = F' (x)}$ $X_{yo}$ $F$ $k_t$ $t$ $k_t$

P(k_t = k)={K\elegir k}p_t^k(1-p_t)^{Kk},\,\quad \quad k=0,1,\dots,K.

El muestreo significativo se refiere a la construcción y uso de otra función de densidad (para X), comúnmente conocida como densidad sesgada, en un experimento computacional (simulación). La nueva densidad permite que el evento ocurra con mayor frecuencia, por lo que la longitud de la secuencia para un valor dado de la varianza de las estadísticas construidas disminuirá. En otras palabras, para una estadística K dada, el uso de densidad sesgada da como resultado una varianza menor que la estimación de Monte Carlo convencional. A partir de la definición , podemos ingresar de la siguiente manera: $F_{*}$ ${ X \ge t\ }$ $p_{t}$ $F_{*}$

p_t = {E}[X\ge t]

= \int (x \ge t) \frac{f(x)}{f_*(x)} f_*(x) \,dx

= {E_*} [(X \ge t) W(X)]

dónde

W(\cdot) \equiv \frac{f(\cdot)}{f_*(\cdot)}

es la razón de verosimilitud y se llama función de ponderación. La última igualdad conduce a la consideración de estadísticas.

\hat p_t = \frac{1}{K}\,\sum_{i=1}^K (X_i \ge t) W(X_i),\,\quad \quad X_i \sim f_*

Esta es una estadística OT para y no se rechaza cuando se usa . Por lo tanto, el procedimiento de simulación para VZ se puede formular como la preparación de una secuencia de eventos independientes y uniformemente distribuidos para la densidad , cuando cada evento tendrá un peso mayor y los eventos adicionales se aceptarán como antes si son mayores que . El resultado se promedia sobre todas las estadísticas . Es fácil demostrar que la varianza de la estimación OT será igual a $p_{t}$ $F_{*}$ $F_{*}$ $W$ $t$ $k$

Var_{*}{\hat {p}}_{t}={\frac {1}{K}}Var_{*}[(X\geq t)W(X)]

= \frac{1}{K}\Grande[{E_*}[(X \ge t)^2 W^2(X)] - p_t^2 \Grande]

= \frac{1}{K}\Grande[{E}[(X \ge t)^2 W(X)] - p_t^2 \Grande]

Ahora, el problema de TO se puede formular como encontrar una densidad de probabilidad tal que la varianza de las nuevas estadísticas sea menor que la obtenida por el método habitual de Monte Carlo. Si en el problema es posible construir una densidad de probabilidad sesgada para la cual la varianza es 0, entonces se denomina densidad de probabilidad sesgada óptima. $F_{*}$

Métodos para construir distribuciones sesgadas

Aunque existen muchos métodos para trazar densidades sesgadas, los siguientes dos métodos son los más comunes cuando se utilizan EOI.

Escalado

Desplace una medida de probabilidad a una región escalando una variable aleatoria por un número mayor que uno. Tal escala conduce a un aumento en la importancia de la cola de la densidad de probabilidad y, por lo tanto, da un aumento en la probabilidad de que ocurran los eventos "deseados". Con toda probabilidad, el escalado fue uno de los primeros métodos de sesgo ampliamente utilizados en la práctica. Implementado fácilmente en algoritmos reales, este método ofrece una mejora bastante modesta en la eficiencia de la simulación en comparación con otros métodos de sesgo. ${ X \ge t\ }$ $X$

En el VZ al escalar, la densidad de probabilidad para la simulación se define como la densidad original para la variable aleatoria escalada . Si es importante para nosotros estimar la cola de la densidad de probabilidad hacia arriba, elija . Las nuevas funciones de densidad y peso, respectivamente, son ${\ estilo de visualización aX}$ $a>1$

{\displaystyle f_{*}(x)={\frac {1}{a}}f{\bigg (}{\frac {x}{a}}{\bigg )))

W(x)= a \frac{f(x)}{f(x/a)} \, .

Mientras que el escalado cambia la medida de probabilidad a la región deseada de eventos "deseados", también cambia la probabilidad a la región . Si es la suma de variables aleatorias, la distribución de probabilidad se produce en el -ésimo espacio. Como consecuencia, esto reduce la eficiencia de la IO a medida que aumenta (efecto de dimensionalidad). ${\ estilo de visualización X <t}$ $X$ $norte$ $norte$ $norte$

Difusión

Otra técnica de sesgo simple y efectiva se basa en traducir la densidad de probabilidad (y por lo tanto la variable aleatoria) a una región donde la probabilidad aumenta. Las traslaciones no conducen al efecto de dimensión. Esta técnica se ha aplicado con éxito en aplicaciones del mundo real, como el modelado de sistemas de comunicación digital . A menudo, este método es más eficaz que el escalado. Bajo el sesgo de traducción, la nueva densidad de probabilidad se define como

f_{*}(x)=f(xc),\quad c>0

donde es el valor de cambio elegido de la condición de minimizar la varianza de las estadísticas IS. $C$

Efectos de la complejidad del sistema

El problema fundamental del TO es la dificultad de construir una buena distribución sesgada a medida que el sistema en estudio se vuelve más complejo. En este sentido, los sistemas con una memoria larga se denominan sistemas complejos, ya que para sistemas donde se realiza un procesamiento complejo de un pequeño número de parámetros de entrada (es decir, en problemas de pequeña dimensión), el problema de construir un OT es más sencillo. Por ejemplo, en la teoría de la señalización digital, la memoria larga (o la gran dimensionalidad de las condiciones iniciales) conduce a tres tipos de problemas:

memoria larga (fuerte interacción entre personajes)
memoria de longitud indefinida (decodificadores Viterbi)
memoria de longitud posiblemente infinita (ecualizadores adaptativos)

En principio, las ideas básicas de la EO no cambian cuando se aplican a este tipo de problemas, pero la implementación se vuelve mucho más complicada. Una estrategia exitosa para lidiar con problemas de memoria larga puede ser dividir el problema completo en varias partes mejor definidas. Luego se aplica el EOI a cada uno de los subproblemas de forma independiente.

Estimaciones numéricas del AT

Para determinar el éxito de la densidad de IO encontrada, es útil tener una estimación numérica de la reducción en la cantidad de cálculos cuando se aplica. Para tal estimación, generalmente se usa la relación , que puede interpretarse como un factor para aumentar la velocidad con la que las estadísticas OT alcanzarán la misma precisión que las estadísticas obtenidas por el método habitual de Monte Carlo. El valor de la relación solo se puede obtener empíricamente, ya que las varianzas de las estadísticas son casi imposibles de derivar analíticamente. $\sigma_{MC}^{2}/\sigma_{IS}^{2}$

Precio función de varianza

La varianza no es la única función de precio para modelar, ya que existen otros tipos de funciones de precio que se utilizan en varias aplicaciones estadísticas, como la desviación media absoluta. Sin embargo, la varianza se cita comúnmente en la literatura, posiblemente debido al uso de la varianza en el cálculo de los intervalos de confianza y en la expresión para medir la eficiencia . $\sigma_{MC}^{2}/\sigma_{IS}^{2}$

Un problema con el uso de la varianza es que la relación sobreestima la reducción en el esfuerzo computacional cuando se usa EOI, ya que este parámetro no tiene en cuenta el tiempo adicional requerido para calcular la función de ponderación. Por tanto, en una aplicación real, la mejora resultante de la aplicación de la EOI debe ser evaluada por otros métodos. Quizás un problema más serio en términos de eficiencia en la EOI es el tiempo para desarrollar e implementar la técnica en sí y la construcción analítica de la función de peso necesaria (si no se conoce de antemano). $\sigma_{MC}^{2}/\sigma_{IS}^{2}$

Véase también

Método de Montecarlo
Muestreo zonificado
Muestreo zonal recursivo
Métodos secuenciales de Monte Carlo o filtro de partículas

Literatura

IM Sobol. Métodos numéricos de Montecarlo. M.: Nauka, 1973
PJSmith, M.Shafi y H. Gao, "Simulación rápida: una revisión de la importancia de las técnicas de muestreo en los sistemas de comunicación", IEEE J.Select.Areas Commun., vol. 15, págs. 597-613, mayo de 1997.
M. Ferrari, S. Bellini, "Simulación de muestreo de importancia de códigos de productos turbo", ICC2001, The IEEE International Conference on Communications, vol. 9, págs. 2773–2777, junio de 2001.
Tommy Oberg, Modulación, detección y codificación, John Wiley & Sons, Inc., Nueva York, 2001.
R. Srinivasan., Muestreo de importancia. Nueva York: Springer, 2002.

Además

"Muestreo de importancia: aplicaciones en comunicaciones y detección", Rajan Srinivasan, Springer-Verlag, Berlín, 2002.
"Introducción a la simulación de eventos raros", James Antonio Bucklew, Springer-Verlag, Nueva York, 2004.

Enlaces

Página de inicio de métodos secuenciales de Monte Carlo (filtrado de partículas) en la Universidad de Cambridge
Introducción a la importancia del muestreo en simulaciones de eventos raros European journal of Physics. documento PDF.
Métodos adaptativos de monte carlo para simulaciones de eventos raros: métodos adaptativos de monte carlo para simulaciones de eventos raros Winter Simulation Conference
Cuba - una biblioteca para la integración numérica multidimensional