Méthode de l'entropie croisée

La méthode de l'entropie-croisée (CE) attribuée à Reuven Rubinstein est une méthode générale d'optimisation de type Monte-Carlo, combinatoire ou continue. La méthode a été conçue à l'origine pour la simulation d'événements rares, où des densités de probabilités très faibles doivent être estimées correctement, par exemple dans l'analyse de la sécurité des réseaux, les modèles de file d'attente, ou l'analyse des performances des systèmes de télécommunication. La méthode CE peut être appliquée à tout problème d'optimisation combinatoire où les observations sont bruitées comme le problème du voyageur de commerce, le problème d'affectation quadratique, le problème d'alignement de séquences, le problème de la coupure maximale et les problèmes d'allocation de mémoire, tout comme des problèmes d'optimisation continue avec de nombreux extrema locaux.

La méthode CE se décompose en deux phases :

1. Générer aléatoirement un échantillon de données (trajectoires, vecteurs, etc.) selon un mécanisme spécifique.
2. Mettre à jour les paramètres du mécanisme de génération aléatoire à partir de l'échantillon de données pour produire un meilleur échantillon à l'itération suivante. Cette étape implique de minimiser l'entropie croisée ou la divergence de Kullback-Leibler.

Estimation via l'échantillonnage préférentiel

Considérons le problème général d'estimation de la quantité $\ell = \mathbb{E}_{\mathbf{u}}[H(\mathbf{X})] = \int H(\mathbf{x})\, f(\mathbf{x}; \mathbf{u})\, \textrm{d}\mathbf{x}$, où H est une fonction objectif et $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 $\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ù $\mathbf{X}_1,\dots,\mathbf{X}_N$ est un échantillon de variables aléatoires de densité $g\,$. Pour H positif, l'optimum théorique de la densité de probabilité des variables aléatoires est donné par $g^*(\mathbf{x}) = H(\mathbf{x}) f(\mathbf{x};\mathbf{u})/\ell$. Cependant $\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 g ^* .

Algorithme CE générique

1. Choisir un vecteur des paramètres initial $\mathbf{v}^{(0)}$; poser t = 1.
2. Générer un échantillon de variables aléatoires $\mathbf{X}_1,\dots,\mathbf{X}_N$ selon la densité $f(\cdot;\mathbf{v}^{(t-1)})$
3. Calculer $\mathbf{v}^{(t)}$, où
   $\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 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 $f\,$ fait partie des fonctions de la famille exponentielle naturelle
• Quand $f\,$ est discrète avec un support fini
• Quand $H(\mathbf{X}) = \mathrm{I}_{\{\mathbf{x}\in A\}}$ et $f(\mathbf{X}_i;\mathbf{u}) = f(\mathbf{X}_i;\mathbf{v}^{(t-1)})$, alors $\mathbf{v}^{(t)}$ correspond à l'estimateur du maximum de vraisemblance basé sur les $\mathbf{X}_k \in A$.

Optimisation continue—exemple

Le même algorithme CE peut être utilisé pour l'optimisation et l'estimation. Soit le problème consistant à maximiser une fonction S(x), par exemple, $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 $\mathbb{P}_{\boldsymbol{\theta}}(S(X)\geq\gamma)$ pour un niveau donné $\gamma\,$, et une famille de distributions de probabilité paramètriques $\left\{f(\cdot;\boldsymbol{\theta})\right\}$, par exemple la loi normale à une dimension, dont les parmètres sont la moyenne $\mu_t\,$ et la variance $\sigma_t^2$ (tel que $\boldsymbol{\theta} = (\mu,\sigma^2)$ ici). Ainsi, pour un $\gamma\,$ donné, l'objectif est de déterminer $\boldsymbol{\theta}$ tel que la quantité $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 $\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.

Pseudo-code

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);         // Génère 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 parmè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

Méthodes liées

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

Voir aussi

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

Références

• (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.

Liens externes

• Page d'accueil de la méthode CE