De Wikipedia, la enciclopedia libre
Saltar a navegación Saltar a búsqueda

En estadística , el muestreo por importancia es una técnica general para estimar propiedades de una distribución particular , mientras que solo se generan muestras a partir de una distribución diferente a la distribución de interés. Está relacionado con el muestreo paraguas en física computacional . Dependiendo de la aplicación, el término puede referirse al proceso de muestreo de esta distribución alternativa, el proceso de inferencia o ambos.

Teoría básica [ editar ]

Sea una variable aleatoria en algún espacio de probabilidad . Deseamos estimar el valor esperado de X bajo P , denotado E [ X; P ]. Si tenemos muestras aleatorias estadísticamente independientes , generadas de acuerdo con P , entonces una estimación empírica de E [ X; P ] es

y la precisión de esta estimación depende de la varianza de X :

La idea básica del muestreo de importancia es muestrear los estados de una distribución diferente para reducir la varianza de la estimación de E [ X; P ], o cuando el muestreo de P es difícil. Esto se logra eligiendo primero una variable aleatoria tal que E [ L ; P ] = 1 y que P - casi en todas partes . Con la variable L definimos una probabilidad que satisface

Por lo tanto, la variable X / L se muestreará bajo P ( L ) para estimar E [ X; P ] como se indicó anteriormente y esta estimación se mejora cuando .

Cuando X es de signo constante sobre Ω, la mejor variable L sería claramente , de modo que X / L * es la constante buscada E [ X; P ] y una sola muestra bajo P ( L *) es suficiente para dar su valor. Desafortunadamente, no podemos tomar esa decisión, ¡porque E [ X; P ] es precisamente el valor que estamos buscando! Sin embargo, este mejor caso teórico L * nos da una idea de la importancia que tiene el muestreo:

a la derecha, está uno de los elementos infinitesimales que suman E [ X ; P ]:

por lo tanto, un buen cambio de probabilidad P ( L ) en el muestreo de importancia redistribuirá la ley de X de modo que las frecuencias de sus muestras se clasifiquen directamente de acuerdo con sus pesos en E [ X ; P ]. De ahí el nombre "muestreo por importancia".

El muestreo de importancia se utiliza a menudo como un integrador de Monte Carlo . Cuando es la distribución uniforme y , E [ X; P ] corresponde a la integral de la función real .

Aplicación a la inferencia probabilística [ editar ]

Estos métodos se utilizan con frecuencia para estimar densidades posteriores o expectativas en problemas de estimación de estados y / o parámetros en modelos probabilísticos que son demasiado difíciles de tratar analíticamente, por ejemplo, en redes bayesianas .

Aplicación a la simulación [ editar ]

El muestreo de importancia es una técnica de reducción de la varianza que se puede utilizar en el método de Monte Carlo . La idea detrás del muestreo de importancia es que ciertos valores de las variables aleatorias de entrada en una simulación tienen más impacto en el parámetro que se estima que otros. Si estos valores "importantes" se enfatizan mediante el muestreo con mayor frecuencia, entonces el estimadorla varianza se puede reducir. Por tanto, la metodología básica en el muestreo de importancia es elegir una distribución que "fomente" los valores importantes. Este uso de distribuciones "sesgadas" dará como resultado un estimador sesgado si se aplica directamente en la simulación. Sin embargo, los resultados de la simulación se ponderan para corregir el uso de la distribución sesgada, y esto asegura que el nuevo estimador de muestreo de importancia sea insesgado. El peso viene dado por la razón de verosimilitud , es decir, la derivada Radon-Nikodym de la verdadera distribución subyacente con respecto a la distribución de simulación sesgada.

La cuestión fundamental en la implementación de la simulación de muestreo de importancia es la elección de la distribución sesgada que fomenta las regiones importantes de las variables de entrada. Elegir o diseñar una buena distribución sesgada es el "arte" del muestreo de importancia. Las recompensas por una buena distribución pueden ser enormes ahorros de tiempo de ejecución; la penalización por una mala distribución puede ser tiempos de ejecución más largos que para una simulación general de Monte Carlo sin muestreo de importancia.

