La méthode de l'entropie croisée (CEM) est une technique de Monte Carlo à usage général pour résoudre des problèmes difficiles d'optimisation et d'estimation d'événements rares. Elle a été introduite par Reuven Rubinstein en 1997 comme méthode pour estimer les probabilités d'événements rares, et a rapidement été étendue à l'optimisation combinatoire et continue. La méthode génère itérativement des échantillons aléatoires à partir d'une distribution de probabilité paramétrée, les évalue, et met à jour les paramètres de la distribution pour se concentrer sur les meilleurs échantillons, appelés l'ensemble d'élite. Cette approche est particulièrement efficace pour les problèmes où la fonction objectif est bruitée, non différentiable, ou présente de nombreux optima locaux.
L'idée centrale de CEM est de minimiser l'entropie croisée entre la distribution d'échantillonnage et une distribution idéale qui place toute la masse de probabilité sur la solution optimale. En pratique, cela est réalisé en répétant deux étapes : l'échantillonnage à partir de la distribution courante, et la mise à jour de la distribution en utilisant l'estimation du maximum de vraisemblance des échantillons d'élite. La méthode est simple à implémenter, nécessite peu d'hyperparamètres, et converge souvent rapidement, ce qui en fait un choix populaire dans des domaines tels que l'apprentissage par renforcement, la robotique et la recherche opérationnelle.
Cadre algorithmique
La méthode de l'entropie croisée fonctionne dans une boucle itérative. Initialement, une distribution de probabilité (souvent une gaussienne multivariée ou une distribution catégorielle) est définie sur l'espace des solutions. À chaque itération, un lot de solutions candidates est tiré de cette distribution. Chaque candidate est évaluée à l'aide d'une fonction de score, et la fraction des meilleures performances (typiquement 10 % à 20 %) est sélectionnée comme ensemble d'élite. Les paramètres de la distribution sont ensuite mis à jour pour s'adapter à ces échantillons d'élite, généralement en calculant la moyenne et la variance de l'échantillon pour les distributions gaussiennes ou les fréquences empiriques pour les distributions catégorielles.
Pour éviter une convergence prématurée, un paramètre de lissage est souvent introduit, mélangeant les nouveaux paramètres avec les précédents. Ce lissage aide à maintenir l'exploration et évite de rester bloqué dans des optima locaux. Le processus se répète jusqu'à ce qu'un critère d'arrêt soit satisfait, comme un nombre maximal d'itérations ou un changement négligeable dans le meilleur score.
Applications en apprentissage automatique
Dans apprentissage automatique, CEM a été utilisé pour l'optimisation des hyperparamètres, la recherche d'architecture neuronale et l'entraînement de politiques dans des contextes de apprentissage par renforcement. Par exemple, dans apprentissage profond, CEM peut optimiser les poids d'un petit réseau de neurones sans rétropropagation, ce qui est utile lorsque les gradients sont indisponibles ou coûteux. Il a également été appliqué au réglage fin de grands modèles de langage pour l'optimisation discrète de prompts, où l'espace de recherche est combinatoire.
Dans la recherche en intelligence artificielle, CEM est souvent comparé aux stratégies évolutionnaires et aux variantes de SGD. Contrairement aux méthodes basées sur les gradients, CEM ne nécessite pas que l'objectif soit différentiable, ce qui le rend adapté à l'optimisation en boîte noire. Il a été utilisé dans robotique pour l'optimisation de trajectoires et dans les systèmes de conduite autonome pour le réglage des paramètres.
Relation avec l'estimation d'événements rares
La motivation originale de CEM était d'estimer la probabilité d'événements rares, tels que des défaillances de systèmes ou des pertes financières extrêmes. Dans ce contexte, la méthode utilise l'échantillonnage d'importance pour réduire la variance. L'algorithme construit de manière adaptative une distribution d'échantillonnage qui met l'accent sur la région d'intérêt, permettant des estimations précises avec beaucoup moins d'échantillons que le Monte Carlo naïf. Ce double usage - optimisation et estimation - découle de la même base mathématique : minimiser la divergence de Kullback-Leibler entre la distribution d'échantillonnage et une distribution d'échantillonnage d'importance optimale.
Extensions et variantes
Plusieurs extensions de CEM ont été développées. La version continue utilise des distributions gaussiennes ou des mélanges de gaussiennes, tandis que la version discrète traite des problèmes combinatoires comme le problème du voyageur de commerce. Une variante notable est la méthode de l'entropie croisée améliorée, qui incorpore une mémoire des échantillons d'élite passés pour stabiliser les mises à jour. Une autre extension est l'utilisation de CEM dans l'apprentissage par renforcement basé sur un modèle, où il planifie des actions en optimisant une séquence sur un modèle du monde appris. Cette approche a été popularisée dans des algorithmes récents de apprentissage par renforcement profond, comme le cadre Model-Based Policy Optimization (MBPO).
CEM a également été combiné avec apprentissage par curriculum, où la difficulté des échantillons est progressivement augmentée, et avec augmentation de données pour une optimisation robuste. Dans optimisation bayésienne, CEM peut servir d'optimiseur de fonction d'acquisition.
Considérations pratiques
Lors de l'application de CEM, le choix de la famille de distribution et de la fraction d'élite est critique. Une fraction d'élite trop petite peut conduire à une convergence prématurée, tandis qu'une trop grande ralentit la progression. Le paramètre de lissage, souvent réglé entre 0,5 et 0,9, équilibre l'exploration et l'exploitation. Pour les problèmes de haute dimension, le nombre d'échantillons par itération doit être adapté en conséquence, ce qui peut devenir coûteux en calcul. Malgré ces défis, la simplicité et la robustesse de CEM en ont fait un incontournable dans la boîte à outils d'optimisation.
En pratique, CEM est souvent utilisé comme référence dans les articles de recherche, et ses performances sont comparables à celles de méthodes plus complexes comme optimisation bayésienne sur de nombreux problèmes de référence. Il est implémenté dans plusieurs bibliothèques open-source, y compris le paquet cma pour Python, bien que le CEM classique soit distinct de CMA-ES (Covariance Matrix Adaptation Evolution Strategy), qui est un algorithme connexe mais séparé.
Voir aussi
- algorithme évolutionnaire
- méthode de Monte Carlo
- apprentissage par renforcement
- optimisation en boîte noire