Método de entropía cruzada

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

El método aproxima el estimador de muestreo de importancia óptimo 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 siguiente iteración.

Reuven Rubinstein desarrolló el método en el contexto de la simulación de eventos raros , donde se deben estimar probabilidades muy pequeñas, 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 al problema del viajante , la asignación cuadrática , la alineación de secuencias de ADN , el corte máximo y los problemas de asignación de búferes.

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} } ,

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

${\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})}}}$,

dónde${\displaystyle \mathbf {X} _{1},\dots ,\mathbf {X} _{N}}$es una muestra aleatoria de${\displaystyle g\,}$. Para positivo${\displaystyle H}$, la densidad de muestreo de importancia (PDF) teóricamente óptima viene dada por

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

Sin embargo, esto depende de lo desconocido.${\displaystyle \ell }$El método CE tiene como objetivo aproximar la función de densidad de probabilidad óptima seleccionando de forma adaptativa a los miembros de la familia paramétrica que estén más cerca (en el sentido de Kullback-Leibler ) de la función de densidad de probabilidad óptima .${\displaystyle g^{*}}$.

1. Elija el vector de parámetros inicial.${\displaystyle \mathbf {v} ^{(0)}}$; establecer t = 1.
2. Generar una muestra aleatoria${\displaystyle \mathbf {X} _{1},\dots ,\mathbf {X} _{N}}$de${\displaystyle f(\cdot$ ;\mathbf {v} ^{(t-1)})}
3. Resuelve para${\displaystyle \mathbf {v} ^{(t)}}$, dónde${\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 al paso 3 se puede encontrar analíticamente . Las situaciones en las que esto ocurre son:

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

El mismo algoritmo CE se puede utilizar para optimización, en lugar de estimación. Supongamos que el problema es maximizar alguna función.${\displaystyle S}$, Por ejemplo, ${\displaystyle S(x)={\textrm {e}}^{-(x-2)^{2}}+0.8\,{\textrm {e}}^{-(x+2)^{2}}}$Para aplicar CE, primero se considera el problema estocástico asociado de estimación ${\displaystyle \mathbb {P} _{\boldsymbol {\theta }}(S(X)\geq \gamma )}$ para un nivel determinado${\displaystyle \gamma \,}$y familia paramétrica${\displaystyle \left\{f(\cdot$ ;{\boldsymbol {\theta }})\right\}} , por ejemplo la distribución gaussiana unidimensional , parametrizada por su media${\displaystyle \mu _{t}\,}$y varianza${\displaystyle \sigma _{t}^{2}}$(entonces${\displaystyle {\boldsymbol {\theta }}=(\mu ,\sigma ^{2})}$aquí). Por lo tanto, para un dado${\displaystyle \gamma \,}$, el objetivo es encontrar${\displaystyle {\boldsymbol {\theta }}}$de modo que ${\displaystyle D_{\mathrm {KL} }({\textrm {I}}_{\{S(x)\geq \gamma \}}\|f_{\boldsymbol {\theta }})}$ se minimiza. Esto se hace resolviendo la versión de muestra (contraparte estocástica) del problema de minimización de la 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 valor de la función objetivo${\displaystyle \geq \gamma }$. 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 de Distribución Normal Multivariada (EMNA), un algoritmo de estimación de distribución .

// Inicializar parámetros μ := −6 ​​σ 2 := 100 t := 0 máximos := 100 N := 100 Ne := 10 // Mientras maxits no se exceda y no haya convergencia mientras t < maxits y σ 2 > ε hacer // Obtener N muestras de la distribución de muestreo actual X := SampleGaussian( μ , σ 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 := sort(X, S) // Actualizar los parámetros de la distribución de muestreo a través de muestras de élite μ := media(X(1:Ne)) σ 2 := varianza(X(1:Ne)) t := t + 1 // Devuelve la media de la distribución de muestreo final como solución return μ

• 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 por colonia de hormigas

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

• 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.
• Rubinstein, RY (1997). Optimización de modelos de simulación por computadora con eventos raros, European Journal of Operational Research , 99 , 89–112.

• Paquete CEopt para Matlab
• Paquete CEoptim R
• Biblioteca Novacta.Analytics para .NET