Um guia visual para estratégias de evolução
Os modelos de redes neurais são altamente expressivos e flexíveis e, se conseguirmos encontrar um conjunto adequado de parâmetros de modelo, poderemos usar redes neurais para resolver muitos problemas desafiadores.
Sobrevivência do mais forte
O sucesso do aprendizado profundo vem em grande parte da capacidade de usar o algoritmo de retropropagação para calcular com eficiência o gradiente de uma função objetivo sobre cada parâmetro do modelo.
Com esses gradientes, podemos pesquisar com eficiência no espaço de parâmetros para encontrar uma solução que geralmente seja boa o suficiente para que nossa rede neural realize tarefas difíceis.
No entanto, existem muitos problemas onde o algoritmo de retropropagação não pode ser usado. Por exemplo, em problemas de aprendizagem por reforço (RL), também podemos treinar uma rede neural para tomar decisões para executar uma sequência de ações para realizar alguma tarefa em um ambiente.
No entanto, não é trivial estimar o gradiente de sinais de recompensa dados ao agente no futuro para uma ação executada pelo agente agora, especialmente se a recompensa for realizada em muitos intervalos de tempo no futuro. Mesmo que sejamos capazes de calcular gradientes precisos, há também o problema de ficarmos presos em um ótimo local, que existe em muitos casos para tarefas RL.
Toda uma área dentro da RL é dedicada ao estudo deste problema de atribuição de créditos, e grandes progressos foram feitos nos últimos anos. Contudo, a atribuição de crédito ainda é difícil quando os sinais de recompensa são escassos.
No mundo real, as recompensas podem ser escassas e barulhentas. Às vezes, recebemos apenas uma única recompensa, como um cheque de bônus no final do ano, e dependendo do nosso empregador, pode ser difícil descobrir exatamente por que é tão baixo.
Para estes problemas, em vez de confiar numa estimativa de gradiente do futuro muito barulhenta e possivelmente sem sentido para a nossa política, poderíamos simplesmente ignorar qualquer informação de gradiente e tentar usar técnicas de otimização de caixa preta, como algoritmos genéticos (AG) ou ES.
A OpenAI publicou um artigo chamado Evolution Strategies as a Scalable Alternative to Reinforcement Learning , onde mostrou que as estratégias de evolução, embora sejam menos eficientes em termos de dados do que RL, oferecem muitos benefícios.
A capacidade de abandonar o cálculo de gradiente permite que tais algoritmos sejam avaliados de forma mais eficiente. Também é fácil distribuir a computação de um algoritmo ES para milhares de máquinas para computação paralela. Ao executar o algoritmo do zero muitas vezes, eles também mostraram que as políticas descobertas usando ES tendem a ser mais diversas em comparação com as políticas descobertas pelos algoritmos RL.
Gostaria de salientar que mesmo para o problema de identificação de um modelo de aprendizado de máquina, como projetar a arquitetura de uma rede neural, é aquele em que não podemos calcular gradientes diretamente. Embora RL , Evolution , GA etc. possam ser aplicados para busca no espaço de arquiteturas de modelos, neste post focarei apenas na aplicação desses algoritmos para busca de parâmetros de um modelo pré-definido.
O que é uma estratégia de evolução?
A função Rastrigin bidimensional tem muitos ótimos locais (Fonte: Wikipedia ).
Os diagramas abaixo são gráficos de cima para baixo de funções 2D deslocadas de Schaffer e Rastrigin , dois dos vários problemas simples de brinquedo usados para testar algoritmos de otimização de caixa preta contínua.
As regiões mais claras das parcelas representam valores mais elevados. Como você pode ver, existem muitos ótimos locais nesta função. Nosso trabalho é encontrar um conjunto de parâmetros de modelo.
 |
 |