Considere la muestra y la razón de verosimilitud, donde es la función de densidad de probabilidad (masa) de la distribución deseada y es la función de densidad de probabilidad (masa) de la distribución sesgada / propuesta / muestral. Luego, el problema se puede caracterizar eligiendo la distribución de la muestra que minimice la varianza de la muestra escalada:

Se puede demostrar que la siguiente distribución minimiza la varianza anterior: [1]

Observe que cuando , esta varianza se convierte en 0.

Enfoque matemático [ editar ]

Considere estimar mediante simulación la probabilidad de un evento , donde es una variable aleatoria con distribución y función de densidad de probabilidad , donde prima denota derivada . A partir de la distribución se genera una secuencia independiente de longitud e idénticamente distribuida (iid) , y se cuenta el número de variables aleatorias que se encuentran por encima del umbral . La variable aleatoria se caracteriza por la distribución Binomial

Uno puede demostrar eso , y así en el límite que podemos obtener . Tenga en cuenta que la varianza es baja si . El muestreo de importancia se ocupa de la determinación y el uso de una función de densidad alternativa (para ), generalmente denominada densidad de sesgo, para el experimento de simulación. Esta densidad permite que el evento ocurra con más frecuencia, por lo que las longitudes de secuencia se vuelven más pequeñas para una varianza de estimador dada . Alternativamente, para un dato dado , el uso de la densidad de sesgo da como resultado una varianza menor que la de la estimación convencional de Monte Carlo. A partir de la definición de , podemos introducir lo siguiente.

dónde

es una razón de verosimilitud y se denomina función de ponderación. La última igualdad en la ecuación anterior motiva al estimador

Este es el estimador de muestreo de importancia y es insesgado. Es decir, el procedimiento de estimación consiste en generar muestras de iid a partir de y para cada muestra que exceda , la estimación se incrementa por el peso evaluado en el valor de la muestra. Los resultados se promedian entre los ensayos. Se muestra fácilmente que la varianza del estimador muestral de importancia es

Ahora, el problema del muestreo de importancia se centra en encontrar una densidad de sesgo tal que la varianza del estimador de muestreo de importancia sea menor que la varianza de la estimación general de Monte Carlo. Para alguna función de densidad de polarización, que minimiza la varianza y, en determinadas condiciones, la reduce a cero, se denomina función de densidad de polarización óptima.

Métodos convencionales de sesgo [ editar ]

Aunque existen muchos tipos de métodos de sesgo, los dos métodos siguientes son los más utilizados en las aplicaciones del muestreo por importancia.

Escala [ editar ]

El desplazamiento de la masa de probabilidad a la región del evento mediante el escalado positivo de la variable aleatoria con un número mayor que la unidad tiene el efecto de aumentar la varianza (también la media) de la función de densidad. Esto da como resultado una cola más pesada de la densidad, lo que conduce a un aumento en la probabilidad del evento. El escalado es probablemente uno de los primeros métodos de sesgo conocidos y se ha utilizado ampliamente en la práctica. Es simple de implementar y generalmente proporciona ganancias de simulación conservadoras en comparación con otros métodos.

En el muestreo de importancia por escala, la densidad de simulación se elige como la función de densidad de la variable aleatoria escalada , donde normalmente se utiliza para la estimación de la probabilidad de cola. Por transformación,

y la función de ponderación es

Si bien el escalado desplaza la masa de probabilidad a la región del evento deseada, también empuja la masa hacia la región complementaria, lo que no es deseable. Si es una suma de variables aleatorias, la dispersión de la masa tiene lugar en un espacio dimensional. La consecuencia de esto es una ganancia de muestreo de importancia decreciente para aumentar, y se llama efecto de dimensionalidad. Una versión moderna del muestreo de importancia por escala es, por ejemplo, el llamado muestreo a escala sigma (SSS), que ejecuta múltiples análisis de Monte Carlo (MC) con diferentes factores de escala. A diferencia de muchos otros métodos de estimación de alto rendimiento (como distancias WCD en el peor de los casos), SSS no sufre mucho el problema de dimensionalidad. Además, abordar múltiples salidas de MC no causa degradación en la eficiencia. Por otro lado, como WCD, SSS solo está diseñado para variables estadísticas gaussianas y, a diferencia de WCD, el método SSS no está diseñado para proporcionar esquinas estadísticas precisas. Otra desventaja de SSS es que las ejecuciones de MC con factores de gran escala pueden resultar difíciles, por ejemplo, debido a problemas de convergencia del modelo y el simulador. Además, en SSS nos enfrentamos a una fuerte compensación de sesgo-varianza: utilizando factores de gran escala,obtenemos resultados de rendimiento bastante estables, pero cuanto mayores son los factores de escala, mayor es el error de sesgo. Si las ventajas de SSS no importan mucho en la aplicación de interés, a menudo otros métodos son más eficientes.

