El método de entropía cruzada (CEM) es una técnica general de Monte Carlo para resolver problemas difíciles de optimización y estimación de eventos raros. Fue introducido por Reuven Rubinstein en 1997 como un método para estimar probabilidades de eventos raros, y pronto se extendió a la optimización combinatoria y continua. El método genera iterativamente muestras aleatorias a partir de una distribución de probabilidad parametrizada, las evalúa y actualiza los parámetros de la distribución para concentrarse en las mejores muestras, conocidas como el conjunto de élite. Este enfoque es particularmente eficaz para problemas donde la función objetivo es ruidosa, no diferenciable o tiene muchos óptimos locales.
La idea central del CEM es minimizar la entropía cruzada entre la distribución de muestreo y una distribución ideal que coloca toda la masa de probabilidad en la solución óptima. En la práctica, esto se logra repitiendo dos pasos: muestrear de la distribución actual y actualizar la distribución utilizando la estimación de máxima verosimilitud de las muestras de élite. El método es simple de implementar, requiere pocos hiperparámetros y a menudo converge rápidamente, lo que lo convierte en una opción popular en campos como el aprendizaje por refuerzo, la robótica y la investigación de operaciones.
Marco Algorítmico
El método de entropía cruzada opera en un bucle iterativo. Inicialmente, se define una distribución de probabilidad (a menudo una gaussiana multivariada o una distribución categórica) sobre el espacio de soluciones. En cada iteración, se extrae un lote de soluciones candidatas de esta distribución. Cada candidato se evalúa utilizando una función de puntuación, y la fracción de mejor rendimiento (típicamente del 10% al 20%) se selecciona como el conjunto de élite. Los parámetros de la distribución se actualizan entonces para ajustarse a estas muestras de élite, típicamente calculando la media y la varianza muestral para distribuciones gaussianas o las frecuencias empíricas para distribuciones categóricas.
Para prevenir la convergencia prematura, a menudo se introduce un parámetro de suavizado, que combina los nuevos parámetros con los anteriores. Este suavizado ayuda a mantener la exploración y evita quedarse atrapado en óptimos locales. El proceso se repite hasta que se cumple un criterio de parada, como un número máximo de iteraciones o un cambio insignificante en la mejor puntuación.
Aplicaciones en Aprendizaje Automático
En Machine learning, el CEM se ha utilizado para la optimización de hiperparámetros, la búsqueda de arquitecturas neuronales y el entrenamiento de políticas en contextos de Reinforcement learning. Por ejemplo, en Deep learning, el CEM puede optimizar los pesos de una pequeña Neural network sin retropropagación, lo que es útil cuando los gradientes no están disponibles o son costosos. También se ha aplicado al ajuste fino de Large language model para la optimización discreta de indicaciones, donde el espacio de búsqueda es combinatorio.
En la investigación de Artificial intelligence, el CEM se compara a menudo con estrategias evolutivas y Stochastic Gradient Descent Variants. A diferencia de los métodos basados en gradientes, el CEM no requiere que el objetivo sea diferenciable, lo que lo hace adecuado para la optimización de caja negra. Se ha utilizado en Robotics para la optimización de trayectorias y en sistemas de conducción autónoma para el ajuste de parámetros.
Relación con la Estimación de Eventos Raros
La motivación original del CEM era estimar la probabilidad de eventos raros, como fallos de sistemas o pérdidas financieras extremas. En este contexto, el método utiliza el muestreo por importancia para reducir la varianza. El algoritmo construye adaptativamente una distribución de muestreo que enfatiza la región de interés, permitiendo estimaciones precisas con muchas menos muestras que el Monte Carlo ingenuo. Este doble uso - optimización y estimación - proviene de la misma base matemática: minimizar la divergencia de Kullback-Leibler entre la distribución de muestreo y una distribución de muestreo por importancia óptima.
Extensiones y Variantes
Se han desarrollado varias extensiones del CEM. La versión continua utiliza distribuciones gaussianas o mezclas de gaussianas, mientras que la versión discreta maneja problemas combinatorios como el problema del viajante. Una variante notable es el método de entropía cruzada mejorado, que incorpora una memoria de muestras de élite pasadas para estabilizar las actualizaciones. Otra extensión es el uso del CEM en el aprendizaje por refuerzo basado en modelos, donde planifica acciones optimizando una secuencia sobre un modelo del mundo aprendido. Este enfoque se ha popularizado en algoritmos recientes de Deep Reinforcement Learning, como el marco de Optimización de Políticas Basada en Modelos (MBPO).
El CEM también se ha combinado con Curriculum Learning, donde la dificultad de las muestras se aumenta gradualmente, y con Data Augmentation para la optimización robusta. En Bayesian Optimization, el CEM puede servir como optimizador de funciones de adquisición.
Consideraciones Prácticas
Al aplicar el CEM, la elección de la familia de distribuciones y la fracción de élite son críticas. Una fracción de élite demasiado pequeña puede llevar a una convergencia prematura, mientras que una demasiado grande ralentiza el progreso. El parámetro de suavizado, a menudo establecido entre 0.5 y 0.9, equilibra la exploración y la explotación. Para problemas de alta dimensión, el número de muestras por iteración debe escalarse en consecuencia, lo que puede volverse computacionalmente costoso. A pesar de estos desafíos, la simplicidad y robustez del CEM lo han convertido en un elemento básico en la caja de herramientas de optimización.
En la práctica, el CEM se utiliza a menudo como línea base en artículos de investigación, y su rendimiento es comparable al de métodos más complejos como Bayesian Optimization en muchos problemas de referencia. Está implementado en varias bibliotecas de código abierto, incluido el paquete cma para Python, aunque el CEM clásico es distinto de CMA-ES (Estrategia de Evolución con Adaptación de la Matriz de Covarianza), que es un algoritmo relacionado pero separado.
Véase También
- evolutionary-algorithm
- monte-carlo-method
- Reinforcement learning
- black-box-optimization