Método de entropía cruzada

Método de Monte Carlo para muestreo de importancia y optimización

El método de entropía cruzada ( CE ) es un método de Monte Carlo para el muestreo y optimización de importancia . Es aplicable tanto a problemas combinatorios como continuos , con un objetivo estático o ruidoso.

El método aproxima el estimador de muestreo de importancia óptima repitiendo dos fases: ^[1]

1. Extraer una muestra de una distribución de probabilidad .
2. Minimizar la entropía cruzada entre esta distribución y una distribución objetivo para producir una mejor muestra en la próxima iteración.

Reuven Rubinstein desarrolló el método en el contexto de la simulación de eventos poco frecuentes , donde se deben estimar probabilidades minúsculas, por ejemplo, en el análisis de confiabilidad de redes, modelos de colas o análisis de rendimiento de sistemas de telecomunicaciones. El método también se ha aplicado a problemas de vendedor ambulante , asignación cuadrática , alineamiento de secuencias de ADN , corte máximo y asignación de búfer.

Estimación mediante muestreo de importancia

Consideremos el problema general de estimar la cantidad

${\displaystyle \ell =\mathbb {E} _{\mathbf {u} }[H(\mathbf {X} )]=\int H(\mathbf {x} )\,f(\mathbf {x} ;\mathbf {u} )\,{\textrm {d}}\mathbf {x} }$,

donde es una función de rendimiento y es un miembro de una familia paramétrica de distribuciones. Mediante el muestreo de importancia, esta cantidad se puede estimar como ${\displaystyle H}$ ${\displaystyle f(\mathbf {x} ;\mathbf {u} )}$

${\displaystyle {\hat {\ell }}={\frac {1}{N}}\sum _{i=1}^{N}H(\mathbf {X} _{i}){\frac {f(\mathbf {X} _{i};\mathbf {u} )}{g(\mathbf {X} _{i})}}}$,

donde es una muestra aleatoria de . Para valores positivos , la densidad de muestreo de importancia (PDF) teóricamente óptima está dada por ${\displaystyle \mathbf {X} _{1},\dots ,\mathbf {X} _{N}}$ ${\displaystyle g\,}$ ${\displaystyle H}$

${\displaystyle g^{*}(\mathbf {x} )=H(\mathbf {x} )f(\mathbf {x} ;\mathbf {u} )/\ell }$.

Sin embargo, esto depende de la incógnita . El método CE tiene como objetivo aproximar la PDF óptima seleccionando de manera adaptativa los miembros de la familia paramétrica que sean más cercanos (en el sentido de Kullback-Leibler ) a la PDF óptima . ${\displaystyle \ell }$ ${\displaystyle g^{*}}$

Algoritmo CE genérico

1. Elija el vector de parámetros inicial ; establezca t = 1. ${\displaystyle \mathbf {v} ^{(0)}}$
2. Generar una muestra aleatoria de ${\displaystyle \mathbf {X} _{1},\dots ,\mathbf {X} _{N}}$ ${\displaystyle f(\cdot ;\mathbf {v} ^{(t-1)})}$
3. Resolver para , donde ${\displaystyle \mathbf {v} ^{(t)}}$
   ${\displaystyle \mathbf {v} ^{(t)}=\mathop {\textrm {argmax}} _{\mathbf {v} }{\frac {1}{N}}\sum _{i=1}^{N}H(\mathbf {X} _{i}){\frac {f(\mathbf {X} _{i};\mathbf {u} )}{f(\mathbf {X} _{i};\mathbf {v} ^{(t-1)})}}\log f(\mathbf {X} _{i};\mathbf {v} )}$
4. Si se alcanza la convergencia, deténgase ; de ​​lo contrario, aumente t en 1 y repita desde el paso 2.

En varios casos, la solución del paso 3 se puede encontrar analíticamente . Las situaciones en las que esto ocurre son:

• Cuando pertenece a la familia exponencial natural ${\displaystyle f\,}$
• ¿Cuándo es discreto con soporte finito? ${\displaystyle f\,}$
• Cuando y , entonces corresponde al estimador de máxima verosimilitud basado en aquellos . ${\displaystyle H(\mathbf {X} )=\mathrm {I} _{\{\mathbf {x} \in A\}}}$ ${\displaystyle f(\mathbf {X} _{i};\mathbf {u} )=f(\mathbf {X} _{i};\mathbf {v} ^{(t-1)})}$ ${\displaystyle \mathbf {v} ^{(t)}}$ ${\displaystyle \mathbf {X} _{k}\in A}$