Traducción [ editar ]

Otra técnica de polarización simple y efectiva emplea la traducción de la función de densidad (y por lo tanto la variable aleatoria) para colocar gran parte de su masa de probabilidad en la región de eventos raros. La traducción no sufre un efecto de dimensionalidad y se ha utilizado con éxito en varias aplicaciones relacionadas con la simulación de sistemas de comunicación digital . A menudo proporciona mejores ganancias de simulación que el escalado. En el sesgo por traducción, la densidad de simulación viene dada por

donde es la cantidad de desplazamiento y se elegirá para minimizar la varianza del estimador de muestreo de importancia.

Efectos de la complejidad del sistema [ editar ]

El problema fundamental del muestreo por importancia es que diseñar buenas distribuciones sesgadas se vuelve más complicado a medida que aumenta la complejidad del sistema. Los sistemas complejos son los sistemas con mucha memoria, ya que el procesamiento complejo de unas pocas entradas es mucho más fácil de manejar. Esta dimensionalidad o memoria puede causar problemas de tres formas:

  • memoria larga ( interferencia grave entre símbolos (ISI))
  • memoria desconocida ( decodificadores de Viterbi )
  • posiblemente memoria infinita (ecualizadores adaptativos)

En principio, la importancia del muestreo de ideas sigue siendo la misma en estas situaciones, pero el diseño se vuelve mucho más difícil. Un enfoque exitoso para combatir este problema consiste esencialmente en dividir una simulación en varios subproblemas más pequeños y definidos con mayor precisión. Luego, se utilizan estrategias de muestreo de importancia para abordar cada uno de los subproblemas más simples. Ejemplos de técnicas para descomponer la simulación son el acondicionamiento y la simulación de eventos de error (EES) y la simulación regenerativa.

Evaluación del muestreo de importancia [ editar ]

Para identificar técnicas de muestreo de importancia exitosas, es útil poder cuantificar los ahorros de tiempo de ejecución debido al uso del enfoque de muestreo de importancia. La medida de desempeño comúnmente utilizada es , y esto puede interpretarse como el factor de aceleración por el cual el estimador de muestreo de importancia alcanza la misma precisión que el estimador de MC. Esto debe calcularse empíricamente, ya que no es probable que las varianzas del estimador sean analíticamente posibles cuando su media es intratable. Otros conceptos útiles para cuantificar un estimador de muestreo de importancia son los límites de la varianza y la noción de eficiencia asintótica. Una medida relacionada es el denominado tamaño de muestra efectivo (EEE) . [2]

Función de costo de variación [ editar ]

La varianza no es la única función de costo posible para una simulación, y otras funciones de costo, como la desviación absoluta media, se utilizan en diversas aplicaciones estadísticas. Sin embargo, la varianza es la función de costo principal abordada en la literatura, probablemente debido al uso de varianzas en los intervalos de confianza y en la medida de desempeño .

Un problema asociado es el hecho de que la relación sobrestima los ahorros de tiempo de ejecución debido al muestreo de importancia, ya que no incluye el tiempo de cálculo adicional necesario para calcular la función de ponderación. Por lo tanto, algunas personas evalúan la mejora neta del tiempo de ejecución por varios medios. Quizás una sobrecarga más seria del muestreo de importancia es el tiempo necesario para diseñar y programar la técnica y derivar analíticamente la función de ponderación deseada.

Muestreo de importancia múltiple y adaptativa [ editar ]

