Méthode de l'entropie croisée

Considérons le problème général d'estimation de la quantité ${\displaystyle \ell =\mathbb {E} _{\mathbf {u} }[H(\mathbf {X} )]=\int H(\mathbf {x} )\,f(\mathbf {x}$ ;\mathbf {u} )\,{\textrm {d}}\mathbf {x} } , où ${\displaystyle H}$ est une fonction objectif et ${\displaystyle f(\mathbf {x}$ ;\mathbf {u} )} est une densité de probabilité paramétrique. En utilisant l'échantillonnage préférentiel cette quantité peut être estimée par ${\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})}}}$, où ${\displaystyle \mathbf {X} _{1},\dots ,\mathbf {X} _{N}}$ est un échantillon de variables aléatoires de densité ${\displaystyle g\,}$. Pour ${\displaystyle H}$ positif, l'optimum théorique de la densité de probabilité des variables aléatoires est donné par ${\displaystyle g^{*}(\mathbf {x} )=H(\mathbf {x} )f(\mathbf {x}$ ;\mathbf {u} )/\ell } . Cependant ${\displaystyle \ell }$ est un paramètre inconnu. La méthode CE propose d'approcher la densité optimale en sélectionnant les éléments de l'échantillon qui sont les plus proches (au sens de Kullback-Leibler) de la densité optimale ${\displaystyle g^{*}}$.

1. Choisir un vecteur des paramètres initial ${\displaystyle \mathbf {v} ^{(0)}}$; poser ${\displaystyle t=1}$.
2. Créer un échantillon de variables aléatoires ${\displaystyle \mathbf {X} _{1},\dots ,\mathbf {X} _{N}}$ selon la densité ${\displaystyle f(\cdot$ ;\mathbf {v} ^{(t-1)})}
3. Calculer ${\displaystyle \mathbf {v} ^{(t)}}$, où
   ${\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 l'algorithme a convergé alors stopper; sinon, incrémenter ${\displaystyle t}$ de 1 recommencer à l'étape 2.

Dans certains cas, la solution de l'étape 3 peut être trouvée analytiquement. Les situations où cela se produit sont

• Quand ${\displaystyle f\,}$ fait partie des fonctions de la famille exponentielle naturelle
• Quand ${\displaystyle f\,}$ est discrète avec un support fini
• Quand ${\displaystyle H(\mathbf {X} )=\mathrm {I} _{\{\mathbf {x} \in A\}}}$ et ${\displaystyle f(\mathbf {X} _{i};\mathbf {u} )=f(\mathbf {X} _{i};\mathbf {v} ^{(t-1)})}$, alors ${\displaystyle \mathbf {v} ^{(t)}}$ correspond à l'estimateur du maximum de vraisemblance basé sur les ${\displaystyle \mathbf {X} _{k}\in A}$.

Le même algorithme CE peut être utilisé pour l'optimisation et l'estimation. Soit le problème consistant à maximiser une fonction ${\displaystyle S(x)}$, par exemple, ${\displaystyle S(x)={\textrm {e}}^{-(x-2)^{2}}+0.8\,{\textrm {e}}^{-(x+2)^{2}}}$. Pour utiliser l'entropie croisée on doit d'abord considérer le problème stochastique associé de l'estimation de ${\displaystyle \mathbb {P} _{\boldsymbol {\theta }}(S(X)\geq \gamma )}$ pour un niveau donné ${\displaystyle \gamma \,}$, et une famille de distributions de probabilité paramètriques ${\displaystyle \left\{f(\cdot$ ;{\boldsymbol {\theta }})\right\}} , par exemple la loi normale à une dimension, dont les paramètres sont la moyenne ${\displaystyle \mu _{t}\,}$ et la variance ${\displaystyle \sigma _{t}^{2}}$ (tel que ${\displaystyle {\boldsymbol {\theta }}=(\mu ,\sigma ^{2})}$ ici). Ainsi, pour un ${\displaystyle \gamma \,}$ donné, l'objectif est de déterminer ${\displaystyle {\boldsymbol {\theta }}}$ tel que la quantité ${\displaystyle D_{\mathrm {KL} }({\textrm {I}}_{\{S(x)\geq \gamma \}}\|f_{\boldsymbol {\theta }})}$ soit minimisée. Ce qui est fait en utilisant la version échantillonnée (contrepartie stochastique) du problème de la minimisation de la divergence KL, comme précédemment dans l'étape 3. Il se trouve que pour ce choix de distribution les paramètres qui minimisent la version stochastique du problème sont la moyenne et la variance empirique de l'échantillon d'élite qui est composé des tirages dont la valeur de la fonction score est ${\displaystyle \geq \gamma }$. Le plus mauvais des éléments de l'échantillon d'élite sert de paramètre de niveau à l'itération suivante. Cela donne l'algorithme stochastique suivant pour ce problème.

1. mu:=-6; sigma2:=100; t:=0; maxits=100;    // Initialisation des paramètres
2. N:=100; Ne:=10;                           //
3. while t < maxits and sigma2 > epsilon     // Tant que l'on n'a pas convergé et que maxits n'est pas dépassé
4.  X = SampleGaussian(mu, sigma2,N);         // Crée N échantillon à partir de la distribution
5.  S = exp(-(X-2)^2) + 0.8 exp(-(X+2)^2);   // Calcule le score de chaque échantillon
6.  X = sort(X, S);                           // Classe X selon le score (de façon descendante)
7.  mu = mean(X(1:Ne)); sigma2=var(X(1:Ne)); // Mise à jour des paramètres de la distribution
8.  t = t+1;                                 // Incrémentation du nombre d'itérations
9. return mu                                 // Renvoie la moyenne des derniers échantillons comme la solution

• Recuit simulé
• Algorithme génétique
• Algorithme à estimation de distribution
• Recherche tabou

• Entropie croisée
• divergence de Kullback-Leibler
• algorithme probabiliste
• Importance sampling

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Cross-entropy method » (voir la liste des auteurs).
• De Boer, P-T., Kroese, D.P, Mannor, S. and Rubinstein, R.Y. (2005). A Tutorial on the Cross-Entropy Method. Annals of Operations Research, 134 (1), 19—67.
• Rubinstein, R.Y. (1997). Optimization of Computer simulation Models with Rare Events, European Journal of Operations Research, 99, 89-112.
• Rubinstein, R.Y., Kroese, D.P. (2004). The Cross-Entropy Method: A Unified Approach to Combinatorial Optimization, Monte-Carlo Simulation, and Machine Learning, Springer-Verlag, New York.

• Page d'accueil de la méthode CE