O método da entropia cruzada (CEM, do inglês cross-entropy method) é uma técnica de Monte Carlo de propósito geral para resolver problemas difíceis de otimização e estimação de eventos raros. Foi introduzido por Reuven Rubinstein em 1997 como um método para estimar probabilidades de eventos raros e logo foi estendido para otimização combinatória e contínua. O método gera iterativamente amostras aleatórias a partir de uma distribuição de probabilidade parametrizada, avalia-as e atualiza os parâmetros da distribuição para concentrar-se nas amostras de melhor desempenho, conhecidas como conjunto de elite. Essa abordagem é particularmente eficaz para problemas em que a função objetivo é ruidosa, não diferenciável ou possui muitos ótimos locais.
A ideia central do CEM é minimizar a entropia cruzada entre a distribuição de amostragem e uma distribuição ideal que coloca toda a massa de probabilidade na solução ótima. Na prática, isso é alcançado repetindo-se dois passos: amostrar a partir da distribuição atual e atualizar a distribuição usando a estimativa de máxima verossimilhança das amostras de elite. O método é simples de implementar, requer poucos hiperparâmetros e frequentemente converge rapidamente, tornando-o uma escolha popular em áreas como aprendizado por reforço, robótica e pesquisa operacional.
Estrutura Algorítmica
O método da entropia cruzada opera em um loop iterativo. Inicialmente, uma distribuição de probabilidade (frequentemente uma Gaussiana multivariada ou uma distribuição categórica) é definida sobre o espaço de soluções. Em cada iteração, um lote de soluções candidatas é extraído dessa distribuição. Cada candidato é avaliado usando uma função de pontuação, e a fração de melhor desempenho (tipicamente de 10% a 20%) é selecionada como o conjunto de elite. Os parâmetros da distribuição são então atualizados para ajustar-se a essas amostras de elite, geralmente calculando a média e a variância amostrais para distribuições Gaussianas ou as frequências empíricas para distribuições categóricas.
Para evitar convergência prematura, um parâmetro de suavização é frequentemente introduzido, mesclando os novos parâmetros com os anteriores. Essa suavização ajuda a manter a exploração e evita ficar preso em ótimos locais. O processo se repete até que um critério de parada seja atendido, como um número máximo de iterações ou uma mudança desprezível na melhor pontuação.
Aplicações em Aprendizado de Máquina
Em Machine learning, o CEM tem sido usado para otimização de hiperparâmetros, busca de arquitetura neural e treinamento de políticas em contextos de Reinforcement learning. Por exemplo, em Deep learning, o CEM pode otimizar os pesos de uma pequena Neural network sem retropropagação, o que é útil quando gradientes não estão disponíveis ou são caros. Também foi aplicado ao ajuste fino de Large language model para otimização discreta de prompts, onde o espaço de busca é combinatório.
Na pesquisa em Artificial intelligence, o CEM é frequentemente comparado com estratégias evolutivas e Stochastic Gradient Descent Variants. Diferentemente de métodos baseados em gradiente, o CEM não exige que o objetivo seja diferenciável, tornando-o adequado para otimização de caixa-preta. Tem sido usado em Robotics para otimização de trajetórias e em sistemas de direção autônoma para ajuste de parâmetros.
Relação com a Estimação de Eventos Raros
A motivação original do CEM era estimar a probabilidade de eventos raros, como falhas de sistemas ou perdas financeiras extremas. Nesse contexto, o método usa amostragem por importância para reduzir a variância. O algoritmo constrói adaptativamente uma distribuição de amostragem que enfatiza a região de interesse, permitindo estimativas precisas com muito menos amostras do que a Monte Carlo ingênua. Esse uso duplo - otimização e estimação - decorre da mesma base matemática: minimizar a divergência de Kullback-Leibler entre a distribuição de amostragem e uma distribuição ótima de amostragem por importância.
Extensões e Variantes
Várias extensões do CEM foram desenvolvidas. A versão contínua usa distribuições Gaussianas ou misturas de Gaussianas, enquanto a versão discreta lida com problemas combinatórios, como o problema do caixeiro viajante. Uma variante notável é o método da entropia cruzada melhorado, que incorpora uma memória de amostras de elite passadas para estabilizar as atualizações. Outra extensão é o uso do CEM em aprendizado por reforço baseado em modelo, onde ele planeja ações otimizando uma sequência sobre um modelo de mundo aprendido. Essa abordagem foi popularizada em algoritmos recentes de Deep Reinforcement Learning, como o framework Model-Based Policy Optimization (MBPO).
O CEM também foi combinado com Curriculum Learning, onde a dificuldade das amostras é gradualmente aumentada, e com Data Augmentation para otimização robusta. Em Bayesian Optimization, o CEM pode servir como um otimizador de função de aquisição.
Considerações Práticas
Ao aplicar o CEM, a escolha da família de distribuições e da fração de elite é crítica. Uma fração de elite muito pequena pode levar à convergência prematura, enquanto uma muito grande retarda o progresso. O parâmetro de suavização, frequentemente definido entre 0,5 e 0,9, equilibra exploração e explotação. Para problemas de alta dimensão, o número de amostras por iteração deve escalar adequadamente, o que pode se tornar computacionalmente caro. Apesar desses desafios, a simplicidade e a robustez do CEM o tornaram um item essencial na caixa de ferramentas de otimização.
Na prática, o CEM é frequentemente usado como linha de base em artigos de pesquisa, e seu desempenho é comparável ao de métodos mais complexos, como Bayesian Optimization, em muitos problemas de referência. Ele está implementado em várias bibliotecas de código aberto, incluindo o pacote cma para Python, embora o CEM clássico seja distinto do CMA-ES (Estratégia de Evolução com Adaptação da Matriz de Covariância), que é um algoritmo relacionado, porém separado.
Ver Também
- evolutionary-algorithm
- monte-carlo-method
- Reinforcement learning
- black-box-optimization