Cuando diferentes distribuciones propuesta, , se utilizan conjuntamente para la elaboración de las muestras de diferentes funciones propias de ponderación se pueden emplear (por ejemplo, véase [3] [4] [5] [6] ). En un entorno adaptativo, las distribuciones de propuesta , y se actualizan en cada iteración del algoritmo de muestreo de importancia adaptativa. Por lo tanto, dado que se usa una población de densidades propuestas, se pueden emplear varias combinaciones adecuadas de esquemas de muestreo y ponderación. [7] [8] [9] [10] [11] [12] [13]

Ver también [ editar ]

  • Método de Montecarlo
  • Reducción de varianza
  • Muestreo estratificado
  • Muestreo estratificado recursivo
  • Algoritmo VEGAS
  • Filtro de partículas : un método secuencial de Monte Carlo, que utiliza muestreo de importancia
  • Campo auxiliar Monte Carlo
  • Muestreo de rechazo
  • Tasa de bits variable : una aplicación de audio común de muestreo de importancia

Notas [ editar ]

  1. ^ Rubinstein, RY y Kroese, DP (2011). Simulación y método de Monte Carlo (Vol. 707). John Wiley e hijos.
  2. ^ Martino, Luca; Elvira, Víctor; Louzada, Francisco (2017). "Tamaño de muestra efectivo para muestreo de importancia basado en medidas de discrepancia". Procesamiento de señales . 131 : 386–401. arXiv : 1602.03572 . doi : 10.1016 / j.sigpro.2016.08.025 .
  3. ^ Veach, Eric; Guibas, Leonidas J. (1 de enero de 1995). Combinación óptima de técnicas de muestreo para el renderizado Monte Carlo . Actas de la 22ª Conferencia Anual sobre Gráficos por Computadora y Técnicas Interactivas . SIGGRAPH '95. Nueva York, NY, EE.UU .: ACM. págs.  419–428 . CiteSeerX 10.1.1.127.8105 . doi : 10.1145 / 218380.218498 . ISBN  978-0-89791-701-8.
  4. Owen, Art; Asociado, Yi Zhou (1 de marzo de 2000). "Muestreo de importancia seguro y eficaz". Revista de la Asociación Estadounidense de Estadística . 95 (449): 135-143. CiteSeerX 10.1.1.36.4536 . doi : 10.1080 / 01621459.2000.10473909 . ISSN 0162-1459 .  
  5. Elvira, V .; Martino, L .; Luengo, D .; Bugallo, MF (1 de octubre de 2015). "Estimadores eficientes de muestreo de importancia múltiple". Cartas de procesamiento de señales IEEE . 22 (10): 1757-1761. arXiv : 1505.05391 . Código bibliográfico : 2015ISPL ... 22.1757E . doi : 10.1109 / LSP.2015.2432078 . ISSN 1070-9908 . 
  6. ^ Elvira, Víctor; Martino, Luca; Luengo, David; Bugallo, Mónica F. (2017). "Mejora de la población de Montecarlo: esquemas alternativos de ponderación y remuestreo". Procesamiento de señales . 131 : 77–91. arXiv : 1607.02758 . doi : 10.1016 / j.sigpro.2016.07.012 .
  7. ^ Cappé, O .; Guillin, A .; Marin, JM; Robert, CP (1 de diciembre de 2004). "Población Monte Carlo". Revista de Estadística Computacional y Gráfica . 13 (4): 907–929. doi : 10.1198 / 106186004X12803 . ISSN 1061-8600 . 
  8. ^ Martino, L .; Elvira, V .; Luengo, D .; Corander, J. (1 de mayo de 2017). "Muestreo de importancia adaptativa en capas". Estadística y Computación . 27 (3): 599–623. arXiv : 1505.04732 . doi : 10.1007 / s11222-016-9642-5 . ISSN 0960-3174 . 
  9. ^ Cappé, Olivier; Douc, Randal; Guillin, Arnaud; Marin, Jean-Michel; Robert, Christian P. (25 de abril de 2008). "Muestreo de importancia adaptativa en clases de mezcla generales". Estadística y Computación . 18 (4): 447–459. arXiv : 0710.4242 . doi : 10.1007 / s11222-008-9059-x . ISSN 0960-3174 . 
  10. ^ Cornuet, Jean-Marie; Marin, Jean-Michel; Mira, Antonietta; Robert, Christian P. (1 de diciembre de 2012). "Muestreo adaptativo de importancia múltiple". Revista Escandinava de Estadística . 39 (4): 798–812. arXiv : 0907.1254 . doi : 10.1111 / j.1467-9469.2011.00756.x . ISSN 1467-9469 . 
  11. ^ Martino, L .; Elvira, V .; Luengo, D .; Corander, J. (1 de agosto de 2015). "Un muestreador adaptativo de la importancia de la población: aprender de la incertidumbre". Transacciones IEEE sobre procesamiento de señales . 63 (16): 4422–4437. Código Bib : 2015ITSP ... 63.4422M . CiteSeerX 10.1.1.464.9395 . doi : 10.1109 / TSP.2015.2440215 . ISSN 1053-587X .  
  12. ^ Bugallo, Mónica F .; Martino, Luca; Corander, Jukka (1 de diciembre de 2015). "Muestreo de importancia adaptativa en el procesamiento de señales" . Procesamiento de señales digitales . Número especial en honor a William J. (Bill) Fitzgerald. 47 : 36–49. doi : 10.1016 / j.dsp.2015.05.014 .
  13. ^ Bugallo, MF; Elvira, V .; Martino, L .; Luengo, D .; Miguez, J .; Djuric, PM (julio de 2017). "Muestreo de importancia adaptativa: el pasado, el presente y el futuro". Revista de procesamiento de señales IEEE . 34 (4): 60–79. Código bibliográfico : 2017ISPM ... 34 ... 60B . doi : 10.1109 / msp.2017.2699226 . ISSN 1053-5888 . 

