Die Cross-Entropy-Methode (CEM) ist eine allgemeine Monte-Carlo-Technik zur Lösung schwieriger Optimierungs- und Seltenheitsereignis-Schätzprobleme. Sie wurde 1997 von Reuven Rubinstein als Methode zur Schätzung von Wahrscheinlichkeiten seltener Ereignisse eingeführt und bald auf kombinatorische und kontinuierliche Optimierung ausgeweitet. Die Methode erzeugt iterativ Zufallsstichproben aus einer parametrisierten Wahrscheinlichkeitsverteilung, bewertet diese und aktualisiert die Verteilungsparameter, um sich auf die am besten abschneidenden Stichproben zu konzentrieren, die als Elite-Menge bezeichnet werden. Dieser Ansatz ist besonders effektiv für Probleme, bei denen die Zielfunktion verrauscht, nicht differenzierbar ist oder viele lokale Optima aufweist.
Die Kernidee von CEM besteht darin, die Kreuzentropie zwischen der Stichprobenverteilung und einer idealen Verteilung zu minimieren, die die gesamte Wahrscheinlichkeitsmasse auf die optimale Lösung legt. In der Praxis wird dies erreicht, indem wiederholt zwei Schritte durchgeführt werden: Stichprobenziehung aus der aktuellen Verteilung und Aktualisierung der Verteilung mithilfe der Maximum-Likelihood-Schätzung der Elite-Stichproben. Die Methode ist einfach zu implementieren, erfordert wenige Hyperparameter und konvergiert oft schnell, was sie zu einer beliebten Wahl in Bereichen wie Verstärkungslernen, Robotik und Operations Research macht.
Algorithmischer Rahmen
Die Cross-Entropy-Methode arbeitet in einer iterativen Schleife. Zunächst wird eine Wahrscheinlichkeitsverteilung (häufig eine multivariate Gauß-Verteilung oder eine kategoriale Verteilung) über dem Lösungsraum definiert. Bei jeder Iteration wird eine Charge von Kandidatenlösungen aus dieser Verteilung gezogen. Jeder Kandidat wird mithilfe einer Bewertungsfunktion evaluiert, und der am besten abschneidende Anteil (typischerweise 10 % bis 20 %) wird als Elite-Menge ausgewählt. Die Verteilungsparameter werden dann aktualisiert, um diese Elite-Stichproben anzupassen, typischerweise durch Berechnung des Stichprobenmittelwerts und der Varianz für Gauß-Verteilungen oder der empirischen Häufigkeiten für kategoriale Verteilungen.
Um vorzeitige Konvergenz zu verhindern, wird häufig ein Glättungsparameter eingeführt, der die neuen Parameter mit den vorherigen vermischt. Diese Glättung hilft, die Exploration aufrechtzuerhalten und ein Feststecken in lokalen Optima zu vermeiden. Der Prozess wiederholt sich, bis ein Stoppkriterium erfüllt ist, wie eine maximale Anzahl von Iterationen oder eine vernachlässigbare Änderung der besten Punktzahl.
Anwendungen im maschinellen Lernen
Im maschinellen Lernen wurde CEM für Hyperparameter-Optimierung, neuronale Architektursuche und das Training von Richtlinien in Verstärkungslernkontexten verwendet. Beispielsweise kann CEM im tiefen Lernen die Gewichte eines kleinen neuronalen Netzes ohne Backpropagation optimieren, was nützlich ist, wenn Gradienten nicht verfügbar oder teuer sind. Es wurde auch auf die Feinabstimmung von großen Sprachmodellen für die diskrete Prompt-Optimierung angewendet, wo der Suchraum kombinatorisch ist.
In der Forschung zu künstlicher Intelligenz wird CEM oft mit evolutionären Strategien und SGD-Varianten verglichen. Im Gegensatz zu gradientenbasierten Methoden erfordert CEM keine Differenzierbarkeit der Zielfunktion, was es für Black-Box-Optimierung geeignet macht. Es wurde in der Robotik für Trajektorienoptimierung und in autonomen Fahrsystemen zur Parameterabstimmung verwendet.
Beziehung zur Schätzung seltener Ereignisse
Die ursprüngliche Motivation für CEM war die Schätzung der Wahrscheinlichkeit seltener Ereignisse, wie Systemausfälle oder extreme finanzielle Verluste. In diesem Kontext verwendet die Methode Importance Sampling zur Varianzreduktion. Der Algorithmus konstruiert adaptiv eine Stichprobenverteilung, die die interessierende Region betont, was genaue Schätzungen mit weit weniger Stichproben als naives Monte Carlo ermöglicht. Diese doppelte Verwendung - Optimierung und Schätzung - stammt aus derselben mathematischen Grundlage: der Minimierung der Kullback-Leibler-Divergenz zwischen der Stichprobenverteilung und einer optimalen Importance-Sampling-Verteilung.
Erweiterungen und Varianten
Mehrere Erweiterungen von CEM wurden entwickelt. Die kontinuierliche Version verwendet Gauß- oder Gauß-Mischungsverteilungen, während die diskrete Version kombinatorische Probleme wie das Problem des Handlungsreisenden behandelt. Eine bemerkenswerte Variante ist die verbesserte Cross-Entropy-Methode, die ein Gedächtnis früherer Elite-Stichproben einbezieht, um Aktualisierungen zu stabilisieren. Eine weitere Erweiterung ist die Verwendung von CEM im modellbasierten Verstärkungslernen, wo es Aktionen plant, indem es eine Sequenz über ein gelerntes Weltmodell optimiert. Dieser Ansatz wurde in jüngsten Deep-Reinforcement-Learning-Algorithmen populär gemacht, wie dem Model-Based Policy Optimization (MBPO)-Framework.
CEM wurde auch mit Curriculum-Lernen kombiniert, wo die Schwierigkeit der Stichproben schrittweise erhöht wird, und mit Datenaugmentierung für robuste Optimierung. In der Bayesschen Optimierung kann CEM als Optimierer für Akquisitionsfunktionen dienen.
Praktische Überlegungen
Bei der Anwendung von CEM sind die Wahl der Verteilungsfamilie und der Elite-Anteil entscheidend. Ein zu kleiner Elite-Anteil kann zu vorzeitiger Konvergenz führen, während ein zu großer den Fortschritt verlangsamt. Der Glättungsparameter, der oft zwischen 0,5 und 0,9 gesetzt wird, balanciert Exploration und Exploitation. Für hochdimensionale Probleme muss die Anzahl der Stichproben pro Iteration entsprechend skaliert werden, was rechenintensiv werden kann. Trotz dieser Herausforderungen haben die Einfachheit und Robustheit von CEM es zu einem festen Bestandteil des Optimierungswerkzeugsatzes gemacht.
In der Praxis wird CEM oft als Baseline in Forschungsarbeiten verwendet, und seine Leistung ist auf vielen Benchmark-Problemen mit komplexeren Methoden wie Bayesscher Optimierung vergleichbar. Es ist in mehreren Open-Source-Bibliotheken implementiert, einschließlich des cma-Pakets für Python, obwohl das klassische CEM sich von CMA-ES (Covariance Matrix Adaptation Evolution Strategy) unterscheidet, einem verwandten, aber separaten Algorithmus.
Siehe auch
- evolutionärer Algorithmus
- Monte-Carlo-Methode
- Verstärkungslernen
- Black-Box-Optimierung