Optimización continua: ejemplo

El mismo algoritmo CE se puede utilizar para la optimización, en lugar de la estimación. Supongamos que el problema es maximizar alguna función , por ejemplo, . Para aplicar CE, se considera primero el problema estocástico asociado de estimación para un nivel dado , y familia paramétrica , por ejemplo la distribución gaussiana unidimensional , parametrizada por su media y varianza (así aquí). Por lo tanto, para un dado , el objetivo es encontrar de modo que se minimice. Esto se hace resolviendo la versión de muestra (contraparte estocástica) del problema de minimización de divergencia KL, como en el paso 3 anterior. Resulta que los parámetros que minimizan la contraparte estocástica para esta elección de distribución objetivo y familia paramétrica son la media de la muestra y la varianza de la muestra correspondientes a las muestras de élite , que son aquellas muestras que tienen un valor de función objetivo . La peor de las muestras de élite se utiliza entonces como parámetro de nivel para la siguiente iteración. Esto produce el siguiente algoritmo aleatorio que coincide con el llamado Algoritmo de Estimación Normal Multivariante (EMNA), un algoritmo de estimación de distribución . ${\displaystyle S}$ ${\displaystyle S(x)={\textrm {e}}^{-(x-2)^{2}}+0.8\,{\textrm {e}}^{-(x+2)^{2}}}$ ${\displaystyle \mathbb {P} _{\boldsymbol {\theta }}(S(X)\geq \gamma )}$ ${\displaystyle \gamma \,}$ ${\displaystyle \left\{f(\cdot ;{\boldsymbol {\theta }})\right\}}$ ${\displaystyle \mu _{t}\,}$ ${\displaystyle \sigma _{t}^{2}}$ ${\displaystyle {\boldsymbol {\theta }}=(\mu ,\sigma ^{2})}$ ${\displaystyle \gamma \,}$ ${\displaystyle {\boldsymbol {\theta }}}$ ${\displaystyle D_{\mathrm {KL} }({\textrm {I}}_{\{S(x)\geq \gamma \}}\|f_{\boldsymbol {\theta }})}$ ${\displaystyle \geq \gamma }$

Pseudocódigo

// Inicializar parámetrosμ := −6σ2 := 100t:= 0maximos := 100Número := 100No := 10// Mientras que maxits no se excedan y no converjan mientras t < maxits y σ2 > ε sí  // Obtener N muestras de la distribución de muestreo actual X := MuestraGaussiana(μ, σ2, N) // Evaluar la función objetivo en los puntos muestreados S := exp(−(X − 2) ^ 2) + 0,8 exp(−(X + 2) ^ 2) // Ordenar X por valores de la función objetivo en orden descendente X := ordenar(X, S) // Actualizar los parámetros de distribución de muestreo a través de muestras de élite  μ := media(X(1:Ne)) σ2 := var(X(1:Ne)) t := t + 1// Devuelve la media de la distribución de muestreo final como solución de retorno μ

Métodos relacionados

• Recocido simulado
• Algoritmos genéticos
• Búsqueda de armonía
• Algoritmo de estimación de distribución
• Búsqueda tabú
• Estrategia de evolución natural
• Algoritmos de optimización de colonias de hormigas

Véase también

• Entropía cruzada
• Divergencia de Kullback-Leibler
• Algoritmo aleatorio
• Muestreo de importancia

Artículos de revistas

• De Boer, P.-T., Kroese, DP, Mannor, S. y Rubinstein, RY (2005). Un tutorial sobre el método de entropía cruzada. Annals of Operations Research , 134 (1), 19–67.[1]
• Rubinstein, RY (1997). Optimización de modelos de simulación por computadora con eventos raros, European Journal of Operational Research , 99 , 89–112.

Implementaciones de software

• Paquete CEoptim R
• Biblioteca .NET de Novacta.Analytics

Referencias

1. Rubinstein, RY y Kroese, DP (2004), El método de entropía cruzada: un enfoque unificado para la optimización combinatoria, la simulación de Montecarlo y el aprendizaje automático, Springer-Verlag, Nueva York ISBN  978-0-387-21240-1 .