Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Méthode de l'entropie croisée
Résumé
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, et d'échantillonnage préférentiel.
La méthode a été conçue à l'origine pour la simulation d'événements rares, où des densités de probabilité très faibles doivent être estimées correctement, par exemple dans l'analyse de la sécurité des réseaux, les modèles de , 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, l'optimisation quadratique, le problème d'alignement de séquences d'ADN, 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 :
Créer aléatoirement un échantillon de données (trajectoires, vecteurs, etc.) selon un mécanisme spécifique.
Mettre à jour les paramètres du mécanisme de création 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.
Considérons le problème général d'estimation de la quantité , où est une fonction objectif et est une densité de probabilité paramétrique. En utilisant l'échantillonnage préférentiel cette quantité peut être estimée par , où est un échantillon de variables aléatoires de densité . Pour positif, l'optimum théorique de la densité de probabilité des variables aléatoires est donné par
Cependant 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 .
Choisir un vecteur des paramètres initial ; poser .
Créer un échantillon de variables aléatoires selon la densité
Calculer , où
Si l'algorithme a convergé alors stopper; sinon, incrémenter de 1 recommencer à l'étape 2.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.