Referencias [ editar ]

  • Arouna, Bouhari (2004). "Método adaptativo de Monte Carlo, una técnica de reducción de la varianza". Métodos de Monte Carlo y sus aplicaciones . 10 (1): 1–24. doi : 10.1515 / 156939604323091180 .
  • Bucklew, James Antonio (2004). Introducción a la simulación de eventos raros . Nueva York: Springer-Verlag.
  • Doucet, A .; de Freitas, N .; Gordon, N. (2001). Métodos secuenciales de Monte Carlo en la práctica . Saltador. ISBN 978-0-387-95146-1.
  • Ferrari, M .; Bellini, S. (2001). Importancia Simulación de muestreo de códigos de productos turbo . La Conferencia Internacional de Comunicaciones de IEEE . 9 . págs. 2773–2777. doi : 10.1109 / ICC.2001.936655 . ISBN 978-0-7803-7097-5.
  • Mazonka, Oleg (2016). "Fácil como Pi: el método de muestreo de importancia" (PDF) . Revista de referencia . 16 .
  • Oberg, Tommy (2001). Modulación, detección y codificación . Nueva York: John Wiley & Sons.
  • Presione, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007). "Sección 7.9.1 Muestreo de importancia" . Recetas numéricas: el arte de la informática científica (3ª ed.). Nueva York: Cambridge University Press. ISBN 978-0-521-88068-8.
  • Ripley, BD (1987). Simulación estocástica . Wiley & Sons.
  • Smith, PJ; Shafi, M .; Gao, H. (1997). "Simulación rápida: una revisión de las técnicas de muestreo de importancia en los sistemas de comunicación". Revista IEEE sobre áreas seleccionadas en comunicaciones . 15 (4): 597–613. doi : 10.1109 / 49.585771 .
  • Srinivasan, R. (2002). Muestreo de importancia - Aplicaciones en comunicaciones y detección . Berlín: Springer-Verlag.

Enlaces externos [ editar ]

  • Página de inicio de los métodos secuenciales de Monte Carlo (filtrado de partículas) en la Universidad de Cambridge
  • Introducción al muestreo de importancia en simulaciones de eventos raros European journal of Physics. Documento PDF.
  • Métodos adaptativos de monte carlo para simulación de eventos raros: métodos adaptativos de monte carlo para simulaciones de eventos raros Winter Simulation Conference