Embora existam muitas definições de estratégias de evolução, podemos definir uma estratégia de evolução como um algoritmo que fornece ao usuário um conjunto de soluções candidatas para avaliar um problema. A avaliação é baseada em uma função objetivo que recebe uma determinada solução e retorna um único valor de aptidão .
Com base nos resultados de aptidão das soluções atuais, o algoritmo produzirá então a próxima geração de soluções candidatas com maior probabilidade de produzir resultados ainda melhores do que a geração atual. O processo iterativo será interrompido quando a solução mais conhecida for satisfatória para o usuário.
Dado um algoritmo de estratégia de evolução chamado EvolutionStrategy, podemos usar da seguinte maneira:
solver = EvolutionStrategy()
while True:
# ask the ES to give us a set of candidate solutions
solutions = solver.ask()
# create an array to hold the fitness results.
fitness_list = np.zeros(solver.popsize)
# evaluate the fitness for each given solution.
for i in range(solver.popsize):
fitness_list[i] = evaluate(solutions[i])
# give list of fitness results back to ES
solver.tell(fitness_list)
# get best parameter, fitness from ES
best_solution, best_fitness = solver.result()
if best_fitness > MY_REQUIRED_FITNESS:
break
Embora o tamanho da população seja normalmente mantido constante para cada geração, não é necessário que o seja. O ES pode gerar quantas soluções candidatas quisermos, pois as soluções produzidas por um ES são amostradas a partir de uma distribuição cujos parâmetros vão sendo atualizados pelo ES a cada geração. Explicarei esse processo de amostragem com um exemplo de estratégia de evolução simples.
Estratégia de Evolução Simples
Uma das estratégias de evolução mais simples que podemos imaginar irá apenas amostrar um conjunto de soluções de uma distribuição Normal, com uma média qe um desvio padrão fi.
 |
 |
