Mètode d'entropia creuada

El mètode d'entropia creuada ( CE ) és un mètode de Montecarlo per al mostreig d'importància i l'optimització. És aplicable tant a problemes combinatoris com continus, amb un objectiu estàtic o sorollós.

El mètode aproxima l'estimador de mostreig d'importància òptima repetint dues fases:

1. Treu una mostra d'una distribució de probabilitat.
2. Minimitzar l'entropia creuada entre aquesta distribució i una distribució objectiu per produir una millor mostra en la següent iteració.

Reuven Rubinstein va desenvolupar el mètode en el context de la simulació d'esdeveniments rars, on s'han d'estimar probabilitats minúscules, per exemple en l'anàlisi de la fiabilitat de la xarxa, els models de cua o l'anàlisi del rendiment dels sistemes de telecomunicacions. El mètode també s'ha aplicat als problemes del venedor ambulant, l'assignació quadràtica, l'alineació de la seqüència d'ADN, el tall màxim i l'assignació del buffer.

Estimació mitjançant mostreig d'importància

Considereu el problema general d'estimar la quantitat

on $H$ és alguna funció de rendiment i $f(𝐱;𝐮)$ és un membre d'alguna família paramètrica de distribucions. Utilitzant el mostreig d'importància aquesta quantitat es pot estimar com

$\hat{\ell }=\frac{1}{N}\sum _{i=1}^{N}H({𝐗}_i)\frac{f({𝐗}_i;𝐮)}{g({𝐗}_i)}$

on ${𝐗}_1,\dots ,{𝐗}_N$ és una mostra aleatòria de $g$. Per positiu $H$, la densitat de mostreig d'importància teòricament òptima (PDF) ve donada per

$g^{*}(𝐱)=H(𝐱)f(𝐱;𝐮)/\ell$

Això, però, depèn de la desconeguda $\ell$. El mètode CE té com a objectiu aproximar el PDF òptim seleccionant de manera adaptativa els membres de la família paramètrica més propers (en el sentit de Kullback-Leibler ) al PDF òptim. $g^{*}$.

Algorisme genèric CE

1. Trieu el vector del paràmetre inicial ${𝐯}^{(0)}$ ; establir t = 1.
2. Generar una mostra aleatòria ${𝐗}_1,\dots ,{𝐗}_N$ des de $f(\cdot ;{𝐯}^{(t-1)})$
3. Resol per ${𝐯}^{(t)}$, on

${𝐯}^{(t)}={\text{argmax}}_{𝐯}\frac{1}{N}\sum _{i=1}^{N}H({𝐗}_i)\frac{f({𝐗}_i;𝐮)}{f({𝐗}_i;{𝐯}^{(t-1)})}\log f({𝐗}_i;𝐯)$

4. Si s'aconsegueix la convergència, atureu-vos ; en cas contrari, augmenta t en 1 i repeteix des del pas 2.

En diversos casos, la solució al pas 3 es pot trobar analíticament. Les situacions en què això passa són

• Quan $f$ pertany a la família exponencial natural
• Quan $f$ és discret amb suport finit
• Quan $H(𝐗)={\mathrm{I}}_{\{𝐱\in A\}}$ i $f({𝐗}_i;𝐮)=f({𝐗}_i;{𝐯}^{(t-1)})$, doncs ${𝐯}^{(t)}$ correspon a l'estimador de màxima versemblança basat en aquests ${𝐗}_k\in A$.

Optimització contínua — exemple

El mateix algorisme CE es pot utilitzar per a l'optimització, en lloc d'estimar. Suposem que el problema és maximitzar alguna funció $S$, per exemple, $S(x)={\text{e}}^{-(x-2{)}^2}+0.8{\text{e}}^{-(x+2{)}^2}$. Per aplicar CE, primer es considera el problema estocàstic associat de l'estimació ${\mathbb{P}}_{\mathit{\theta }}(S(X)\ge \gamma )$ per a un nivell determinat $\gamma$, i família paramètrica $\{f(\cdot ;\mathit{\theta })\}$, per exemple la distribució gaussiana unidimensional, parametritzada per la seva mitjana ${\mu }_t$ i la variància ${\sigma }_t^2$ (així $\mathit{\theta }=(\mu ,{\sigma }^2)$ aquí). Per tant, per un fet $\gamma$, l'objectiu és trobar $\mathit{\theta }$ de manera que $D_{\mathrm{K}\mathrm{L}}({\text{I}}_{\{S(x)\ge \gamma \}}\Vert f_{\mathit{\theta }})$ es minimitza. Això es fa resolent la versió de mostra (contrapart estocàstica) del problema de minimització de la divergència KL, com al pas 3 anterior. Resulta que els paràmetres que minimitzen la contrapartida estocàstica per a aquesta elecció de distribució objectiu i família paramètrica són la mitjana mostral i la variància mostral corresponents a les mostres d'elit, que són aquelles mostres que tenen valor de funció objectiu. $\ge \gamma$. La pitjor de les mostres d'elit s'utilitza com a paràmetre de nivell per a la següent iteració. Això produeix el següent algorisme aleatoritzat que coincideix amb l'anomenat Estimation of Multivariate Normal Algorithm (EMNA), un algorisme d'estimació de distribució.