Na visualização acima, o ponto verde indica a média da distribuição em cada geração, os pontos azuis são as soluções amostradas e o ponto vermelho é a melhor solução encontrada até agora pelo nosso algoritmo.
Este algoritmo simples geralmente funciona apenas para problemas simples. Dada a sua natureza gananciosa, ele descarta todas as soluções, exceto a melhor, e pode ficar propenso a ficar preso em um ótimo local para problemas mais complicados. Seria benéfico amostrar a próxima geração a partir de uma distribuição de probabilidade que representasse um conjunto mais diversificado de ideias, em vez de apenas a partir da melhor solução da geração atual.
Algoritmo Genético Simples
Um dos algoritmos de otimização de caixa preta mais antigos é o algoritmo genético. Existem muitas variações com muitos graus de sofisticação, mas vou ilustrar aqui a versão mais simples.
A ideia é bastante simples: manter apenas 10% das soluções com melhor desempenho na geração atual e deixar o resto da população morrer. Na próxima geração, amostrar uma nova solução é selecionar aleatoriamente duas soluções das sobreviventes da geração anterior e recombinar seus parâmetros para formar uma nova solução.
Este processo de recombinação cruzada usa um sorteio para determinar de qual pai obter cada parâmetro. No caso da nossa função de brinquedo 2D, a nossa nova solução pode herdar [de um dos pais com 50% de chance. Ruído gaussiano com desvio padrão fixo também será injetado em cada nova solução após este processo de recombinação.
 |
 |
A figura acima ilustra como funciona o algoritmo genético simples. Os pontos verdes representam os membros da população de elite da geração anterior, os pontos azuis são os descendentes que formam o conjunto de soluções candidatas e o ponto vermelho é a melhor solução.
Os algoritmos genéticos ajudam a diversidade, acompanhando um conjunto diversificado de soluções candidatas para reproduzir a próxima geração. Contudo, na prática, a maioria das soluções na população sobrevivente de elite tende a convergir para um ótimo local ao longo do tempo. Existem variações mais sofisticadas de AG, como CoSyNe , ESP e NEAT , onde a ideia é agrupar soluções semelhantes na população em espécies diferentes, para manter uma melhor diversidade ao longo do tempo.
Estratégia de Evolução de Adaptação de Matriz Covariância (CMA-ES)
Uma deficiência do Simple ES e do Simple GA é que nosso parâmetro de ruído de desvio padrão é fixo. Há momentos em que queremos explorar mais e aumentar o desvio padrão do nosso espaço de busca, e há momentos em que estamos confiantes de que estamos perto de um bom ótimo e queremos apenas ajustar a solução. Basicamente, queremos que nosso processo de pesquisa se comporte assim:
 |
 |
Incrível, não é? O processo de busca mostrado na figura acima é produzido pela Estratégia de Evolução de Adaptação de Matriz de Covariância (CMA-ES) . CMA-ES é um algoritmo que pode pegar os resultados de cada geração e aumentar ou diminuir de forma adaptativa o espaço de busca para a próxima geração.
Não se adaptará apenas à média e sigma parâmetros, mas calculará toda a matriz de covariância do espaço de parâmetros. Em cada geração, o CMA-ES fornece os parâmetros de uma distribuição normal multivariada para amostrar soluções. Então, como ele sabe como aumentar ou diminuir o espaço de busca?
Antes de discutirmos sua metodologia, vamos revisar como estimar uma matriz de covariância . Isto será importante para compreendermos mais adiante a metodologia do CMA-ES.
Se quisermos estimar a matriz de covariância de toda a nossa população amostrada de tamanho de , podemos fazer isso usando o conjunto de equações abaixo para calcular a estimativa de máxima verossimilhança de uma matriz de covariância.
O CMA-ES modifica a fórmula de cálculo de covariância acima de uma maneira inteligente para adaptá-la bem a um problema de otimização. Vou explicar como isso acontece passo a passo.
 |
 |
 |
 |
Calcule a pontuação de aptidão de cada solução candidata na geração.
Vamos visualizar o esquema mais uma vez, sobre todo o processo de busca em ambos os problemas:
 |
 |
Como o CMA-ES pode adaptar a sua matriz de média e de covariância utilizando informações das melhores soluções, pode decidir lançar uma rede mais ampla quando as melhores soluções estão distantes, ou estreitar o espaço de busca quando as melhores soluções estão próximas.
Minha descrição do algoritmo CMA-ES para um problema de brinquedo 2D é altamente simplificada para transmitir a ideia. Para mais detalhes sugiro a leitura do Tutorial CMA-ES elaborado por Nikolaus Hansen, autor do CMA-ES.
Este algoritmo é um dos algoritmos de otimização sem gradiente mais populares que existem e tem sido o algoritmo preferido de muitos pesquisadores e profissionais. A única desvantagem real é o desempenho se o número de parâmetros do modelo que precisamos resolver for grande, pois o cálculo da covariância. CMA-ES é meu algoritmo preferido quando o espaço de busca é inferior a mil parâmetros. Achei que ainda era utilizável até ~ 10K de parâmetros se eu estivesse disposto a ser paciente.
Estratégias de evolução natural
Imagine se você tivesse construído um simulador de vida artificial e experimentasse uma rede neural diferente para controlar o comportamento de cada formiga dentro de uma colônia de formigas. Usar a Estratégia de Evolução Simples para esta tarefa otimizará características e comportamentos que beneficiam formigas individuais e, a cada geração sucessiva, nossa população estará cheia de formigas alfa que só se preocupam com seu próprio bem-estar.
Em vez de usar uma regra baseada na sobrevivência das formigas mais aptas, e se você adotar uma abordagem alternativa onde você pega a soma de todos os valores de aptidão de toda a população de formigas e otimiza essa soma para maximizar o bem-estar? de toda a população de formigas ao longo de gerações sucessivas? Bem, você acabaria criando uma utopia marxista.
Uma fraqueza percebida dos algoritmos mencionados até agora é que eles descartam a maioria das soluções e mantêm apenas as melhores soluções. Soluções fracas contêm informações sobre o que não fazer, e estas são informações valiosas para calcular uma melhor estimativa para a próxima geração.
Muitas pessoas que estudaram RL estão familiarizadas com o artigo REINFORCE . Neste artigo de 1992, Williams delineou uma abordagem para estimar o gradiente das recompensas esperadas em relação aos parâmetros do modelo de uma rede neural política.
Este artigo também propôs usar o REINFORCE como uma estratégia de evolução, na Seção 6 do artigo. Este caso especial do REINFORCE-ES foi expandido posteriormente em Gradientes de Política de Exploração de Parâmetros (PEPG, 2009) e Estratégias de Evolução Natural (NES, 2014).
Nesta abordagem, queremos utilizar todas as informações de cada membro da população, boas ou más, para estimar um sinal gradiente que possa mover toda a população para uma direção melhor na próxima geração.
Como estamos estimando um gradiente, também podemos usar esse gradiente em uma regra de atualização SGD padrão normalmente usada para aprendizado profundo. Podemos até usar esse gradiente estimado com Momentum SGD, RMSProp ou Adam, se quisermos.
A ideia é maximizar o valor esperado da pontuação de aptidão de uma solução amostrada. Se o resultado esperado for suficientemente bom, então o membro com melhor desempenho dentro de uma população amostrada será ainda melhor, pelo que a optimização para a expectativa pode ser uma abordagem sensata. Maximizar a pontuação de aptidão esperada de uma solução amostrada é quase o mesmo que maximizar a pontuação de aptidão total de toda a população.
Essas duas fórmulas podem ser inseridas novamente na fórmula do gradiente aproximado para derivar regras de atualização explícitas.
Nos artigos mencionados acima, eles derivaram regras de atualização mais explícitas, incorporaram uma linha de base e introduziram outros truques, como amostragem antitética no PEPG, em que minha implementação se baseia. A NES propôs incorporar o inverso da Matriz de Informação de Fisher na regra de atualização de gradiente. Mas o conceito é basicamente o mesmo de outros algoritmos ES, onde atualizamos a média e o desvio padrão de uma distribuição normal multivariada a cada nova geração e amostramos um novo conjunto de soluções da distribuição atualizada. Abaixo está uma visualização deste algoritmo em ação, seguindo as fórmulas descritas acima:
 |
 |
Vemos que este algoritmo é capaz de alterar dinamicamente explorar ou ajustar o espaço da solução conforme necessário. Ao contrário do CMA-ES, não há estrutura de correlação em nossa implementação, portanto não obtemos amostras de elipse diagonal, apenas as verticais ou horizontais, embora em princípio possamos derivar regras de atualização para incorporar toda a matriz de covariância se precisarmos. , em detrimento da eficiência computacional.
Gosto deste algoritmo porque, como o CMA-ES, se adaptar para que nosso espaço de pesquisa possa ser expandido ou reduzido ao longo do tempo. Como o parâmetro de correlação não é usado nesta implementação, a eficiência do algoritmo. Normalmente uso PEPG quando o número de parâmetros do modelo excede vários milhares.
Estratégia de evolução OpenAI
No artigo da OpenAI , eles implementam uma estratégia de evolução que é um caso especial do algoritmo REINFORCE-ES descrito anteriormente.
 |
 |
Além da simplificação, este artigo também propôs uma modificação da regra de atualização que é adequada para computação paralela em diferentes máquinas de trabalho. Em sua regra de atualização, uma grande grade de números aleatórios foi pré-calculada usando uma semente fixa. Ao fazer isso, cada trabalhador pode reproduzir os parâmetros de todos os outros trabalhadores ao longo do tempo, e cada trabalhador precisa apenas comunicar um único número, o resultado final da aptidão, a todos os outros trabalhadores.
Isto é importante se quisermos escalar estratégias de evolução para milhares ou mesmo um milhão de trabalhadores localizados em máquinas diferentes, uma vez que embora possa não ser viável transmitir um vetor de solução inteiro um milhão de vezes em cada atualização de geração, pode ser viável transmitir apenas os resultados finais de condicionamento físico.
No artigo, eles mostraram que usando 1.440 trabalhadores no Amazon EC2 eles foram capazes de resolver a tarefa de caminhada do Mujoco Humanoid em aproximadamente 10 minutos.
Eu acho que, em princípio, esta regra de atualização paralela deveria funcionar com o algoritmo original, onde eles também podem se adaptar, mas talvez na prática eles quisessem manter o número de peças móveis ao mínimo para experimentos de computação paralela em grande escala.
Este artigo inspirador também discutiu muitos outros aspectos práticos da implantação de ES para tarefas do tipo RL, e eu recomendo fortemente que você o leia para saber mais.
Modelagem de condicionamento físico
A maioria dos algoritmos acima são geralmente combinados com um método de modelagem de aptidão , como o método de modelagem de aptidão baseado em classificação que discutirei aqui. A modelagem da aptidão nos permite evitar que valores discrepantes na população dominem o cálculo do gradiente aproximado mencionado anteriormente:
Para mitigar isso, pode-se aplicar uma transformação de classificação da aptidão. Em vez de usar a função de aptidão real, classificaríamos os resultados e usaríamos uma função de aptidão aumentada que é proporcional à classificação da solução na população. Abaixo está uma comparação da aparência do conjunto original de aptidão e da aparência da aptidão classificada:
Atribuiremos um valor de aptidão aumentado de -0,50 ao pior desempenho, -0,49 à segunda pior solução,…, 0,49 à segunda melhor solução e, finalmente, um valor de aptidão de 0,50 à melhor solução.
Este conjunto aumentado de valores de aptidão será usado para calcular a atualização do gradiente, em vez dos valores de aptidão reais. De certa forma, é semelhante a apenas aplicar a Normalização em Lote aos resultados, mas de forma mais direta. Existem métodos alternativos para moldar o condicionamento físico, mas todos eles basicamente fornecem resultados semelhantes no final.
Acho que a modelagem de aptidão é muito útil para tarefas de RL se a função objetivo for não determinística para uma determinada rede de políticas, o que geralmente acontece em ambientes de RL onde os mapas são gerados aleatoriamente e vários oponentes têm políticas aleatórias.
É menos útil para otimizar funções bem comportadas que são determinísticas, e o uso da modelagem de aptidão às vezes pode diminuir o tempo necessário para encontrar uma boa solução.
MNIST
Embora ES possa ser uma maneira de procurar soluções mais novas que são difíceis de serem encontradas pelos métodos baseados em gradiente, ele ainda tem um desempenho muito inferior aos métodos baseados em gradiente em muitos problemas onde podemos calcular gradientes de alta qualidade.
Por exemplo, apenas um idiota tentaria usar um algoritmo genético para classificação de imagens. Mas às vezes essas pessoas existem no mundo, e às vezes essas explorações podem ser frutíferas!
Como todos os algoritmos de ML devem ser testados no MNIST, também tentei aplicar esses vários algoritmos ES para encontrar pesos para uma rede pequena e simples de 2 camadas usada para classificar o MNIST, apenas para ver onde estamos em comparação com o SGD. O convnet possui apenas ~ 11k parâmetros para que possamos acomodar o algoritmo CMA-ES mais lento. O código e os experimentos estão disponíveis aqui .
Abaixo estão os resultados para vários métodos ES, usando um tamanho populacional de 101, em mais de 300 épocas. Acompanhamos os parâmetros do modelo com melhor desempenho em todo o conjunto de treinamento no final de cada época e avaliamos esse modelo uma vez no conjunto de teste após 300 épocas.
É interessante como às vezes a precisão do conjunto de teste é maior do que a do conjunto de treinamento para os modelos que apresentam pontuações mais baixas.
| Método | Conjunto de trem | Conjunto de teste |
|---|---|---|
| Linha de base de Adam (BackProp) | 99,8 | 98,9 |
| GA simples | 82,1 | 82,4 |
| CMA-ES | 98,4 | 98,1 |
| OpenAI-ES | 96,0 | 96,2 |
| PEPG | 98,5 | 98,0 |
Ambos os algoritmos alcançaram aproximadamente 98% de precisão do teste, 1% menor que a linha de base do SGD/ADAM. Talvez a capacidade de alterar dinamicamente sua matriz de covariância e os parâmetros de desvio padrão ao longo de cada geração tenham permitido ajustar seus pesos melhor do que a variação mais simples do OpenAI.
Tente você mesmo
Provavelmente existem implementações de código aberto de todos os algoritmos descritos neste artigo. O autor do CMA-ES, Nikolaus Hansen, tem mantido uma implementação do CMA-ES baseada numpy com muitos recursos. Sua implementação em python me apresentou à interface do loop de treinamento descrita anteriormente.
Como essa interface é bastante fácil de usar, também implementei outros algoritmos, como Simple Genetic Algorithm, PEPG e OpenAI’s ES usando a mesma interface, e coloquei-os em um pequeno arquivo python chamado , e também envolvi a biblioteca CMA-ES es.pyoriginal nesta pequena biblioteca. Dessa forma, posso comparar rapidamente diferentes algoritmos ES alterando apenas uma linha:
import es
#solver = es.SimpleGA(...)
#solver = es.PEPG(...)
#solver = es.OpenES(...)
solver = es.CMAES(...)
while True:
solutions = solver.ask()
fitness_list = np.zeros(solver.popsize)
for i in range(solver.popsize):
fitness_list[i] = evaluate(solutions[i])
solver.tell(fitness_list)
result = solver.result()
if result[1] > MY_REQUIRED_FITNESS:
break
Você pode ver exemploses.py no GitHub e no notebook IPython usando os vários algoritmos ES.
Neste notebook IPython que acompanha es.py, mostro como usar os solucionadores ES es.pypara resolver uma versão 100-dimensional da função Rastrigin com ainda mais pontos ótimos locais. A versão 100-D é um pouco mais desafiadora do que a versão trivial 2D usada para produzir as visualizações neste artigo. Abaixo está uma comparação do desempenho de vários algoritmos discutidos:
